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 Concrete Methods Modifier and Type Method Description protected PointValues.Relation
componentRelate(double minLat, double maxLat, double minLon, double maxLon)
protected PointValues.Relation
componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy)
protected 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 componentPointValues.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 PointValues.Relation componentRelate(double minLat, double maxLat, double minLon, double maxLon)
-
componentRelateTriangle
protected PointValues.Relation componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy)
-
internalComponentRelate
protected PointValues.Relation internalComponentRelate(double minLat, double maxLat, double minLon, double maxLon)
Returns relation to the provided rectangle for this component
-
-