public abstract class EdgeTree
extends java.lang.Object
Construction takes O(n log n)
time for sorting and tree construction.
relate()
are O(n)
, but for most
practical lines and polygons are much faster than brute force.
Modifier and Type | Class and Description |
---|---|
(package private) static class |
EdgeTree.Edge
Internal tree node: represents geometry edge from lat1,lon1 to lat2,lon2.
|
Modifier and Type | Field and Description |
---|---|
protected EdgeTree |
left |
double |
maxLat
maximum latitude of this geometry's bounding box area
|
double |
maxLon
maximum longitude of this geometry's bounding box area
|
protected double |
maxX
maximum longitude of this component or any of its children
|
protected double |
maxY
maximum latitude of this component or any of its children
|
double |
minLat
minimum latitude of this geometry's bounding box area
|
double |
minLon
minimum longitude of this geometry's bounding box area
|
protected EdgeTree |
right |
protected boolean |
splitX
which dimension was this node split on
|
protected EdgeTree.Edge |
tree
root node of edge tree
|
Modifier | Constructor and Description |
---|---|
protected |
EdgeTree(double minLat,
double maxLat,
double minLon,
double maxLon,
double[] lats,
double[] lons) |
Modifier and Type | Method and Description |
---|---|
protected abstract PointValues.Relation |
componentRelate(double minLat,
double maxLat,
double minLon,
double maxLon)
Returns relation to the provided rectangle for this component
|
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
|
private static EdgeTree.Edge |
createTree(double[] lats,
double[] lons)
Creates an edge interval tree from a set of geometry vertices.
|
private static EdgeTree.Edge |
createTree(EdgeTree.Edge[] edges,
int low,
int high)
Creates tree from sorted edges (with range low and high inclusive)
|
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 component
|
private PointValues.Relation |
internalComponentRelateTriangle(double ax,
double ay,
double bx,
double by,
double cx,
double cy) |
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
|
PointValues.Relation |
relate(double minLat,
double maxLat,
double minLon,
double maxLon)
Returns relation to the provided rectangle
|
PointValues.Relation |
relateTriangle(double ax,
double ay,
double bx,
double by,
double cx,
double cy)
Returns relation to the provided triangle
|
public final double minLat
public final double maxLat
public final double minLon
public final double maxLon
protected double maxY
protected double maxX
protected boolean splitX
protected EdgeTree left
protected EdgeTree right
protected final EdgeTree.Edge tree
protected EdgeTree(double minLat, double maxLat, double minLon, double maxLon, double[] lats, double[] lons)
public PointValues.Relation relateTriangle(double ax, double ay, double bx, double by, double cx, double cy)
public PointValues.Relation relate(double minLat, double maxLat, double minLon, double maxLon)
protected abstract PointValues.Relation componentRelate(double minLat, double maxLat, double minLon, double maxLon)
protected abstract PointValues.Relation componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy)
private PointValues.Relation internalComponentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy)
protected PointValues.Relation internalComponentRelate(double minLat, double maxLat, double minLon, double maxLon)
protected static EdgeTree createTree(EdgeTree[] components, int low, int high, boolean splitX)
protected static boolean pointInTriangle(double x, double y, double ax, double ay, double bx, double by, double cx, double cy)
private static EdgeTree.Edge createTree(double[] lats, double[] lons)
private static EdgeTree.Edge createTree(EdgeTree.Edge[] edges, int low, int high)