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 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 Classes

Modifier and Type	Class	Description
private static class	ConvexHull.RadialComparator	Compares Coordinates 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 input Coordinate array.
ConvexHull(Geometry geometry)	Create a new convex hull construction for the input Geometry.

Method Summary

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 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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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 input Geometry.

ConvexHull

public ConvexHull(Coordinate[] pts,
                  GeometryFactory geomFactory)

Create a new convex hull construction for the input Coordinate array.

Method Detail

extractCoordinates

private static Coordinate[] extractCoordinates(Geometry geom)

getConvexHull

public Geometry getConvexHull()

Returns a 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.

Returns:

if the convex hull contains 3 or more points, a Polygon; 2 points, a LineString; 1 point, a Point; 0 points, an empty GeometryCollection.

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, a Polygon 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