General sets (LazySet)

Every set type in this library is a subtype of the abstract type LazySet.

LazySets.LazySetType
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
source

This interface requires to implement the following function:

LazySets.API.dimMethod
dim(X::LazySet)

Compute the ambient dimension of a set.

Input

  • X – set

Output

The ambient dimension of the set.

source

Support vector and support function

Most LazySet types (particularly convex ones) define a function σ to compute the support vector. The support function, ρ, can optionally be defined; otherwise, a fallback definition based on σ is used.

LazySets.API.σMethod
σ(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.

source
LazySets.API.ρMethod
ρ(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)\]

source
LazySets.API.ρMethod

Extended help

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

Algorithm

The default implementation computes a support vector via σ.

source

Globally defined set functions and default implementations

LazySets.○Method
○(c, a)

Convenience constructor of Ellipsoids or Ball2s depending on the type of a.

Input

  • c – center
  • a – additional parameter (either a shape matrix for Ellipsoid or a radius for Ball2)

Output

A Ellipsoids or Ball2s depending on the type of a.

Notes

"" can be typed by \bigcirc<tab>.

source
LazySets.API.an_elementMethod
an_element(X::LazySet)

Return some element of a nonempty set.

Input

  • X – set

Output

An element of X unless X is empty.

source
LazySets.API.an_elementMethod

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.

source
LazySets.API.areaMethod
area(X::LazySet)

Compute the area of a two-dimensional set.

Input

  • X – two-dimensional set

Output

A number representing the area of X.

source
LazySets.API.areaMethod

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.

source
LazySets.chebyshev_center_radiusMethod
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.

source
LazySets.API.complementMethod
complement(X::LazySet)

Compute the complement of a set.

Input

  • X – set

Output

A set representing the complement of X.

source
LazySets.API.complementMethod

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.

source
LazySets.API.concretizeMethod
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.

source
LazySets.API.concretizeMethod

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.

source
LazySets.API.constraintsMethod
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.

source
LazySets.API.constraintsMethod

Extended help

constraints(X::LazySet)

Algorithm

The default implementation computes all constraints via constraints_list.

source
LazySets.API.convex_hullMethod
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]\}.\]

source
LazySets.API.convex_hullMethod

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.

source

copy(::Type{LazySet})

MiniQhull.delaunayMethod
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.

source
LazySets.API.diameterFunction
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 with the same center.

source
LazySets.API.diameterFunction

Extended help

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

Algorithm

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

source
Base.eltypeMethod
eltype(T::Type{<:LazySet})

Determine the numeric type of a set type.

Input

  • T – set type

Output

The numeric type of T.

source
Base.eltypeMethod

Extended help

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

Algorithm

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

source

Extended help

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

Algorithm

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

source
Base.eltypeMethod
eltype(X::LazySet)

Determine the numeric type of a set.

Input

  • X – set

Output

The numeric type of X.

source
Base.eltypeMethod

Extended help

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

Algorithm

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

source

Extended help

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

Algorithm

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

source
Base.extremaMethod
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.

source
Base.extremaMethod

Extended help

extrema(X::LazySet)

Algorithm

The default implementation computes the extrema via low and high.

source
Base.extremaMethod
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.

source
Base.extremaMethod

Extended help

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

Algorithm

The default implementation computes the extrema via low and high.

source
LazySets.API.highMethod
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.

source
LazySets.API.highMethod

Extended help

high(X::LazySet)

Algorithm

The default implementation applies high in each dimension.

source
LazySets.API.isboundedMethod

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.

source
LazySets._isbounded_unit_dimensionsMethod
_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.

source
LazySets.API.isboundedtypeMethod

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.

source
LazySets.API.isconvextypeMethod
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.

source
LazySets.API.isconvextypeMethod

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
source
Base.isemptyFunction
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$
source
Base.isemptyFunction

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.

source
LazySets.API.isoperationMethod

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
source
LazySets.API.ispolyhedralMethod
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.

source
LazySets.API.ispolyhedralMethod

Extended help

ispolyhedral(::LazySet)

Algorithm

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

source
LazySets.API.lowMethod
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.

source
LazySets.API.lowMethod

Extended help

low(X::LazySet)

Algorithm

The default implementation applies low in each dimension.

source
LinearAlgebra.normFunction
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.

source
LinearAlgebra.normFunction

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.

source
Polyhedra.polyhedronMethod
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.

