Convex Hulls

Convex Hulls

In this section we illustrate the convex hull operation. We give examples of the symbolic implementation, and the concrete convex hull in low dimensions.

Symbolic convex hull

The lazy convex hull, ConvexHull, is the binary operator that implements the convex hull of the union between two convex sets.

using Plots, LazySets

A = 1/sqrt(2.) * [1 -1; 1 1]
Bn = n -> BallInf(ones(n), 0.2)

X = Bn(2)
Y = CH(X, exp(A) * X)
ConvexHull{Float64,BallInf{Float64},LinearMap{Float64,BallInf{Float64},Float64,Array{Float64,2}}}(BallInf{Float64}([1.0, 1.0], 0.2), LinearMap{Float64,BallInf{Float64},Float64,Array{Float64,2}}([1.54186 -1.31754; 1.31754 1.54186], BallInf{Float64}([1.0, 1.0], 0.2)))

The name CH is an alias for ConvexHull, so you can use both interchangeably. This type is parametric in the operands's types.

p = plot(X, 1e-2, color="blue")
plot!(p, exp(A) * X, 1e-2, color="green")
plot!(p, Y, 1e-2, color="red", alpha=0.2)
-0.25 0.00 0.25 0.50 0.75 1.00 1.0 1.5 2.0 2.5 3.0 3.5

We can as well work with a 100-dimensional set:

using SparseArrays

X = Bn(100)
A = blockdiag([sparse(A) for i in 1:50]...)
Y = CH(X, exp(Matrix(A)) * X)

dim(Y)
100

To take the convex hull of a large number of sets, there is the n-ary type ConvexHullArray. For instance, below we create a collection of balls b via list comprehension, and pass them to create a new ConvexHullArray instance.

b = [Ball2([2*pi*i/100, sin(2*pi*i/100)], 0.05) for i in 1:100];
c = ConvexHullArray(b);

plot(c, 1e-3, alpha=0.1, color="blue")
plot!(b, 1e-3, alpha=0.5, color="red")
0 1 2 3 4 5 6 -1.0 -0.5 0.0 0.5 1.0

2D convex hull

In two dimensions the convex_hull function computes the concrete convex hull of a set of points.

points = N -> [randn(2) for i in 1:N]
v = points(30)
hull = convex_hull(v)
typeof(hull), length(v), length(hull)
(Array{Array{Float64,1},1}, 30, 6)

Notice that the output is a vector of floating point numbers representing the coordinates of the points, and that the number of points in the convex hull has decreased.

We can plot both the random points and the polygon generated by the convex hull with the plot function:

p = plot([Singleton(vi) for vi in v])
plot!(p, VPolygon(hull), alpha=0.2)
-1 0 1 2 -2 -1 0 1

Using static vectors

Usual vectors are such that you can push! and pop! without changing its type: the size is not a static property. Vectors of fixed size, among other types, are provided by the StaticArrays.jl package from the JuliaArrays ecosystem. Using static arrays for vectors of "small" dimension can dramatically improve performance.

Since the convex hull algorithm supports any AbstractVector, it can be applied with static vectors. The following example illustrates this fact.

v = points(1000)
convex_hull(points(3)) # warm-up

@time convex_hull(v)
  0.000249 seconds (17 allocations: 12.953 KiB)
10-element Array{Array{Float64,1},1}:
 [-3.49183, 1.82106]
 [-2.88414, -2.17789]
 [-1.94917, -2.82841]
 [-0.355406, -3.04909]
 [0.894313, -2.66359]
 [2.42473, -1.71248]
 [3.7595, -0.641799]
 [1.90957, 2.47573]
 [1.6495, 2.87817]
 [0.735983, 3.37051]

Now working with static vectors:

using StaticArrays

convex_hull([@SVector(rand(2)) for i in 1:3]) # warm-up

v_static = [SVector{2, Float64}(vi) for vi in v]
@time convex_hull(v_static)
  0.000166 seconds (17 allocations: 25.203 KiB)
10-element Array{StaticArrays.SArray{Tuple{2},Float64,1,2},1}:
 [-3.49183, 1.82106]
 [-2.88414, -2.17789]
 [-1.94917, -2.82841]
 [-0.355406, -3.04909]
 [0.894313, -2.66359]
 [2.42473, -1.71248]
 [3.7595, -0.641799]
 [1.90957, 2.47573]
 [1.6495, 2.87817]
 [0.735983, 3.37051]