Package org.apache.lucene.geo
Class EdgeTree
- java.lang.Object
-
- org.apache.lucene.geo.EdgeTree
-
public class EdgeTree extends java.lang.Object
Internal tree node: represents geometry edge from lat1,lon1 to lat2,lon2. The sort value islow
, which is the minimum latitude of the edge.max
stores the maximum latitude of this edge or any children.
-
-
Field Summary
Fields Modifier and Type Field Description private static byte
FALSE
helper bytes to signal if a point is on an edge, it is within the edge tree or disjoint(package private) EdgeTree
left
left child edge, or null(package private) double
low
min of this edge(package private) double
max
max latitude of this edge or any childrenprivate static byte
ON_EDGE
(package private) EdgeTree
right
right child edge, or nullprivate static byte
TRUE
(package private) double
x1
(package private) double
x2
(package private) double
y1
(package private) double
y2
-
Constructor Summary
Constructors Constructor Description EdgeTree(double x1, double y1, double x2, double y2, double low, double max)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description 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.private byte
containsPnPoly(double x, double y)
Returns byte 0x00 if the point crosses this edge subtree an even number of times.protected 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)protected boolean
crossesBox(double minX, double maxX, double minY, double maxY, boolean includeBoundary)
Returns true if the box crosses any edge in this edge subtreeprotected boolean
crossesLine(double minX, double maxX, double minY, double maxY, double a2x, double a2y, double b2x, double b2y)
Returns true if the line crosses any edge in this edge subtreeprotected 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 subtreeprotected boolean
isPointOnLine(double x, double y)
returns true if the provided x, y point lies on the line
-
-
-
Field Detail
-
y1
final double y1
-
y2
final double y2
-
x1
final double x1
-
x2
final double x2
-
low
final double low
min of this edge
-
max
double max
max latitude of this edge or any children
-
left
EdgeTree left
left child edge, or null
-
right
EdgeTree right
right child edge, or null
-
FALSE
private static final byte FALSE
helper bytes to signal if a point is on an edge, it is within the edge tree or disjoint- See Also:
- Constant Field Values
-
TRUE
private static final byte TRUE
- See Also:
- Constant Field Values
-
ON_EDGE
private static final byte ON_EDGE
- See Also:
- Constant Field Values
-
-
Method Detail
-
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
protected boolean isPointOnLine(double x, double y)
returns true if the provided x, y point lies on the line
-
crossesTriangle
protected 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
protected 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
protected boolean crossesLine(double minX, double maxX, double minY, double maxY, double a2x, double a2y, double b2x, double b2y)
Returns true if the line crosses any edge in this edge subtree
-
createTree
protected static EdgeTree createTree(double[] x, double[] y)
Creates an edge interval tree from a set of geometry vertices.- Returns:
- root node of the tree.
-
-