Convex Hull

We represent convex hulls using a ConvexHull type, which is simply a type containing points and indices:

DelaunayTriangulation.ConvexHullType
ConvexHull{P,I}

Struct storing the results for a convex hull.

Fields

  • points::P

The complete set of points.

  • indices::I

Indices of points in points corresponding to the convex hull, in counter-clockwise order, and indices[begin] == indices[end].

For a triangulation, convex hulls are obtained from the unconstrained form, but if they need to be reconstructed then we can do so with the monotone chain algorithm.

DelaunayTriangulation.convex_hullMethod
convex_hull(points; IntegerType::Type{I}=Int) where {I}

Computes the convex hull of points using Graham's scan. Returns a ConvexHull object.

Note that if there are a trio of points on the convex hull that are collinear, they will all be included, instead of only taking the endpoints of the collinear points.