General sets (LazySet)

LazySet{N}

Abstract type for the set types in LazySets.

Notes

LazySet types should be parameterized with a type N, typically N<:Real, for using different numeric types.

Every LazySet must implement the following function:

• dim(X::LazySet) – the ambient dimension of X

While not strictly required, it is useful to implement the following function:

• σ(d::AbstractVector, X::LazySet) – the support vector of X in a given direction d

Implementing the function

• ρ(d::AbstractVector, X::LazySet) – the support function of X in a given direction d

is optional because there is a fallback implementation relying on σ. However, for potentially unbounded sets (which includes most lazy set types) this fallback cannot be used and an explicit implementation should be provided.

The subtypes of LazySet (including abstract interfaces):

julia> subtypes(LazySet, false)
17-element Vector{Any}:
 AbstractAffineMap
 AbstractPolynomialZonotope
 Bloating
 CachedMinkowskiSumArray
 CartesianProduct
 CartesianProductArray
 Complement
 ConvexSet
 Intersection
 IntersectionArray
 MinkowskiSum
 MinkowskiSumArray
 Polygon
 QuadraticMap
 Rectification
 UnionSet
 UnionSetArray

If we only consider concrete subtypes, then:

julia> concrete_subtypes = subtypes(LazySet, true);

julia> length(concrete_subtypes)
53

julia> println.(concrete_subtypes);
AffineMap
Ball1
Ball2
BallInf
Ballp
Bloating
CachedMinkowskiSumArray
CartesianProduct
CartesianProductArray
Complement
ConvexHull
ConvexHullArray
DensePolynomialZonotope
Ellipsoid
EmptySet
ExponentialMap
ExponentialProjectionMap
HParallelotope
HPolygon
HPolygonOpt
HPolyhedron
HPolytope
HalfSpace
Hyperplane
Hyperrectangle
Intersection
IntersectionArray
Interval
InverseLinearMap
Line
Line2D
LineSegment
LinearMap
MinkowskiSum
MinkowskiSumArray
Polygon
QuadraticMap
Rectification
ResetMap
SimpleSparsePolynomialZonotope
Singleton
SparsePolynomialZonotope
Star
SymmetricIntervalHull
Tetrahedron
Translation
UnionSet
UnionSetArray
Universe
VPolygon
VPolytope
ZeroSet
Zonotope

dim(X::LazySet)

Compute the ambient dimension of a set.

Input

• X – set

Output

The ambient dimension of the set.

σ(d::AbstractVector, X::LazySet)

Compute a support vector of a set in a given direction.

Input

• d – direction
• X – set

Output

A support vector of X in direction d.

Notes

A convenience alias support_vector is also available.

ρ(d::AbstractVector, X::LazySet)

Evaluate the support function of a set in a given direction.

Input

• d – direction
• X – set

Output

The evaluation of the support function of X in direction d.

Notes

A convenience alias support_function is also available.

We have the following identity based on the support vector $σ$:

\[ ρ(d, X) = d ⋅ σ(d, X)\]

Extended help

ρ(d::AbstractVector, X::LazySet)

Algorithm

The default implementation computes a support vector via σ.

an_element(X::LazySet)

Return some element of a nonempty set.

Input

• X – set

Output

An element of X unless X is empty.

Extended help

an_element(X::LazySet)

Algorithm

The default implementation computes a support vector along direction $[1, 0, …, 0]$. This may fail for unbounded sets.

area(X::LazySet)

Compute the area of a two-dimensional set.

Input

• X – two-dimensional set

Output

A number representing the area of X.

Extended help

area(X::LazySet)

Notes

This algorithm is applicable to any polytopic set X whose list of vertices can be computed via vertices_list.

Algorithm

Let m be the number of vertices of X. We consider the following instances:

• m = 0, 1, 2: the output is zero.
• m = 3: the triangle case is solved using the Shoelace formula with 3 points.
• m = 4: the quadrilateral case is solved by the factored version of the Shoelace formula with 4 points.

Otherwise, the general Shoelace formula is used; for details see the Wikipedia page.

chebyshev_center_radius(P::LazySet;
                        [backend]=default_polyhedra_backend(P),
                        [solver]=default_lp_solver_polyhedra(eltype(P); presolve=true))

Compute a Chebyshev center and the corresponding radius of a polytopic set.

Input

• P – polytopic set
• backend – (optional; default: default_polyhedra_backend(P)) the backend for polyhedral computations
• solver – (optional; default: default_lp_solver_polyhedra(N; presolve=true)) the LP solver passed to Polyhedra

Output

The pair (c, r) where c is a Chebyshev center of P and r is the radius of the largest Euclidean ball with center c enclosed by P.

Notes

The Chebyshev center is the center of a largest Euclidean ball enclosed by P. In general, the center of such a ball is not unique, but the radius is.

Algorithm

We call Polyhedra.chebyshevcenter.

complement(X::LazySet)

Compute the complement of a set.

Input

• X – set

Output

