LazySets.API — Module

API

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 — Type

LazySet

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.

source

Unary set functions

LazySets.API.an_element — Method

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.area — Method

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.center — Method

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

Compute the center of a centrally symmetric set in a given dimension.

Input

X – centrally symmetric set
i – dimension

Output

A real number representing the center of the set in the given dimension.

source

LazySets.API.center — Method

center(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.

source

LazySets.API.complement — Method

complement(X::LazySet)

Compute the complement of a set.

Input

X – set

Output

A set representing the complement of X.

source

LazySets.API.concretize — Method

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.constraints_list — Method

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

source

LazySets.API.constraints — Method

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.convex_hull — Method

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.diameter — Function

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.dim — Method

dim(X::LazySet)

Compute the ambient dimension of a set.

Input

X – set

Output

The ambient dimension of the set.

source

Base.eltype — Method

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

Determine the numeric type of a set type.

Input

T – set type

Output

The numeric type of T.

source

Base.eltype — Method

eltype(X::LazySet)

Determine the numeric type of a set.

Input

X – set

Output

The numeric type of X.

source

Base.extrema — Method

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.extrema — Method

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

Mixed set functions

LazySets.API.affine_map — Method

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.exponential_map — Method

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

Base.:∈ — Method

∈(x::AbstractVector, X::LazySet)

Check whether a point lies in a set.

Input

x – point/vector
X – set

Output

true iff $x ∈ X$.

source

LazySets.API.is_interior_point — Method

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.linear_map — Method

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

SparseArrays.permute — Method

permute(X::LazySet, p::AbstractVector{Int})

Permute the dimensions of a set according to a given permutation vector.

Input

X – set
p – permutation vector

Output

A new set corresponding to X where the dimensions have been permuted according to p.

source

LazySets.API.project — Method

project(X::LazySet, block::AbstractVector{Int})

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

Output

A set representing the projection of X to block block.

source

LazySets.API.sample — Function

sample(X::LazySet, [m]::Int=1;
       [rng]::AbstractRNG=GLOBAL_RNG,
       [seed]::Union{Int,Nothing}=nothing)

Compute random samples from a set.

Input

X – set
m – (optional; default: 1) number of random samples
rng – (optional, default: GLOBAL_RNG) random number generator
seed – (optional, default: nothing) seed for reseeding

Output

A vector of m elements in X if X is nonempty, and an error otherwise.

source

LazySets.API.scale — Method

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

Compute the scaling of a set.

Input

α – scalar
X – set

Output

A set representing $α ⋅ X$.

source

LazySets.API.scale! — Method

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

Scale a set by modifying it.

Input

α – scalar
X – set

Output

The scaled set representing $α ⋅ X$.

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.support_function — Function

Extended help

ρ(d::AbstractVector, B::Ball1)

Algorithm

Let $c$ and $r$ be the center and radius of the ball $B$ in the 1-norm, respectively. Then:

\[ρ(d, B) = ⟨d, c⟩ + r ‖d‖_∞.\]

source

ρ(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

Extended help

ρ(d::AbstractVector, B::Ball2)

Algorithm

Let $c$ and $r$ be the center and radius of the ball $B$ in the 2-norm, respectively. Then:

\[ρ(d, B) = ⟨d, c⟩ + r ‖d‖_2.\]

source

Extended help

ρ(d::AbstractVector, B::BallInf)

Algorithm

Let $B$ be a ball in the infinity norm with center $c$ and radius $r$ and let $d$ be the direction of interest. For balls with dimensions less than $30$, we use the implementation for AbstractHyperrectangle, tailored to a BallInf, which computes

\[ ∑_{i=1}^n d_i (c_i + \textrm{sgn}(d_i) · r)\]

where $\textrm{sgn}(α) = 1$ if $α ≥ 0$ and $\textrm{sgn}(α) = -1$ if $α < 0$.

For balls of higher dimension, we instead exploit that for a support vector $v = σ(d, B) = c + \textrm{sgn}(d) · (r, …, r)ᵀ$ we have

\[ ρ(d, B) = ⟨d, v⟩ = ⟨d, c⟩ + ⟨d, \textrm{sgn}(d) · (r, …, r)ᵀ⟩ = ⟨d, c⟩ + r · ∑_{i=1}^n |d_i|\]

where $⟨·, ·⟩$ denotes the dot product.

source

Extended help

ρ(d::AbstractVector, U::Universe)

Algorithm

If the direction is all zero, the result is zero. Otherwise, the result is Inf.

source

ρ(d::AbstractVector, P::SparsePolynomialZonotope; [enclosure_method]=nothing)

Bound the support function of $P$ in the direction $d$.

Input

d – direction
P – sparse polynomial zonotope
enclosure_method – (optional; default: nothing) method to use for enclosure; an AbstractEnclosureAlgorithm from the Rangeenclosures.jl package

Output

An overapproximation of the support function in the given direction.

Algorithm

This method implements Proposition 3.1.16 in [1].

[1] Kochdumper, Niklas. Extensions of polynomial zonotopes and their application to verification of cyber-physical systems. PhD diss., Technische Universität München, 2022.

source

Extended help

ρ(d::AbstractVector, hs::HalfSpace)

Output

Unless the direction is (a multiple of) the normal direction of the half-space, the result is Inf.

source

Extended help

ρ(d::AbstractVector, E::Ellipsoid)

Algorithm

The support value is $cᵀ d + ‖Bᵀ d‖₂$, where $c$ is the center and $Q = B Bᵀ$ is the shape matrix of E.

source

Extended help

ρ(d::AbstractVector, H::Hyperplane)

Output

If the set is unbounded in the given direction, the result is Inf.

source

Algorithm

The default implementation computes a support vector via σ.

source

ρ(d::AbstractVector, Z::AbstractZonotope)

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

Input

d – direction
Z – zonotopic set

Output

The evaluation of the support function in the given direction.

Algorithm

The support value is $cᵀ d + ‖Gᵀ d‖₁$, where $c$ is the center and $G$ is the generator matrix of Z.

source

ρ(d::AbstractVector, H::AbstractHyperrectangle)

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

Input

d – direction
H – hyperrectangular set

Output

The evaluation of the support function in the given direction.

source

ρ(d::AbstractVector, S::AbstractSingleton)

Evaluate the support function of a set with a single value in a given direction.

Input

d – direction
S – set with a single value

Output

The support value in the given direction.

source

ρ(d::AbstractVector, am::AbstractAffineMap)

Evaluate the support function of an affine map.

Input

d – direction
am – affine map

Output

The evaluation of the support function in the given direction.

source

ρ(d::AbstractVector, B::AbstractBallp)

Evaluate the support function of a ball in the p-norm in the given direction.

Input

d – direction
B – ball in the p-norm

Output

Evaluation of the support function in the given direction.

Algorithm

Let $c$ and $r$ be the center and radius of the ball $B$ in the p-norm, respectively, and let $q = \frac{p}{p-1}$. Then:

\[ρ(d, B) = ⟨d, c⟩ + r ‖d‖_q.\]

source

ρ(d::AbstractVector, cup::UnionSet)

Evaluate the support function of the union of two sets in a given direction.

Input

d – direction
cup – union of two sets

Output

The evaluation of the support function in the given direction.

Algorithm

The support function of the union of two sets $X$ and $Y$ evaluates to the maximum of the support-function evaluations of $X$ and $Y$.

source

ρ(d::AbstractVector, B::Bloating)

Return the support function of a bloated set in a given direction.

Input

d – direction
B – bloated set

Output

The support function of the bloated set in the given direction.

source

ρ(d::AbstractVector, cp::CartesianProduct)

Evaluate the support function of a Cartesian product.

Input

d – direction
cp – Cartesian product

Output

The evaluation of the support function in the given direction. If the direction has norm zero, the result depends on the wrapped sets.

source

ρ(d::AbstractVector, cpa::CartesianProductArray)

Evaluate the support function of a Cartesian product of a finite number of sets.

Input

d – direction
cpa – Cartesian product of a finite number of sets

Output

The evaluation of the support function in the given direction. If the direction has norm zero, the result depends on the wrapped sets.

source

ρ(d::AbstractVector, ch::ConvexHull)

Evaluate the support function of the convex hull of two sets in a given direction.

Input

d – direction
ch – convex hull of two sets

Output

The evaluation of the support function of the convex hull in the given direction.

source

ρ(d::AbstractVector, cha::ConvexHullArray)

Evaluate the support function of a convex hull of a finite number of sets in a given direction.

Input

d – direction
cha – convex hull of a finite number of sets

Output

The evaluation of the support function of the convex hull of a finite number of sets in the given direction.

Algorithm

This algorithm calculates the maximum over all $ρ(d, X_i)$, where the $X_1, …, X_k$ are the sets in the array of cha.

source

ρ(d::AbstractVector, em::ExponentialMap;
  [backend]=get_exponential_backend())

Evaluate the support function of the exponential map.

Input

d – direction
em – exponential map
backend – (optional; default: get_exponential_backend()) exponentiation backend

Output

The evaluation of the support function in the given direction.

Notes

If $E = \exp(M)⋅X$, where $M$ is a matrix and $X$ is a set, it follows that $ρ(d, E) = ρ(\exp(M)^T d, X)$ for any direction $d$.

source

ρ(d::AbstractVector, eprojmap::ExponentialProjectionMap;
  [backend]=get_exponential_backend())

Evaluate the support function of a projection of an exponential map.

Input

d – direction
eprojmap – projection of an exponential map
backend – (optional; default: get_exponential_backend()) exponentiation backend

Output

Evaluation of the support function in the given direction. If the direction has norm zero, the result depends on the wrapped set.

Notes

If $S = (L⋅M⋅R)⋅X$, where $L$ and $R$ are matrices, $M$ is a matrix exponential, and $X$ is a set, it follows that $ρ(d, S) = ρ(R^T⋅M^T⋅L^T⋅d, X)$ for any direction $d$.

source

ρ(d::AbstractVector, cap::Intersection)

Return an upper bound on the support function of the intersection of two sets in a given direction.

Input

d – direction
cap – intersection of two sets

Output

An upper bound on the support function in the given direction.

Algorithm

The support function of an intersection of $X$ and $Y$ is upper-bounded by the minimum of the support-function evaluations for $X$ and $Y$.

source

ρ(d::AbstractVector, cap::Intersection{N, S1, S2};
  algorithm::String="line_search", kwargs...
 ) where {N, S1<:LazySet{N},
             S2<:Union{HalfSpace{N}, Hyperplane{N}, Line2D{N}}}

Evaluate the support function of the intersection of a compact set and a half-space/hyperplane/line in a given direction.

Input

d – direction
cap – lazy intersection of a compact set and a half-space/hyperplane/ line
algorithm – (optional, default: "line_search"): the algorithm to calculate the support function; valid options are:
- "line_search" – solve the associated univariate optimization problem using a line-search method (either Brent or the Golden Section method)
- "projection" – only valid for intersection with a hyperplane/line; evaluate the support function by reducing the problem to the 2D intersection of a rank-2 linear transformation of the given compact set in the plane generated by the given direction d and the hyperplane's normal vector n
- "simple" – take the $\min$ of the support-function evaluation of each operand

Output

The scalar value of the support function of the set cap in the given direction.

Notes

It is assumed that the first set of the intersection (cap.X) is compact.

Any additional number of arguments to the algorithm backend can be passed as keyword arguments.

Algorithm

The algorithms are based on solving the associated optimization problem

\[\min_{λ ∈ D_h} ρ(ℓ - λa, X) + λb.\]

where $D_h = \{ λ : λ ≥ 0 \}$ if $H$ is a half-space or $D_h = \{ λ : λ ∈ ℝ \}$ if $H$ is a hyperplane.

For additional information we refer to:

[1] G. Frehse, R. Ray. Flowpipe-Guard Intersection for Reachability Computations with Support Functions. [2] C. Le Guernic. Reachability Analysis of Hybrid Systems with Linear Continuous Dynamics, PhD thesis [3] T. Rockafellar, R. Wets. Variational Analysis.

source

ρ(d::AbstractVector, cap::Intersection{N, S1, S2};
  kwargs...) where {N, S1<:LazySet{N}, S2<:AbstractPolyhedron{N}}

Return an upper bound on the support function of the intersection between a compact set and a polyhedron along a given direction.

Input

d – direction
cap – intersection of a compact set and a polyhedron
kwargs – additional arguments that are passed to the support-function algorithm

Output

An upper bound of the support function of the given intersection.

Algorithm

The idea is to solve the univariate optimization problem ρ(di, X ∩ Hi) for each half-space in the polyhedron and then take the minimum. This gives an overapproximation of the exact support value.

This algorithm is inspired from [1].

[1] G. Frehse, R. Ray. Flowpipe-Guard Intersection for Reachability Computations with Support Functions.

Notes

This method relies on the constraints_list of the polyhedron.

source

ρ(d::AbstractVector, cap::Intersection{N, S1, S2}; kwargs...
 ) where {N, S1<:AbstractPolyhedron{N}, S2<:AbstractPolyhedron{N}}

Evaluate the support function of the intersection between two polyhedral sets.

Input

d – direction
cap – intersection of two polyhedral sets
kwargs – additional arguments that are passed to the support-function algorithm

Output

The evaluation of the support function in the given direction.

Algorithm

We combine the constraints of the two polyhedra to a new HPolyhedron, for which we then evaluate the support function.

source

ρ(d::AbstractVector, lm::LinearMap; kwargs...)

Evaluate the support function of the linear map.

Input

d – direction
lm – linear map
kwargs – additional arguments that are passed to the support function algorithm

Output

The evaluation of the support function in the given direction. If the direction has norm zero, the result depends on the wrapped set.

Notes

If $L = M⋅S$, where $M$ is a matrix and $S$ is a set, it follows that $ρ(d, L) = ρ(M^T d, S)$ for any direction $d$.

source

ρ(d::AbstractVector, ilm::InverseLinearMap)

Evaluate the support function of the inverse linear map.

Input

d – direction
ilm – inverse linear map

Output

The evaluation of the support function in the given direction. If the direction has norm zero, the result depends on the wrapped set.

Notes

If $L = M^{-1}⋅X$, where $M$ is a matrix and $X$ is a set, it follows that $ρ(d, L) = ρ((M^T)^{-1} d, X)$ for any direction $d$.

source

ρ(d::AbstractVector, ms::MinkowskiSum)

Evaluate the support function of a Minkowski sum of two sets.

Input

d – direction
ms – Minkowski sum of two sets

Output

The evaluation of the support function in the given direction.

Algorithm

The support function in direction $d$ of the Minkowski sum of two sets $X$ and $Y$ is the sum of the support functions of $X$ and $Y$ in direction $d$.

source

ρ(d::AbstractVector, msa::MinkowskiSumArray)

Evaluate the support function of a Minkowski sum of a finite number of sets in a given direction.

Input

d – direction
msa – Minkowski sum of a finite number of sets

Output

The evaluation of the support function in the given direction.

Algorithm

The support function of the Minkowski sum of multiple sets evaluations to the sum of the support-function evaluations of each set.

source

ρ(d::AbstractVector, rm::ResetMap)

Evaluate the support function of a reset map.

Input

d – direction
rm – reset map

Output

The evaluation of the support function in the given direction.

Notes

We use the usual dot-product definition, but for unbounded sets we redefine the product between $0$ and $±∞$ as $0$; Julia returns NaN here.

julia> Inf * 0.0
NaN

See the discussion here.

source

ρ(d::AbstractVector, tr::Translation)

Evaluate the support function of a translation.

Input

d – direction
tr – translation of a set

Output

The evaluation of the support function in the given direction.

source

ρ(d::AbstractVector, cup::UnionSetArray)

Evaluate the support function of the union of a finite number of sets in a given direction.

Input

d – direction
cup – union of a finite number of sets

Output

The evaluation of the support function in the given direction.

Algorithm

The support function of the union of a finite number of sets $X₁, X₂, ...$ can be obtained as the maximum of $ρ(d, X₂), ρ(d, X₂), ...$.

source

ρ(d::AbstractVector, R::Rectification)

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

Input

d – direction
R – rectification

Output

The support value of the rectification in the given direction.

Algorithm

We use different procedures for different types of input sets. If the wrapped set has a suitable structure for which we can efficiently compute the support vector, we fall back to the evaluation of the support function by means of the support vector. Otherwise we compute the union of projections to obtain a precise result (see to_union_of_projections), and then compute the support function for this union. (The union is cached internally, so subsequent queries are more efficient.)

source

Extended help

ρ(d::AbstractVector{M}, P::HPoly{N};
  solver=default_lp_solver(M, N)) where {M, N}

Input

solver – (optional, default: default_lp_solver(M, N)) the backend used to solve the linear program

Output

If P is unbounded in the given direction, there are two cases:

If P is an HPolytope, we throw an error.
If P is an HPolyedron, the result is Inf.

source

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.support_vector — Function

Extended help

σ(d::AbstractVector, P::VPolygon)

Output

If the direction has norm zero, the first vertex is returned.

Algorithm

This implementation uses a binary search algorithm when the polygon has more than 10 vertices and a brute-force search when it has 10 or fewer vertices. The brute-force search compares the projection of each vector along the given direction and runs in $O(n)$ where $n$ is the number of vertices. The binary search runs in $O(log n)$ and we follow this implementation based on an algorithm described in [1].

[1] Joseph O'Rourke, Computational Geometry in C (2nd Edition).

source

σ(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

Extended help

σ(d::AbstractVector, B::Ball2)

Notes

Let $c$ and $r$ be the center and radius of a ball $B$ in the 2-norm, respectively. For nonzero direction $d$ we have

\[σ(d, B) = c + r \frac{d}{‖d‖_2}.\]

This function requires computing the 2-norm of the input direction, which is performed in the given precision of the numeric datatype of both the direction and the set. Exact inputs are not supported.

source

Extended help

σ(d::AbstractVector, L::LineSegment)

Algorithm

If the angle between the vector $q - p$ and $d$ is bigger than 90° and less than 270° (measured in counter-clockwise order), the result is $p$, otherwise it is $q$. If the angle is exactly 90° or 270°, or if the direction has norm zero, this implementation returns $q$.

source

Extended help

σ(d::AbstractVector, U::Universe)

Output

A vector with infinity values, except in dimensions where the direction is zero.

source

Extended help

σ(d::AbstractVector, hs::HalfSpace)

Output

The support vector in the given direction, which is only defined in the following two cases:

The direction has norm zero.
The direction is (a multiple of) the normal direction of the half-space.

In both cases the result is any point on the boundary (the defining hyperplane). Otherwise this function throws an error.

source

Extended help

σ(d::AbstractVector, E::Ellipsoid)

Algorithm

Let $E$ be an ellipsoid of center $c$ and shape matrix $Q = BB^\mathrm{T}$. Its support vector along direction $d$ can be deduced from that of the unit Euclidean ball $\mathcal{B}_2$ using the algebraic relations for the support vector,

\[σ_{B\mathcal{B}_2 ⊕ c}(d) = c + Bσ_{\mathcal{B}_2} (B^\mathrm{T} d) = c + \dfrac{Qd}{\sqrt{d^\mathrm{T}Q d}}.\]

source

Extended help

σ(d::AbstractVector, P::VPolytope)

Algorithm

A support vector maximizes the support function. For a polytope, the support function is always maximized in some vertex. Hence it is sufficient to check all vertices.

source

Extended help

σ(d::AbstractVector, H::Hyperplane)

Output

A support vector in the given direction, which is only defined in the following two cases:

The direction has norm zero.
The direction is the hyperplane's normal direction or its opposite direction.

In all cases, any point on the hyperplane is a solution. Otherwise this function throws an error.

source

Extended help

σ(d::AbstractVector, T::Tetrahedron)

Algorithm

This method falls back to the VPolytope implementation.

source

σ(d::AbstractVector, Z::AbstractZonotope)

Return a support vector of a zonotopic set in a given direction.

Input

d – direction
Z – zonotopic set

Output

A support vector in the given direction. If the direction has norm zero, the vertex with $ξ_i = 1 \ \ ∀ i = 1,…, p$ is returned.

source

σ(d::AbstractVector, H::AbstractHyperrectangle)

Return a support vector of a hyperrectangular set in a given direction.

Input

d – direction
H – hyperrectangular set

Output

A support vector in the given direction.

If the direction vector is zero in dimension $i$, the result will have the center's coordinate in that dimension. For instance, for the two-dimensional infinity-norm ball, if the direction points to the right, the result is the vector [1, 0] in the middle of the right-hand facet.

If the direction has norm zero, the result can be any point in H. The default implementation returns the center of H.

source

σ(d::AbstractVector, S::AbstractSingleton)

Return the support vector of a set with a single value.

Input

d – direction
S – set with a single value

Output

The support vector, which is the set's vector itself, irrespective of the given direction.

source

σ(d::AbstractVector, am::AbstractAffineMap)

Return a support vector of an affine map.

Input

d – direction
am – affine map

Output

A support vector in the given direction.

source

σ(d::AbstractVector, B::AbstractBallp)

Return the support vector of a ball in the p-norm in a given direction.

Input

d – direction
B – ball in the p-norm

Output

The support vector in the given direction. If the direction has norm zero, the center of the ball is returned.

Algorithm

The support vector of the unit ball in the $p$-norm along direction $d$ is:

\[σ(d, \mathcal{B}_p^n(0, 1)) = \dfrac{\tilde{v}}{‖\tilde{v}‖_q},\]

where $\tilde{v}_i = \frac{|d_i|^q}{d_i}$ if $d_i ≠ 0$ and $\tilde{v}_i = 0$ otherwise, for all $i=1,…,n$, and $q$ is the conjugate number of $p$. By the affine transformation $x = r\tilde{x} + c$, one obtains that the support vector of $\mathcal{B}_p^n(c, r)$ is

\[σ(d, \mathcal{B}_p^n(c, r)) = \dfrac{v}{‖v‖_q},\]

where $v_i = c_i + r\frac{|d_i|^q}{d_i}$ if $d_i ≠ 0$ and $v_i = 0$ otherwise, for all $i = 1, …, n$.

source

σ(d::AbstractVector, P::HPolygonOpt;
  [linear_search]::Bool=(length(P.constraints) < 10))

Return a support vector of an optimized polygon in a given direction.

Input

d – direction
P – optimized polygon in constraint representation
linear_search – (optional, default: see below) flag for controlling whether to perform a linear search or a binary search

Output

The support vector in the given direction. The result is always one of the vertices; in particular, if the direction has norm zero, any vertex is returned.

Algorithm

Comparison of directions is performed using polar angles; see the definition of ⪯ for two-dimensional vectors.

For polygons with 10 or more constraints we use a binary search by default.

source

σ(d::AbstractVector, cup::UnionSet; [algorithm]="support_vector")

Return a support vector of the union of two sets in a given direction.

Input

d – direction
cup – union of two sets
algorithm – (optional, default: "supportvector"): the algorithm to compute the support vector; if "supportvector", use the support vector of each argument; if "support_function" use the support function of each argument and evaluate the support vector of only one of them

Output

A support vector in the given direction.

Algorithm

The support vector of the union of two sets $X$ and $Y$ can be obtained as the vector that maximizes the support function of either $X$ or $Y$, i.e., it is sufficient to find the $\argmax(ρ(d, X), ρ(d, Y)])$ and evaluate its support vector.

The default implementation, with option algorithm="support_vector", computes the support vector of $X$ and $Y$ and then compares the support function using a dot product.

If the support function can be computed more efficiently, the alternative implementation algorithm="support_function" can be used, which evaluates the support function of each set directly and then calls only the support vector of either $X$ or $Y$.

source

σ(d::AbstractVector, B::Bloating)

Return the support vector of a bloated set in a given direction.

Input

d – direction
B – bloated set

Output

The support vector of the bloated set in the given direction.

source

σ(d::AbstractVector, cp::CartesianProduct)

Return a support vector of a Cartesian product.

Input

d – direction
cp – Cartesian product

Output

A support vector in the given direction. If the direction has norm zero, the result depends on the wrapped sets.

source

σ(d::AbstractVector, cpa::CartesianProductArray)

Compute a support vector of a Cartesian product of a finite number of sets.

Input

d – direction
cpa – Cartesian product of a finite number of sets

Output

A support vector in the given direction. If the direction has norm zero, the result depends on the product sets.

source

σ(d::AbstractVector, ch::ConvexHull)

Return a support vector of the convex hull of two sets in a given direction.

Input

d – direction
ch – convex hull of two sets

Output

A support vector of the convex hull in the given direction.

source

σ(d::AbstractVector, cha::ConvexHullArray)

Return a support vector of a convex hull of a finite number of sets in a given direction.

Input

d – direction
cha – convex hull of a finite number of sets

Output

A support vector in the given direction.

source

σ(d::AbstractVector, em::ExponentialMap;
  [backend]=get_exponential_backend())

Return a support vector of an exponential map.

Input

d – direction
em – exponential map
backend – (optional; default: get_exponential_backend()) exponentiation backend

Output

A support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

Notes

If $E = \exp(M)⋅X$, where $M$ is a matrix and $X$ is a set, it follows that $σ(d, E) = \exp(M)⋅σ(\exp(M)^T d, X)$ for any direction $d$.

source

σ(d::AbstractVector, eprojmap::ExponentialProjectionMap;
  [backend]=get_exponential_backend())

Return a support vector of a projection of an exponential map.

Input

d – direction
eprojmap – projection of an exponential map
backend – (optional; default: get_exponential_backend()) exponentiation backend

Output

A support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

Notes

If $S = (L⋅M⋅R)⋅X$, where $L$ and $R$ are matrices, $M$ is a matrix exponential, and $X$ is a set, it follows that $σ(d, S) = L⋅M⋅R⋅σ(R^T⋅M^T⋅L^T⋅d, X)$ for any direction $d$.

source

σ(d::AbstractVector, cap::Intersection)

Return a support vector of an intersection of two sets in a given direction.

Input

d – direction
cap – intersection of two sets

Output

A support vector in the given direction.

Algorithm

We compute the concrete intersection, which may be expensive.

source

σ(d::AbstractVector, ia::IntersectionArray)

Return a support vector of an intersection of a finite number of sets in a given direction.

Input

d – direction
ia – intersection of a finite number of sets

Output

A support vector in the given direction. If the direction has norm zero, the result depends on the individual sets.

Algorithm

This implementation computes the concrete intersection, which can be expensive.

source

σ(d::AbstractVector, lm::LinearMap)

Return a support vector of the linear map.

Input

d – direction
lm – linear map

Output

A support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

Notes

If $L = M⋅S$, where $M$ is a matrix and $S$ is a set, it follows that $σ(d, L) = M⋅σ(M^T d, S)$ for any direction $d$.

source

σ(d::AbstractVector, ilm::InverseLinearMap)

Return a support vector of a inverse linear map.

Input

d – direction
ilm – inverse linear map

Output

A support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

Notes

If $L = M^{-1}⋅X$, where $M$ is a matrix and $X$ is a set, since (M^T)^{-1}=(M^{-1})^T, it follows that $σ(d, L) = M^{-1}⋅σ((M^T)^{-1} d, X)$ for any direction $d$.

source

σ(d::AbstractVector, ms::MinkowskiSum)

Return a support vector of a Minkowski sum of two sets.

Input

d – direction
ms – Minkowski sum of two sets

Output

A support vector in the given direction. If the direction has norm zero, the result depends on the summand sets.

Algorithm

A valid support vector in direction $d$ of the Minkowski sum of two sets $X$ and $Y$ is the sum of the support vectors of $X$ and $Y$ in direction $d$.

source

σ(d::AbstractVector, msa::MinkowskiSumArray)

Return a support vector of a Minkowski sum of a finite number of sets in a given direction.

Input

d – direction
msa – Minkowski sum of a finite number of sets

Output

A support vector in the given direction. If the direction has norm zero, the result depends on the summand sets.

source

σ(d::AbstractVector, cms::CachedMinkowskiSumArray)

Return a support vector of a cached Minkowski sum in a given direction.

Input

d – direction
cms – cached Minkowski sum

Output

A support vector in the given direction. If the direction has norm zero, the result depends on the summand sets.

Notes

The result is cached, i.e., any further query with the same direction runs in constant time. When sets are added to the cached Minkowski sum, the query is only performed for the new sets.

source

σ(d::AbstractVector, rm::ResetMap)

Return a support vector of a reset map.

Input

d – direction
rm – reset map

Output

A support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

source

σ(d::AbstractVector, sih::SymmetricIntervalHull)

Return a support vector of the symmetric interval hull of a set in a given direction.

Input

d – direction
sih – symmetric interval hull of a set

Output

A support vector of the symmetric interval hull of a set in the given direction. If the direction has norm zero, the origin is returned.

Algorithm

For each non-zero entry in d we need to either look up the bound (if it has been computed before) or compute it, in which case we store it for future queries.

source

σ(d::AbstractVector, tr::Translation)

Return a support vector of a translation.

Input

d – direction
tr – translation of a set

Output

A support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

source

σ(d::AbstractVector, cup::UnionSetArray; [algorithm]="support_vector")

Return a support vector of the union of a finite number of sets in a given direction.

Input

d – direction
cup – union of a finite number of sets
algorithm – (optional, default: "supportvector"): the algorithm to compute the support vector; if "supportvector", use the support vector of each argument; if "support_function", use the support function of each argument and evaluate the support vector of only one of them

Output

A support vector in the given direction.

Algorithm

The support vector of the union of a finite number of sets $X₁, X₂, ...$ can be obtained as the vector that maximizes the support function, i.e., it is sufficient to find the $\argmax([ρ(d, X₂), ρ(d, X₂), ...])$ and evaluate its support vector.

The default implementation, with option algorithm="support_vector", computes the support vector of all $X₁, X₂, ...$ and then compares the support function using the dot product.

source

σ(d::AbstractVector, R::Rectification)

Return a support vector of a rectification.

Input

d – direction
R – rectification

Output

A support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

source

σ(d::AbstractVector,
  R::Rectification{N, <:AbstractHyperrectangle{N}}) where {N}

Return a support vector of the rectification of a hyperrectangular set.

Input

d – direction
R – rectification of a hyperrectangular set

Output

A support vector in the given direction.

Algorithm

Let $R(·)$ be the rectification of a vector respectively a set, and let $H$ be a hyperrectangle. Then $σ_{R(H)}(d) = R(σ_{H}(d))$.

source

σ(d::AbstractVector, R::Rectification{N, <:CartesianProduct{N}}) where {N}

Return a support vector of the rectification of a Cartesian product of two sets.

Input

d – direction
R – rectification of a Cartesian product of two sets

Output

A support vector in the given direction.

Notes

Note that this implementation creates new Rectification objects that do not get preserved. Hence a second support-vector query does not benefit from the computations in the first query. For this use case another implementation should be added.

Algorithm

Rectification distributes with the Cartesian product. Let $R(·)$ be the rectification of a set. We can just query a support vector for $R(X)$ and $R(Y)$ recursively: $σ_{R(X × Y)}(d) = σ_{R(X)}(d_X) × σ_{R(Y)}(d_Y)$, where $x × y$ concatenates vectors $x$ and $y$.

source

σ(d::AbstractVector,
  R::Rectification{N, <:CartesianProductArray{N}}) where {N}

Return a support vector of the rectification of a Cartesian product of a finite number of sets.

Input

d – direction
R – rectification of a Cartesian product of a finite number of sets

Output

A support vector in the given direction.

Notes

Algorithm

Rectification distributes with the Cartesian product. Let $R(·)$ be the rectification of a set. We can just query a support vector for each subspace recursively: $σ_{R(X_1 × ⋯ × X_m)}(d) = σ_{R(X_1)}(d_{X_1}) × ⋯ × σ_{R(X_m)}(d_{X_m})$, where $x × y$ concatenates vectors $x$ and $y$.

source

Extended help

σ(d::AbstractVector{M}, P::HPoly{N};
  solver=default_lp_solver(M, N) where {M, N}

Input

solver – (optional, default: default_lp_solver(M, N)) the backend used to solve the linear program

Output

If P is unbounded in the given direction, there are two cases:

If P is an HPolytope, we throw an error.
If P is an HPolyedron, the result contains ±Inf entries.

source

Extended help

σ(d::AbstractVector, P::HPolygon;
  [linear_search]::Bool=(length(P.constraints) < 10))

Input

linear_search – (optional, default: see below) flag for controlling whether to perform a linear search or a binary search

Output

The result is always one of the vertices; in particular, if the direction has norm zero, any vertex is returned.

Algorithm

Comparison of directions is performed using polar angles; see the definition of ⪯ for two-dimensional vectors.

For polygons with 10 or more constraints we use a binary search by default.

source

LazySets.API.translate — Method

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.translate! — Method

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

Translate a set with a vector by modifying it.

Input

X – set
v – vector

Output

The translated set representing $X + \{v\}$.

source

Binary set functions

LazySets.API.cartesian_product — Method

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.difference — Method

difference(X::LazySet, Y::LazySet)

Compute the set difference of two sets.

Input

X – set
Y – 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 \}\]

source

ReachabilityBase.Arrays.distance — Method

distance(X::LazySet, Y::LazySet; [p]::Real=2)

Compute the standard distance (induced by the $p$-norm) between two sets.

Input

X – set
Y – set
p – (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 otherwise the $p$-norm of the shortest line segment between any pair of points. Formally,

\[ \inf_{x ∈ H_1, y ∈ H_2} \{ d(x, y) \}.\]

source

LazySets.API.exact_sum — Method

exact_sum(X::LazySet, Y::LazySet)

Compute the exact sum of two parametric sets.

Input

X – parametric set
Y – 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.

source

LazySets.API.intersection — Method

intersection(X::LazySet, Y::LazySet)

Compute the intersection of two sets.

Input

X – set
Y – 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\}.\]

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.isdisjoint — Method

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

LazySets.API.is_intersection_empty — Function

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

Convenience alias for the isdisjoint function.

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

LazySets.API.isequivalent — Method

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.:⊂ — 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

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

LazySets.API.linear_combination — Method

linear_combination(X::LazySet, Y::LazySet)

Compute the linear combination of two sets.

Input

X – set
Y – 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$.

source

LazySets.API.minkowski_difference — Method

minkowski_difference(X::LazySet, Y::LazySet)

Compute the Minkowski difference of two sets.

Input

X – set
Y – 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.

source

LazySets.API.pontryagin_difference — Function

pontryagin_difference(X::LazySet, Y::LazySet)

Convenience alias for the minkowski_difference function.

source

LazySets.API.minkowski_sum — Method

minkowski_sum(X::LazySet, Y::LazySet)

Compute the Minkowski sum of two sets.

Input

X – set
Y – 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\}.\]

source