public class ConvexHull
extends java.lang.Object
Geometry
.
The convex hull is the smallest convex Geometry that contains all the
points in the input Geometry.
Uses the Graham Scan algorithm.
Modifier and Type | Class and Description |
---|---|
private static class |
ConvexHull.RadialComparator
Compares
Coordinate s for their angle and distance
relative to an origin. |
Modifier and Type | Field and Description |
---|---|
private GeometryFactory |
geomFactory |
private Coordinate[] |
inputPts |
Constructor and Description |
---|
ConvexHull(Coordinate[] pts,
GeometryFactory geomFactory)
Create a new convex hull construction for the input
Coordinate array. |
ConvexHull(Geometry geometry)
Create a new convex hull construction for the input
Geometry . |
Modifier and Type | Method and Description |
---|---|
private Coordinate[] |
cleanRing(Coordinate[] original) |
private Coordinate[] |
computeOctPts(Coordinate[] inputPts) |
private Coordinate[] |
computeOctRing(Coordinate[] inputPts) |
private static Coordinate[] |
extractCoordinates(Geometry geom) |
Geometry |
getConvexHull()
Returns a
Geometry that represents the convex hull of the input
geometry. |
private java.util.Stack |
grahamScan(Coordinate[] c)
Uses the Graham Scan algorithm to compute the convex hull vertices.
|
private boolean |
isBetween(Coordinate c1,
Coordinate c2,
Coordinate c3) |
private Geometry |
lineOrPolygon(Coordinate[] coordinates) |
private Coordinate[] |
padArray3(Coordinate[] pts) |
private Coordinate[] |
preSort(Coordinate[] pts) |
private Coordinate[] |
reduce(Coordinate[] inputPts)
Uses a heuristic to reduce the number of points scanned
to compute the hull.
|
protected Coordinate[] |
toCoordinateArray(java.util.Stack stack)
An alternative to Stack.toArray, which is not present in earlier versions
of Java.
|
private GeometryFactory geomFactory
private Coordinate[] inputPts
public ConvexHull(Geometry geometry)
Geometry
.public ConvexHull(Coordinate[] pts, GeometryFactory geomFactory)
Coordinate
array.private static Coordinate[] extractCoordinates(Geometry geom)
public Geometry getConvexHull()
Geometry
that represents the convex hull of the input
geometry.
The returned geometry contains the minimal number of points needed to
represent the convex hull. In particular, no more than two consecutive
points will be collinear.Polygon
;
2 points, a LineString
;
1 point, a Point
;
0 points, an empty GeometryCollection
.protected Coordinate[] toCoordinateArray(java.util.Stack stack)
private Coordinate[] reduce(Coordinate[] inputPts)
Note that even if the method used to determine the polygon vertices is not 100% robust, this does not affect the robustness of the convex hull.
To satisfy the requirements of the Graham Scan algorithm, the returned array has at least 3 entries.
pts
- the points to reduceprivate Coordinate[] padArray3(Coordinate[] pts)
private Coordinate[] preSort(Coordinate[] pts)
private java.util.Stack grahamScan(Coordinate[] c)
c
- a list of points, with at least 3 entriesprivate boolean isBetween(Coordinate c1, Coordinate c2, Coordinate c3)
private Coordinate[] computeOctRing(Coordinate[] inputPts)
private Coordinate[] computeOctPts(Coordinate[] inputPts)
private Geometry lineOrPolygon(Coordinate[] coordinates)
vertices
- the vertices of a linear ring, which may or may not be
flattened (i.e. vertices collinear)LineString
if the vertices are
collinear; otherwise, a Polygon
with unnecessary
(collinear) vertices removedprivate Coordinate[] cleanRing(Coordinate[] original)
vertices
- the vertices of a linear ring, which may or may not be
flattened (i.e. vertices collinear)