Utilities
Macros
LazySets.@neutral
— Macro@neutral(SET, NEUT)
Create methods to make a lazy set operation commutative with a given neutral-element set type.
Input
SET
– set type of lazy operationNEUT
– set type of neutral element
Output
Nothing.
Notes
This macro generates four functions (possibly two more if @absorbing
has been used in advance, and possibly two or four more if @declare_array_version
has been used in advance).
Examples
@neutral(MinkowskiSum, N)
creates at least the following methods:
neutral(::MinkowskiSum) = N
MinkowskiSum(X, N) = X
MinkowskiSum(N, X) = X
MinkowskiSum(N, N) = N
LazySets.@absorbing
— Macro@absorbing(SET, ABS)
Create methods to make a lazy set operation commutative with a given absorbing-element set type.
Input
SET
– set type of lazy operationABS
– set type of absorbing element
Output
Nothing.
Notes
This macro generates four functions (possibly two more if @neutral
has been used in advance, and possibly two or four more if @declare_array_version
has been used in advance).
Examples
@absorbing(MinkowskiSum, A)
creates at least the following methods:
absorbing(::MinkowskiSum) = A
MinkowskiSum(X, A) = A
MinkowskiSum(A, X) = A
MinkowskiSum(A, A) = A
LazySets.@neutral_absorbing
— Macro@neutral_absorbing(SET, NEUT, ABS)
Create two methods to avoid method ambiguities for a lazy set operation with respect to neutral-element and absorbing-element set types.
Input
SET
– set type of lazy operationNEUT
– set type of neutral elementABS
– set type of absorbing element
Output
A quoted expression containing the function definitions.
Notes
This macro is used internally in other macros.
Examples
@neutral_absorbing(MinkowskiSum, N, A)
creates the following methods as quoted expressions:
MinkowskiSum(N, A) = A
MinkowskiSum(A, N) = A
LazySets.@declare_array_version
— Macro@declare_array_version(SET, SETARR)
Create methods to connect a lazy set operation with its array set type.
Input
SET
– set type of lazy operationSETARR
– set type of array version
Output
Nothing.
Notes
This macro generates six functions (and possibly up to eight more if @neutral
/@absorbing
has been used in advance for the base and/or array set type).
Examples
@declare_array_version(MinkowskiSum, MinkowskiSumArray)
creates at least the following methods:
array_constructor(::MinkowskiSum) = MinkowskiSumArray
is_array_constructor(::MinkowskiSumArray) = true
MinkowskiSum!(X, Y)
MinkowskiSum!(X, arr)
MinkowskiSum!(arr, X)
MinkowskiSum!(arr1, arr2)
LazySets.@array_neutral
— Macro@array_neutral(FUN, NEUT, SETARR)
Create two methods to avoid method ambiguities for a lazy set operation with respect to the neutral-element set type and the array set type.
Input
FUN
– function nameNEUT
– set type of neutral elementSETARR
– set type of array version
Output
A quoted expression containing the function definitions.
Examples
@array_neutral(MinkowskiSum, N, ARR)
creates the following methods as quoted expressions:
MinkowskiSum(N, ARR) = ARR
MinkowskiSum(ARR, N) = ARR
LazySets.@array_absorbing
— Macro@array_absorbing(FUN, ABS, SETARR)
Create two methods to avoid method ambiguities for a lazy set operation with respect to the absorbing-element set type and the array set type.
Input
FUN
– function nameABS
– set type of absorbing elementSETARR
– set type of array version
Output
A quoted expression containing the function definitions.
Examples
@array_absorbing(MinkowskiSum, ABS, ARR)
creates the following methods as quoted expressions:
MinkowskiSum(ABS, ARR) = ABS
MinkowskiSum(ARR, ABS) = ABS
Types
LazySets.CachedPair
— TypeCachedPair{N}
A mutable pair of an index and a vector.
Fields
idx
– indexvec
– vector
Inspection of set interfaces
LazySets.implementing_sets
— Functionimplementing_sets(op::Function;
signature::Tuple{Vector{Type}, Int}=(Type[], 1),
type_args=Float64, binary::Bool=false)
Compute a dictionary containing information about availability of (unary or binary) concrete set operations.
Input
op
– set operation (respectively itsFunction
object)signature
– (optional, default:Type[]
) the type signature of the function without theLazySet
type(s) (see also theindex
option and theExamples
section below)index
– (optional, default:1
) index of the set type in the signature in the unary case (see thebinary
option)type_args
– (optional, default:Float64
) type arguments added to theLazySet
(s) when searching for available methods; valid inputs are a type ornothing
, and in the unary case (see thebinary
option) it can also be a list of typesbinary
– (optional, default:false
) flag indicating whetherop
is a binary function (true
) or a unary function (false
)
Output
A dictionary with three keys each mapping to a list:
"available"
– This list contains all set types such that there exists an implementation ofop
."missing"
– This list contains all set types such that there does not exist an implementation ofop
. Note that this is the complement of the"available"
list."specific"
– This list contains all set types such that there exists a type-specific implementation. Note that those set types also occur in the"available"
list.
In the unary case, the lists contain set types. In the binary case, the lists contain pairs of set types.
Examples
tovrep
is only available for polytopic set types in vertex or constraint representation (and HPolyhedron
).
julia> using LazySets: implementing_sets
julia> dict = implementing_sets(tovrep);
julia> dict["available"]
6-element Vector{Type}:
HPolygon
HPolygonOpt
HPolyhedron
HPolytope
VPolygon
VPolytope
Every convex set type implements the function σ
.
julia> dict = implementing_sets(σ; signature=Type[AbstractVector], index=2);
julia> dict["missing"]
6-element Vector{Type}:
Complement
LazySets.AbstractStar
Polygon
QuadraticMap
SimpleSparsePolynomialZonotope
SparsePolynomialZonotope
Some operations are not available for sets with rational numbers.
julia> N = Rational{Int};
julia> dict = implementing_sets(σ; signature=Type[AbstractVector{N}], index=2, type_args=N);
julia> Ball2 ∈ dict["missing"]
true
For binary functions, the dictionary contains pairs of set types. This check takes several seconds because it considers all possible set-type combinations.
julia> dict = LazySets.implementing_sets(convex_hull; binary=true);
julia> (HPolytope, HPolytope) ∈ dict["available"]
true
File formats
LazySets.read_gen
— Methodread_gen(filename::String)
Read a sequence of polygons stored in vertex representation (gen format).
Input
filename
– path of the file containing the polygons
Output
A list of polygons in vertex representation.
Notes
The x
and y
coordinates of each vertex should be separated by an empty space and polygons are separated by empty lines (even the last polygon). For example:
1.01 1.01
0.99 1.01
0.99 0.99
1.01 0.99
0.908463 1.31047
0.873089 1.31047
0.873089 1.28452
0.908463 1.28452
This is parsed as
2-element Array{VPolygon{Float64, Vector{Float64}},1}:
VPolygon{Float64, Vector{Float64}}([[1.01, 1.01], [0.99, 1.01], [0.99, 0.99], [1.01, 0.99]])
VPolygon{Float64, Vector{Float64}}([[0.908463, 1.31047], [0.873089, 1.31047], [0.873089, 1.28452], [0.908463, 1.28452]])
Sampling
LazySets._sample_unit_nsphere_muller!
— Function_sample_unit_nsphere_muller!(D::Vector{Vector{N}}, n::Int, p::Int;
[rng]::AbstractRNG=GLOBAL_RNG,
[seed]::Union{Int, Nothing}=nothing) where {N}
Draw samples from a uniform distribution on an $n$-dimensional unit sphere using Muller's method.
Input
D
– output, vector of pointsn
– dimension of the spherep
– number of random samplesrng
– (optional, default:GLOBAL_RNG
) random number generatorseed
– (optional, default:nothing
) seed for reseeding
Output
The modified vector D
.
Algorithm
This function implements Muller's method of normalized Gaussians [1] to uniformly sample over the $n$-dimensional sphere $S^n$ (which is the bounding surface of the $n$-dimensional unit ball).
Given $n$ canonical Gaussian random variables $Z₁, Z₂, …, Z_n$, the distribution of the vectors
\[\dfrac{1}{α}\left(z₁, z₂, …, z_n\right)^T,\]
where $α := \sqrt{z₁² + z₂² + … + z_n²}$, is uniform over $S^n$.
[1] Muller, Mervin E. A note on a method for generating points uniformly on n-dimensional spheres. Communications of the ACM 2.4 (1959): 19-20.
LazySets._sample_unit_nball_muller!
— Function_sample_unit_nball_muller!(D::Vector{Vector{N}}, n::Int, p::Int;
[rng]::AbstractRNG=GLOBAL_RNG,
[seed]::Union{Int, Nothing}=nothing) where {N}
Draw samples from a uniform distribution on an $n$-dimensional unit ball using Muller's method.
Input
D
– output, vector of pointsn
– dimension of the ballp
– number of random samplesrng
– (optional, default:GLOBAL_RNG
) random number generatorseed
– (optional, default:nothing
) seed for reseeding
Output
The modified vector D
.
Algorithm
This function implements Muller's method of normalized Gaussians [1] to uniformly sample from the interior of the unit ball.
Given $n$ Gaussian random variables $Z₁, Z₂, …, Z_n$ and a uniformly distributed random variable $r$ with support in $[0, 1]$, the distribution of the vectors
\[\dfrac{r^{1/n}}{α} \left(z₁, z₂, …, z_n\right)^T,\]
where $α := \sqrt{z₁² + z₂² + … + z_n²}$, is uniform over the $n$-dimensional unit ball.
[1] Muller, Mervin E. A note on a method for generating points uniformly on n-dimensional spheres. Communications of the ACM 2.4 (1959): 19-20.
LazySets.sample
— Functionsample(B::Ball2{N}, [nsamples]::Int;
[rng]::AbstractRNG=GLOBAL_RNG,
[seed]::Union{Int, Nothing}=nothing) where {N}
Return samples from a uniform distribution on the given ball in the 2-norm.
Input
B
– ball in the 2-normnsamples
– number of random samplesrng
– (optional, default:GLOBAL_RNG
) random number generatorseed
– (optional, default:nothing
) seed for reseeding
Output
A linear array of nsamples
elements drawn from a uniform distribution in B
.
Algorithm
Random sampling with uniform distribution in B
is computed using Muller's method of normalized Gaussians. This function requires the package Distributions
. See _sample_unit_nball_muller!
for implementation details.
sample(X::LazySet{N}, num_samples::Int;
[sampler]=_default_sampler(X),
[rng]::AbstractRNG=GLOBAL_RNG,
[seed]::Union{Int, Nothing}=nothing,
[include_vertices]=false,
[VN]=Vector{N}) where {N}
Random sampling of an arbitrary set X
.
Input
X
– set to be samplednum_samples
– number of random samplessampler
– (optional, default:_default_sampler(X)
) the sampler used; falls back toCombinedSampler
rng
– (optional, default:GLOBAL_RNG
) random number generatorseed
– (optional, default:nothing
) seed for reseedinginclude_vertices
– (optional, default:false
) option to include the vertices ofX
VN
– (optional, default:Vector{N}
) vector type of the sampled points
Output
A vector of num_samples
vectors. If num_samples
is not passed, the result is just one sample (not wrapped in a vector).
Algorithm
See the documentation of the respective Sampler
.
Notes
If include_vertices == true
, we include all vertices computed with vertices
. Alternatively if a number $k$ is passed, we plot the first $k$ vertices returned by vertices(X)
.
LazySets.AbstractSampler
— TypeAbstractSampler
Abstract type for defining new sampling methods.
Notes
All subtypes should implement a sample!(D, X, ::Method)
method where the first argument is the output (vector of vectors), the second argument is the set to be sampled, and the third argument is the sampler instance.
LazySets.CombinedSampler
— TypeCombinedSampler <: AbstractSampler
Type used for sampling arbitrary sets by trying different sampling strategies.
Algorithm
The algorithm is to first try a RejectionSampler
100 times. If that fails, it tries a RandomWalkSampler
.
LazySets.FaceSampler
— TypeFaceSampler <: AbstractSampler
Type used for sampling from the k
-faces of a set.
Fields
dim
– dimension of the faces to be sampled; a negative number is interpreted asn - dim
wheren
is the dimension of the set
Notes
For a three-dimensional polytope, the following face dimensions exist:
- 3-face – the polytope itself
- 2-faces – 2-dimensional polygonal faces
- 1-faces – 1-dimensional edges
- 0-faces – 0-dimensional vertices
For more information see Wikipedia.
Algorithm
Currently only hyperrectangles are supported. For each point to be sampled, we randomly split the integers 1 .. n
into two subgroups of size k
and n-k
respectively. For the i-th coordinate in the first group, we sample in the interval low(H, i) .. high(H, i)
. For the i-th coordinate in the second group, we randomly pick either low(H, i)
or high(H, i)
.
LazySets.HalfSpaceSampler
— TypeHalfSpaceSampler{D} <: AbstractSampler
Type used for sampling from a half-space.
Fields
distribution
– (optional, default:nothing
) distribution from which samples are drawn
Notes
If distribution
is nothing
(default), the sampling algorithm uses a DefaultUniform
over $[0, 1]^n$.
LazySets.HyperplaneSampler
— TypeHyperplaneSampler{D} <: AbstractSampler
Type used for sampling from a hyperplane.
Fields
distribution
– (optional, default:nothing
) distribution from which samples are drawn
Notes
If distribution
is nothing
(default), the sampling algorithm uses a DefaultUniform
over $[0, 1]^n$.
LazySets.SingletonSampler
— TypeSingletonSampler <: AbstractSampler
Type used for sampling from a singleton.
LazySets.RejectionSampler
— TypeRejectionSampler{D} <: AbstractSampler
Type used for rejection sampling of a bounded set X
.
Fields
distribution
– (optional, default:DefaultUniform
) distribution from which the sample is drawntight
– (optional, default:false
) set totrue
if the support of the distribution is known to coincide with the setX
maxiter
– (optional, default:Inf
) maximum number of iterations before giving up
Algorithm
Draw a sample $x$ from a given distribution of a box-overapproximation of the original set $X$ in all $n$ dimensions. The function rejects a drawn sample $x$ and redraws as long as the sample is not contained in the original set $X$, i.e., while $x ∉ X$.
Notes
The maxiter
parameter is useful when sampling from sets that are small compared to their box approximation, e.g., flat sets, for which the probability of sampling from within the set is close to zero.
LazySets.RandomWalkSampler
— TypeRandomWalkSampler <: AbstractSampler
Type used for sampling from a convex polytope using its vertex representation. This is especially useful if rejection sampling does not work because the polytope is flat.
Fields
variant
– (optional, default:true
) choice of a variant (see below)
Notes
The sampling is not uniform - points in the center of the polytope are more likely to be sampled.
The set to be sampled from must provide its vertices via vertices_list
.
Algorithm
Choose a random convex combination of the vertices of a convex polytope X
.
If variant == false
, we proceed as follows. Let $V = \{v_i\}_i$ denote the set of vertices of X
. Then any point $p \in \mathbb{R}^n$ of the convex polytope $X$ is a convex combination of its vertices, i.e., $p = \sum_{i} v_i α_i$ for some (non-negative) coefficients $\{α_i\}_i$ that add up to 1. The algorithm chooses a random convex combination (the $α_i$). To produce this combination, we apply the finite-difference operator on a sorted uniform sample over $[0, 1]$; the method can be found in [1] and [2].
If variant == true
, we start from a random vertex and then repeatedly walk toward a random vertex inside the polytope.
References
[1] Rubin, Donald B. The Bayesian bootstrap. The annals of statistics (1981): 130-134.
Symbolics
LazySets._vec
— Function_vec(vars)
Transform a tuple of operations into one vector of operations.
Input
vars
– tuple where each element is either variable-like (Num
) or a vector of variables (Vector{Num}
)
Output
A vector of Operation
obtained by concatenating each tuple component.
Examples
julia> using Symbolics
julia> vars = @variables x[1:2] y
2-element Vector{Any}:
x[1:2]
y
julia> LazySets._vec(vars)
3-element Vector{Num}:
x[1]
x[2]
y
Functions for numbers
LazySets.sign_cadlag
— Functionsign_cadlag(x::Real)
This function works like the sign function but is $1$ for input $0$.
Input
x
– real scalar
Output
$1$ if $x ≥ 0$, $-1$ otherwise.
Notes
This is the sign function right-continuous at zero (see càdlàg function). It can be used with vector-valued arguments via the dot operator.
Examples
julia> LazySets.sign_cadlag.([-0.6, 1.3, 0.0])
3-element Vector{Float64}:
-1.0
1.0
1.0
LazySets.minmax
— Functionminmax(a, b, c)
Compute the minimum and maximum of three numbers a, b, c.
Input
a
– numberb
– numberc
– number
Output
The minimum and maximum of three given numbers.
Examples
julia> LazySets.minmax(1.4, 52.4, -5.2)
(-5.2, 52.4)
LazySets.arg_minmax
— Functionarg_minmax(a, b, c)
Compute the indices of the minimum and maximum of three numbers a, b, c.
Input
a
– first numberb
– second numberc
– third number
Output
The indices of the minimum and maximum of the three given numbers.
Examples
julia> LazySets.arg_minmax(1.4, 52.4, -5.2)
(3, 2)
Other functions
LazySets._an_element_helper_hyperplane
— Function_an_element_helper_hyperplane(a::AbstractVector{N}, b,
[nonzero_entry_a]::Int) where {N}
Helper function that computes an element on a hyperplane $a⋅x = b$.
Input
a
– normal directionb
– constraintnonzero_entry_a
– (optional, default: computes the first index) indexi
such thata[i]
is different from 0
Output
An element on a hyperplane.
Algorithm
We compute the point on the hyperplane as follows:
- We already found a nonzero entry of $a$ in dimension, say, $i$.
- We set $x[i] = b / a[i]$.
- We set $x[j] = 0$ for all $j ≠ i$.
LazySets.binary_search_constraints
— Functionbinary_search_constraints(d::AbstractVector{N},
constraints::Vector{<:HalfSpace{N}};
[start_index]::Int=div(length(constraints)+1, 2),
[choose_lower]::Bool=false) where {N}
Perform a binary search in the constraints.
Input
d
– directionconstraints
– constraintsstart_index
– (optional, default:div(length(constraints)+1, 2)
) start indexchoose_lower
– (optional, default:false
) flag for choosing the lower index (see the 'Output' section)
Output
In the default setting, the result is the smallest index k
such that d <= constraints[k].a
, or length(constraints)+1
if no such k
exists. If the choose_lower
flag is set, the result is the largest index k
such that constraints[k].a < d
, which is equivalent to being k-1
in the normal setting.
LazySets.get_constrained_lowdimset
— Functionget_constrained_lowdimset(cpa::CartesianProductArray{N, S},
P::AbstractPolyhedron{N}) where {N, S}
Preprocessing step for the intersection between a Cartesian product of a finite number of sets and a polyhedron.
Input
cpa
– Cartesian product of a finite number of setsP
– polyhedron
Output
A four-tuple of:
- a low-dimensional
CartesianProductArray
in the constrained dimensions of the original setcpa
- the variables in the constrained blocks,
- the original block structure of the low-dimensional sets,
- the list of the constrained blocks.
LazySets.get_radius!
— Functionget_radius!(sih::SymmetricIntervalHull{N}, i::Int) where {N}
Compute the radius of the symmetric interval hull of a set in a given dimension.
Input
sih
– symmetric interval hull of a seti
– dimension in which the radius should be computed
Output
The radius of the symmetric interval hull of a set in a given dimension.
Algorithm
We ask for the extrema
of the underlying set in dimension i
.
LazySets.is_tighter_same_dir_2D
— Functionis_tighter_same_dir_2D(c1::HalfSpace,
c2::HalfSpace;
[strict]::Bool=false)
Check if the first of two two-dimensional constraints with equivalent normal direction is tighter.
Input
c1
– first linear constraintc2
– second linear constraintstrict
– (optional; default:false
) check for strictly tighter constraints?
Output
true
iff the first constraint is tighter.
LazySets._leq_trig
— Function_leq_trig(u::AbstractVector{N}, v::AbstractVector{N}) where {N<:AbstractFloat}
Compare two 2D vectors by their direction.
Input
u
– first 2D directionv
– second 2D direction
Output
true
iff $\arg(u) [2π] ≤ \arg(v) [2π]$.
Notes
The argument is measured in counter-clockwise fashion, with the 0 being the direction (1, 0).
Algorithm
The implementation uses the arctangent function with sign, atan
, which for two arguments implements the atan2
function.
LazySets.same_block_structure
— Functionsame_block_structure(x::AbstractVector{S1}, y::AbstractVector{S2}
) where {S1<:LazySet, S2<:LazySet}
Check whether two vectors of sets have the same block structure, i.e., the $i$-th entry in the vectors have the same dimension.
Input
x
– first vectory
– second vector
Output
true
iff the vectors have the same block structure.
LazySets._σ_hyperplane_halfspace
— Function _σ_hyperplane_halfspace(d::AbstractVector, a, b;
[error_unbounded]::Bool=true,
[halfspace]::Bool=false)
Return a support vector of a hyperplane $a⋅x = b$ in direction d
.
Input
d
– directiona
– normal directionb
– constrainterror_unbounded
– (optional, default:true
)true
if an error should be thrown whenever the set is unbounded in the given directionhalfspace
– (optional, default:false
)true
if the support vector should be computed for a half-space
Output
A pair (v, f)
where v
is a vector and f
is a Boolean flag.
The flag f
is false
in one of the following cases:
- The direction has norm zero.
- The direction is (a multiple of) the hyperplane's normal direction.
- The direction is (a multiple of) the opposite of the hyperplane's normal
direction and halfspace
is false
. In all these cases, v
is any point on the hyperplane.
Otherwise, the flag f
is true
, the set is unbounded in the given direction, and v
is any vector.
If error_unbounded
is true
and the set is unbounded in the given direction, this function throws an error instead of returning.
Notes
For correctness, consider the weak duality of LPs: If the primal is unbounded, then the dual is infeasible. Since there is only a single constraint, the feasible set of the dual problem is $a ⋅ y == d$, $y ≥ 0$ (with objective function $b ⋅ y$). It is easy to see that this problem is infeasible whenever $a$ is not parallel to $d$.