java.lang.Object
org.apache.lucene.geo.EdgeTree
Internal tree node: represents geometry edge from [x1, y1] to [x2, y2]. The sort value is
low
, which is the minimum y of the edge. max
stores the maximum y of this edge or any
children.
Construction takes O(n log n)
time for sorting and tree construction. Methods are
O(n)
, but for most practical lines and polygons are much faster than brute force.
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate static final byte
helper bytes to signal if a point is on an edge, it is within the edge tree or disjoint(package private) EdgeTree
left child edge, or null(package private) final double
min Y of this edge(package private) double
max Y of this edge or any childrenprivate static final byte
(package private) EdgeTree
right child edge, or nullprivate static final byte
(package private) final double
(package private) final double
(package private) final double
(package private) final double
-
Constructor Summary
ConstructorsModifierConstructorDescriptionprivate
EdgeTree
(double x1, double y1, double x2, double y2, double low, double max) -
Method Summary
Modifier and TypeMethodDescriptionprotected boolean
contains
(double x, double y) Returns true if the point is on an edge or crosses the edge subtree an odd number of times.private byte
containsPnPoly
(double x, double y) Returns byte 0x00 if the point crosses this edge subtree an even number of times.(package private) static EdgeTree
createTree
(double[] x, double[] y) Creates an edge interval tree from a set of geometry vertices.private static EdgeTree
createTree
(EdgeTree[] edges, int low, int high) Creates tree from sorted edges (with range low and high inclusive)(package private) boolean
crossesBox
(double minX, double maxX, double minY, double maxY, boolean includeBoundary) Returns true if the box crosses any edge in this edge subtree(package private) boolean
crossesLine
(double minX, double maxX, double minY, double maxY, double a2x, double a2y, double b2x, double b2y, boolean includeBoundary) Returns true if the line crosses any edge in this edge subtree(package private) boolean
crossesTriangle
(double minX, double maxX, double minY, double maxY, double ax, double ay, double bx, double by, double cx, double cy, boolean includeBoundary) Returns true if the triangle crosses any edge in this edge subtree(package private) boolean
isPointOnLine
(double x, double y) returns true if the provided x, y point lies on the line
-
Field Details
-
y1
final double y1 -
y2
final double y2 -
x1
final double x1 -
x2
final double x2 -
low
final double lowmin Y of this edge -
max
double maxmax Y of this edge or any children -
left
EdgeTree leftleft child edge, or null -
right
EdgeTree rightright child edge, or null -
FALSE
private static final byte FALSEhelper bytes to signal if a point is on an edge, it is within the edge tree or disjoint- See Also:
-
TRUE
private static final byte TRUE- See Also:
-
ON_EDGE
private static final byte ON_EDGE- See Also:
-
-
Constructor Details
-
EdgeTree
private EdgeTree(double x1, double y1, double x2, double y2, double low, double max)
-
-
Method Details
-
contains
protected boolean contains(double x, double y) Returns true if the point is on an edge or crosses the edge subtree an odd number of times. -
containsPnPoly
private byte containsPnPoly(double x, double y) Returns byte 0x00 if the point crosses this edge subtree an even number of times. Returns byte 0x01 if the point crosses this edge subtree an odd number of times. Returns byte 0x02 if the point is on one of the edges.See https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html for more information.
-
isPointOnLine
boolean isPointOnLine(double x, double y) returns true if the provided x, y point lies on the line -
crossesTriangle
boolean crossesTriangle(double minX, double maxX, double minY, double maxY, double ax, double ay, double bx, double by, double cx, double cy, boolean includeBoundary) Returns true if the triangle crosses any edge in this edge subtree -
crossesBox
boolean crossesBox(double minX, double maxX, double minY, double maxY, boolean includeBoundary) Returns true if the box crosses any edge in this edge subtree -
crossesLine
boolean crossesLine(double minX, double maxX, double minY, double maxY, double a2x, double a2y, double b2x, double b2y, boolean includeBoundary) Returns true if the line crosses any edge in this edge subtree -
createTree
Creates an edge interval tree from a set of geometry vertices.- Returns:
- root node of the tree.
-
createTree
Creates tree from sorted edges (with range low and high inclusive)
-