LazySets.API
— ModuleAPI
This module contains an API (application programming interface) for set libraries. The module only defines and documents the general functions and does not provide implementations.
Set interface
LazySets.API.LazySet
— TypeLazySet
Abstract type for a set of points.
This type is not exported and is only used to define interface methods without type piracy.
The LazySets
library defines its own set interface, which is also called LazySet
.
Unary set functions
LazySets.API.an_element
— Methodan_element(X::LazySet)
Return some element of a nonempty set.
Input
X
– set
Output
An element of X
unless X
is empty.
LazySets.API.area
— Methodarea(X::LazySet)
Compute the area of a two-dimensional set, respectively the surface area of a three-dimensional set.
Input
X
– two- or three-dimensional set
Output
A number representing the (surface) area of X
.
LazySets.API.center
— Methodcenter(X::LazySet, i::Int)
Compute the center of a centrally symmetric set in a given dimension.
Input
X
– centrally symmetric seti
– dimension
Output
A real number representing the center of the set in the given dimension.
LazySets.API.center
— Methodcenter(X::LazySet)
Compute the center of a centrally symmetric set.
Input
X
– centrally symmetric set
Output
A vector with the center, or midpoint, of X
.
LazySets.API.complement
— Methodcomplement(X::LazySet)
Compute the complement of a set.
Input
X
– set
Output
A set representing the complement of X
.
LazySets.API.concretize
— Methodconcretize(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.
LazySets.API.constraints_list
— Methodconstraints_list(X::LazySet)
Compute a list of linear constraints of a polyhedral set.
Input
X
– polyhedral set
Output
A list of the linear constraints of X
.
LazySets.API.constraints
— Methodconstraints(X::LazySet)
Construct an iterator over the constraints of a polyhedral set.
Input
X
– polyhedral set
Output
An iterator over the constraints of X
.
LazySets.API.convex_hull
— Methodconvex_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]\}.\]
LazySets.API.diameter
— Functiondiameter(X::LazySet, [p]::Real=Inf)
Return the diameter of a set.
Input
X
– setp
– (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.
LazySets.API.dim
— Methoddim(X::LazySet)
Compute the ambient dimension of a set.
Input
X
– set
Output
The ambient dimension of the set.
Base.eltype
— Methodeltype(T::Type{<:LazySet})
Determine the numeric type of a set type.
Input
T
– set type
Output
The numeric type of T
.
Base.eltype
— Methodeltype(X::LazySet)
Determine the numeric type of a set.
Input
X
– set
Output
The numeric type of X
.
Base.extrema
— Methodextrema(X::LazySet, i::Int)
Compute the lowest and highest coordinate of a set in a given dimension.
Input
X
– seti
– 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.
Base.extrema
— Methodextrema(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
.
LazySets.API.high
— Methodhigh(X::LazySet, i::Int)
Compute the highest coordinate of a set in a given dimension.
Input
X
– seti
– dimension
Output
A real number representing the highest coordinate of the set in the given dimension.
Notes
The resulting value is the upper end of the projection.
LazySets.API.high
— Methodhigh(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
.
LazySets.API.isbounded
— Methodisbounded(X::LazySet)
Check whether a set is bounded.
Input
X
– set
Output
true
iff the set is bounded.
Notes
See also isboundedtype(::Type{<:LazySet})
.
LazySets.API.isboundedtype
— Methodisboundedtype(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)
.
LazySets.API.isconvextype
— Methodisconvextype(T::Type{<:LazySet})
Check whether T
is convex just by using type information.
Input
T
– subtype ofLazySet
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.
Base.isempty
— Functionisempty(X::LazySet, witness::Bool=false)
Check whether a set is empty.
Input
X
– setwitness
– (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$
LazySets.API.isoperation
— Methodisoperation(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})
.
LazySets.API.isoperationtype
— Methodisoperationtype(T::Type{<:LazySet})
Check whether a set type is a (lazy) set operation.
Input
T
– set type
Output
true
iff the set type represents a set operation.
Notes
See also isoperation(::LazySet)
.
LazySets.API.ispolyhedral
— Methodispolyhedral(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.
LazySets.API.isuniversal
— Functionisuniversal(X::LazySet, witness::Bool=false)
Check whether a set is universal.
Input
X
– setwitness
– (optional, default:false
) compute a witness if activated
Output
- If the
witness
option is deactivated:true
iff $X = ℝ^n$ - If the
witness
option is activated:(true, [])
iff $X = ℝ^n$(false, v)
iff $X ≠ ℝ^n$ for some $v ∉ X$
LazySets.API.low
— Methodlow(X::LazySet, i::Int)
Compute the lowest coordinate of a set in a given dimension.
Input
X
– seti
– dimension
Output
A real number representing the lowest coordinate of the set in the given dimension.
Notes
The resulting value is the lower end of the projection.
LazySets.API.low
— Methodlow(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
.
LinearAlgebra.norm
— Functionnorm(X::LazySet, [p]::Real=Inf)
Return the norm of a set.
Input
X
– setp
– (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.
LazySets.API.radius
— Functionradius(X::LazySet, [p]::Real=Inf)
Return the radius of a set.
Input
X
– setp
– (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.
Base.rand
— Methodrand(T::Type{<:LazySet}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
[rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing
)
Create a random set of the given set type.
Input
T
– set typeN
– (optional, default:Float64
) numeric typedim
– (optional, default: 2) dimensionrng
– (optional, default:GLOBAL_RNG
) random number generatorseed
– (optional, default:nothing
) seed for reseeding
Output
A random set of the given set type.
ReachabilityBase.Arrays.rectify
— Methodrectify(X::LazySet)
Compute the rectification of a set.
Input
X
– set
Output
A set representing the rectification of X
.
LazySets.API.reflect
— Methodreflect(X::LazySet)
Compute the reflection of a set in the origin.
Input
X
– set
Output
A set representing the reflection $-X$.
LazySets.API.vertices_list
— Methodvertices_list(X::LazySet)
Compute a list of vertices of a polytopic set.
Input
X
– polytopic set
Output
A list of the vertices of X
.
LazySets.API.vertices
— Methodvertices(X::LazySet)
Construct an iterator over the vertices of a polytopic set.
Input
X
– polytopic set
Output
An iterator over the vertices of X
.
LazySets.API.volume
— Methodvolume(X::LazySet)
Compute the volume, or Lebesgue measure, of a set.
Input
X
– set
Output
A real number representing the Lebesgue measure of X
.
Notes
The Lebesgue measure has the following common special cases:
- In 1D, it coincides with the length.
- In 2D, it coincides with the area (see also
area
). - In 3D, it coincides with the volume.
In higher dimensions, it is also known as the hypervolume or simply volume.
Mixed set functions
LazySets.API.affine_map
— Methodaffine_map(M::AbstractMatrix, X::LazySet, v::AbstractVector)
Compute the affine map $M · X + v$.
Input
M
– matrixX
– setv
– translation vector
Output
A set representing the affine map $M · X + v$.
ReachabilityBase.Arrays.distance
— Methoddistance(x::AbstractVector, X::LazySet; [p]::Real=2)
distance(X::LazySet, x::AbstractVector; [p]::Real=2)
Compute the standard distance (induced by the $p$-norm) between a point and a set.
Input
x
– point/vectorX
– setp
– (optional; default:2
) value of the $p$-norm
Output
A real number representing the distance between x
and X
.
Notes
The standard distance is zero if the point lies inside the set, and infinite if the set is empty. Otherwise, it is the $p$-norm of the shortest line segment between the point and any other point in the set. Formally,
\[ \inf_{y ∈ X} \{ d(x, y) \}.\]
LazySets.API.exponential_map
— Methodexponential_map(M::AbstractMatrix, X::LazySet)
Compute the exponential map of M
and X
, i.e., $eᴹ ⋅ X$.
Input
M
– matrixX
– set
Output
A set representing the exponential map $eᴹ ⋅ X$.
Base.:∈
— Method∈(x::AbstractVector, X::LazySet)
Check whether a point lies in a set.
Input
x
– point/vectorX
– set
Output
true
iff $x ∈ X$.
LazySets.API.is_interior_point
— Methodis_interior_point(v::AbstractVector, X::LazySet; [p]::Real=Inf, [ε]::Real=_rtol(eltype(X)))
Check whether a point is contained in the interior of a set.
Input
v
– point/vectorX
– setp
– (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 ε
.
LazySets.API.linear_map
— Methodlinear_map(M::AbstractMatrix, X::LazySet)
Compute the linear map $M · X$.
Input
M
– matrixX
– set
Output
A set representing the linear map $M · X$.
SparseArrays.permute
— Methodpermute(X::LazySet, p::AbstractVector{Int})
Permute the dimensions of a set according to a given permutation vector.
Input
X
– setp
– permutation vector
Output
A new set corresponding to X
where the dimensions have been permuted according to p
.
LazySets.API.project
— Methodproject(X::LazySet, block::AbstractVector{Int})
Project a set to a given block by using a concrete linear map.
Input
X
– setblock
– block structure - a vector with the dimensions of interest
Output
A set representing the projection of X
to block block
.
LazySets.API.sample
— Functionsample(X::LazySet, [m]::Int=1;
[rng]::AbstractRNG=GLOBAL_RNG,
[seed]::Union{Int,Nothing}=nothing)
Compute random samples from a set.
Input
X
– setm
– (optional; default: 1) number of random samplesrng
– (optional, default:GLOBAL_RNG
) random number generatorseed
– (optional, default:nothing
) seed for reseeding
Output
A vector of m
elements in X
if X
is nonempty, and an error otherwise.
LazySets.API.scale
— Methodscale(α::Real, X::LazySet)
Compute the scaling of a set.
Input
α
– scalarX
– set
Output
A set representing $α ⋅ X$.
LazySets.API.scale!
— Methodscale!(α::Real, X::LazySet)
Scale a set by modifying it.
Input
α
– scalarX
– set
Output
The scaled set representing $α ⋅ X$.
LazySets.API.ρ
— Methodρ(d::AbstractVector, X::LazySet)
Evaluate the support function of a set in a given direction.
Input
d
– directionX
– set
Output
The evaluation of the support function of X
in direction d
.
Notes
The convenience alias support_function
is also available.
We have the following identity based on the support vector $σ$:
\[ ρ(d, X) = d ⋅ σ(d, X)\]
LazySets.API.σ
— Methodσ(d::AbstractVector, X::LazySet)
Compute a support vector of a set in a given direction.
Input
d
– directionX
– set
Output
A support vector of X
in direction d
.
Notes
The convenience alias support_vector
is also available.
LazySets.API.translate
— Methodtranslate(X::LazySet, v::AbstractVector)
Compute the translation of a set with a vector.
Input
X
– setv
– vector
Output
A set representing $X + \{v\}$.
LazySets.API.translate!
— Methodtranslate!(X::LazySet, v::AbstractVector)
Translate a set with a vector by modifying it.
Input
X
– setv
– vector
Output
The translated set representing $X + \{v\}$.
Binary set functions
LazySets.API.cartesian_product
— Methodcartesian_product(X::LazySet, Y::LazySet)
Compute the Cartesian product of two sets.
Input
X
– setY
– 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\}.\]
LazySets.API.convex_hull
— Methodconvex_hull(X::LazySet, Y::LazySet)
Compute the convex hull of (the union of) two sets.
Input
X
– setY
– set
Output
A set representing the convex hull of $X ∪ Y$.
Notes
See convex_hull(::LazySet)
for the convex hull of a single set.
LazySets.API.difference
— Methoddifference(X::LazySet, Y::LazySet)
Compute the set difference of two sets.
Input
X
– setY
– set
Output
A set representing the difference $X ∖ Y$.
Notes
The set difference is defined as:
\[ X ∖ Y = \{x \mid x ∈ X \text{ and } x ∉ Y \}\]
ReachabilityBase.Arrays.distance
— Methoddistance(X::LazySet, Y::LazySet; [p]::Real=2)
Compute the standard distance (induced by the $p$-norm) between two sets.
Input
X
– setY
– setp
– (optional; default:2
) value of the $p$-norm
Output
A real number representing the distance between X
and Y
.
Notes
The standard distance is zero if the sets intersect, and infinite if one of the sets is empty. Otherwise, it is the $p$-norm of the shortest line segment between any pair of points. Formally,
\[ \inf_{x ∈ X, y ∈ Y} \{ d(x, y) \}.\]
LazySets.API.exact_sum
— Methodexact_sum(X::LazySet, Y::LazySet)
Compute the exact sum of two parametric sets.
Input
X
– parametric setY
– parametric set
Output
A set representing the exact sum, sometimes written $X ⊞ Y$.
Notes
For parametric sets, the exact sum behaves like the Minkowski sum, except that the parameters are shared. Thus, for nonparametric sets, it coincides with the Minkowski sum.
LazySets.API.intersection
— Methodintersection(X::LazySet, Y::LazySet)
Compute the intersection of two sets.
Input
X
– setY
– set
Output
A set representing the intersection $X ∩ Y$.
Notes
The intersection of two sets $X$ and $Y$ is defined as
\[ X ∩ Y = \{x \mid x ∈ X \text{ and } x ∈ Y\}.\]
Base.:≈
— Method≈(X::LazySet, Y::LazySet)
Check whether two sets of the same type are approximately equal.
Input
X
– setY
– set of the same base type asX
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. Note that, unlike most other binary operations, a query with X
and Y
of different dimension is allowed (and results in the answer false
).
"≈
" can be typed by \approx<tab>
. The convenience alias isapprox
is also available.
Base.isdisjoint
— Methodisdisjoint(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
– setY
– setwitness
– (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.
Base.:==
— Method==(X::LazySet, Y::LazySet)
Check whether two sets use exactly the same set representation.
Input
X
– setY
– 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. Note that, unlike most other binary operations, a query with X
and Y
of different dimension is allowed (and results in the answer false
).
LazySets.API.isequivalent
— Methodisequivalent(X::LazySet, Y::LazySet)
Check whether two sets are equivalent, i.e., represent the same set of points.
Input
X
– setY
– set
Output
true
iff X
is equivalent to Y
(up to numerical precision).
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
– setY
– setwitness
– (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
:
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
– setY
– setwitness
– (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.
LazySets.API.linear_combination
— Methodlinear_combination(X::LazySet, Y::LazySet)
Compute the linear combination of two sets.
Input
X
– setY
– set
Output
A set representing the linear combination of X
and Y
.
Notes
The linear combination of two sets $X$ and $Y$ is defined as
\[ \left\{\frac{1}{2}(1+λ)x + \frac{1}{2}(1-λ)y \mid x ∈ X, y ∈ Y, λ ∈ [-1, 1]\right\}.\]
If $X$ and $Y$ are convex, their linear combination is identical with the convex hull of their union $X ∪ Y$.
LazySets.API.minkowski_difference
— Methodminkowski_difference(X::LazySet, Y::LazySet)
Compute the Minkowski difference of two sets.
Input
X
– setY
– set
Output
A set representing the Minkowski difference $X ⊖ Y$.
Notes
The Minkowski difference of two sets $X$ and $Y$ is defined as
\[ X ⊖ Y = \{z \mid \{z\} ⊕ Y ⊆ X\}\]
The convenience alias pontryagin_difference
is also available.
There is some inconsistency in the literature regarding the naming conventions. In this library, both Minkowski difference and Pontryagin difference refer to the geometric difference of two sets.
LazySets.API.minkowski_sum
— Methodminkowski_sum(X::LazySet, Y::LazySet)
Compute the Minkowski sum of two sets.
Input
X
– setY
– set
Output
A set representing the Minkowski sum $X ⊕ Y$.
Notes
The Minkowski sum of two sets $X$ and $Y$ is defined as
\[ X ⊕ Y = \{x + y \mid x ∈ X, y ∈ Y\}.\]