A set representing the complement of X.

Extended help

complement(X::LazySet)

Algorithm

The default implementation assumes that X is polyhedral and returns a UnionSetArray of HalfSpaces, i.e., the output is the union of the linear constraints which are obtained by complementing each constraint of X. For any pair of sets $(X, Y)$ we have the identity $(X ∩ Y)^C = X^C ∪ Y^C$. We can apply this identity for each constraint that defines a polyhedral set.

concretize(X::LazySet)

Construct a concrete representation of a (possibly lazy) set.

Input

• X – set

Output

A concrete representation of X (as far as possible).

Notes

Since not every lazy set has a concrete set representation in this library, the result may still be partially lazy.

Extended help

concretize(X::LazySet)

Algorithm

The default implementation returns X. All relevant lazy set types should override this behavior, typically by recursively calling concretize on the set arguments.

constraints(X::LazySet)

Construct an iterator over the constraints of a polyhedral set.

Input

• X – polyhedral set

Output

An iterator over the constraints of X.

Extended help

constraints(X::LazySet)

Algorithm

The default implementation computes all constraints via constraints_list.

convex_hull(X::LazySet)

Compute the convex hull of a set.

Input

• X – set

Output

A set representing the convex hull of X.

Notes

The convex hull of a set $X$ is defined as

\[ \{λx + (1-λ)y \mid x, y ∈ X, λ ∈ [0, 1]\}.\]

Extended help

convex_hull(X::LazySet; kwargs...)

Output

The set X itself if its type indicates that it is convex, or a new set with the list of the vertices describing the convex hull.

Algorithm

For non-convex sets, this method relies on the vertices_list method.

delaunay(X::LazySet)

Compute the Delaunay triangulation of the given polytopic set.

Input

• X – polytopic set
• compute_triangles_3d – (optional; default: false) flag to compute the 2D triangulation of a 3D set

Output

A union of polytopes in vertex representation.

Notes

This implementation requires the package MiniQhull.jl, which uses the library Qhull.

The method works in arbitrary dimension and the requirement is that the list of vertices of X can be obtained.

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

Return the diameter of a set.

Input

• X – set
• p – (optional, default: Inf) norm

Output

A real number representing the diameter.

Notes

The diameter of a set is the maximum distance between any two elements of the set, or, equivalently, the diameter of the enclosing ball (of the given $p$-norm) of minimal volume.

Extended help

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

Algorithm

The default implementation applies the function radius and doubles the result.

eltype(T::Type{<:LazySet})

Determine the numeric type of a set type.

Input

• T – set type

Output

The numeric type of T.

Extended help

eltype(::Type{<:LazySet{N}}) where {N}

Algorithm

The default implementation assumes that the first type parameter is the numeric type.

Extended help

eltype(::LazySet{N}) where {N}

Algorithm

The default implementation assumes that the first type parameter is the numeric type.

eltype(X::LazySet)

Determine the numeric type of a set.

Input

• X – set

Output

The numeric type of X.

Extended help

eltype(::Type{<:LazySet{N}}) where {N}

Algorithm

The default implementation assumes that the first type parameter is the numeric type.

Extended help

eltype(::LazySet{N}) where {N}

Algorithm

The default implementation assumes that the first type parameter is the numeric type.

extrema(X::LazySet)

Compute the lowest and highest coordinate of a set in each dimension.

Input

• X – set

Output

Two vectors with the lowest and highest coordinates of X in each dimension.

Notes

See also extrema(X::LazySet, i::Int).

The result is equivalent to (low(X), high(X)), but sometimes it can be computed more efficiently.

The resulting points are the lowest and highest corners of the box approximation, so they are not necessarily contained in X.

Algorithm

The default implementation computes the extrema via low and high.

Extended help

extrema(X::LazySet)

Algorithm

The default implementation computes the extrema via low and high.

extrema(X::LazySet, i::Int)

Compute the lowest and highest coordinate of a set in a given dimension.

Input

• X – set
• i – dimension

Output

Two real numbers representing the lowest and highest coordinate of the set in the given dimension.

Notes

The result is equivalent to (low(X, i), high(X, i)), but sometimes it can be computed more efficiently.

The resulting values are the lower and upper ends of the projection.

Extended help

extrema(X::LazySet, i::Int)

Algorithm

The default implementation computes the extrema via low and high.

high(X::LazySet)

Compute the highest coordinate of a set in each dimension.

Input

• X – set

Output

A vector with the highest coordinate of the set in each dimension.

Notes

See also high(X::LazySet, i::Int).

The result is the uppermost corner of the box approximation, so it is not necessarily contained in X.

Extended help

high(X::LazySet)

Algorithm

The default implementation applies high in each dimension.

isbounded(X::LazySet)

Check whether a set is bounded.

Input

• X – set

Output

true iff the set is bounded.

Notes

See also isboundedtype(::Type{<:LazySet}).

Extended help

isbounded(X::LazySet; [algorithm]="support_function")

