Home

PlanarConvexHulls.jl

PlanarConvexHulls provides a ConvexHull type, which represents the convex hull of a set of 2D points by its extreme points. Functionality includes:

Types

The ConvexHull type

PlanarConvexHulls.ConvexHull — Type.
struct ConvexHull{O<:PlanarConvexHulls.VertexOrder, T, P<:StaticArrays.StaticArray{Tuple{2},T,1}, V<:AbstractArray{P<:StaticArrays.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.

source
PlanarConvexHulls.SConvexHull — Type.
SConvexHull{N, T}

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

source
PlanarConvexHulls.DConvexHull — Type.
DConvexHull{N, T}

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

source
PlanarConvexHulls.vertices — Function.
vertices(hull)

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

source
PlanarConvexHulls.num_vertices — Function.
num_vertices(hull)

Return the number of vertices of the given ConvexHull.

source

VertexOrders

PlanarConvexHulls.VertexOrder — Type.
abstract type VertexOrder

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

source
PlanarConvexHulls.CCW — Type.
struct CCW <: PlanarConvexHulls.VertexOrder

Counterclockwise vertex order.

source
PlanarConvexHulls.CW — Type.
struct CW <: PlanarConvexHulls.VertexOrder

Clockwise vertex order.

source

Algorithms

PlanarConvexHulls.is_ordered_and_strongly_convex — Function.
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).

source
PlanarConvexHulls.jarvis_march! — Function.
jarvis_march!(hull, points; atol)

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.

source
PlanarConvexHulls.area — Function.
area(hull)

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

source
PlanarConvexHulls.centroid — Function.
centroid(hull)

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

source
Base.in — Method.
in(point, hull)

Return whether point is in hull.

source
PlanarConvexHulls.closest_point — Function.
closest_point(p, hull)

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

source
PlanarConvexHulls.hrep — Function.
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.

source
PlanarConvexHulls.hrep! — Function.
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.

source