Convex hull of a set of points

Convex hull in a plane

This examples shows how to find the convex hull in the context of a plane. First we have to create an object representing the vertices. We have multiple ways of doing this

In [1]:
using Polyhedra

v = convexhull([0, 0], [0, 1], [1, 0], [0.1, 0.1]) # list of points
v = vrep([[0, 0], [0, 1], [1, 0], [0.1, 0.1]]) # vector of points
Out[1]:
V-representation Polyhedra.PointsHull{Float64, Vector{Float64}, Int64}:
4-element iterator of Vector{Float64}:
 [0.0, 0.0]
 [0.0, 1.0]
 [1.0, 0.0]
 [0.1, 0.1]

number of points × dimension matrix

In [2]:
x = [0,0,1,0.1]
y = [0,1,0,0.1]
v = vrep([x y])
Out[2]:
V-representation MixedMatVRep{Float64, Matrix{Float64}}:
4-element iterator of Vector{Float64}:
 [0.0, 0.0]
 [0.0, 1.0]
 [1.0, 0.0]
 [0.1, 0.1]

Then we can compute the hull of these points using the planar_hull function

In [3]:
Polyhedra.planar_hull(v)
Out[3]:
V-representation Polyhedra.Hull{Float64, Vector{Float64}, Int64}:
3-element iterator of Vector{Float64}:
 [0.0, 0.0]
 [0.0, 1.0]
 [1.0, 0.0]

Convex hull in higher dimension

In higher dimension, we can do it with a linear programming solver implementing the MathOptInterface, e.g.,

In [4]:
import GLPK

removevredundancy(v, GLPK.Optimizer)
Out[4]:
V-representation Polyhedra.Hull{Float64, Vector{Float64}, Int64}:
3-element iterator of Vector{Float64}:
 [0.0, 0.0]
 [0.0, 1.0]
 [1.0, 0.0]

We can also use any Polyhedral library implementing the interface of this package. If we don't specify any library, it falls back to a default one implementing on this package which will use the planar_hull if the dimension is 2 (so it's equivalent to the first approach shown above):

In [5]:
p = polyhedron(v)
removevredundancy!(p)
p
Out[5]:
Polyhedron DefaultPolyhedron{Float64, MixedMatHRep{Float64, Matrix{Float64}}, MixedMatVRep{Float64, Matrix{Float64}}}:
3-element iterator of Vector{Float64}:
 [0.0, 0.0]
 [0.0, 1.0]
 [1.0, 0.0]

We can also specify a library:

In [6]:
using CDDLib

p = polyhedron(v, CDDLib.Library())
removevredundancy!(p)
p
Out[6]:
Polyhedron CDDLib.Polyhedron{Float64}:
3-element iterator of Vector{Float64}:
 [0.0, 0.0]
 [0.0, 1.0]
 [1.0, 0.0]

This notebook was generated using Literate.jl.