source
LazySets.API.radiusFunction
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 with the same center.

source
LazySets.API.radiusFunction

Extended help

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

Algorithm

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

source
Base.rationalizeMethod
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.

source
ReachabilityBase.Arrays.rectifyFunction

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.

source
LazySets.API.reflectMethod
reflect(X::LazySet)

Compute the reflection of a set in the origin.

Input

  • X – set

Output

A set representing the reflection $-X$.

source
LazySets.API.reflectMethod

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

source
LazySets.singleton_listMethod
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).

source
LazySets.API.surfaceMethod
surface(X::LazySet)

Compute the surface area of a set.

Input

  • X – set

Output

A real number representing the surface area of X.

source
LazySets.API.surfaceMethod

Extended help

surface(X::LazySet)

Algorithm

The default implementation applies area for two-dimensional sets.

source
LazySets.triangulateMethod
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.

source
LazySets.tohrepMethod
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.

source
LazySets.tosimplehrepMethod
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).

source
LazySets.tovrepMethod
tovrep(P::LazySet)

Convert a polytopic set to vertex representation.

Input

  • P – polytopic set

Output

A VPolytope.

source
LazySets.API.verticesMethod
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.

source
LazySets.API.verticesMethod

Extended help

vertices(X::LazySet)

Algorithm

The default implementation computes all vertices via vertices_list.

source
LazySets.API.affine_mapMethod
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$.

source
LazySets.API.affine_mapMethod

Extended help

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

Algorithm

The default implementation applies the functions linear_map and translate.

source
LazySets.API.exponential_mapMethod
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$.

source
LazySets.API.exponential_mapMethod

Extended help

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

Algorithm

The default implementation applies the functions exp and linear_map.

source
LazySets.API.is_interior_pointMethod
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 ε.

source
LazySets.API.is_interior_pointMethod

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.

source
LazySets.API.linear_mapMethod
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$.

source
LazySets.API.projectFunction
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.

source
LazySets.API.projectFunction
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.
source
LazySets.API.projectFunction
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 ε.
source
LazySets.API.projectFunction
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.

source
LazySets.API.scaleMethod
scale(α::Real, X::LazySet)

Compute the scaling of a set.

Input

  • α – scalar
  • X – set

Output

A set representing $α ⋅ X$.

source
LazySets.API.scaleMethod

Extended help

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

Algorithm

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

source
LazySets.API.translateMethod
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\}$.

source
LazySets.API.translateMethod

Extended help

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

Algorithm

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

source
LazySets.API.cartesian_productMethod
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\}.\]

source
LazySets.API.cartesian_productMethod
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".

source
LazySets.API.convex_hullMethod
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.

source
Base.:≈Method
≈(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>.

source
Base.:≈Method

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
source
Base.isdisjointMethod
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.

source
Base.isdisjointFunction

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.

source
Base.:==Method
==(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.

source
Base.:==Method

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
source
LazySets.API.isequivalentMethod
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).

source
LazySets.API.isequivalentMethod

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
source
LazySets.API.:⊂Method
⊂(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:

source
LazySets.API.:⊂Function

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:

source
Base.:⊆Method
⊆(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.

source
Base.:⊆Function

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.

source
LazySets.API.minkowski_differenceMethod
minkowski_difference(P::LazySet, Q::LazySet)

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

Input

  • P – polytopic set
  • Q – compact convex 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, …, N\}.\]

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

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

source
LazySets.API.minkowski_sumMethod
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.

source

Undocumented implementations:

Plotting

Plotting via the Plots package is available for one- or two-dimensional sets. The default algorithm is to plot an outer approximation using the support function (1D) respectively the support vector (2D). This means that (1) plotting will fail if these functionalities are not available (e.g., for lazy Intersections) and (2) that plots of non-convex sets can be misleading. The implementation below internally relies on the function plot_recipe. For some set types (e.g., Intersection), the default implementation is overridden.

RecipesBase.apply_recipeMethod
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
source
RecipesBase.apply_recipeMethod
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
  • – (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
source
LazySets.plot_vlistMethod
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 ε.

source
LazySets.plot_recipeMethod
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).

source

For three-dimensional sets, we support Makie:

LazySets.plot3dFunction
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)
source
LazySets.plot3d!Function
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.

source

Aliases for set types

LazySets.CompactSetType
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).

source
LazySets.NonCompactSetType
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).

source

Implementations

Concrete set representations:

Lazy set operations: