Convex Hull

convex_hull(X::LazySet, Y::LazySet; [algorithm]=nothing,
            [backend]=nothing, [solver]=nothing)

Compute the convex hull of two polytopic sets.

Input

• X – polytopic set
• Y – polytopic set
• algorithm – (optional, default: nothing) the convex-hull algorithm
• backend – (optional, default: nothing) backend for polyhedral computations (used for higher-dimensional sets)
• solver – (optional, default: nothing) the linear-programming solver used in the backend

Output

If the sets are empty, the result is an EmptySet. If the convex hull consists of a single point, the result is a Singleton. If the input sets are one-dimensional, the result is an Interval. If the input sets are two-dimensional, the result is a VPolygon. Otherwise the result is a VPolytope.

Algorithm

We compute the vertices of both X and Y using vertices_list and then compute the convex hull of the union of those vertices.

convex_hull(points::Vector{VN}; [algorithm]=nothing, [backend]=nothing,
            [solver]=nothing) where {N, VN<:AbstractVector{N}}

Compute the convex hull of a list of points.

Input

• points – list of points
• algorithm – (optional, default: nothing) the convex-hull algorithm; see below for valid options
• backend – (optional, default: nothing) polyhedral computation backend for higher-dimensional point sets
• solver – (optional, default: nothing) the linear-programming solver used in the backend

Output

The convex hull as a list of points.

Algorithm

A pre-processing step treats the cases with up to two points for one dimension and up to four points for two dimensions. For more points in one resp. two dimensions, we use more general algorithms.

For the one-dimensional case, we return the minimum and maximum points, in that order.

The two-dimensional case is handled with a planar convex-hull algorithm. The following algorithms are available:

• "monotone_chain" – compute the convex hull of points in the plane using Andrew's monotone-chain method
• "monotone_chain_sorted" – the same as "monotone_chain" but assuming that the points are already sorted in counter-clockwise fashion

See the reference docstring of each of those algorithms for details.

The higher-dimensional case is treated using the concrete polyhedra library Polyhedra, which gives access to libraries such as CDDLib and ConvexHull.jl. These libraries can be chosen via the backend argument.

Notes

For the in-place version use convex_hull! instead of convex_hull.

Examples

Compute the convex hull of a random set of points:

julia> points = [randn(2) for i in 1:30]; # 30 random points in 2D

julia> hull = convex_hull(points);

julia> typeof(hull)
Vector{Vector{Float64}} (alias for Array{Array{Float64, 1}, 1})

monotone_chain!(points::Vector{VN}; sort::Bool=true
               ) where {N, VN<:AbstractVector{N}}

Compute the convex hull of a list of points in the plane using Andrew's monotone-chain method.

Input

• points – list of 2D vectors; will be sorted in-place inside this method
• sort – (optional, default: true) flag for sorting the vertices lexicographically; sortedness is required for correctness

Output

List of vectors containing the 2D coordinates of the corner points of the convex hull.

Notes

For large sets of points, it is convenient to use static vectors to get maximum performance. For information on how to convert usual vectors into static vectors, see the type SVector provided by the StaticArrays package.

Algorithm

This method implements Andrew's monotone-chain convex hull algorithm to construct the convex hull of a set of $n$ points in the plane in $O(n \log n)$ time. For further details see Monotone chain