Input

• algorithm – (optional, default: "support_function") algorithm choice, possible options are "support_function" and "stiemke"

Algorithm

See the documentation of _isbounded_unit_dimensions or _isbounded_stiemke for details.

_isbounded_unit_dimensions(X::LazySet)

Check whether a set is bounded in each unit dimension.

Input

• X – set

Output

true iff the set is bounded in each unit dimension.

Algorithm

This function asks for upper and lower bounds in each ambient dimension.

isboundedtype(T::Type{<:LazySet})

Check whether a set type only represents bounded sets.

Input

• T – set type

Output

true iff the set type only represents bounded sets.

Notes

See also isbounded(::LazySet).

Extended help

isboundedtype(::Type{<:LazySet})

Notes

Note that some sets may still represent an unbounded set even though their type actually does not (example: HPolytope, because the construction with non-bounding linear constraints is allowed).

Algorithm

The default implementation returns false. All set types that can determine boundedness should override this behavior.

isconvextype(T::Type{<:LazySet})

Check whether T is convex just by using type information.

Input

• T – subtype of LazySet

Output

true iff the set type only represents convex sets.

Notes

Since this operation only acts on types (not on values), it can return false negatives, i.e., there may be instances where the set is convex, even though the answer of this function is false. The examples below illustrate this point.

Extended help

isconvextype(::Type{<:LazySet})

Algorithm

The default implementation returns false. All set types that can determine convexity should override this behavior.

Examples

A ball in the infinity norm is always convex:

julia> isconvextype(BallInf)
true

The union (UnionSet) of two sets may in general be either convex or not. Since convexity cannot be decided by just using type information, isconvextype returns false.

julia> isconvextype(UnionSet)
false

However, the type parameters of set operations allow to decide convexity in some cases by falling back to the convexity information of the argument types. Consider the lazy intersection. The intersection of two convex sets is always convex:

julia> isconvextype(Intersection{Float64, BallInf{Float64}, BallInf{Float64}})
true

isempty(X::LazySet, witness::Bool=false)

Check whether a set is empty.

Input

• X – set
• witness – (optional, default: false) compute a witness if activated

Output

• If the witness option is deactivated: true iff $X = ∅$
• If the witness option is activated:
  • (true, []) iff $X = ∅$
  • (false, v) iff $X ≠ ∅$ for some $v ∈ X$

Extended help

isempty(P::LazySet, witness::Bool=false;
        [use_polyhedra_interface]::Bool=false, [solver]=nothing,
        [backend]=nothing)

Input

• witness – (optional, default: false) compute a witness if activated
• use_polyhedra_interface – (optional, default: false) if true, we use the Polyhedra interface for the emptiness test
• solver – (optional, default: nothing) LP-solver backend; uses default_lp_solver if not provided
• backend – (optional, default: nothing) backend for polyhedral computations in Polyhedra; uses default_polyhedra_backend(P) if not provided

Notes

This implementation assumes that P is polyhedral.

The default value of the backend is set internally and depends on whether the use_polyhedra_interface option is set. If the option is set, we use default_polyhedra_backend(P).

Witness production is not supported if use_polyhedra_interface is true.

Algorithm

The algorithm sets up a feasibility LP for the constraints of P. If use_polyhedra_interface is true, we call Polyhedra.isempty. Otherwise, we set up the LP internally.

isoperation(X::LazySet)

Check whether a set is an instance of a (lazy) set operation.

Input

• X – set

Output

true iff X is an instance of a set-based operation.

Notes

See also isoperationtype(::Type{<:LazySet}).

Extended help

isoperation(X::LazySet)

Algorithm

The default implementation checks whether the set type of the input is an operation type using isoperationtype(::Type{<:LazySet}).

Examples

julia> B = BallInf([0.0, 0.0], 1.0);

julia> isoperation(B)
false

julia> isoperation(B ⊕ B)
true

ispolyhedral(X::LazySet)

Check whether a set is polyhedral.

Input

• X – set

Output

true only if the set is polyhedral.

Notes

The answer is conservative, i.e., may sometimes be false even if the set is polyhedral.

Extended help

ispolyhedral(::LazySet)

Algorithm

The default implementation returns false. All set types that can determine the polyhedral property should override this behavior.

low(X::LazySet)

Compute the lowest coordinates of a set in each dimension.

Input

• X – set

Output

A vector with the lowest coordinate of the set in each dimension.

Notes

See also low(X::LazySet, i::Int).

The result is the lowermost corner of the box approximation, so it is not necessarily contained in X.

Extended help

low(X::LazySet)

Algorithm

The default implementation applies low in each dimension.

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

Return the norm of a set.

Input

• X – set
• p – (optional, default: Inf) norm

Output

A real number representing the norm.

Notes

The norm of a set is the norm of the enclosing ball (of the given $p$-norm) of minimal volume that is centered in the origin.

Extended help

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

Algorithm

The default implementation handles the case p == Inf using extrema. Otherwise it checks whether X is polytopic, in which case it iterates over all vertices.

