Polygon.jl

struct ConvexHull{O<:Polygon.VertexOrder, T, P<:StaticArraysCore.StaticArray{Tuple{2}, T, 1}, V<:AbstractArray{P<:StaticArraysCore.StaticArray{Tuple{2}, T, 1}, 1}}

Represents the convex hull of a set of 2D points by its extreme points (vertices), which are stored according to the VertexOrder given by the first type parameter.

SConvexHull{N, T}

The default statically-sized ConvexHull type. Backed by an SVector{N, SVector{2, T}} with vertices ordered counter-clockwise.

DConvexHull{N, T}

The default dynamically-sized ConvexHull type. Backed by a Vector{SVector{2, T}} with vertices ordered counter-clockwise.

vertices(hull)

Return the ConvexHull's (ordered) vector of vertices.

num_vertices(hull)

Return the number of vertices of the given ConvexHull.

abstract type VertexOrder

A VertexOrder represents the order in which the vertices of a ConvexHull are stored.

struct CCW <: Polygon.VertexOrder

Counterclockwise vertex order.

struct CW <: Polygon.VertexOrder

Clockwise vertex order.

is_ordered_and_strongly_convex(vertices, order)

Return whether vertices are ordered according to vertex order type O (a subtype of VertexOrder), and as a result strongly convex (see e.g. CGAL documentation for a definition of strong convexity).

jarvis_march!(hull, points)

Compute the convex hull of points and store the result in hull using the Jarvis march (gift wrapping) algorithm. This algorithm has $O(nh)$ complexity, where $n$ is the number of points and $h$ is the number of vertices of the convex hull.

area(hull)

Compute the area of the given ConvexHull using the shoelace formula.

centroid(hull)

Compute the centroid or geometric center of the given ConvexHull using the formulas given here.

in(point, hull)

Return whether point is in hull.

closest_point(p, hull)

Find the closest point to p within hull. If p is inside hull, p itself is returned.

hrep(hull)

Return the equivalent halfspace representation of the convex hull, i.e. matrix $A$ and vector $b$ such that the set of points inside the hull is

\[\left\{ x \mid A x \le b \right\}\]

If hull is backed by a statically sized vector of vertices, the output (A, b) will be statically sized as well. If the vector of vertices is additionally immutable (e.g., a StaticArrays.SVector), then hrep will not perform any dynamic memory allocation.

hrep!(A, b, hull)

Return the equivalent halfspace representation of the convex hull, i.e. matrix $A$ and vector $b$ such that the set of points inside the hull is

\[\left\{ x \mid A x \le b \right\}\]

This function stores its output in the (mutable) matrix A and vector b.