Package org.apache.lucene.geo
Class EdgeTree
- java.lang.Object
-
- org.apache.lucene.geo.EdgeTree
-
- Direct Known Subclasses:
Polygon2D
public abstract class EdgeTree extends Object
2D line/polygon geometry implementation represented as a balanced interval tree of edges.Construction takes
O(n log n)
time for sorting and tree construction.relate()
areO(n)
, but for most practical lines and polygons are much faster than brute force.- NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.
-
-
Field Summary
Fields Modifier and Type Field Description protected EdgeTree
left
double
maxLat
maximum latitude of this geometry's bounding box areadouble
maxLon
maximum longitude of this geometry's bounding box areaprotected double
maxX
maximum longitude of this component or any of its childrenprotected double
maxY
maximum latitude of this component or any of its childrendouble
minLat
minimum latitude of this geometry's bounding box areadouble
minLon
minimum longitude of this geometry's bounding box areaprotected EdgeTree
right
protected boolean
splitX
which dimension was this node split onprotected org.apache.lucene.geo.EdgeTree.Edge
tree
root node of edge tree
-
Constructor Summary
Constructors Modifier Constructor Description protected
EdgeTree(double minLat, double maxLat, double minLon, double maxLon, double[] lats, double[] lons)
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description protected abstract PointValues.Relation
componentRelate(double minLat, double maxLat, double minLon, double maxLon)
Returns relation to the provided rectangle for this componentprotected abstract PointValues.Relation
componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy)
Returns relation to the provided triangle for this componentprotected static EdgeTree
createTree(EdgeTree[] components, int low, int high, boolean splitX)
Creates tree from sorted components (with range low and high inclusive)protected PointValues.Relation
internalComponentRelate(double minLat, double maxLat, double minLon, double maxLon)
Returns relation to the provided rectangle for this componentprotected static boolean
pointInTriangle(double x, double y, double ax, double ay, double bx, double by, double cx, double cy)
Compute whether the given x, y point is in a triangle; uses the winding order methodPointValues.Relation
relate(double minLat, double maxLat, double minLon, double maxLon)
Returns relation to the provided rectanglePointValues.Relation
relateTriangle(double ax, double ay, double bx, double by, double cx, double cy)
Returns relation to the provided triangle
-
-
-
Field Detail
-
minLat
public final double minLat
minimum latitude of this geometry's bounding box area
-
maxLat
public final double maxLat
maximum latitude of this geometry's bounding box area
-
minLon
public final double minLon
minimum longitude of this geometry's bounding box area
-
maxLon
public final double maxLon
maximum longitude of this geometry's bounding box area
-
maxY
protected double maxY
maximum latitude of this component or any of its children
-
maxX
protected double maxX
maximum longitude of this component or any of its children
-
splitX
protected boolean splitX
which dimension was this node split on
-
left
protected EdgeTree left
-
right
protected EdgeTree right
-
tree
protected final org.apache.lucene.geo.EdgeTree.Edge tree
root node of edge tree
-
-
Method Detail
-
relateTriangle
public PointValues.Relation relateTriangle(double ax, double ay, double bx, double by, double cx, double cy)
Returns relation to the provided triangle
-
relate
public PointValues.Relation relate(double minLat, double maxLat, double minLon, double maxLon)
Returns relation to the provided rectangle
-
componentRelate
protected abstract PointValues.Relation componentRelate(double minLat, double maxLat, double minLon, double maxLon)
Returns relation to the provided rectangle for this component
-
componentRelateTriangle
protected abstract PointValues.Relation componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy)
Returns relation to the provided triangle for this component
-
internalComponentRelate
protected PointValues.Relation internalComponentRelate(double minLat, double maxLat, double minLon, double maxLon)
Returns relation to the provided rectangle for this component
-
createTree
protected static EdgeTree createTree(EdgeTree[] components, int low, int high, boolean splitX)
Creates tree from sorted components (with range low and high inclusive)
-
pointInTriangle
protected static boolean pointInTriangle(double x, double y, double ax, double ay, double bx, double by, double cx, double cy)
Compute whether the given x, y point is in a triangle; uses the winding order method
-
-