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 LazySets, Plots

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

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

This type is parametric in the operands's types.

p = plot(X, 1e-2, color="blue")
plot!(p, expm(A) * X, 1e-2, color="green")
plot!(p, Y, 1e-2, color="red", alpha=0.2)
-0.2 0.0 0.2 0.4 0.6 0.8 1.0 1.0 1.5 2.0 2.5 3.0

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

X = Bn(100)
A = blkdiag([sparse(A) for i in 1:50]...)
Y = CH(X, expm(full(A)) * X)

dim(Y)
100

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, 7)

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[Singleton(vi) for vi in v])
plot!(p, VPolygon(hull), alpha=0.2)
-1 0 1 2 -2 -1 0 1 2

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.000284 seconds (99 allocations: 19.732 KiB)
13-element Array{Array{Float64,1},1}:
 [-3.57082, -0.334894]
 [-3.24391, -2.06592]
 [-1.36416, -2.72219]
 [-0.486683, -2.66038]
 [0.0349125, -2.59923]
 [1.11136, -2.36075]
 [2.2975, -1.8815]
 [2.71024, -1.10962]
 [2.85177, 0.000998387]
 [2.61265, 1.14589]
 [1.66675, 2.0625]
 [-0.370397, 3.68034]
 [-2.63059, 1.35663]

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.000209 seconds (19 allocations: 25.391 KiB)
13-element Array{SVector{2,Float64},1}:
 [-3.57082, -0.334894]
 [-3.24391, -2.06592]
 [-1.36416, -2.72219]
 [-0.486683, -2.66038]
 [0.0349125, -2.59923]
 [1.11136, -2.36075]
 [2.2975, -1.8815]
 [2.71024, -1.10962]
 [2.85177, 0.000998387]
 [2.61265, 1.14589]
 [1.66675, 2.0625]
 [-0.370397, 3.68034]
 [-2.63059, 1.35663]