ml::ConvexHull2D Namespace Reference

Functions
MLPOINTCLOUDUTILS_EXPORT std::vector< Vector2 >	createConvexHull (std::vector< Vector2 > points)
	Calculates the convex hull of the given points. More...
MLPOINTCLOUDUTILS_EXPORT std::vector< Vector2 >	createConvexHullFromSortedPoints (const std::vector< Vector2 > &points)
	Calculates the convex hull of the given sorted points. More...

Function Documentation

createConvexHull()

MLPOINTCLOUDUTILS_EXPORT std::vector<Vector2> ml::ConvexHull2D::createConvexHull

(

std::vector< Vector2 >

points

)

Calculates the convex hull of the given points.

The algorithm used is "Monotone chain" aka "Andrews algorithm" and runs in O(N * log(N)) due to sorting.

createConvexHullFromSortedPoints()

MLPOINTCLOUDUTILS_EXPORT std::vector<Vector2> ml::ConvexHull2D::createConvexHullFromSortedPoints

(

const std::vector< Vector2 > &

points

)

Calculates the convex hull of the given sorted points.

The method expects that points is sorted lexicographically. It does not matter if the points are ordered by y or x first, the only difference will be the orientation of the hull (upper/lower, left/right) The algorithm used is "Monotone chain" aka "Andrews algorithm" and runs in O(N) because the points are already sorted.