Package org.locationtech.jts.algorithm
Class ConvexHull
java.lang.Object
org.locationtech.jts.algorithm.ConvexHull
Computes the convex hull of a
Geometry
.
The convex hull is the smallest convex Geometry that contains all the
points in the input Geometry.
Uses the Graham Scan algorithm.
- Version:
- 1.7
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static class
ComparesCoordinate
s for their angle and distance relative to an origin. -
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionConvexHull
(Coordinate[] pts, GeometryFactory geomFactory) Create a new convex hull construction for the inputCoordinate
array.ConvexHull
(Geometry geometry) Create a new convex hull construction for the inputGeometry
. -
Method Summary
Modifier and TypeMethodDescriptionprivate Coordinate[]
cleanRing
(Coordinate[] original) private Coordinate[]
computeOctPts
(Coordinate[] inputPts) private Coordinate[]
computeOctRing
(Coordinate[] inputPts) private static Coordinate[]
extractCoordinates
(Geometry geom) Returns aGeometry
that represents the convex hull of the input geometry.private 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
(Stack stack) An alternative to Stack.toArray, which is not present in earlier versions of Java.
-
Field Details
-
geomFactory
-
inputPts
-
-
Constructor Details
-
ConvexHull
Create a new convex hull construction for the inputGeometry
. -
ConvexHull
Create a new convex hull construction for the inputCoordinate
array.
-
-
Method Details
-
extractCoordinates
-
getConvexHull
Returns aGeometry
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.- Returns:
- if the convex hull contains 3 or more points, a
Polygon
; 2 points, aLineString
; 1 point, aPoint
; 0 points, an emptyGeometryCollection
.
-
toCoordinateArray
An alternative to Stack.toArray, which is not present in earlier versions of Java. -
reduce
Uses a heuristic to reduce the number of points scanned to compute the hull. The heuristic is to find a polygon guaranteed to be in (or on) the hull, and eliminate all points inside it. A quadrilateral defined by the extremal points in the four orthogonal directions can be used, but even more inclusive is to use an octilateral defined by the points in the 8 cardinal directions.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.
- Parameters:
pts
- the points to reduce- Returns:
- the reduced list of points (at least 3)
-
padArray3
-
preSort
-
grahamScan
Uses the Graham Scan algorithm to compute the convex hull vertices.- Parameters:
c
- a list of points, with at least 3 entries- Returns:
- a Stack containing the ordered points of the convex hull ring
-
isBetween
- Returns:
- whether the three coordinates are collinear and c2 lies between c1 and c3 inclusive
-
computeOctRing
-
computeOctPts
-
lineOrPolygon
- Parameters:
vertices
- the vertices of a linear ring, which may or may not be flattened (i.e. vertices collinear)- Returns:
- a 2-vertex
LineString
if the vertices are collinear; otherwise, aPolygon
with unnecessary (collinear) vertices removed
-
cleanRing
- Parameters:
vertices
- the vertices of a linear ring, which may or may not be flattened (i.e. vertices collinear)- Returns:
- the coordinates with unnecessary (collinear) vertices removed
-