How to use convex hull?

[Hugo-Trentesaux]

In Matlab, the convhull function allows to find the convex hull around a list of vertices defined by their coordinates. Is it possible with the Polyhedra.convexhull function?

The same syntax does not work:

julia> convexhull([0,0,1,0.1], [0,1,0,0.1])
V-representation Polyhedra.PointsHull{Float64, Vector{Float64}, Int64}:
2-element iterator of Vector{Float64}:
 [0.0, 0.0, 1.0, 0.1]
 [0.0, 1.0, 0.0, 0.1]

and the documentation only tells about convex hull of two polyhedra.

[blegat]

In your example, you have created the convex hull of two 4-dimensional points, while I guess you want the convex hull of 4 2-dimensional points. Here a 3 ways to do it:

julia> v = convexhull([0, 0], [0, 1], [1, 0], [0.1, 0.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]

julia> v = vrep([[0, 0], [0, 1], [1, 0], [0.1, 0.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]

julia> x = [0,0,1,0.1]
4-element Vector{Float64}:
 0.0
 0.0
 1.0
 0.1

julia> y = [0,1,0,0.1]
4-element Vector{Float64}:
 0.0
 1.0
 0.0
 0.1

julia> v = vrep([x y])
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]

Now these objects represent the convex hull you're looking for but you would additionally like the representation to be minimal (not contain the redundant points). In 2-dimensions, this is quite easy to do, there is the planar_hull function of this package that does it:

julia> Polyhedra.planar_hull(v)
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]

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

julia> import GLPK

julia> removevredundancy(v, GLPK.Optimizer)
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]

You can also use any Polyhedral library implementing the interface of this package. If you 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):

julia> p = polyhedron(v)

julia> removevredundancy!(p)

julia> p
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]

You can also specify a library:

julia> using CDDLib

julia> p = polyhedron(v, CDDLib.Library())
Polyhedron CDDLib.Polyhedron{Float64}:
4-element iterator of Vector{Float64}:
 [0.0, 0.0]
 [0.0, 1.0]
 [1.0, 0.0]
 [0.1, 0.1]

julia> removevredundancy!(p)

julia> p
Polyhedron CDDLib.Polyhedron{Float64}:
3-element iterator of Vector{Float64}:
 [0.0, 0.0]
 [0.0, 1.0]
 [1.0, 0.0]

I guess adding an example with the content of this post would be useful.

[Hugo-Trentesaux]

Thanks for your answer. I added a documentation page in PR #262 by copy-pasting your answer and replacing "you" by "we". I'm not familiar with the documentation workflow, so I created a .jl file by hand, even it seems other ones are automatically generated from a Jupyter notebook.

[blegat]

Closed by https://github.com/JuliaPolyhedra/Polyhedra.jl/pull/262