Convex hull

ConvexHull{N, S1<:LazySet{N}, S2<:LazySet{N}} <: ConvexSet{N}

Type that represents the convex hull of the union of two sets, i.e., the set

\[Z = \{z ∈ ℝ^n : z = λx + (1-λ)y,\qquad x ∈ X, y ∈ Y,λ ∈ [0, 1] \}.\]

Fields

• X – set
• Y – set

Notes

The EmptySet is the neutral element for ConvexHull.

This type is always convex.

The convenience alias CH is also available.

Examples

The convex hull of two 100-dimensional Euclidean balls:

julia> b1, b2 = Ball2(zeros(100), 0.1), Ball2(4*ones(100), 0.2);

julia> c = ConvexHull(b1, b2);

julia> typeof(c)
ConvexHull{Float64, Ball2{Float64, Vector{Float64}}, Ball2{Float64, Vector{Float64}}}

swap(ch::ConvexHull)

Return a new ConvexHull object with the arguments swapped.

Input

• ch – convex hull of two sets

Output

A new ConvexHull object with the arguments swapped.

dim(ch::ConvexHull)

Return the dimension of a convex hull of two sets.

Input

• ch – convex hull of two sets

Output

The ambient dimension of the convex hull of two sets.

ρ(d::AbstractVector, ch::ConvexHull)

Evaluate the support function of the convex hull of two sets in a given direction.

Input

• d – direction
• ch – convex hull of two sets

Output

The evaluation of the support function of the convex hull in the given direction.

σ(d::AbstractVector, ch::ConvexHull)

Return a support vector of the convex hull of two sets in a given direction.

Input

• d – direction
• ch – convex hull of two sets

Output

A support vector of the convex hull in the given direction.

isbounded(ch::ConvexHull)

Check whether the convex hull of two sets is bounded.

Input

• ch – convex hull of two sets

Output

true iff both wrapped sets are bounded.

isempty(ch::ConvexHull)

Check whether the convex hull of two sets is empty.

Input

• ch – convex hull

Output

true iff both wrapped sets are empty.

vertices_list(ch::ConvexHull; [apply_convex_hull]::Bool=true,
              [backend]=nothing)

Return a list of vertices of the convex hull of two sets.

Input

• ch – convex hull of two sets
• apply_convex_hull – (optional, default: true) if true, post-process the vertices using a convex-hull algorithm
• backend – (optional, default: nothing) backend for computing the convex hull (see argument apply_convex_hull)

Output

A list of vertices.

ConvexHullArray{N, S<:LazySet{N}} <: ConvexSet{N}

Type that represents the symbolic convex hull of a finite number of sets.

Fields

• array – array of sets

Notes

The EmptySet is the neutral element for ConvexHullArray.

A ConvexHullArray is always convex.

The convenience alias CHArray is also available.

Examples

Convex hull of 100 two-dimensional balls whose centers follow a sinusoidal:

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

julia> c = ConvexHullArray(b);

ConvexHull!(X, Y)

Convenience function to compute the lazy convex hull and modify ConvexHullArrays in-place.

dim(cha::ConvexHullArray)

Return the dimension of the convex hull of a finite number of sets.

Input

• cha – convex hull of a finite number of sets

Output

The ambient dimension of the convex hull of a finite number of sets, or 0 if there is no set in the array.

ρ(d::AbstractVector, cha::ConvexHullArray)

Evaluate the support function of a convex hull of a finite number of sets in a given direction.

Input

• d – direction
• cha – convex hull of a finite number of sets

Output

The evaluation of the support function of the convex hull of a finite number of sets in the given direction.

Algorithm

This algorithm calculates the maximum over all $ρ(d, X_i)$, where the $X_1, …, X_k$ are the sets in the array of cha.

σ(d::AbstractVector, cha::ConvexHullArray)

Return a support vector of a convex hull of a finite number of sets in a given direction.

Input

• d – direction
• cha – convex hull of a finite number of sets

Output

A support vector in the given direction.

isbounded(cha::ConvexHullArray)

Check whether a convex hull of a finite number of sets is bounded.

Input

• cha – convex hull of a finite number of sets

Output

true iff all wrapped sets are bounded.

array(cha::ConvexHullArray)

Return the array of a convex hull of a finite number of sets.

Input

• cha – convex hull of a finite number of sets

Output

The array of a convex hull of a finite number of sets.

isempty(cha::ConvexHullArray)

Check whether a convex hull of a finite number of sets is empty.

Input

• cha – convex hull of a finite number of sets

Output

true iff all wrapped sets are empty.

vertices_list(cha::ConvexHullArray; [apply_convex_hull]::Bool=true,
              [backend]=nothing, [prune]::Bool=apply_convex_hull)

Return a list of vertices of the convex hull of a finite number of sets.

Input

• cha – convex hull of a finite number of sets
• apply_convex_hull – (optional, default: true) if true, post-process the vertices using a convex-hull algorithm
• backend – (optional, default: nothing) backend for computing the convex hull (see argument apply_convex_hull)
• prune – (optional, default: apply_convex_hull) alias for apply_convex_hull

Output

A list of vertices.