polyhedron(P::LazySet; [backend]=default_polyhedra_backend(P))

Compute a set representation from Polyhedra.jl.

Input

• P – polyhedral set
• backend – (optional, default: call default_polyhedra_backend(P)) the polyhedral computations backend

Output

A set representation in the Polyhedra library.

Notes

For further information on the supported backends see Polyhedra's documentation.

Algorithm

This default implementation uses tosimplehrep, which computes the constraint representation of P. Set types preferring the vertex representation should implement their own method.

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

Return the radius of a set.

Input

• X – set
• p – (optional, default: Inf) norm

Output

A real number representing the radius.

Notes

The radius of a set is the radius of the enclosing ball (of the given $p$-norm) of minimal volume.

Extended help

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

Algorithm

The default implementation handles the case p == Inf using ballinf_approximation.

rationalize(::Type{T}, X::LazySet, tol::Real) where {T<:Integer}

Approximate a set represented with floating-point numbers as a set represented with rationals of the given integer type.

Input

• T – (optional, default: Int) integer type to represent the rationals
• X – set represented by floating-point components
• tol – (optional, default: eps(N)) tolerance of the result; each rationalized component will differ by no more than tol with respect to the floating-point value

Output

A set of the same base type as X where each numerical component is of type Rational{T}.

Algorithm

The default implementation rationalizes each field.

rectify(X::LazySet)

Compute the rectification of a set.

Input

• X – set

Output

A set representing the rectification of X.

Extended help

rectify(X::LazySet, [concrete_intersection]::Bool=false)

Algorithm

For each dimension in which X is both positive and negative, we split X into these two parts and then project the negative part to zero.

reflect(X::LazySet)

Compute the reflection of a set in the origin.

Input

• X – set

Output

A set representing the reflection $-X$.

Extended help

reflect(P::LazySet)

Output

The set -P, which is either of type HPolytope if P is a polytope (i.e., bounded) or of type HPolyhedron otherwise.

Algorithm

This function requires that the list of constraints of the set P is available, i.e., that it can be written as $P = \{z ∈ ℝⁿ: ⋂ sᵢᵀz ≤ rᵢ, i = 1, ..., N\}.$

This function can be used to implement the alternative definition of the Minkowski difference

\[ A ⊖ B = \{a − b \mid a ∈ A, b ∈ B\} = A ⊕ (-B)\]

by calling minkowski_sum(A, reflect(B)).

singleton_list(P::LazySet)

Return the vertices of a polytopic set as a list of singletons.

Input

• P – polytopic set

Output

A list of the vertices of P as Singletons.

Notes

This function relies on vertices_list, which raises an error if the set is not polytopic (e.g., unbounded).

triangulate(X::LazySet)

Triangulate the faces of a three-dimensional polytopic set.

Input

• X – three-dimensional polytopic set

Output

A tuple (p, c) where p is a matrix, with each column containing a point, and c is a list of 3-tuples containing the indices of the points in each triangle.

Notes

This function triangulates all faces of a 3D polytope. The result is a list of (flat) triangles in 3D which describe the boundary of X.

X must contain at least three vertices.

tohrep(P::LazySet)

Convert a polyhedral set to constraint representation.

Input

• P – polyhedral set

Output

An HPolyhedron if P is bounded (via isboundedtype) or an HPolytope otherwise.

tosimplehrep(S::LazySet)

Return the simple constraint representation $Ax ≤ b$ of a polyhedral set from its list of linear constraints.

Input

• S – polyhedral set

Output

The tuple (A, b) where A is the matrix of normal directions and b is the vector of offsets.

Algorithm

This fallback implementation relies on constraints_list(S).

tovrep(P::LazySet)

Convert a polytopic set to vertex representation.

Input

• P – polytopic set

Output

A VPolytope.

vertices(X::LazySet)

Construct an iterator over the vertices of a polytopic set.

Input

• X – polytopic set

Output

An iterator over the vertices of X.

Extended help

vertices(X::LazySet)

Algorithm

The default implementation computes all vertices via vertices_list.

affine_map(M::AbstractMatrix, X::LazySet, v::AbstractVector)

Compute the affine map $M · X + v$.

Input

• M – matrix
• X – set
• v – translation vector

Output

A set representing the affine map $M · X + v$.

Extended help

affine_map(M, X::LazySet, v::AbstractVector; [kwargs]...)

Algorithm

The default implementation applies the functions linear_map and translate.

exponential_map(M::AbstractMatrix, X::LazySet)

Compute the exponential map of M and X, i.e., $eᴹ ⋅ X$.

Input

• M – matrix
• X – set

Output

A set representing the exponential map $eᴹ ⋅ X$.

Extended help

exponential_map(M::AbstractMatrix, X::LazySet)

Algorithm

The default implementation applies the functions exp and linear_map.

is_interior_point(v::AbstractVector{<:Real}, X::LazySet; kwargs...) end

