Minkowski sum
Binary Minkowski sum (MinkowskiSum)
LazySets.MinkowskiSum
— Type.MinkowskiSum{N<:Real, S1<:LazySet{N}, S2<:LazySet{N}} <: LazySet{N}
Type that represents the Minkowski sum of two convex sets.
Fields
X
– first convex setY
– second convex set
Notes
The ZeroSet
is the neutral element and the EmptySet
is the absorbing element for MinkowskiSum
.
LazySets.:⊕
— Method.⊕(X::LazySet, Y::LazySet)
Unicode alias constructor ⊕ (oplus
) for the lazy Minkowski sum operator.
Base.:+
— Method.X + Y
Convenience constructor for Minkowski sum.
Input
X
– a convex setY
– another convex set
Output
The symbolic Minkowski sum of $X$ and $Y$.
LazySets.swap
— Method.swap(ms::MinkowskiSum)
Return a new MinkowskiSum
object with the arguments swapped.
Input
ms
– Minkowski sum of two convex sets
Output
A new MinkowskiSum
object with the arguments swapped.
LazySets.dim
— Method.dim(ms::MinkowskiSum)
Return the dimension of a Minkowski sum.
Input
ms
– Minkowski sum
Output
The ambient dimension of the Minkowski sum.
LazySets.ρ
— Method.ρ(d::AbstractVector{N}, ms::MinkowskiSum{N}) where {N<:Real}
Return the support function of a Minkowski sum.
Input
d
– directionms
– Minkowski sum
Output
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$.
LazySets.σ
— Method.σ(d::AbstractVector{N}, ms::MinkowskiSum{N}) where {N<:Real}
Return the support vector of a Minkowski sum.
Input
d
– directionms
– Minkowski sum
Output
The support vector in the given direction. If the direction has norm zero, the result depends on the summand sets.
Algorithm
The 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$.
LazySets.isbounded
— Method.isbounded(ms::MinkowskiSum)
Determine whether a Minkowski sum is bounded.
Input
ms
– Minkowski sum
Output
true
iff both wrapped sets are bounded.
Base.isempty
— Method.isempty(ms::MinkowskiSum)
Return if a Minkowski sum is empty or not.
Input
ms
– Minkowski sum
Output
true
iff any of the wrapped sets are empty.
LazySets.constraints_list
— Method.constraints_list(ms::MinkowskiSum)
Return the list of constraints of a lazy Minkowski sum of two polyhedral sets.
Input
ms
– Minkowski sum of two polyhedral sets
Output
The list of constraints of the Minkowski sum.
Algorithm
We compute a concrete set representation via minkowski_sum
and call constraints_list
on the result.
Base.:∈
— Method.∈(x::AbstractVector{N}, ms::MinkowskiSum{N, <:AbstractSingleton, <:LazySet}) where {N}
Check whether a given point is contained in the Minkowski sum of a singleton and a set.
Input
x
– pointms
– lazy Minkowski sum of a singleton and a set
Output
true
iff $x ∈ ms$.
Algorithm
Note that $x ∈ (S ⊕ P)$, where $S$ is a singleton set, $S = \{s\}$ and $P$ is a set, if and only if $(x-s) ∈ P$.
Inherited from LazySet
:
$n$-ary Minkowski sum (MinkowskiSumArray)
LazySets.MinkowskiSumArray
— Type.MinkowskiSumArray{N<:Real, S<:LazySet{N}} <: LazySet{N}
Type that represents the Minkowski sum of a finite number of convex sets.
Fields
array
– array of convex sets
Notes
This type assumes that the dimensions of all elements match.
The ZeroSet
is the neutral element and the EmptySet
is the absorbing element for MinkowskiSumArray
.
Constructors:
MinkowskiSumArray(array::Vector{<:LazySet})
– default constructorMinkowskiSumArray([n]::Int=0, [N]::Type=Float64)
– constructor for an empty sum with optional size hint and numeric type
LazySets.dim
— Method.dim(msa::MinkowskiSumArray)
Return the dimension of a Minkowski sum of a finite number of sets.
Input
msa
– Minkowski sum array
Output
The ambient dimension of the Minkowski sum of a finite number of sets.
LazySets.ρ
— Method.ρ(d::AbstractVector{N}, msa::MinkowskiSumArray{N}) where {N<:Real}
Return the support function of a Minkowski sum array of a finite number of sets in a given direction.
Input
d
– directionmsa
– Minkowski sum array
Output
The support function in the given direction.
Algorithm
The support function of the Minkowski sum of sets is the sum of the support functions of each set.
LazySets.σ
— Method.σ(d::AbstractVector{N}, msa::MinkowskiSumArray{N}) where {N<:Real}
Return the support vector of a Minkowski sum of a finite number of sets in a given direction.
Input
d
– directionmsa
– Minkowski sum array
Output
The support vector in the given direction. If the direction has norm zero, the result depends on the summand sets.
LazySets.isbounded
— Method.isbounded(msa::MinkowskiSumArray)
Determine whether a Minkowski sum of a finite number of convex sets is bounded.
Input
msa
– Minkowski sum of a finite number of convex sets
Output
true
iff all wrapped sets are bounded.
Base.isempty
— Method.isempty(msa::MinkowskiSumArray)
Return if a Minkowski sum array is empty or not.
Input
msa
– Minkowski sum array
Output
true
iff any of the wrapped sets are empty.
LazySets.array
— Method.array(cpa::CartesianProductArray{N, S}) where {N<:Real, S<:LazySet{N}}
Return the array of a Cartesian product of a finite number of convex sets.
Input
cpa
– Cartesian product array
Output
The array of a Cartesian product of a finite number of convex sets.
array(cha::ConvexHullArray{N, S}) where {N<:Real, S<:LazySet{N}}
Return the array of a convex hull of a finite number of convex sets.
Input
cha
– convex hull array
Output
The array of a convex hull of a finite number of convex sets.
array(ia::IntersectionArray{N, S}) where {N<:Real, S<:LazySet{N}}
Return the array of an intersection of a finite number of convex sets.
Input
ia
– intersection of a finite number of convex sets
Output
The array of an intersection of a finite number of convex sets.
array(msa::MinkowskiSumArray{N, S}) where {N<:Real, S<:LazySet{N}}
Return the array of a Minkowski sum of a finite number of convex sets.
Input
msa
– Minkowski sum array
Output
The array of a Minkowski sum of a finite number of convex sets.
array(cms::CachedMinkowskiSumArray{N, S}) where {N<:Real, S<:LazySet{N}}
Return the array of a caching Minkowski sum.
Input
cms
– caching Minkowski sum
Output
The array of a caching Minkowski sum.
array(cup::UnionSetArray{N, S}) where {N<:Real, S<:LazySet{N}}
Return the array of a union of a finite number of convex sets.
Input
cup
– union of a finite number of convex sets
Output
The array that holds the union of a finite number of convex sets.
Inherited from LazySet
:
$n$-ary Minkowski sum with cache (CachedMinkowskiSumArray)
LazySets.CachedMinkowskiSumArray
— Type.CachedMinkowskiSumArray{N<:Real, S<:LazySet{N}} <: LazySet{N}
Type that represents the Minkowski sum of a finite number of convex sets. Support vector queries are cached.
Fields
array
– array of convex setscache
– cache of support vector query results
Notes
This type assumes that the dimensions of all elements match.
The ZeroSet
is the neutral element and the EmptySet
is the absorbing element for CachedMinkowskiSumArray
.
The cache (field cache
) is implemented as dictionary whose keys are directions and whose values are pairs (k, s)
where k
is the number of elements in the array array
when the support vector was evaluated last time, and s
is the support vector that was obtained. Thus this type assumes that array
is not modified except by adding new sets at the end.
Constructors:
CachedMinkowskiSumArray(array::Vector{<:LazySet})
– default constructorCachedMinkowskiSumArray([n]::Int=0, [N]::Type=Float64)
– constructor for an empty sum with optional size hint and numeric type
LazySets.dim
— Method.dim(cms::CachedMinkowskiSumArray)
Return the dimension of a caching Minkowski sum.
Input
cms
– caching Minkowski sum
Output
The ambient dimension of the caching Minkowski sum.
LazySets.σ
— Method.σ(d::AbstractVector{N}, cms::CachedMinkowskiSumArray{N}) where {N<:Real}
Return the support vector of a caching Minkowski sum in a given direction.
Input
d
– directioncms
– caching Minkowski sum
Output
The 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 caching Minkowski sum, the query is only performed for the new sets.
LazySets.isbounded
— Method.isbounded(cms::CachedMinkowskiSumArray)
Determine whether a caching Minkowski sum is bounded.
Input
cms
– caching Minkowski sum
Output
true
iff all wrapped sets are bounded.
Base.isempty
— Method.isempty(cms::CachedMinkowskiSumArray)
Return if a caching Minkowski sum array is empty or not.
Input
cms
– caching Minkowski sum
Output
true
iff any of the wrapped sets are empty.
Notes
Forgotten sets cannot be checked anymore. Usually they have been empty because otherwise the support vector query should have crashed before. In that case, the caching Minkowski sum should not be used further.
LazySets.array
— Method.array(cpa::CartesianProductArray{N, S}) where {N<:Real, S<:LazySet{N}}
Return the array of a Cartesian product of a finite number of convex sets.
Input
cpa
– Cartesian product array
Output
The array of a Cartesian product of a finite number of convex sets.
array(cha::ConvexHullArray{N, S}) where {N<:Real, S<:LazySet{N}}
Return the array of a convex hull of a finite number of convex sets.
Input
cha
– convex hull array
Output
The array of a convex hull of a finite number of convex sets.
array(ia::IntersectionArray{N, S}) where {N<:Real, S<:LazySet{N}}
Return the array of an intersection of a finite number of convex sets.
Input
ia
– intersection of a finite number of convex sets
Output
The array of an intersection of a finite number of convex sets.
array(msa::MinkowskiSumArray{N, S}) where {N<:Real, S<:LazySet{N}}
Return the array of a Minkowski sum of a finite number of convex sets.
Input
msa
– Minkowski sum array
Output
The array of a Minkowski sum of a finite number of convex sets.
array(cms::CachedMinkowskiSumArray{N, S}) where {N<:Real, S<:LazySet{N}}
Return the array of a caching Minkowski sum.
Input
cms
– caching Minkowski sum
Output
The array of a caching Minkowski sum.
array(cup::UnionSetArray{N, S}) where {N<:Real, S<:LazySet{N}}
Return the array of a union of a finite number of convex sets.
Input
cup
– union of a finite number of convex sets
Output
The array that holds the union of a finite number of convex sets.
LazySets.forget_sets!
— Method.forget_sets!(cms::CachedMinkowskiSumArray)
Tell a caching Minkowski sum to forget the stored sets (but not the support vectors). Only those sets are forgotten such that for each cached direction the support vector has been computed before.
Input
cms
– caching Minkowski sum
Output
The number of sets that have been forgotten.
Notes
This function should only be used under the assertion that no new directions are queried in the future; otherwise such support vector results will be incorrect.
This implementation is optimistic and first tries to remove all sets. However, it also checks that for all cached directions the support vector has been computed before. If it finds that this is not the case, the implementation identifies the biggest index $k$ such that the above holds for the $k$ oldest sets, and then it only removes these. See the example below.
Examples
julia> x1 = BallInf(ones(3), 3.); x2 = Ball1(ones(3), 5.);
julia> cms1 = CachedMinkowskiSumArray(2); cms2 = CachedMinkowskiSumArray(2);
julia> d = ones(3);
julia> a1 = array(cms1); a2 = array(cms2);
julia> push!(a1, x1); push!(a2, x1);
julia> σ(d, cms1); σ(d, cms2);
julia> push!(a1, x2); push!(a2, x2);
julia> σ(d, cms1);
julia> idx1 = forget_sets!(cms1) # support vector was computed for both sets
2
julia> idx1 = forget_sets!(cms2) # support vector was only computed for first set
1
Inherited from LazySet
: