PlanarConvexHulls.jl
PlanarConvexHulls provides a ConvexHull
type, which represents the convex hull of a set of 2D points by its extreme points. Functionality includes:
- convexity test
- construction of a convex hull given a set of points
- area
- centroid
- point-in-convex-hull test
- closest point within convex hull
- equivalent halfspace representation of the convex hull
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.
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.
PlanarConvexHulls.DConvexHull
— Type.DConvexHull{N, T}
The default dynamically-sized ConvexHull
type. Backed by a Vector{SVector{2, T}}
with vertices ordered counter-clockwise.
PlanarConvexHulls.vertices
— Function.vertices(hull)
Return the ConvexHull
's (ordered) vector of vertices.
PlanarConvexHulls.num_vertices
— Function.num_vertices(hull)
Return the number of vertices of the given ConvexHull
.
VertexOrder
s
PlanarConvexHulls.VertexOrder
— Type.abstract type VertexOrder
A VertexOrder
represents the order in which the vertices of a ConvexHull
are stored.
PlanarConvexHulls.CCW
— Type.struct CCW <: PlanarConvexHulls.VertexOrder
Counterclockwise vertex order.
PlanarConvexHulls.CW
— Type.struct CW <: PlanarConvexHulls.VertexOrder
Clockwise vertex order.
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).
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.
PlanarConvexHulls.area
— Function.area(hull)
Compute the area of the given ConvexHull
using the shoelace formula.
PlanarConvexHulls.centroid
— Function.centroid(hull)
Compute the centroid or geometric center of the given ConvexHull
using the formulas given here.
Base.in
— Method.in(point, hull)
Return whether point
is in hull
.
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.
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
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.
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
This function stores its output in the (mutable) matrix A
and vector b
.