Check whether a point is contained in the interior of a set.

Input

• v – point/vector
• X – set
• p – (optional; default: Inf) norm of the ball used to apply the error tolerance
• ε – (optional; default: _rtol(eltype(X))) error tolerance of the check

Output

true iff the point v is strictly contained in X with tolerance ε.

Extended help

is_interior_point(v::AbstractVector{<:Real}, X::LazySet; [kwargs]...)

Algorithm

The default implementation determines v ∈ interior(X) with error tolerance ε by checking whether a Ballp of norm p with center v and radius ε is contained in X.

linear_map(M::AbstractMatrix, X::LazySet)

Compute the linear map $M · X$.

Input

• M – matrix
• X – set

Output

A set representing the linear map $M · X$.

Extended help

linear_map(M::AbstractMatrix, P::LazySet; kwargs...)

Algorithm

The default implementation assumes that P is polyhedral and applies an algorithm based on the set type (see _linear_map_polyhedron).

project(X::LazySet, block::AbstractVector{Int}, [::Nothing=nothing],
        [n]::Int=dim(X); [kwargs...])

Project a set to a given block by using a concrete linear map.

Input

• X – set
• block – block structure - a vector with the dimensions of interest
• nothing – (default: nothing) needed for dispatch
• n – (optional, default: dim(X)) ambient dimension of the set X

Output

A set representing the projection of X to block block.

Algorithm

We apply the function linear_map.

project(X::LazySet, block::AbstractVector{Int}, set_type::Type{<:LazySet},
        [n]::Int=dim(X); [kwargs...])

Project a set to a given block and set type, possibly involving an overapproximation.

Input

• X – set
• block – block structure - a vector with the dimensions of interest
• set_type – target set type
• n – (optional, default: dim(X)) ambient dimension of the set X

Output

A set of type set_type representing an overapproximation of the projection of X.

Algorithm

1. Project the set X with M⋅X, where M is the identity matrix in the block

coordinates and zero otherwise.

1. Overapproximate the projected set using overapproximate and set_type.

project(X::LazySet, block::AbstractVector{Int},
        set_type_and_precision::Pair{<:UnionAll,<:Real}, [n]::Int=dim(X);
        [kwargs...])

Project a set to a given block and set type with a certified error bound.

Input

• X – set
• block – block structure - a vector with the dimensions of interest
• set_type_and_precision – pair (T, ε) of a target set type T and an error bound ε for approximation
• n – (optional, default: dim(X)) ambient dimension of the set X

Output

A set representing the epsilon-close approximation of the projection of X.

Notes

Currently we only support HPolygon as set type, which implies that the set must be two-dimensional.

Algorithm

1. Project the set X with M⋅X, where M is the identity matrix in the block

coordinates and zero otherwise.

1. Overapproximate the projected set with the given error bound ε.

project(X::LazySet, block::AbstractVector{Int}, ε::Real, [n]::Int=dim(X);
        [kwargs...])

Project a set to a given block and set type with an error bound.

Input

• X – set
• block – block structure - a vector with the dimensions of interest
• ε – error bound for approximation
• n – (optional, default: dim(X)) ambient dimension of the set X

Output

A set representing the epsilon-close approximation of the projection of X.

Algorithm

1. Project the set X with M⋅X, where M is the identity matrix in the block

coordinates and zero otherwise.

1. Overapproximate the projected set with the given error bound ε.

The target set type is chosen automatically.

scale(α::Real, X::LazySet)

Compute the scaling of a set.

Input

• α – scalar
• X – set

Output

A set representing $α ⋅ X$.

Extended help

scale(α::Real, X::LazySet)

Algorithm

The default implementation computes linear_map with the diagonal matrix $α*I$.

translate(X::LazySet, v::AbstractVector)

Compute the translation of a set with a vector.

Input

• X – set
• v – vector

Output

A set representing $X + \{v\}$.

Extended help

translate(X::LazySet, v::AbstractVector)

Algorithm

The default implementation calls translate! on a copy of X.

cartesian_product(X::LazySet, Y::LazySet)

Compute the Cartesian product of two sets.

Input

• X – set
• Y – set

Output

A set representing the Cartesian product $X × Y$.

Notes

The Cartesian product of two sets $X$ and $Y$ is defined as

\[ X × Y = \{[x, y] \mid x ∈ X, y ∈ Y\}.\]

cartesian_product(X::LazySet, Y::LazySet; [backend]=nothing,
                  [algorithm]::String="vrep")

Compute the Cartesian product of two sets.

Input

• X – set

• Y – set

• backend – (optional, default: nothing) backend for polyhedral computation

• algorithm – (optional, default: "hrep") the method used to transform the sets X and Y before taking the Cartesian product; choose between:

  • "vrep" (use the vertex representation)
  • "hrep" (use the constraint representation)
  • "hrep_polyhedra" (use the constraint representation and Polyhedra)

Output

