Iterative refinement

overapproximate_hausdorff(X::S, ε::Real) where {N<:AbstractFloat, S<:LazySet{N}}

Return an ε-close overapproximation of the given 2D convex set (in terms of the Hausdorff distance) in the form of a polygon in constraint representation.

Input

• X – 2D convex set
• ε – error bound

Output

A polygon in constraint representation.

LocalApproximation{N, VN<:AbstractVector{N}}

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 – flag stating whether this approximation is refinable
• err – error upper bound

Notes

The criteria for being refinable are determined in new_approx.

PolygonalOverapproximation{N, SN<:LazySet{N}, VN<:AbstractVector{N}}

Type that represents a polygonal overapproximation of a convex set.

Fields

• S – convex set
• approx_stack – stack of local approximations that still need to be examined
• constraints – vector of half-spaces that are already finalized (i.e., they satisfy the given error bound)

new_approx(S::LazySet, p1::VN, d1::VN,
           p2::VN, d2::VN) where {N<:AbstractFloat, VN<:AbstractVector{N}}

Create a LocalApproximation instance for the given excerpt of a polygonal overapproximation.

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::VN, d1::VN,
                  p2::VN, d2::VN) where {N, VN<:AbstractVector{N}}

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(approx::LocalApproximation, S::LazySet)

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

Input

• approx – local approximation to be refined
• S – 2D convex set

Output

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

tohrep(Ω::PolygonalOverapproximation)

Convert a polygonal overapproximation into a polygon in constraint representation.

Input

• Ω – polygonal overapproximation of a convex set

Output

A polygon in constraint representation.

Algorithm

Internally, the constraints of Ω are already sorted.

convert(::Type{HalfSpace}, approx::LocalApproximation)

Convert a local approximation to a half-space.

Input

• approx – local approximation

Output

A half-space.