Approximations

Module Approximations.jl – polygonal approximation of convex sets through support vectors.

decompose(S::LazySet, [set_type]::Type=HPolygon
         )::CartesianProductArray

Compute an overapproximation of the projections of the given convex set over each two-dimensional subspace.

Input

• S – convex set

• set_type – (optional, default: HPolygon) type of set approximation in 2D

Output

A CartesianProductArray corresponding to the Cartesian product of two-dimensional sets of type set_type.

Algorithm

For each 2D block a specific decompose_2D method is called, dispatched on the set_type argument.

decompose(S::LazySet, ɛi::Vector{Float64})::CartesianProductArray

Compute an overapproximation of the projections of the given convex set over each two-dimensional subspace with a certified error bound.

Input

• S – convex set

• ɛi – array with the error bound for each projection (different error bounds can be passed for different blocks)

Output

A CartesianProductArray corresponding to the Cartesian product of $2 × 2$ polygons.

Algorithm

This algorithm assumes a decomposition into two-dimensional subspaces only, i.e., partitions of the form $[2, 2, …, 2]$. In particular, if S is a CartesianProductArray, no check is performed to verify that assumption.

The algorithm proceeds as follows:

1. Project the set S into each partition, with M⋅S, where M is the identity matrix in the block coordinates and zero otherwise.

2. Overapproximate the set with a given error bound, ɛi[i], for $i = 1, …, b$,

3. Return the result as a CartesianProductArray.

decompose(S::LazySet, ɛ::Float64, [set_type]::Type=HPolygon
         )::CartesianProductArray

Compute an overapproximation of the projections of the given convex set over each two-dimensional subspace with a certified error bound.

Input

• S – convex set

• ɛ – error bound

• set_type – (optional, default: HPolygon) type of set approximation in 2D

Output

A CartesianProductArray corresponding to the Cartesian product of two-dimensional sets of type set_type.

Notes

This function is a particular case of decompose(S, ɛi), where the same error bound for each block is assumed.

The set_type argument is ignored if $ɛ ≠ \text{Inf}$.

overapproximate(S::LazySet, ::Type{HPolygon})::HPolygon

Return an approximation of a given 2D convex set as a box-shaped polygon.

Input

• S – convex set, assumed to be two-dimensional

• HPolygon for dispatch

Output

A box-shaped polygon in constraint representation.

overapproximate(S::LazySet)::HPolygon

Alias for overapproximate(S, HPolygon).

overapproximate(S::LazySet, Type{Hyperrectangle})::Hyperrectangle

Return an approximation of a given 2D convex set as a hyperrectangle.

Input

• S – convex set, assumed to be two-dimensional

• Hyperrectangle for dispatch

Output

A hyperrectangle.

overapproximate(S::LazySet, ɛ::Float64)::HPolygon

Return an ɛ-close approximation of the given 2D set (in terms of Hausdorff distance) as a polygon.

Input

• S – convex set, assumed to be two-dimensional

• ɛ – error bound

Output

A polygon in constraint representation.

ballinf_approximation(S)

Overapproximate a convex set by a tight ball in the infinity norm.

Input

• S – convex set

Output

A tight ball in the infinity norm.

Algorithm

The center and radius of the box are obtained by evaluating the support function of the given convex set along the canonical directions.

box_approximation(S::LazySet)::Hyperrectangle

Overapproximate a convex set by a tight hyperrectangle.

Input

• S – convex set

Output

A tight hyperrectangle.

Algorithm

The center of the hyperrectangle is obtained by averaging the support function of the given set in the canonical directions, and the lengths of the sides can be recovered from the distance among support functions in the same directions.

interval_hull

Alias for box_approximation.

box_approximation_symmetric(S::LazySet)::Hyperrectangle

Overapproximate a convex set by a tight hyperrectangle centered in the origin.

Input

• S – convex set

Output

A tight hyperrectangle centered in the origin.

Algorithm

The center of the box is the origin, and the radius is obtained by computing the maximum value of the support function evaluated at the canonical directions.

symmetric_interval_hull

Alias for box_approximation_symmetric.

box_approximation_helper(S::LazySet)

Common code of box_approximation and box_approximation_symmetric.

Input

• S – convex set

Output

A tuple containing the data that is needed to construct a tightly overapproximating hyperrectangle.

• c – center

• r – radius

Algorithm

The center of the hyperrectangle is obtained by averaging the support function of the given convex set in the canonical directions. The lengths of the sides can be recovered from the distance among support functions in the same directions.

norm(S::LazySet, [p]::Real=Inf)

Return the norm of a convex set. It is the norm of the enclosing ball (of the given norm) of minimal volume.

Input

• S – convex set

• p – (optional, default: Inf) norm

Output

A real number representing the norm.

radius(S::LazySet, [p]::Real=Inf)

Return the radius of a convex set. It is the radius of the enclosing ball (of the given norm) of minimal volume with the same center.

Input

• S – convex set

• p – (optional, default: Inf) norm

Output

A real number representing the radius.

diameter(S::LazySet, [p]::Real=Inf)

Return the diameter of a convex set. It is the maximum distance between any two elements of the set, or, equivalently, the diameter of the enclosing ball (of the given norm) of minimal volume with the same center.

Input

• S – convex set

• p – (optional, default: Inf) norm

Output

A real number representing the diameter.

LocalApproximation{N<:Real}

Type that represents a local approximation in 2D.

Fields

• p1 – first inner point

• d1 – first direction

• p2 – second inner point

• d2 – second direction

• q – intersection of the lines l1 ⟂ d1 at p1 and l2 ⟂ d2 at p2

• refinable – states if this approximation is refinable

• err – error upper bound

Notes

The criteria for refinable are determined in the method new_approx.

PolygonalOverapproximation{N<:Real}

Type that represents the polygonal approximation of a convex set.

Fields

• S – convex set

• approx_list – vector of local approximations

new_approx(S::LazySet, p1::Vector{N}, d1::Vector{N}, p2::Vector{N}, d2::Vector{N}) where {N<:Real}

Input

• S – convex set

• p1 – first inner point

• d1 – first direction

• p2 – second inner point

• d2 – second direction

Output

A local approximation of S in the given directions.

addapproximation!(Ω::PolygonalOverapproximation,
    p1::Vector{N}, d1::Vector{N}, p2::Vector{N}, d2::Vector{N}) where {N<:Real}

Input

• Ω – polygonal overapproximation of a convex set

• p1 – first inner point

• d1 – first direction

• p2 – second inner point

• d2 – second direction

Output

The list of local approximations in Ω of the set Ω.S is updated in-place and the new approximation is returned by this function.

refine(Ω::PolygonalOverapproximation, i::Int)::Tuple{LocalApproximation, LocalApproximation}

Refine a given local approximation of the polygonal approximation of a convex set, by splitting along the normal direction to the approximation.

Input

• Ω – polygonal overapproximation of a convex set

• i – integer index for the local approximation to be refined

Output

The tuple consisting of the refined right and left local approximations.

tohrep(Ω::PolygonalOverapproximation)::AbstractHPolygon

Convert a polygonal overapproximation into a concrete polygon.

Input

• Ω – polygonal overapproximation of a convex set

Output

A polygon in constraint representation.

approximate(S::LazySet, ɛ::Float64)::Vector{Approximation2D}

Return an ɛ-close approximation of the given 2D convex set (in terms of Hausdorff distance) as an inner and an outer approximation composed by sorted local Approximation2D.

Input

• S – 2D convex set

• ɛ – error bound

Output

An ɛ-close approximation of the given 2D convex set.