Package org.locationtech.jts.algorithm
Class ConvexHull
- java.lang.Object
-
- org.locationtech.jts.algorithm.ConvexHull
-
public class ConvexHull extends java.lang.Object
Computes the convex hull of aGeometry
. 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 Classes Modifier and Type Class Description private static class
ConvexHull.RadialComparator
ComparesCoordinate
s for their angle and distance relative to an origin.
-
Field Summary
Fields Modifier and Type Field Description private GeometryFactory
geomFactory
private Coordinate[]
inputPts
-
Constructor Summary
Constructors Constructor Description ConvexHull(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
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method 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 aGeometry
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.
-
-
-
Field Detail
-
geomFactory
private GeometryFactory geomFactory
-
inputPts
private Coordinate[] inputPts
-
-
Constructor Detail
-
ConvexHull
public ConvexHull(Geometry geometry)
Create a new convex hull construction for the inputGeometry
.
-
ConvexHull
public ConvexHull(Coordinate[] pts, GeometryFactory geomFactory)
Create a new convex hull construction for the inputCoordinate
array.
-
-
Method Detail
-
extractCoordinates
private static Coordinate[] extractCoordinates(Geometry geom)
-
getConvexHull
public Geometry 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
protected Coordinate[] toCoordinateArray(java.util.Stack stack)
An alternative to Stack.toArray, which is not present in earlier versions of Java.
-
reduce
private Coordinate[] reduce(Coordinate[] inputPts)
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
private Coordinate[] padArray3(Coordinate[] pts)
-
preSort
private Coordinate[] preSort(Coordinate[] pts)
-
grahamScan
private java.util.Stack grahamScan(Coordinate[] c)
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
private boolean isBetween(Coordinate c1, Coordinate c2, Coordinate c3)
- Returns:
- whether the three coordinates are collinear and c2 lies between c1 and c3 inclusive
-
computeOctRing
private Coordinate[] computeOctRing(Coordinate[] inputPts)
-
computeOctPts
private Coordinate[] computeOctPts(Coordinate[] inputPts)
-
lineOrPolygon
private Geometry lineOrPolygon(Coordinate[] coordinates)
- 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
private Coordinate[] cleanRing(Coordinate[] original)
- 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
-
-