General sets (LazySet)
Every set type in this library is a subtype of the abstract type LazySet
.
LazySets.LazySet
— TypeLazySet{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 ofX
While not strictly required, it is useful to implement the following function:
σ(d::AbstractVector, X::LazySet)
– the support vector ofX
in a given directiond
Implementing the function
ρ(d::AbstractVector, X::LazySet)
– the support function ofX
in a given directiond
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
This interface requires to implement the following function:
LazySets.API.dim
— Methoddim(X::LazySet)
Compute the ambient dimension of a set.
Input
X
– set
Output
The ambient dimension of the set.
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
– directionX
– set
Output
A support vector of X
in direction d
.
Notes
A convenience alias support_vector
is also available.
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
A convenience alias support_function
is also available.
We have the following identity based on the support vector $σ$:
\[ ρ(d, X) = d ⋅ σ(d, X)\]
LazySets.API.ρ
— MethodExtended help
ρ(d::AbstractVector, X::LazySet)
Algorithm
The default implementation computes a support vector via σ
.
Globally defined set functions and default implementations
LazySets.○
— Method○(c, a)
Convenience constructor of Ellipsoid
s or Ball2
s depending on the type of a
.
Input
c
– centera
– additional parameter (either a shape matrix forEllipsoid
or a radius forBall2
)
Output
A Ellipsoid
s or Ball2
s depending on the type of a
.
Notes
"○
" can be typed by \bigcirc<tab>
.
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.an_element
— MethodExtended help
an_element(X::LazySet)
Algorithm
The default implementation computes a support vector along direction $[1, 0, …, 0]$. This may fail for unbounded sets.
LazySets.API.area
— Methodarea(X::LazySet)
Compute the area of a two-dimensional set.
Input
X
– two-dimensional set
Output
A number representing the area of X
.
LazySets.API.area
— MethodExtended 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.
LazySets.chebyshev_center_radius
— Methodchebyshev_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 setbackend
– (optional; default:default_polyhedra_backend(P)
) the backend for polyhedral computationssolver
– (optional; default:default_lp_solver_polyhedra(N; presolve=true)
) the LP solver passed toPolyhedra
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
.
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.complement
— MethodExtended help
complement(X::LazySet)
Algorithm
The default implementation assumes that X
is polyhedral and returns a UnionSetArray
of HalfSpace
s, 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.
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.concretize
— MethodExtended 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.
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.constraints
— MethodExtended help
constraints(X::LazySet)
Algorithm
The default implementation computes all constraints via constraints_list
.
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.convex_hull
— MethodExtended 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.
copy(::Type{LazySet})
MiniQhull.delaunay
— Methoddelaunay(X::LazySet)
Compute the Delaunay triangulation of the given polytopic set.
Input
X
– polytopic setcompute_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.
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 with the same center.
LazySets.API.diameter
— FunctionExtended help
diameter(X::LazySet, [p]::Real=Inf)
Algorithm
The default implementation applies the function radius
and doubles the result.
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
— MethodExtended 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.
Base.eltype
— Methodeltype(X::LazySet)
Determine the numeric type of a set.
Input
X
– set
Output
The numeric type of X
.
Base.eltype
— MethodExtended 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.
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
.
Base.extrema
— MethodExtended help
extrema(X::LazySet)
Algorithm
The default implementation computes the extrema via low
and high
.
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
— MethodExtended help
extrema(X::LazySet, i::Int)
Algorithm
The default implementation computes the extrema via low
and high
.
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.high
— MethodExtended help
high(X::LazySet)
Algorithm
The default implementation applies high
in each dimension.
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.isbounded
— MethodExtended 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.
LazySets._isbounded_unit_dimensions
— Method_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.
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.isboundedtype
— MethodExtended 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.
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.
LazySets.API.isconvextype
— MethodExtended 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
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$
Base.isempty
— FunctionExtended 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 activateduse_polyhedra_interface
– (optional, default:false
) iftrue
, we use thePolyhedra
interface for the emptiness testsolver
– (optional, default:nothing
) LP-solver backend; usesdefault_lp_solver
if not providedbackend
– (optional, default:nothing
) backend for polyhedral computations inPolyhedra
; usesdefault_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.
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.isoperation
— MethodExtended 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
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.ispolyhedral
— MethodExtended help
ispolyhedral(::LazySet)
Algorithm
The default implementation returns false
. All set types that can determine the polyhedral property should override this behavior.
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
.
LazySets.API.low
— MethodExtended help
low(X::LazySet)
Algorithm
The default implementation applies low
in each dimension.
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.
LinearAlgebra.norm
— FunctionExtended 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.
Polyhedra.polyhedron
— Methodpolyhedron(P::LazySet; [backend]=default_polyhedra_backend(P))
Compute a set representation from Polyhedra.jl
.
Input
P
– polyhedral setbackend
– (optional, default: calldefault_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.
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 with the same center.
LazySets.API.radius
— FunctionExtended help
radius(X::LazySet, [p]::Real=Inf)
Algorithm
The default implementation handles the case p == Inf
using ballinf_approximation
.
Base.rationalize
— Methodrationalize(::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 rationalsX
– set represented by floating-point componentstol
– (optional, default:eps(N)
) tolerance of the result; each rationalized component will differ by no more thantol
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.
ReachabilityBase.Arrays.rectify
— Methodrectify(X::LazySet)
Compute the rectification of a set.
Input
X
– set
Output
A set representing the rectification of X
.
ReachabilityBase.Arrays.rectify
— FunctionExtended 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.
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.reflect
— MethodExtended 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))
.
LazySets.singleton_list
— Methodsingleton_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 Singleton
s.
Notes
This function relies on vertices_list
, which raises an error if the set is not polytopic (e.g., unbounded).
LazySets.API.surface
— Methodsurface(X::LazySet)
Compute the surface area of a set.
Input
X
– set
Output
A real number representing the surface area of X
.
LazySets.API.surface
— MethodExtended help
surface(X::LazySet)
Algorithm
The default implementation applies area
for two-dimensional sets.
LazySets.triangulate
— Methodtriangulate(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.
LazySets.tohrep
— Methodtohrep(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.
LazySets.tosimplehrep
— Methodtosimplehrep(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)
.
LazySets.tovrep
— Methodtovrep(P::LazySet)
Convert a polytopic set to vertex representation.
Input
P
– polytopic set
Output
A VPolytope
.
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.vertices
— MethodExtended help
vertices(X::LazySet)
Algorithm
The default implementation computes all vertices via vertices_list
.
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$.
LazySets.API.affine_map
— MethodExtended help
affine_map(M, X::LazySet, v::AbstractVector; [kwargs]...)
Algorithm
The default implementation applies the functions linear_map
and translate
.
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$.
LazySets.API.exponential_map
— MethodExtended help
exponential_map(M::AbstractMatrix, X::LazySet)
Algorithm
The default implementation applies the functions exp
and linear_map
.
LazySets.API.is_interior_point
— Methodis_interior_point(v::AbstractVector{<:Real}, X::LazySet; kwargs...) end
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.is_interior_point
— MethodExtended 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
.
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$.
LazySets.API.linear_map
— MethodExtended 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
).
LazySets.API.linear_map
— Methodlinear_map(a::Number, X::LazySet; kwargs...)
Alias for scale(a, X; kwargs...)
.
LazySets.API.project
— Functionproject(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
– setblock
– block structure - a vector with the dimensions of interestnothing
– (default:nothing
) needed for dispatchn
– (optional, default:dim(X)
) ambient dimension of the setX
Output
A set representing the projection of X
to block block
.
Algorithm
We apply the function linear_map
.
LazySets.API.project
— Functionproject(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
– setblock
– block structure - a vector with the dimensions of interestset_type
– target set typen
– (optional, default:dim(X)
) ambient dimension of the setX
Output
A set of type set_type
representing an overapproximation of the projection of X
.
Algorithm
- Project the set
X
withM⋅X
, whereM
is the identity matrix in the block
coordinates and zero otherwise.
- Overapproximate the projected set using
overapproximate
andset_type
.
LazySets.API.project
— Functionproject(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
– setblock
– block structure - a vector with the dimensions of interestset_type_and_precision
– pair(T, ε)
of a target set typeT
and an error boundε
for approximationn
– (optional, default:dim(X)
) ambient dimension of the setX
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
- Project the set
X
withM⋅X
, whereM
is the identity matrix in the block
coordinates and zero otherwise.
- Overapproximate the projected set with the given error bound
ε
.
LazySets.API.project
— Functionproject(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
– setblock
– block structure - a vector with the dimensions of interestε
– error bound for approximationn
– (optional, default:dim(X)
) ambient dimension of the setX
Output
A set representing the epsilon-close approximation of the projection of X
.
Algorithm
- Project the set
X
withM⋅X
, whereM
is the identity matrix in the block
coordinates and zero otherwise.
- Overapproximate the projected set with the given error bound
ε
.
The target set type is chosen automatically.
LazySets.API.scale
— Methodscale(α::Real, X::LazySet)
Compute the scaling of a set.
Input
α
– scalarX
– set
Output
A set representing $α ⋅ X$.
LazySets.API.scale
— MethodExtended help
scale(α::Real, X::LazySet)
Algorithm
The default implementation calls scale!
on a copy of X
.
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
— MethodExtended help
translate(X::LazySet, v::AbstractVector)
Algorithm
The default implementation calls translate!
on a copy of X
.
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.cartesian_product
— Methodcartesian_product(X::LazySet, Y::LazySet; [backend]=nothing,
[algorithm]::String="vrep")
Compute the Cartesian product of two sets.
Input
X
– setY
– setbackend
– (optional, default:nothing
) backend for polyhedral computationalgorithm
– (optional, default: "hrep") the method used to transform the setsX
andY
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"
.
LazySets.API.convex_hull
— Methodconvex_hull(X::LazySet, Y::LazySet; [algorithm]=nothing,
[backend]=nothing, [solver]=nothing)
Compute the convex hull of two polytopic sets.
Input
X
– polytopic setY
– polytopic setalgorithm
– (optional, default:nothing
) the convex-hull algorithmbackend
– (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.
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.
The convenience alias isapprox
is also available.
"≈
" can be typed by \approx<tab>
.
Base.:≈
— MethodExtended 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
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.isdisjoint
— FunctionExtended 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.
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.
Base.:==
— MethodExtended 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
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.isequivalent
— MethodExtended 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
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
:
LazySets.API.:⊂
— FunctionExtended 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
:
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.
Base.:⊆
— FunctionExtended 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
.
LazySets.API.minkowski_difference
— Methodminkowski_difference(P::LazySet, Q::LazySet)
Concrete Minkowski difference (geometric difference) of a polytopic set and a compact convex set.
Input
P
– polytopic setQ
– compact convex set that is subtracted fromP
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\}.\]
LazySets.API.minkowski_sum
— Methodminkowski_sum(P::LazySet, Q::LazySet;
[backend]=nothing, [algorithm]=nothing, [prune]=true)
Compute the Minkowski sum of two polyhedral sets.
Input
P
– polyhedral setQ
– polyhedral setbackend
– (optional, default:nothing
) polyhedral computations backendalgorithm
– (optional, default:nothing
) algorithm to eliminate variables; available options arePolyhedra.FourierMotzkin
,Polyhedra.BlockElimination
, andPolyhedra.ProjectGenerators
prune
– (optional, default:true
) iftrue
, 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.
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 Intersection
s) 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_recipe
— Methodplot_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
RecipesBase.apply_recipe
— Methodplot_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 boundNφ
– (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
LazySets.plot_vlist
— Methodplot_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 ε
.
LazySets.plot_recipe
— Methodplot_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).
For three-dimensional sets, we support Makie
:
LazySets.plot3d
— Functionplot3d(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
– setbackend
– (optional, default:default_polyhedra_backend(S)
) backend for polyhedral computationsalpha
– (optional, default:1.0
) float in[0,1]
; the alpha or transparency valuecolor
– (optional, default::blue
)Symbol
orColorant
; 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; useavailable_gradients()
to see which gradients are available, which can also be used as[:red, :black]
colorrange
– (optional, default:nothing
, which falls back toMakie.Automatic()
) a tuple(min, max)
wheremin
andmax
specify the data range to be used for indexing thecolormap
interpolate
– (optional, default:false
) a boolean for heatmap and images; toggles color interpolation between nearby pixelsoverdraw
– (optional, default:false
)shading
– (optional, default:true
) a boolean that toggles shading (for meshes)transparency
– (optional, default:true
) iftrue
, the set is transparent, otherwise it is displayed as a solid objectvisible
– (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)
LazySets.plot3d!
— Functionplot3d!(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.
Aliases for set types
LazySets.CompactSet
— TypeCompactSet
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).
LazySets.NonCompactSet
— TypeNonCompactSet
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).
Implementations
Concrete set representations:
Lazy set operations:
- Affine map (AffineMap)
- Linear map (LinearMap)
- Exponential map (ExponentialMap)
- Exponential projection map (ExponentialProjectionMap)
- Reset map (ResetMap)
- Translation
- Bloating
- Binary Cartesian product (CartesianProduct)
- $n$-ary Cartesian product (CartesianProductArray)
- Binary convex hull (ConvexHull)
- $n$-ary convex hull (ConvexHullArray)
- Binary intersection
- $n$-ary intersection (IntersectionArray)
- Binary Minkowski sum (MinkowskiSum)
- $n$-ary Minkowski sum (MinkowskiSumArray)
- $n$-ary Minkowski sum with cache (CachedMinkowskiSumArray)
- Binary set union (UnionSet)
- $n$-ary set union (UnionSetArray)
- Complement
- Rectification