geos::algorithm::ConvexHull Class Reference

Computes the convex hull of a Geometry. More...

#include <ConvexHull.h>

Collaboration diagram for geos::algorithm::ConvexHull:

Public Member Functions
	ConvexHull (const geom::Geometry *newGeometry)
	~ConvexHull ()
std::unique_ptr< geom::Geometry >	getConvexHull ()

Private Member Functions
void	extractCoordinates (const geom::Geometry *geom)
std::unique_ptr< geom::CoordinateSequence >	toCoordinateSequence (geom::Coordinate::ConstVect &cv)
void	computeOctPts (const geom::Coordinate::ConstVect &src, geom::Coordinate::ConstVect &tgt)
bool	computeOctRing (const geom::Coordinate::ConstVect &src, geom::Coordinate::ConstVect &tgt)
void	reduce (geom::Coordinate::ConstVect &pts)
void	padArray3 (geom::Coordinate::ConstVect &pts)
	parameter will be modified More...
void	preSort (geom::Coordinate::ConstVect &pts)
	parameter will be modified More...
int	polarCompare (const geom::Coordinate &o, const geom::Coordinate &p, const geom::Coordinate &q)
void	grahamScan (const geom::Coordinate::ConstVect &c, geom::Coordinate::ConstVect &ps)
std::unique_ptr< geom::Geometry >	lineOrPolygon (const geom::Coordinate::ConstVect &vertices)
void	cleanRing (const geom::Coordinate::ConstVect &input, geom::Coordinate::ConstVect &cleaned)
bool	isBetween (const geom::Coordinate &c1, const geom::Coordinate &c2, const geom::Coordinate &c3)

Private Attributes
const geom::GeometryFactory *	geomFactory
geom::Coordinate::ConstVect	inputPts

Detailed Description

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.

Last port: algorithm/ConvexHull.java rev. 1.26 (JTS-1.7)

Definition at line 59 of file ConvexHull.h.

Constructor & Destructor Documentation

geos::algorithm::ConvexHull::ConvexHull

(

const geom::Geometry *

newGeometry

)

Create a new convex hull construction for the input Geometry.

geos::algorithm::ConvexHull::~ConvexHull

(

)

Member Function Documentation

void geos::algorithm::ConvexHull::cleanRing ( const geom::Coordinate::ConstVect &  input, geom::Coordinate::ConstVect &  cleaned  )

private

Write in 'cleaned' a version of 'input' with collinear vertexes removed.

void geos::algorithm::ConvexHull::computeOctPts ( const geom::Coordinate::ConstVect &  src, geom::Coordinate::ConstVect &  tgt  )

private

bool geos::algorithm::ConvexHull::computeOctRing ( const geom::Coordinate::ConstVect &  src, geom::Coordinate::ConstVect &  tgt  )

private

void geos::algorithm::ConvexHull::extractCoordinates ( const geom::Geometry *  geom )

private

std::unique_ptr<geom::Geometry> geos::algorithm::ConvexHull::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.

void geos::algorithm::ConvexHull::grahamScan ( const geom::Coordinate::ConstVect &  c, geom::Coordinate::ConstVect &  ps  )

private

bool geos::algorithm::ConvexHull::isBetween ( const geom::Coordinate &  c1, const geom::Coordinate &  c2, const geom::Coordinate &  c3  )

private

Returns

whether the three coordinates are collinear and c2 lies between c1 and c3 inclusive

std::unique_ptr<geom::Geometry> geos::algorithm::ConvexHull::lineOrPolygon ( const geom::Coordinate::ConstVect &  vertices )

private

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

void geos::algorithm::ConvexHull::padArray3 ( geom::Coordinate::ConstVect &  pts )

private

parameter will be modified

int geos::algorithm::ConvexHull::polarCompare ( const geom::Coordinate &  o, const geom::Coordinate &  p, const geom::Coordinate &  q  )

private

Given two points p and q compare them with respect to their radial ordering about point o. First checks radial ordering. If points are collinear, the comparison is based on their distance to the origin.

p < q iff

• ang(o-p) < ang(o-q) (e.g. o-p-q is CCW)
• or ang(o-p) == ang(o-q) && dist(o,p) < dist(o,q)

Parameters

o	the origin
p	a point
q	another point

Returns

-1, 0 or 1 depending on whether p is less than, equal to or greater than q

void geos::algorithm::ConvexHull::preSort ( geom::Coordinate::ConstVect &  pts )

private

parameter will be modified

void geos::algorithm::ConvexHull::reduce ( geom::Coordinate::ConstVect &  pts )

private

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 resulting array has at least 3 entries.

Parameters

pts	The vector of const Coordinate pointers to be reduced (to at least 3 elements)

WARNING: the parameter will be modified

std::unique_ptr<geom::CoordinateSequence> geos::algorithm::ConvexHull::toCoordinateSequence ( geom::Coordinate::ConstVect &  cv )

private

Create a CoordinateSequence from the Coordinate::ConstVect This is needed to construct the geometries. Here coordinate copies happen The returned object is newly allocated !NO EXCEPTION SAFE!

Member Data Documentation

const geom::GeometryFactory* geos::algorithm::ConvexHull::geomFactory

private

Definition at line 61 of file ConvexHull.h.

geom::Coordinate::ConstVect geos::algorithm::ConvexHull::inputPts

private

Definition at line 62 of file ConvexHull.h.

---

The documentation for this class was generated from the following file:

• ConvexHull.h