public final class Polygon2D
extends java.lang.Object
Construction takes O(n log n)
time for sorting and tree construction.
contains()
and relate()
are O(n)
, but for most
practical polygons are much faster than brute force.
Loosely based on the algorithm described in http://www-ma2.upc.es/geoc/Schirra-pointPolygon.pdf.
Modifier and Type | Class and Description |
---|---|
(package private) static class |
Polygon2D.Edge
Internal tree node: represents polygon edge from lat1,lon1 to lat2,lon2.
|
Modifier and Type | Field and Description |
---|---|
private Polygon2D |
holes
tree of holes, or null
|
private Polygon2D |
left |
double |
maxLat
maximum latitude of this polygon's bounding box area
|
double |
maxLon
maximum longitude of this polygon's bounding box area
|
private double |
maxX
maximum longitude of this component or any of its children
|
private double |
maxY
maximum latitude of this component or any of its children
|
double |
minLat
minimum latitude of this polygon's bounding box area
|
double |
minLon
minimum longitude of this polygon's bounding box area
|
private Polygon2D |
right |
private boolean |
splitX
which dimension was this node split on
|
private Polygon2D.Edge |
tree
root node of edge tree
|
Modifier | Constructor and Description |
---|---|
private |
Polygon2D(Polygon polygon,
Polygon2D holes) |
Modifier and Type | Method and Description |
---|---|
private boolean |
componentContains(double latitude,
double longitude)
Returns true if the point is contained within this polygon component.
|
private PointValues.Relation |
componentRelate(double minLat,
double maxLat,
double minLon,
double maxLon)
Returns relation to the provided rectangle for this component
|
boolean |
contains(double latitude,
double longitude)
Returns true if the point is contained within this polygon.
|
static Polygon2D |
create(Polygon... polygons)
Builds a Polygon2D from multipolygon
|
private static Polygon2D.Edge |
createTree(double[] polyLats,
double[] polyLons)
Creates an edge interval tree from a set of polygon vertices.
|
private static Polygon2D.Edge |
createTree(Polygon2D.Edge[] edges,
int low,
int high)
Creates tree from sorted edges (with range low and high inclusive)
|
private static Polygon2D |
createTree(Polygon2D[] components,
int low,
int high,
boolean splitX)
Creates tree from sorted components (with range low and high inclusive)
|
private int |
numberOfCorners(double minLat,
double maxLat,
double minLon,
double maxLon) |
private static int |
orient(double ax,
double ay,
double bx,
double by,
double cx,
double cy)
Returns a positive value if points a, b, and c are arranged in counter-clockwise order,
negative value if clockwise, zero if collinear.
|
PointValues.Relation |
relate(double minLat,
double maxLat,
double minLon,
double maxLon)
Returns relation to the provided rectangle
|
public final double minLat
public final double maxLat
public final double minLon
public final double maxLon
private double maxY
private double maxX
private boolean splitX
private Polygon2D left
private Polygon2D right
private final Polygon2D holes
private final Polygon2D.Edge tree
public boolean contains(double latitude, double longitude)
See https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html for more information.
private boolean componentContains(double latitude, double longitude)
public PointValues.Relation relate(double minLat, double maxLat, double minLon, double maxLon)
private PointValues.Relation componentRelate(double minLat, double maxLat, double minLon, double maxLon)
private int numberOfCorners(double minLat, double maxLat, double minLon, double maxLon)
private static Polygon2D createTree(Polygon2D[] components, int low, int high, boolean splitX)
private static Polygon2D.Edge createTree(double[] polyLats, double[] polyLons)
private static Polygon2D.Edge createTree(Polygon2D.Edge[] edges, int low, int high)
private static int orient(double ax, double ay, double bx, double by, double cx, double cy)