The VPolytope (if "vrep" was used) or HPolytope/HPolyhedron (if "hrep" or "hrep_polyhedra" was used) obtained by the concrete Cartesian product of X and Y. The choice between HPolytope and HPolyhedron is made based on boundedness information deduced from the type.

Notes

For further information on the supported backends see Polyhedra's documentation.

If X can be converted to a one-dimensional interval and the vertices of Y are available, use algorithm="vrep".

convex_hull(X::LazySet, Y::LazySet; [algorithm]=nothing,
            [backend]=nothing, [solver]=nothing)

Compute the convex hull of two polytopic sets.

Input

• X – polytopic set
• Y – polytopic set
• algorithm – (optional, default: nothing) the convex-hull algorithm
• backend – (optional, default: nothing) backend for polyhedral computations (used for higher-dimensional sets)
• solver – (optional, default: nothing) the linear-programming solver used in the backend

Output

If the sets are empty, the result is an EmptySet. If the convex hull consists of a single point, the result is a Singleton. If the input sets are one-dimensional, the result is an Interval. If the input sets are two-dimensional, the result is a VPolygon. Otherwise the result is a VPolytope.

Algorithm

We compute the vertices of both X and Y using vertices_list and then compute the convex hull of the union of those vertices.

≈(X::LazySet, Y::LazySet)

Check whether two sets of the same type are approximately equal.

Input

• X – set
• Y – set of the same base type as X

Output

true iff X is approximately equal to Y.

Notes

The check is purely syntactic and the sets need to have the same base type, i.e., X::T1 ≈ Y::T2 always returns false even if X and Y represent the same set. But X::T{Int64} ≈ Y::T{Float64} is a valid comparison.

The convenience alias isapprox is also available.

"≈" can be typed by \approx<tab>.

Extended help

≈(X::LazySet, Y::LazySet)

Algorithm

The default implementation recursively compares the fields of X and Y until a mismatch is found.

Examples

julia> HalfSpace([1], 1) ≈ HalfSpace([1.0], 1.0)
true

julia> HalfSpace([1], 1) ≈ HalfSpace([1.00000001], 0.99999999)
true

julia> BallInf([0.0], 1.0) ≈ Hyperrectangle([0.0], [1.0])
false

isdisjoint(X::LazySet, Y::LazySet, [witness]::Bool=false)

Check whether two sets are disjoint (i.e., do not intersect), and optionally compute a witness.

Input

• X – set
• Y – set
• witness – (optional, default: false) compute a witness if activated

Output

• If the witness option is deactivated: true iff $X ∩ Y = ∅$
• If the witness option is activated:
  • (true, []) iff $X ∩ Y = ∅$
  • (false, v) iff $X ∩ Y ≠ ∅$ for some $v ∈ X ∩ Y$

Notes

The convenience alias is_intersection_empty is also available.

Extended help

isdisjoint(X::LazySet, Y::LazySet, [witness]::Bool=false)

Algorithm

This is a fallback implementation that computes the concrete intersection, intersection, of the given sets.

A witness is constructed using the an_element implementation of the result.

==(X::LazySet, Y::LazySet)

Check whether two sets use exactly the same set representation.

Input

• X – set
• Y – set

Output

true iff X is equal to Y.

Notes

The check is purely syntactic and the sets need to have the same base type, i.e., X::T1 == Y::T2 always returns false even if X and Y represent the same set. But X::T{Int64} == Y::T{Float64} is a valid comparison.

Extended help

==(X::LazySet, Y::LazySet)

Algorithm

The default implementation recursively compares the fields of X and Y until a mismatch is found.

Examples

julia> HalfSpace([1], 1) == HalfSpace([1.0], 1.0)
true

julia> HalfSpace([1], 1) == HalfSpace([1.00000001], 0.99999999)
false

julia> BallInf([0.0], 1.0) == Hyperrectangle([0.0], [1.0])
false

isequivalent(X::LazySet, Y::LazySet)

Check whether two sets are equivalent, i.e., represent the same set of points.

Input

• X – set
• Y – set

Output

true iff X is equivalent to Y (up to numerical precision).

Extended help

isequivalent(X::LazySet, Y::LazySet)

Algorithm

The default implementation first checks X ≈ Y, which returns true if and only if X and Y have the same base type and approximately the same values. If that fails, the implementation checks the double inclusion X ⊆ Y && Y ⊆ X.

Examples

julia> X = BallInf([0.1, 0.2], 0.3);

julia> Y = convert(HPolytope, X);

julia> X == Y
false

julia> isequivalent(X, Y)
true

⊂(X::LazySet, Y::LazySet, [witness]::Bool=false)

Check whether a set is a strict subset of another set, and optionally compute a witness.

Input

• X – set
• Y – set
• witness – (optional, default: false) compute a witness if activated

Output

• If the witness option is deactivated: true iff $X ⊂ Y$
• If the witness option is activated:
  • (true, v) iff $X ⊂ Y$ for some $v ∈ Y ∖ X$
  • (false, []) iff $X ⊂ Y$ does not hold

Notes

Strict inclusion is sometimes written as ⊊. The following identity holds:

\[ X ⊂ Y ⇔ X ⊆ Y ∧ Y ⊈ X\]

Algorithm

The default implementation first checks inclusion of X in Y and then checks noninclusion of Y in X:

Extended help

⊂(X::LazySet, Y::LazySet, [witness]::Bool=false)

Algorithm

The default implementation first checks inclusion of X in Y and then checks noninclusion of Y in X:

⊆(X::LazySet, Y::LazySet, [witness]::Bool=false)

Check whether a set is a subset of another set, and optionally compute a witness.

Input

• X – set
• Y – set
• witness – (optional, default: false) compute a witness if activated

Output

• If the witness option is deactivated: true iff $X ⊆ Y$
• If the witness option is activated:
  • (true, []) iff $X ⊆ Y$
  • (false, v) iff $X ⊈ Y$ for some $v ∈ X ∖ Y$

Notes

The convenience alias issubset is also available.

Extended help

⊆(X::LazySet, Y::LazySet, witness::Bool=false)

Algorithm

The default implementation assumes that Y is polyhedral, i.e., that constraints_list(Y) is available, and checks inclusion of X in every constraint of Y.

minkowski_difference(P::LazySet, Q::LazySet)

Concrete Minkowski difference (geometric difference) of a polytopic set and a compact set.

Input

• P – polytopic set
• Q – compact set that is subtracted from P

Output

An HPolytope that corresponds to the Minkowski difference of P minus Q if P is bounded, and an HPolyhedron if P is unbounded.

Notes

This implementation requires that the set P is polyhedral and that the set Q is bounded.

Algorithm

This method implements Kolmanovsky and Gilbert [KG98], Theorem 2.3:

Suppose $P$ is a polyhedron

\[P = \{z ∈ ℝ^n: sᵢᵀz ≤ rᵢ,~i = 1, …, k\}.\]

where $sᵢ ∈ ℝ^n, sᵢ ≠ 0$, and $rᵢ ∈ ℝ$. Assume $ρ(sᵢ,Q)$ is defined for $i = 1, …, k$. Then the Minkowski difference is

\[\{z ∈ ℝ^n: sᵢᵀz ≤ rᵢ - ρ(sᵢ,Q),~i = 1, …, k\}.\]

While the algorithm applies the support function to Q, we have that $P ⊖ Q = P ⊖ \text{CH}(Q)$ whenever P is convex, where CH denotes the convex hull. Hence, if Q is not convex by type information, we wrap it in a lazy ConvexHull.

minkowski_sum(P::LazySet, Q::LazySet;
              [backend]=nothing, [algorithm]=nothing, [prune]=true)

Compute the Minkowski sum of two polyhedral sets.

Input

• P – polyhedral set
• Q – polyhedral set
• backend – (optional, default: nothing) polyhedral computations backend
• algorithm – (optional, default: nothing) algorithm to eliminate variables; available options are Polyhedra.FourierMotzkin, Polyhedra.BlockElimination, and Polyhedra.ProjectGenerators
• prune – (optional, default: true) if true, apply a post-processing to remove redundant constraints or vertices

Output

In two dimensions, if the sets are polygons, the result is a VPolygon. In higher dimensions, the result is an HPolytope if both P and Q are known to be bounded by their types, and an HPolyhedron otherwise.

Notes

This method requires that the list of constraints of both sets P and Q can be obtained. After obtaining the respective lists of constraints, the minkowski_sum method for polyhedral sets is used.

plot_lazyset(X::LazySet{N}, [ε]::Real=N(PLOT_PRECISION); ...) where {N}

Plot a set.

Input

• X – set
• ε – (optional, default: PLOT_PRECISION) approximation error bound

Notes

This recipe just defines the default plotting options and then calls the function plot_recipe, which then implements the set-specific plotting.

The argument ε is ignored by some set types, e.g., for polyhedra (subtypes of AbstractPolyhedron).

Examples

julia> B = Ball2(ones(2), 0.1);

julia> plot(B, 1e-3)  # default accuracy value (explicitly given for clarity here)

julia> plot(B, 1e-2)  # faster but less accurate than the previous call

plot_list(list::AbstractVector{VN}, [ε]::Real=N(PLOT_PRECISION),
          [Nφ]::Int=PLOT_POLAR_DIRECTIONS; [same_recipe]=false; ...)
    where {N, VN<:LazySet{N}}

Plot a list of sets.

Input

• list – list of sets (1D or 2D)
• ε – (optional, default: PLOT_PRECISION) approximation error bound
• Nφ – (optional, default: PLOT_POLAR_DIRECTIONS) number of polar directions (used to plot lazy intersections)
• same_recipe – (optional, default: false) switch for faster plotting but without individual plot recipes (see notes below)

Notes

For each set in the list we apply an individual plot recipe.

The option same_recipe provides access to a faster plotting scheme where all sets in the list are first converted to polytopes and then plotted in one single run. This, however, is not suitable when plotting flat sets (line segments, singletons) because then the polytope plot recipe does not deliver good results. Hence by default we do not use this option. For plotting a large number of (non-flat) polytopes, we highly advise activating this option.

Examples

julia> B1 = BallInf(zeros(2), 0.4);

julia> B2 = BallInf(ones(2), 0.4);

julia> plot([B1, B2])

Some of the sets in the list may not be plotted precisely but rather overapproximated first. The second argument ε controls the accuracy of this overapproximation.

julia> Bs = [BallInf(zeros(2), 0.4), Ball2(ones(2), 0.4)];

julia> plot(Bs, 1e-3)  # default accuracy value (explicitly given for clarity)

julia> plot(Bs, 1e-2)  # faster but less accurate than the previous call

plot_vlist(X::S, ε::Real) where {S<:LazySet}

Return a list of vertices used for plotting a two-dimensional set.

Input

• X – two-dimensional set
• ε – precision parameter

Output

A list of vertices of a polygon P. For convex X, P usually satisfies that the Hausdorff distance to X is less than ε.

plot_recipe(X::LazySet, [ε])

Convert a compact convex set to a pair (x, y) of points for plotting.

Input

• X – compact convex set
• ε – approximation-error bound

Output

A pair (x, y) of points that can be plotted.

Notes

We do not support three-dimensional or higher-dimensional sets at the moment.

Algorithm

One-dimensional sets are converted to an Interval.

For two-dimensional sets, we first compute a polygonal overapproximation. The second argument, ε, corresponds to the error in Hausdorff distance between the overapproximating set and X. On the other hand, if you only want to produce a fast box-overapproximation of X, pass ε=Inf.

Finally, we use the plot recipe for the constructed set (interval or polygon).

plot3d(S::LazySet; [backend]=default_polyhedra_backend(S), [alpha]=1.0,
       [color]=:blue, [colormap]=:viridis, [colorrange]=nothing,
       [interpolate]=false, [overdraw]=false, [shading]=true,
       [transparency]=true, [visible]=true)

Plot a three-dimensional set using Makie.

Input

• S – set
• backend – (optional, default: default_polyhedra_backend(S)) backend for polyhedral computations
• alpha – (optional, default: 1.0) float in [0,1]; the alpha or transparency value
• color – (optional, default: :blue) Symbol or Colorant; the color of the main plot element (markers, lines, etc.), which can be a color symbol/string like :red
• colormap – (optional, default: :viridis) the color map of the main plot; use available_gradients() to see which gradients are available, which can also be used as [:red, :black]
• colorrange – (optional, default: nothing, which falls back to Makie.Automatic()) a tuple (min, max) where min and max specify the data range to be used for indexing the colormap
• interpolate – (optional, default: false) a boolean for heatmap and images; toggles color interpolation between nearby pixels
• overdraw – (optional, default: false)
• shading – (optional, default: true) a boolean that toggles shading (for meshes)
• transparency – (optional, default: true) if true, the set is transparent, otherwise it is displayed as a solid object
• visible – (optional, default: true) a boolean that toggles visibility of the plot

For a complete list of attributes and usage see Makie's documentation.

Notes

This plot recipe works by computing the list of constraints of S and converting to a polytope in H-representation. Then, this polytope is transformed with Polyhedra.Mesh and plotted using the mesh function.

If the function constraints_list is not applicable to your set S, try overapproximation first; e.g. via

julia> Sapprox = overapproximate(S, SphericalDirections(10))

julia> using Polyhedra, GLMakie

julia> plot3d(Sapprox)

The number 10 above corresponds to the number of directions considered; for better resolution use higher values (but it will take longer).

For efficiency consider using the CDDLib backend, as in

julia> using CDDLib

julia> plot3d(Sapprox, backend=CDDLib.Library())

Examples

The functionality requires both Polyhedra and a Makie backend. After loading LazySets, do using Polyhedra, GLMakie (or another Makie backend).

julia> using LazySets, Polyhedra, GLMakie

julia> plot3d(10 * rand(Hyperrectangle, dim=3))

julia> plot3d!(10 * rand(Hyperrectangle, dim=3), color=:red)

plot3d!(S::LazySet; backend=default_polyhedra_backend(S), [alpha]=1.0,
       [color]=:blue, [colormap]=:viridis, [colorrange]=nothing,
       [interpolate]=false, [overdraw]=false, [shading]=true,
       [transparency]=true, [visible]=true)

Plot a three-dimensional set using Makie.

Input

See plot3d for the description of the inputs. For a complete list of attributes and usage see Makie's documentation.

Notes

See the documentation of plot3d for examples.

CompactSet

An alias for compact set types.

Notes

Most lazy operations are not captured by this alias because whether their result is compact depends on the argument(s).

NonCompactSet

An alias for non-compact set types.

Notes

Most lazy operations are not captured by this alias because whether their result is non-compact depends on the argument(s).