Common Set Representations
This section of the manual describes the basic set representation types.
Balls
Euclidean norm ball
LazySets.Ball2
— Type.Ball2{N<:AbstractFloat} <: AbstractPointSymmetric{N}
Type that represents a ball in the 2-norm.
Fields
center
– center of the ball as a real vectorradius
– radius of the ball as a real scalar ($≥ 0$)
Notes
Mathematically, a ball in the 2-norm is defined as the set
where $c ∈ \mathbb{R}^n$ is its center and $r ∈ \mathbb{R}_+$ its radius. Here $‖ ⋅ ‖_2$ denotes the Euclidean norm (also known as 2-norm), defined as $‖ x ‖_2 = \left( \sum\limits_{i=1}^n |x_i|^2 \right)^{1/2}$ for any $x ∈ \mathbb{R}^n$.
Examples
Create a five-dimensional ball B
in the 2-norm centered at the origin with radius 0.5:
julia> B = Ball2(zeros(5), 0.5)
LazySets.Ball2{Float64}([0.0, 0.0, 0.0, 0.0, 0.0], 0.5)
julia> dim(B)
5
Evaluate B
's support vector in the direction $[1,2,3,4,5]$:
julia> σ([1.,2.,3.,4.,5.], B)
5-element Array{Float64,1}:
0.06742
0.13484
0.20226
0.26968
0.3371
LazySets.dim
— Method.dim(S::AbstractPointSymmetric)::Int
Return the ambient dimension of a point symmetric set.
Input
S
– set
Output
The ambient dimension of the set.
LazySets.σ
— Method.σ(d::V, B::Ball2{N}) where {N<:AbstractFloat, V<:AbstractVector{N}}
Return the support vector of a 2-norm ball in a given direction.
Input
d
– directionB
– ball in the 2-norm
Output
The support vector in the given direction. If the direction has norm zero, the origin is returned.
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
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.
Base.:∈
— Method.∈(x::AbstractVector{N}, B::Ball2{N})::Bool where {N<:AbstractFloat}
Check whether a given point is contained in a ball in the 2-norm.
Input
x
– point/vectorB
– ball in the 2-norm
Output
true
iff $x ∈ B$.
Notes
This implementation is worst-case optimized, i.e., it is optimistic and first computes (see below) the whole sum before comparing to the radius. In applications where the point is typically far away from the ball, a fail-fast implementation with interleaved comparisons could be more efficient.
Algorithm
Let $B$ be an $n$-dimensional ball in the 2-norm with radius $r$ and let $c_i$ and $x_i$ be the ball's center and the vector $x$ in dimension $i$, respectively. Then $x ∈ B$ iff $\left( ∑_{i=1}^n |c_i - x_i|^2 \right)^{1/2} ≤ r$.
Examples
julia> B = Ball2([1., 1.], sqrt(0.5))
LazySets.Ball2{Float64}([1.0, 1.0], 0.7071067811865476)
julia> ∈([.5, 1.6], B)
false
julia> ∈([.5, 1.5], B)
true
LazySets.an_element
— Method.an_element(S::LazySet{N}) where {N<:Real}
Return some element of a convex set.
Input
S
– convex set
Output
An element of a convex set.
an_element(S::AbstractPointSymmetric{N})::Vector{N} where {N<:Real}
Return some element of a point symmetric set.
Input
S
– point symmetric set
Output
The center of the point symmetric set.
LazySets.center
— Method.center(B::Ball2{N})::Vector{N} where {N<:AbstractFloat}
Return the center of a ball in the 2-norm.
Input
B
– ball in the 2-norm
Output
The center of the ball in the 2-norm.
Infinity norm ball
LazySets.BallInf
— Type.BallInf{N<:Real} <: AbstractHyperrectangle{N}
Type that represents a ball in the infinity norm.
Fields
center
– center of the ball as a real vectorradius
– radius of the ball as a real scalar ($≥ 0$)
Notes
Mathematically, a ball in the infinity norm is defined as the set
where $c ∈ \mathbb{R}^n$ is its center and $r ∈ \mathbb{R}_+$ its radius. Here $‖ ⋅ ‖_∞$ denotes the infinity norm, defined as $‖ x ‖_∞ = \max\limits_{i=1,…,n} \vert x_i \vert$ for any $x ∈ \mathbb{R}^n$.
Examples
Create the two-dimensional unit ball and compute its support function along the positive $x=y$ direction:
julia> B = BallInf(zeros(2), 1.0)
LazySets.BallInf{Float64}([0.0, 0.0], 1.0)
julia> dim(B)
2
julia> ρ([1., 1.], B)
2.0
LazySets.dim
— Method.dim(P::AbstractPointSymmetricPolytope)::Int
Return the ambient dimension of a point symmetric set.
Input
P
– set
Output
The ambient dimension of the set.
LazySets.σ
— Method.σ(d::V, H::AbstractHyperrectangle{N}) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of a hyperrectangular set in a given direction.
Input
d
– directionH
– hyperrectangular set
Output
The support vector in the given direction. If the direction has norm zero, the vertex with biggest values is returned.
Base.:∈
— Method.∈(x::AbstractVector{N}, H::AbstractHyperrectangle{N})::Bool where {N<:Real}
Check whether a given point is contained in a hyperrectangular set.
Input
x
– point/vectorH
– hyperrectangular set
Output
true
iff $x ∈ H$.
Algorithm
Let $H$ be an $n$-dimensional hyperrectangular set, $c_i$ and $r_i$ be the box's center and radius and $x_i$ be the vector $x$ in dimension $i$, respectively. Then $x ∈ H$ iff $|c_i - x_i| ≤ r_i$ for all $i=1,…,n$.
LazySets.an_element
— Method.an_element(S::LazySet{N}) where {N<:Real}
Return some element of a convex set.
Input
S
– convex set
Output
An element of a convex set.
an_element(P::AbstractPointSymmetricPolytope{N})::Vector{N} where {N<:Real}
Return some element of a point symmetric polytope.
Input
P
– point symmetric polytope
Output
The center of the point symmetric polytope.
Base.LinAlg.norm
— Method.norm(S::LazySet, [p]::Real=Inf)
Return the norm of a convex set. It is the norm of the enclosing ball (of the given $p$-norm) of minimal volume that is centered in the origin.
Input
S
– convex setp
– (optional, default:Inf
) norm
Output
A real number representing the norm.
norm(H::AbstractHyperrectangle, [p]::Real=Inf)::Real
Return the norm of a hyperrectangular set.
Input
H
– hyperrectangular setp
– (optional, default:Inf
) norm
Output
A real number representing the norm.
Notes
The norm of a hyperrectangular set is defined as the norm of the enclosing ball, of the given $p$-norm, of minimal volume that is centered in the origin.
LazySets.radius
— Method.radius(S::LazySet, [p]::Real=Inf)
Return the radius of a convex set. It is the radius of the enclosing ball (of the given $p$-norm) of minimal volume with the same center.
Input
S
– convex setp
– (optional, default:Inf
) norm
Output
A real number representing the radius.
radius(H::AbstractHyperrectangle, [p]::Real=Inf)::Real
Return the radius of a hyperrectangular set.
Input
H
– hyperrectangular setp
– (optional, default:Inf
) norm
Output
A real number representing the radius.
Notes
The radius is defined as the radius of the enclosing ball of the given $p$-norm of minimal volume with the same center. It is the same for all corners of a hyperrectangular set.
radius(B::BallInf, [p]::Real=Inf)::Real
Return the radius of a ball in the infinity norm.
Input
B
– ball in the infinity normp
– (optional, default:Inf
) norm
Output
A real number representing the radius.
Notes
The radius is defined as the radius of the enclosing ball of the given $p$-norm of minimal volume with the same center.
LazySets.diameter
— Method.diameter(S::LazySet, [p]::Real=Inf)
Return the diameter of a convex set. It 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.
Input
S
– convex setp
– (optional, default:Inf
) norm
Output
A real number representing the diameter.
diameter(H::AbstractHyperrectangle, [p]::Real=Inf)::Real
Return the diameter of a hyperrectangular set.
Input
H
– hyperrectangular setp
– (optional, default:Inf
) norm
Output
A real number representing the diameter.
Notes
The diameter is defined as the maximum distance in the given $p$-norm between any two elements of the set. Equivalently, it is the diameter of the enclosing ball of the given $p$-norm of minimal volume with the same center.
LazySets.vertices_list
— Method.vertices_list(H::AbstractHyperrectangle{N})::Vector{Vector{N}} where {N<:Real}
Return the list of vertices of a hyperrectangular set.
Input
H
– hyperrectangular set
Output
A list of vertices.
Notes
For high dimensions, it is preferable to develop a vertex_iterator
approach.
LazySets.singleton_list
— Method.singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}
Return the vertices of a polytopic as a list of singletons.
Input
P
– a polytopic set
Output
List containing a singleton for each vertex.
LazySets.center
— Method.center(B::BallInf{N})::Vector{N} where {N<:Real}
Return the center of a ball in the infinity norm.
Input
B
– ball in the infinity norm
Output
The center of the ball in the infinity norm.
LazySets.radius_hyperrectangle
— Method.radius_hyperrectangle(B::BallInf{N})::Vector{N} where {N<:Real}
Return the box radius of a infinity norm ball, which is the same in every dimension.
Input
B
– infinity norm ball
Output
The box radius of the ball in the infinity norm.
LazySets.radius_hyperrectangle
— Method.radius_hyperrectangle(B::BallInf{N}, i::Int)::N where {N<:Real}
Return the box radius of a infinity norm ball in a given dimension.
Input
B
– infinity norm ball
Output
The box radius of the ball in the infinity norm in the given dimension.
Manhattan norm ball
LazySets.Ball1
— Type.Ball1{N<:Real} <: AbstractPointSymmetricPolytope{N}
Type that represents a ball in the 1-norm, also known as Manhattan or Taxicab norm.
It is defined as the set
where $c ∈ \mathbb{R}^n$ is its center and $r ∈ \mathbb{R}_+$ its radius.
Fields
center
– center of the ball as a real vectorradius
– radius of the ball as a scalar ($≥ 0$)
Examples
Unit ball in the 1-norm in the plane:
julia> B = Ball1(zeros(2), 1.)
LazySets.Ball1{Float64}([0.0, 0.0], 1.0)
julia> dim(B)
2
We evaluate the support vector in the East direction:
julia> σ([0.,1], B)
2-element Array{Float64,1}:
0.0
1.0
LazySets.dim
— Method.dim(P::AbstractPointSymmetricPolytope)::Int
Return the ambient dimension of a point symmetric set.
Input
P
– set
Output
The ambient dimension of the set.
LazySets.σ
— Method.σ(d::V, B::Ball1{N}) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of a ball in the 1-norm in a given direction.
Input
d
– directionB
– ball in the 1-norm
Output
Support vector in the given direction.
Base.:∈
— Method.∈(x::AbstractVector{N}, B::Ball1{N})::Bool where {N<:Real}
Check whether a given point is contained in a ball in the 1-norm.
Input
x
– point/vectorB
– ball in the 1-norm
Output
true
iff $x ∈ B$.
Notes
This implementation is worst-case optimized, i.e., it is optimistic and first computes (see below) the whole sum before comparing to the radius. In applications where the point is typically far away from the ball, a fail-fast implementation with interleaved comparisons could be more efficient.
Algorithm
Let $B$ be an $n$-dimensional ball in the 1-norm with radius $r$ and let $c_i$ and $x_i$ be the ball's center and the vector $x$ in dimension $i$, respectively. Then $x ∈ B$ iff $∑_{i=1}^n |c_i - x_i| ≤ r$.
Examples
julia> B = Ball1([1., 1.], 1.);
julia> ∈([.5, -.5], B)
false
julia> ∈([.5, 1.5], B)
true
LazySets.an_element
— Method.an_element(S::LazySet{N}) where {N<:Real}
Return some element of a convex set.
Input
S
– convex set
Output
An element of a convex set.
an_element(P::AbstractPointSymmetricPolytope{N})::Vector{N} where {N<:Real}
Return some element of a point symmetric polytope.
Input
P
– point symmetric polytope
Output
The center of the point symmetric polytope.
LazySets.vertices_list
— Method.vertices_list(B::Ball1{N})::Vector{Vector{N}} where {N<:Real}
Return the list of vertices of a ball in the 1-norm.
Input
B
– ball in the 1-norm
Output
A list containing the vertices of the ball in the 1-norm.
LazySets.singleton_list
— Method.singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}
Return the vertices of a polytopic as a list of singletons.
Input
P
– a polytopic set
Output
List containing a singleton for each vertex.
LazySets.center
— Method.center(B::Ball1{N})::Vector{N} where {N<:Real}
Return the center of a ball in the 1-norm.
Input
B
– ball in the 1-norm
Output
The center of the ball in the 1-norm.
p-norm ball
LazySets.Ballp
— Type.Ballp{N<:AbstractFloat} <: AbstractPointSymmetric{N}
Type that represents a ball in the p-norm, for $1 ≤ p ≤ ∞$.
It is defined as the set
where $c ∈ \mathbb{R}^n$ is its center and $r ∈ \mathbb{R}_+$ its radius. Here $‖ ⋅ ‖_p$ for $1 ≤ p ≤ ∞$ denotes the vector $p$-norm, defined as $‖ x ‖_p = \left( \sum\limits_{i=1}^n |x_i|^p \right)^{1/p}$ for any $x ∈ \mathbb{R}^n$.
Fields
p
– norm as a real scalarcenter
– center of the ball as a real vectorradius
– radius of the ball as a scalar ($≥ 0$)
Notes
The special cases $p=1$, $p=2$ and $p=∞$ fall back to the specialized types Ball1
, Ball2
and BallInf
, respectively.
Examples
A five-dimensional ball in the $p=3/2$ norm centered at the origin of radius 0.5:
julia> B = Ballp(3/2, zeros(5), 0.5)
LazySets.Ballp{Float64}(1.5, [0.0, 0.0, 0.0, 0.0, 0.0], 0.5)
julia> dim(B)
5
We evaluate the support vector in direction $[1,2,…,5]$:
julia> σ([1., 2, 3, 4, 5], B)
5-element Array{Float64,1}:
0.013516
0.054064
0.121644
0.216256
0.3379
LazySets.dim
— Method.dim(S::AbstractPointSymmetric)::Int
Return the ambient dimension of a point symmetric set.
Input
S
– set
Output
The ambient dimension of the set.
LazySets.σ
— Method.σ(d::V, B::Ballp) where {N<:AbstractFloat, V<:AbstractVector{N}}
Return the support vector of a Ballp
in a given direction.
Input
d
– directionB
– 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:
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
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$.
Base.:∈
— Method.∈(x::AbstractVector{N}, B::Ballp{N})::Bool where {N<:AbstractFloat}
Check whether a given point is contained in a ball in the p-norm.
Input
x
– point/vectorB
– ball in the p-norm
Output
true
iff $x ∈ B$.
Notes
This implementation is worst-case optimized, i.e., it is optimistic and first computes (see below) the whole sum before comparing to the radius. In applications where the point is typically far away from the ball, a fail-fast implementation with interleaved comparisons could be more efficient.
Algorithm
Let $B$ be an $n$-dimensional ball in the p-norm with radius $r$ and let $c_i$ and $x_i$ be the ball's center and the vector $x$ in dimension $i$, respectively. Then $x ∈ B$ iff $\left( ∑_{i=1}^n |c_i - x_i|^p \right)^{1/p} ≤ r$.
Examples
julia> B = Ballp(1.5, [1., 1.], 1.)
LazySets.Ballp{Float64}(1.5, [1.0, 1.0], 1.0)
julia> ∈([.5, -.5], B)
false
julia> ∈([.5, 1.5], B)
true
LazySets.an_element
— Method.an_element(S::LazySet{N}) where {N<:Real}
Return some element of a convex set.
Input
S
– convex set
Output
An element of a convex set.
an_element(S::AbstractPointSymmetric{N})::Vector{N} where {N<:Real}
Return some element of a point symmetric set.
Input
S
– point symmetric set
Output
The center of the point symmetric set.
LazySets.center
— Method.center(B::Ballp{N})::Vector{N} where {N<:AbstractFloat}
Return the center of a ball in the p-norm.
Input
B
– ball in the p-norm
Output
The center of the ball in the p-norm.
Ellipsoid
LazySets.Ellipsoid
— Type.Ellipsoid{N<:AbstractFloat} <: AbstractPointSymmetric{N}
Type that represents an ellipsoid.
It is defined as the set
where $c \in \mathbb{R}^n$ is its center and $Q \in \mathbb{R}^{n×n}$ its shape matrix, which should be a positive definite matrix. An ellipsoid can also be characterized as the image of a Euclidean ball by an invertible linear transformation. It is the higher-dimensional generalization of an ellipse.
Fields
center
– center of the ellipsoidshape matrix
– real positive definite matrix, i.e. it is equal to its transpose and $x^\mathrm{T}Qx > 0$ for all nonzero $x$
Examples
If the center is not specified, it is assumed that the center is the origin. For instance, a 3D ellipsoid with center at the origin and the shape matrix being the identity can be created with:
julia> E = Ellipsoid(eye(3))
LazySets.Ellipsoid{Float64}([0.0, 0.0, 0.0], [1.0 0.0 0.0; 0.0 1.0 0.0; 0.0 0.0 1.0])
julia> dim(E)
3
julia> an_element(E)
3-element Array{Float64,1}:
0.0
0.0
0.0
This ellipsoid corresponds to the unit Euclidean ball. Let's evaluate its support vector in a given direction:
julia> σ(ones(3), E)
3-element Array{Float64,1}:
0.57735
0.57735
0.57735
A two-dimensional ellipsoid with given center and shape matrix:
julia> E = Ellipsoid(ones(2), diagm([2.0, 0.5]))
LazySets.Ellipsoid{Float64}([1.0, 1.0], [2.0 0.0; 0.0 0.5])
LazySets.σ
— Method.σ(d::V, E::Ellipsoid{N})::V where{N<:AbstractFloat, V<:AbstractVector{N}}
Return the support vector of an ellipsoid in a given direction.
Input
d
– directionE
– ellipsoid
Output
Support vector in the given direction.
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,
LazySets.center
— Method.center(E::Ellipsoid{N})::Vector{N} where {N<:AbstractFloat}
Return the center of the ellipsoid.
Input
E
– ellipsoid
Output
The center of the ellipsoid.
Base.:∈
— Method.∈(x::AbstractVector{N}, E::Ellipsoid{N})::Bool where {N<:AbstractFloat}
Check whether a given point is contained in an ellipsoid.
Input
x
– point/vectorE
– ellipsoid
Output
true
iff x ∈ E
.
Algorithm
The point $x$ belongs to the ellipsoid of center $c$ and shape matrix $Q$ if and only if
EmptySet
LazySets.EmptySet
— Type.EmptySet{N<:Real} <: LazySet{N}
Type that represents the empty set, i.e., the set with no elements.
LazySets.∅
— Constant.∅
An EmptySet
instance of type Float64
.
LazySets.dim
— Method.dim(∅::EmptySet)
Return the dimension of the empty set, which is -1 by convention.
Input
∅
– an empty set
Output
-1
by convention.
LazySets.σ
— Method.σ(d, ∅)
Return the support vector of an empty set.
Input
∅
– an empty set
Output
An error.
Base.:∈
— Method.∈(x::AbstractVector, ∅::EmptySet)::Bool
Check whether a given point is contained in an empty set.
Input
x
– point/vector∅
– empty set
Output
The output is always false
.
Examples
julia> ∈([1.0, 0.0], ∅)
false
LazySets.an_element
— Method.an_element(S::LazySet{N}) where {N<:Real}
Return some element of a convex set.
Input
S
– convex set
Output
An element of a convex set.
an_element(∅::EmptySet)
Return some element of an empty set.
Input
∅
– empty set
Output
An error.
Half-Space
LazySets.HalfSpace
— Type.HalfSpace{N<:Real} <: LazySet{N}
Type that represents a (closed) half-space of the form $a⋅x ≤ b$.
Fields
a
– normal directionb
– constraint
Examples
The set $y ≥ 0$ in the plane:
julia> HalfSpace([0, -1.], 0.)
LazySets.HalfSpace{Float64}([0.0, -1.0], 0.0)
LazySets.LinearConstraint
— Type.LinearConstraint
Alias for HalfSpace
LazySets.dim
— Method.dim(hs::HalfSpace)::Int
Return the dimension of a half-space.
Input
hs
– half-space
Output
The ambient dimension of the half-space.
LazySets.σ
— Method.σ(d::V, hs::HalfSpace) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of a half-space.
Input
d
– directionhs
– half-space
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 the half-space's normal direction.
In both cases the result is any point on the boundary (the defining hyperplane). Otherwise this function throws an error.
LazySets.an_element
— Method.an_element(S::LazySet{N}) where {N<:Real}
Return some element of a convex set.
Input
S
– convex set
Output
An element of a convex set.
an_element(hs::HalfSpace{N})::Vector{N} where {N<:Real}
Return some element of a half-space.
Input
hs
– half-space
Output
An element on the defining hyperplane.
Base.:∈
— Method.∈(x::AbstractVector{N}, hs::HalfSpace{N})::Bool where {N<:Real}
Check whether a given point is contained in a half-space.
Input
x
– point/vectorhs
– half-space
Output
true
iff $x ∈ hs$.
Algorithm
We just check if $x$ satisfies $a⋅x ≤ b$.
LazySets.halfspace_left
— Method.halfspace_left(p::AbstractVector{N},
q::AbstractVector{N})::HalfSpace{N} where {N<:Real}
Return a half-space describing the 'left' of a two-dimensional line segment through two points.
Input
p
– first pointq
– second point
Output
The half-space whose boundary goes through the two points p
and q
and which describes the left-hand side of the directed line segment pq
.
Algorithm
The implementation is simple: the half-space $a⋅x ≤ b$ is calculated as a = [dy, -dx]
, where $d = (dx, dy)$ denotes the line segment pq
, that is, $\vec{d} = \vec{p} - \vec{q}$, and b = dot(p, a)
.
Examples
The left half-space of the "east" and "west" directions in two-dimensions are the upper and lower half-spaces:
julia> import LazySets.halfspace_left
julia> halfspace_left([0.0, 0.0], [1.0, 0.0])
LazySets.HalfSpace{Float64}([0.0, -1.0], 0.0)
julia> halfspace_left([0.0, 0.0], [-1.0, 0.0])
LazySets.HalfSpace{Float64}([0.0, 1.0], 0.0)
We create a box from the sequence of line segments that describe its edges:
julia> H1 = halfspace_left([-1.0, -1.0], [1.0, -1.0]);
julia> H2 = halfspace_left([1.0, -1.0], [1.0, 1.0]);
julia> H3 = halfspace_left([1.0, 1.0], [-1.0, 1.0]);
julia> H4 = halfspace_left([-1.0, 1.0], [-1.0, -1.0]);
julia> H = HPolygon([H1, H2, H3, H4]);
julia> B = BallInf([0.0, 0.0], 1.0);
julia> B ⊆ H && H ⊆ B
true
LazySets.halfspace_right
— Method.halfspace_right(p::AbstractVector{N},
q::AbstractVector{N})::HalfSpace{N} where {N<:Real}
Return a half-space describing the 'right' of a two-dimensional line segment through two points.
Input
p
– first pointq
– second point
Output
The half-space whose boundary goes through the two points p
and q
and which describes the right-hand side of the directed line segment pq
.
Algorithm
See the documentation of halfspace_left
.
Hyperplane
LazySets.Hyperplane
— Type.Hyperplane{N<:Real} <: LazySet{N}
Type that represents a hyperplane of the form $a⋅x = b$.
Fields
a
– normal directionb
– constraint
Examples
The plane $y = 0$:
julia> Hyperplane([0, 1.], 0.)
LazySets.Hyperplane{Float64}([0.0, 1.0], 0.0)
LazySets.dim
— Method.dim(hp::Hyperplane)::Int
Return the dimension of a hyperplane.
Input
hp
– hyperplane
Output
The ambient dimension of the hyperplane.
LazySets.σ
— Method.σ(d::V, hp::Hyperplane) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of a hyperplane.
Input
d
– directionhp
– hyperplane
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 the hyperplane's normal direction.
In both cases the result is any point on the hyperplane. Otherwise this function throws an error.
LazySets.an_element
— Method.an_element(S::LazySet{N}) where {N<:Real}
Return some element of a convex set.
Input
S
– convex set
Output
An element of a convex set.
an_element(hp::Hyperplane{N})::Vector{N} where {N<:Real}
Return some element of a hyperplane.
Input
hp
– hyperplane
Output
An element in the hyperplane.
Base.:∈
— Method.∈(x::AbstractVector{N}, hp::Hyperplane{N})::Bool where {N<:Real}
Check whether a given point is contained in a hyperplane.
Input
x
– point/vectorhp
– hyperplane
Output
true
iff $x ∈ hp$.
Algorithm
We just check if $x$ satisfies $a⋅x = b$.
Hyperrectangles
LazySets.Hyperrectangle
— Type.Hyperrectangle{N<:Real} <: AbstractHyperrectangle{N}
Type that represents a hyperrectangle.
A hyperrectangle is the Cartesian product of one-dimensional intervals.
Fields
center
– center of the hyperrectangle as a real vectorradius
– radius of the ball as a real vector, i.e., half of its width along each coordinate direction
LazySets.Hyperrectangle
— Method.Hyperrectangle(;kwargs...)
Construct a hyperrectangle from keyword arguments.
Input
kwargs
– keyword arguments; two combinations are allowed:center
,radius
– vectorshigh
,low
– vectors (if bothcenter
andradius
are also defined, those are chosen instead)
Output
A hyperrectangle.
Examples
The following three constructions are equivalent:
julia> c = ones(2);
julia> r = [0.1, 0.2];
julia> l = [0.9, 0.8];
julia> h = [1.1, 1.2];
julia> H1 = Hyperrectangle(c, r)
LazySets.Hyperrectangle{Float64}([1.0, 1.0], [0.1, 0.2])
julia> H2 = Hyperrectangle(center=c, radius=r)
LazySets.Hyperrectangle{Float64}([1.0, 1.0], [0.1, 0.2])
julia> H3 = Hyperrectangle(low=l, high=h)
LazySets.Hyperrectangle{Float64}([1.0, 1.0], [0.1, 0.2])
LazySets.dim
— Method.dim(P::AbstractPointSymmetricPolytope)::Int
Return the ambient dimension of a point symmetric set.
Input
P
– set
Output
The ambient dimension of the set.
LazySets.σ
— Method.σ(d::V, H::AbstractHyperrectangle{N}) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of a hyperrectangular set in a given direction.
Input
d
– directionH
– hyperrectangular set
Output
The support vector in the given direction. If the direction has norm zero, the vertex with biggest values is returned.
Base.:∈
— Method.∈(x::AbstractVector{N}, H::AbstractHyperrectangle{N})::Bool where {N<:Real}
Check whether a given point is contained in a hyperrectangular set.
Input
x
– point/vectorH
– hyperrectangular set
Output
true
iff $x ∈ H$.
Algorithm
Let $H$ be an $n$-dimensional hyperrectangular set, $c_i$ and $r_i$ be the box's center and radius and $x_i$ be the vector $x$ in dimension $i$, respectively. Then $x ∈ H$ iff $|c_i - x_i| ≤ r_i$ for all $i=1,…,n$.
LazySets.an_element
— Method.an_element(S::LazySet{N}) where {N<:Real}
Return some element of a convex set.
Input
S
– convex set
Output
An element of a convex set.
an_element(P::AbstractPointSymmetricPolytope{N})::Vector{N} where {N<:Real}
Return some element of a point symmetric polytope.
Input
P
– point symmetric polytope
Output
The center of the point symmetric polytope.
Base.LinAlg.norm
— Method.norm(S::LazySet, [p]::Real=Inf)
Return the norm of a convex set. It is the norm of the enclosing ball (of the given $p$-norm) of minimal volume that is centered in the origin.
Input
S
– convex setp
– (optional, default:Inf
) norm
Output
A real number representing the norm.
norm(H::AbstractHyperrectangle, [p]::Real=Inf)::Real
Return the norm of a hyperrectangular set.
Input
H
– hyperrectangular setp
– (optional, default:Inf
) norm
Output
A real number representing the norm.
Notes
The norm of a hyperrectangular set is defined as the norm of the enclosing ball, of the given $p$-norm, of minimal volume that is centered in the origin.
LazySets.radius
— Method.radius(S::LazySet, [p]::Real=Inf)
Return the radius of a convex set. It is the radius of the enclosing ball (of the given $p$-norm) of minimal volume with the same center.
Input
S
– convex setp
– (optional, default:Inf
) norm
Output
A real number representing the radius.
radius(H::AbstractHyperrectangle, [p]::Real=Inf)::Real
Return the radius of a hyperrectangular set.
Input
H
– hyperrectangular setp
– (optional, default:Inf
) norm
Output
A real number representing the radius.
Notes
The radius is defined as the radius of the enclosing ball of the given $p$-norm of minimal volume with the same center. It is the same for all corners of a hyperrectangular set.
LazySets.diameter
— Method.diameter(S::LazySet, [p]::Real=Inf)
Return the diameter of a convex set. It 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.
Input
S
– convex setp
– (optional, default:Inf
) norm
Output
A real number representing the diameter.
diameter(H::AbstractHyperrectangle, [p]::Real=Inf)::Real
Return the diameter of a hyperrectangular set.
Input
H
– hyperrectangular setp
– (optional, default:Inf
) norm
Output
A real number representing the diameter.
Notes
The diameter is defined as the maximum distance in the given $p$-norm between any two elements of the set. Equivalently, it is the diameter of the enclosing ball of the given $p$-norm of minimal volume with the same center.
LazySets.vertices_list
— Method.vertices_list(H::AbstractHyperrectangle{N})::Vector{Vector{N}} where {N<:Real}
Return the list of vertices of a hyperrectangular set.
Input
H
– hyperrectangular set
Output
A list of vertices.
Notes
For high dimensions, it is preferable to develop a vertex_iterator
approach.
LazySets.singleton_list
— Method.singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}
Return the vertices of a polytopic as a list of singletons.
Input
P
– a polytopic set
Output
List containing a singleton for each vertex.
LazySets.center
— Method.center(H::Hyperrectangle{N})::Vector{N} where {N<:Real}
Return the center of a hyperrectangle.
Input
H
– hyperrectangle
Output
The center of the hyperrectangle.
LazySets.radius_hyperrectangle
— Method.radius_hyperrectangle(H::Hyperrectangle{N})::Vector{N} where {N<:Real}
Return the box radius of a hyperrectangle in every dimension.
Input
H
– hyperrectangle
Output
The box radius of the hyperrectangle.
LazySets.radius_hyperrectangle
— Method.radius_hyperrectangle(H::Hyperrectangle{N}, i::Int)::N where {N<:Real}
Return the box radius of a hyperrectangle in a given dimension.
Input
H
– hyperrectangle
Output
The radius in the given dimension.
LazySets.high
— Method.high(H::Hyperrectangle{N})::Vector{N} where {N<:Real}
Return the higher coordinates of a hyperrectangle.
Input
H
– hyperrectangle
Output
A vector with the higher coordinates of the hyperrectangle, one entry per dimension.
LazySets.low
— Method.low(H::Hyperrectangle{N})::Vector{N} where {N<:Real}
Return the lower coordinates of a hyperrectangle.
Input
H
– hyperrectangle
Output
A vector with the lower coordinates of the hyperrectangle, one entry per dimension.
Intervals
LazySets.Interval
— Type.Interval{N<:Real, IN <: AbstractInterval{N}} <: AbstractPointSymmetricPolytope{N}
Type representing an interval on the real line. Mathematically, it is of the form
Fields
dat
– data container for the given interval
Notes
This type relies on the IntervalArithmetic.jl library for representation of intervals and arithmetic operations.
Examples
Unidimensional intervals are symbolic representations of a real closed interval. This type requires the user to load the IntervalArithmetic
library, since artithmetic operations rely on that module.
We can create intervals in different ways, the simpler way is to pass a pair of numbers:
julia> x = Interval(0.0, 1.0)
LazySets.Interval{Float64,IntervalArithmetic.Interval{Float64}}([0, 1])
or a 2-vector:
julia> x = Interval([0.0, 1.0])
LazySets.Interval{Float64,IntervalArithmetic.Interval{Float64}}([0, 1])
Note that if the package IntervalArithmetic
is loaded in the current scope, you have to prepend the LazySets
to the interval type, since there is a name conflict otherwise.
julia> using IntervalArithmetic
WARNING: using IntervalArithmetic.Interval in module Main conflicts with an existing identifier.
julia> x = LazySets.Interval(IntervalArithmetic.Interval(0.0, 1.0))
LazySets.Interval{Float64,IntervalArithmetic.Interval{Float64}}([0, 1])
julia> dim(x)
1
julia> center(x)
1-element Array{Float64,1}:
0.5
This type is such that the usual pairwise arithmetic operators +
, -
, *
trigger the corresponding interval arithmetic backend method, and return a new Interval
object. For the symbolic Minkowksi sum, use MinkowskiSum
or ⊕
.
Interval of other numeric types can be created as well, eg. a rational interval:
julia> Interval(0//1, 2//1)
LazySets.Interval{Rational{Int64},IntervalArithmetic.AbstractInterval{Rational{Int64}}}([0//1, 2//1])
LazySets.dim
— Method.dim(x::Interval)::Int
Return the ambient dimension of an interval.
Input
x
– interval
Output
The integer 1.
LazySets.σ
— Method.σ(d::V, x::Interval{N, IN})::V where {N, IN <: AbstractInterval{N}, V<:AbstractVector{N}}
Return the support vector of an ellipsoid in a given direction.
Input
d
– directionx
– interval
Output
Support vector in the given direction.
LazySets.center
— Method.center(x::Interval)
Return the interval's center.
Input
x
– interval
Output
The center, or midpoint, of $x$.
LazySets.low
— Method.low(x::Interval)
Return the lower component of an interval.
Input
x
– interval
Output
The lower (lo
) component of the interval.
LazySets.high
— Method.high(x::Interval)
Return the higher or upper component of an interval.
Input
x
– interval
Output
The higher (hi
) component of the interval.
LazySets.vertices_list
— Method.vertices_list(x::Interval)
Return the list of vertices of this interval.
Input
x
– interval
Output
The list of vertices of the interval represented as two one-dimensional vectors.
Base.:+
— Method.+(x::Interval, y::Interval)
Return the sum of the intervals.
Input
x
– intervaly
– interval
Output
The sum of the intervals as a new Interval
set.
Base.:-
— Method.-(x::Interval, y::Interval)
Return the difference of the intervals.
Input
x
– intervaly
– interval
Output
The difference of the intervals as a new Interval
set.
Base.:*
— Method. *(x::Interval, y::Interval)
Return the product of the intervals.
Input
x
– intervaly
– interval
Output
The product of the intervals as a new Interval
set.
Base.:∈
— Method.∈(v::AbstractVector, x::Interval)
Return whether a vector is contained in the interval.
Input
v
– one-dimensional vectorx
– interval
Output
true
iff x
contains v
's first component.
Base.:∈
— Method.∈(v::N, x::Interval) where {N}
Return whether a number is contained in the interval.
Input
v
– scalarx
– interval
Output
true
iff x
contains v
.
Line
Line
dim(::Line{Float64})
σ(::AbstractVector{Float64}, ::Line{Float64})
∈(::AbstractVector, ::Line)
an_element(::Line)
Line segment
LazySets.LineSegment
— Type.LineSegment{N<:Real} <: LazySet{N}
Type that represents a line segment in 2D between two points $p$ and $q$.
Fields
p
– first pointq
– second point
Examples
A line segment along the $x = y$ diagonal:
julia> s = LineSegment([0., 0], [1., 1.])
LazySets.LineSegment{Float64}([0.0, 0.0], [1.0, 1.0])
julia> dim(s)
2
Use $plot(s)$ to plot the extreme points of s
and the line segment joining them. Membership test is computed with ∈ (in
):
julia> [0., 0] ∈ s && [.25, .25] ∈ s && [1., 1] ∈ s && !([.5, .25] ∈ s)
true
We can check the intersection with another line segment, and optionally compute a witness (which is just the common point in this case):
julia> sn = LineSegment([1., 0], [0., 1.])
LazySets.LineSegment{Float64}([1.0, 0.0], [0.0, 1.0])
julia> isempty(s ∩ sn)
false
julia> is_intersection_empty(s, sn, true)
(false, [0.5, 0.5])
LazySets.dim
— Method.dim(L::LineSegment)::Int
Return the ambient dimension of a line segment.
Input
L
– line segment
Output
The ambient dimension of the line segment, which is 2.
LazySets.σ
— Method.σ(d::V, L::LineSegment) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of a line segment in a given direction.
Input
d
– directionL
– line segment
Output
The support vector in the given direction.
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$.
Base.:∈
— Method.∈(x::AbstractVector{N}, L::LineSegment{N})::Bool where {N<:Real}
Check whether a given point is contained in a line segment.
Input
x
– point/vectorL
– line segment
Output
true
iff $x ∈ L$.
Algorithm
Let $L = (p, q)$ be the line segment with extremes $p$ and $q$, and let $x$ be the given point.
A necessary condition for $x ∈ (p, q)$ is that the three points are aligned, thus their cross product should be zero.
It remains to check that $x$ belongs to the box approximation of $L$. This amounts to comparing each coordinate with those of the extremes $p$ and $q$.
Notes
The algorithm is inspired from here.
LazySets.halfspace_left
— Method.halfspace_left(L::LineSegment)
Return a half-space describing the 'left' of a two-dimensional line segment through two points.
Input
L
– line segment
Output
The half-space whose boundary goes through the two points p
and q
and which describes the left-hand side of the directed line segment pq
.
LazySets.halfspace_right
— Method.halfspace_right(L::LineSegment)
Return a half-space describing the 'right' of a two-dimensional line segment through two points.
Input
L
– line segment
Output
The half-space whose boundary goes through the two points p
and q
and which describes the right-hand side of the directed line segment pq
.
Polygons
Constraint representation
LazySets.HPolygon
— Type.HPolygon{N<:Real} <: AbstractHPolygon{N}
Type that represents a convex polygon in constraint representation whose edges are sorted in counter-clockwise fashion with respect to their normal directions.
Fields
constraints
– list of linear constraints, sorted by the angle
Notes
The default constructor assumes that the given list of edges is sorted. It does not perform any sorting. Use addconstraint!
to iteratively add the edges in a sorted way.
HPolygon(constraints::Vector{LinearConstraint{<:Real}})
– default constructorHPolygon()
– constructor with no constraintsHPolygon(S::LazySet)
– constructor from another set
LazySets.dim
— Method.dim(P::AbstractPolygon)::Int
Return the ambient dimension of a polygon.
Input
P
– polygon
Output
The ambient dimension of the polygon, which is 2.
LazySets.σ
— Method.σ(d::AbstractVector{<:Real}, P::HPolygon{N})::Vector{N} where {N<:Real}
Return the support vector of a polygon in a given direction.
Input
d
– directionP
– polygon in constraint representation
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 overload of <=
for two-dimensional vectors.
Base.:∈
— Method.∈(x::AbstractVector{N}, P::AbstractHPolygon{N})::Bool where {N<:Real}
Check whether a given 2D point is contained in a polygon in constraint representation.
Input
x
– two-dimensional point/vectorP
– polygon in constraint representation
Output
true
iff $x ∈ P$.
Algorithm
This implementation checks if the point lies on the outside of each edge.
LazySets.an_element
— Method.an_element(S::LazySet{N}) where {N<:Real}
Return some element of a convex set.
Input
S
– convex set
Output
An element of a convex set.
an_element(P::AbstractHPolygon{N})::Vector{N} where {N<:Real}
Return some element of a polygon in constraint representation.
Input
P
– polygon in constraint representation
Output
A vertex of the polygon in constraint representation (the first one in the order of the constraints).
LazySets.vertices_list
— Method.vertices_list(P::AbstractHPolygon{N},
apply_convex_hull::Bool=false
)::Vector{Vector{N}} where {N<:Real}
Return the list of vertices of a polygon in constraint representation.
Input
P
– polygon in constraint representationapply_convex_hull
– (optional, default:false
) to post process or not the intersection of constraints with a convex hull
Output
List of vertices.
LazySets.singleton_list
— Method.singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}
Return the vertices of a polytopic as a list of singletons.
Input
P
– a polytopic set
Output
List containing a singleton for each vertex.
LazySets.tohrep
— Method.tohrep(P::AbstractHPolygon{N})::AbstractHPolygon{N} where {N<:Real}
Build a contraint representation of the given polygon.
Input
P
– polygon in constraint representation
Output
The identity, i.e., the same polygon instance.
tohrep(P::VPolygon{N}, ::Type{HPOLYGON}=HPolygon
)::AbstractHPolygon{N} where {N<:Real, HPOLYGON<:AbstractHPolygon}
Build a constraint representation of the given polygon.
Input
P
– polygon in vertex representationHPOLYGON
– (optional, default:HPolygon
) type of target polygon
Output
The same polygon but in constraint representation, an AbstractHPolygon
.
Algorithm
The algorithms consists of adding an edge for each consecutive pair of vertices. Since the vertices are already ordered in counter-clockwise fashion (CWW), the constraints will be sorted automatically (CCW) if we start with the first edge between the first and second vertex.
LazySets.tovrep
— Method.tovrep(P::AbstractHPolygon{N})::VPolygon{N} where {N<:Real}
Build a vertex representation of the given polygon.
Input
P
– polygon in constraint representation
Output
The same polygon but in vertex representation, a VPolygon
.
LazySets.addconstraint!
— Method.addconstraint!(P::AbstractHPolygon{N},
constraint::LinearConstraint{N})::Void where {N<:Real}
Add a linear constraint to a polygon in constraint representation, keeping the constraints sorted by their normal directions.
Input
P
– polygon in constraint representationconstraint
– linear constraint to add
Output
Nothing.
Optimized constraint representation
LazySets.HPolygonOpt
— Type.HPolygonOpt{N<:Real} <: AbstractHPolygon{N}
Type that represents a convex polygon in constraint representation whose edges are sorted in counter-clockwise fashion with respect to their normal directions. This is a refined version of HPolygon
.
Fields
constraints
– list of linear constraintsind
– index in the list of constraints to begin the search to evaluate the support function
Notes
This structure is optimized to evaluate the support function/vector with a large sequence of directions that are close to each other. The strategy is to have an index that can be used to warm-start the search for optimal values in the support vector computation.
The default constructor assumes that the given list of edges is sorted. It does not perform any sorting. Use addconstraint!
to iteratively add the edges in a sorted way.
HPolygonOpt(constraints::Vector{LinearConstraint{<:Real}}, [ind]::Int)
– default constructor with optional indexHPolygonOpt(S::LazySet)
– constructor from another set
LazySets.dim
— Method.dim(P::AbstractPolygon)::Int
Return the ambient dimension of a polygon.
Input
P
– polygon
Output
The ambient dimension of the polygon, which is 2.
LazySets.σ
— Method.σ(d::AbstractVector{<:Real}, P::HPolygonOpt{N})::Vector{N} where {N<:Real}
Return the support vector of an optimized polygon in a given direction.
Input
d
– directionP
– optimized polygon in constraint representation
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 overload of <=
for two-dimensional vectors.
Base.:∈
— Method.∈(x::AbstractVector{N}, P::AbstractHPolygon{N})::Bool where {N<:Real}
Check whether a given 2D point is contained in a polygon in constraint representation.
Input
x
– two-dimensional point/vectorP
– polygon in constraint representation
Output
true
iff $x ∈ P$.
Algorithm
This implementation checks if the point lies on the outside of each edge.
LazySets.an_element
— Method.an_element(S::LazySet{N}) where {N<:Real}
Return some element of a convex set.
Input
S
– convex set
Output
An element of a convex set.
an_element(P::AbstractHPolygon{N})::Vector{N} where {N<:Real}
Return some element of a polygon in constraint representation.
Input
P
– polygon in constraint representation
Output
A vertex of the polygon in constraint representation (the first one in the order of the constraints).
LazySets.vertices_list
— Method.vertices_list(P::AbstractHPolygon{N},
apply_convex_hull::Bool=false
)::Vector{Vector{N}} where {N<:Real}
Return the list of vertices of a polygon in constraint representation.
Input
P
– polygon in constraint representationapply_convex_hull
– (optional, default:false
) to post process or not the intersection of constraints with a convex hull
Output
List of vertices.
LazySets.singleton_list
— Method.singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}
Return the vertices of a polytopic as a list of singletons.
Input
P
– a polytopic set
Output
List containing a singleton for each vertex.
LazySets.tohrep
— Method.tohrep(P::AbstractHPolygon{N})::AbstractHPolygon{N} where {N<:Real}
Build a contraint representation of the given polygon.
Input
P
– polygon in constraint representation
Output
The identity, i.e., the same polygon instance.
tohrep(P::VPolygon{N}, ::Type{HPOLYGON}=HPolygon
)::AbstractHPolygon{N} where {N<:Real, HPOLYGON<:AbstractHPolygon}
Build a constraint representation of the given polygon.
Input
P
– polygon in vertex representationHPOLYGON
– (optional, default:HPolygon
) type of target polygon
Output
The same polygon but in constraint representation, an AbstractHPolygon
.
Algorithm
The algorithms consists of adding an edge for each consecutive pair of vertices. Since the vertices are already ordered in counter-clockwise fashion (CWW), the constraints will be sorted automatically (CCW) if we start with the first edge between the first and second vertex.
LazySets.tovrep
— Method.tovrep(P::AbstractHPolygon{N})::VPolygon{N} where {N<:Real}
Build a vertex representation of the given polygon.
Input
P
– polygon in constraint representation
Output
The same polygon but in vertex representation, a VPolygon
.
LazySets.addconstraint!
— Method.addconstraint!(P::AbstractHPolygon{N},
constraint::LinearConstraint{N})::Void where {N<:Real}
Add a linear constraint to a polygon in constraint representation, keeping the constraints sorted by their normal directions.
Input
P
– polygon in constraint representationconstraint
– linear constraint to add
Output
Nothing.
Vertex representation
LazySets.VPolygon
— Type.VPolygon{N<:Real} <: AbstractPolygon{N}
Type that represents a polygon by its vertices.
Fields
vertices
– the list of vertices
Notes
The constructor of VPolygon
runs a convex hull algorithm, and the given vertices are sorted in counter-clockwise fashion. The constructor flag apply_convex_hull
can be used to skip the computation of the convex hull.
VPolygon(vertices::Vector{Vector{N}}; apply_convex_hull::Bool=true, algorithm::String="monotone_chain")
LazySets.dim
— Method.dim(P::AbstractPolygon)::Int
Return the ambient dimension of a polygon.
Input
P
– polygon
Output
The ambient dimension of the polygon, which is 2.
LazySets.σ
— Method.σ(d::AbstractVector{<:Real}, P::VPolygon{N})::Vector{N} where {N<:Real}
Return the support vector of a polygon in a given direction.
Input
d
– directionP
– polygon in vertex representation
Output
The support vector in the given direction. If the direction has norm zero, the first vertex is returned.
Algorithm
This implementation performs a brute-force search, comparing the projection of each vector along the given direction. It runs in $O(n)$ where $n$ is the number of vertices.
Notes
For arbitrary points without structure this is the best one can do. However, a more efficient approach can be used if the vertices of the polygon have been sorted in counter-clockwise fashion. In that case a binary search algorithm can be used that runs in $O(\log n)$. See issue #40.
Base.:∈
— Method.∈(x::AbstractVector{N}, P::VPolygon{N})::Bool where {N<:Real}
Check whether a given point is contained in a polygon in vertex representation.
Input
x
– point/vectorP
– polygon in vertex representation
Output
true
iff $x ∈ P$.
Algorithm
This implementation exploits that the polygon's vertices are sorted in counter-clockwise fashion. Under this assumption we can just check if the vertex lies on the left of each edge, using the dot product.
Examples
julia> P = VPolygon([[2.0, 3.0], [3.0, 1.0], [5.0, 1.0], [4.0, 5.0]];
apply_convex_hull=false);
julia> ∈([4.5, 3.1], P)
false
julia> ∈([4.5, 3.0], P)
true
julia> ∈([4.4, 3.4], P) # point lies on the edge -> floating point error
false
julia> P = VPolygon([[2//1, 3//1], [3//1, 1//1], [5//1, 1//1], [4//1, 5//1]];
apply_convex_hull=false);
julia> ∈([44//10, 34//10], P) # with rational numbers the answer is correct
true
LazySets.an_element
— Method.an_element(S::LazySet{N}) where {N<:Real}
Return some element of a convex set.
Input
S
– convex set
Output
An element of a convex set.
an_element(P::VPolygon{N})::Vector{N} where {N<:Real}
Return some element of a polygon in vertex representation.
Input
P
– polygon in vertex representation
Output
The first vertex of the polygon in vertex representation.
LazySets.vertices_list
— Method.vertices_list(P::VPolygon{N})::Vector{Vector{N}} where {N<:Real}
Return the list of vertices of a convex polygon in vertex representation.
Input
P
– a polygon vertex representation
Output
List of vertices.
LazySets.singleton_list
— Method.singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}
Return the vertices of a polytopic as a list of singletons.
Input
P
– a polytopic set
Output
List containing a singleton for each vertex.
LazySets.tohrep
— Method.tohrep(P::VPolygon{N}, ::Type{HPOLYGON}=HPolygon
)::AbstractHPolygon{N} where {N<:Real, HPOLYGON<:AbstractHPolygon}
Build a constraint representation of the given polygon.
Input
P
– polygon in vertex representationHPOLYGON
– (optional, default:HPolygon
) type of target polygon
Output
The same polygon but in constraint representation, an AbstractHPolygon
.
Algorithm
The algorithms consists of adding an edge for each consecutive pair of vertices. Since the vertices are already ordered in counter-clockwise fashion (CWW), the constraints will be sorted automatically (CCW) if we start with the first edge between the first and second vertex.
LazySets.tovrep
— Method.tovrep(P::VPolygon{N})::VPolygon{N} where {N<:Real}
Build a vertex representation of the given polygon.
Input
P
– polygon in vertex representation
Output
The identity, i.e., the same polygon instance.
Sorting directions
LazySets.jump2pi
— Function.jump2pi(x::N)::N where {N<:AbstractFloat}
Return $x + 2π$ if $x$ is negative, otherwise return $x$.
Input
x
– real scalar
Output
$x + 2π$ if $x$ is negative, $x$ otherwise.
Examples
julia> import LazySets.jump2pi
julia> jump2pi(0.0)
0.0
julia> jump2pi(-0.5)
5.783185307179586
julia> jump2pi(0.5)
0.5
Base.:<=
— Method.<=(u::AbstractVector{N}, v::AbstractVector{N})::Bool where {N<:AbstractFloat}
Compares 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, atan2
.
<=(u::AbstractVector{N}, v::AbstractVector{N})::Bool where {N<:Real}
Compares 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 checks the quadrant of each direction, and compares directions using the right-hand rule. In particular, it doesn't use the arctangent.
LazySets.quadrant
— Method.quadrant(w::AbstractVector{N})::Int where {N<:Real}
Compute the quadrant where the direction w
belongs.
Input
w
– direction
Output
An integer from 0 to 3, with the following convention:
^
1 | 0
---+-->
2 | 3
Algorithm
The idea is to encode the following logic function: $11 ↦ 0, 01 ↦ 1, 00 ↦ 2, 10 ↦ 3$, according to the convention of above.
This function is inspired from AGPX's answer in: Sort points in clockwise order?
Polytopes
LazySets.HPolytope
— Type.HPolytope{N<:Real} <: AbstractPolytope{N}
Type that represents a convex polytope in H-representation.
Fields
constraints
– vector of linear constraints
Note
This type is more appropriately a polyhedron, because no check in the constructor is made that the constraints determine a bounded set from the finite intersection of half-spaces. This is a running assumption in this type.
LazySets.dim
— Method.dim(P::HPolytope)::Int
Return the dimension of a polytope in H-representation.
Input
P
– polytope in H-representation
Output
The ambient dimension of the polytope in H-representation. If it has no constraints, the result is $-1$.
LazySets.addconstraint!
— Method.addconstraint!(P::HPolytope{N},
constraint::LinearConstraint{N})::Void where {N<:Real}
Add a linear constraint to a polyhedron in H-representation.
Input
P
– polyhedron in H-representationconstraint
– linear constraint to add
Output
Nothing.
Notes
It is left to the user to guarantee that the dimension of all linear constraints is the same.
LazySets.constraints_list
— Method.constraints_list(P::HPolytope{N})::Vector{LinearConstraint{N}} where {N<:Real}
Return the list of constraints defining a polyhedron in H-representation.
Input
P
– polytope in H-representation
Output
The list of constraints of the polyhedron.
LazySets.σ
— Method.σ(d::AbstractVector{<:Real}, P::HPolytope)::Vector{<:Real}
Return the support vector of a polyhedron (in H-representation) in a given direction.
Input
d
– directionP
– polyhedron in H-representation
Output
The support vector in the given direction.
Algorithm
This implementation uses GLPKSolverLP
as linear programming backend.
Base.:∈
— Method.∈(x::AbstractVector{N}, P::HPolytope{N})::Bool where {N<:Real}
Check whether a given 2D point is contained in a polytope in constraint representation.
Input
x
– two-dimensional point/vectorP
– polytope in constraint representation
Output
true
iff $x ∈ P$.
Algorithm
This implementation checks if the point lies on the outside of each hyperplane. This is equivalent to checking if the point lies in each half-space.
Singletons
LazySets.Singleton
— Type.Singleton{N<:Real} <: AbstractSingleton{N}
Type that represents a singleton, that is, a set with a unique element.
Fields
element
– the only element of the set
LazySets.dim
— Method.dim(P::AbstractPointSymmetricPolytope)::Int
Return the ambient dimension of a point symmetric set.
Input
P
– set
Output
The ambient dimension of the set.
LazySets.σ
— Method.σ(d::V, H::AbstractHyperrectangle{N}) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of a hyperrectangular set in a given direction.
Input
d
– directionH
– hyperrectangular set
Output
The support vector in the given direction. If the direction has norm zero, the vertex with biggest values is returned.
σ(d::AbstractVector{N}, S::AbstractSingleton{N})::Vector{N} where {N<:Real}
Return the support vector of a set with a single value.
Input
d
– directionS
– set with a single value
Output
The support vector, which is the set's vector itself, irrespective of the given direction.
Base.:∈
— Method.∈(x::AbstractVector{N}, H::AbstractHyperrectangle{N})::Bool where {N<:Real}
Check whether a given point is contained in a hyperrectangular set.
Input
x
– point/vectorH
– hyperrectangular set
Output
true
iff $x ∈ H$.
Algorithm
Let $H$ be an $n$-dimensional hyperrectangular set, $c_i$ and $r_i$ be the box's center and radius and $x_i$ be the vector $x$ in dimension $i$, respectively. Then $x ∈ H$ iff $|c_i - x_i| ≤ r_i$ for all $i=1,…,n$.
∈(x::AbstractVector{N}, S::AbstractSingleton{N})::Bool where {N<:Real}
Check whether a given point is contained in a set with a single value.
Input
x
– point/vectorS
– set with a single value
Output
true
iff $x ∈ S$.
Notes
This implementation performs an exact comparison, which may be insufficient with floating point computations.
Base.LinAlg.norm
— Method.norm(S::LazySet, [p]::Real=Inf)
Return the norm of a convex set. It is the norm of the enclosing ball (of the given $p$-norm) of minimal volume that is centered in the origin.
Input
S
– convex setp
– (optional, default:Inf
) norm
Output
A real number representing the norm.
norm(H::AbstractHyperrectangle, [p]::Real=Inf)::Real
Return the norm of a hyperrectangular set.
Input
H
– hyperrectangular setp
– (optional, default:Inf
) norm
Output
A real number representing the norm.
Notes
The norm of a hyperrectangular set is defined as the norm of the enclosing ball, of the given $p$-norm, of minimal volume that is centered in the origin.
LazySets.diameter
— Method.diameter(S::LazySet, [p]::Real=Inf)
Return the diameter of a convex set. It 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.
Input
S
– convex setp
– (optional, default:Inf
) norm
Output
A real number representing the diameter.
diameter(H::AbstractHyperrectangle, [p]::Real=Inf)::Real
Return the diameter of a hyperrectangular set.
Input
H
– hyperrectangular setp
– (optional, default:Inf
) norm
Output
A real number representing the diameter.
Notes
The diameter is defined as the maximum distance in the given $p$-norm between any two elements of the set. Equivalently, it is the diameter of the enclosing ball of the given $p$-norm of minimal volume with the same center.
LazySets.vertices_list
— Method.vertices_list(H::AbstractHyperrectangle{N})::Vector{Vector{N}} where {N<:Real}
Return the list of vertices of a hyperrectangular set.
Input
H
– hyperrectangular set
Output
A list of vertices.
Notes
For high dimensions, it is preferable to develop a vertex_iterator
approach.
vertices_list(S::AbstractSingleton{N})::Vector{Vector{N}} where {N<:Real}
Return the list of vertices of a set with a single value.
Input
S
– set with a single value
Output
A list containing only a single vertex.
LazySets.singleton_list
— Method.singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}
Return the vertices of a polytopic as a list of singletons.
Input
P
– a polytopic set
Output
List containing a singleton for each vertex.
LazySets.center
— Method.center(S::AbstractSingleton{N})::Vector{N} where {N<:Real}
Return the center of a set with a single value.
Input
S
– set with a single value
Output
The only element of the set.
LazySets.radius_hyperrectangle
— Method.radius_hyperrectangle(S::AbstractSingleton{N})::Vector{N} where {N<:Real}
Return the box radius of a set with a single value in every dimension.
Input
S
– set with a single value
Output
The zero vector.
LazySets.radius_hyperrectangle
— Method.radius_hyperrectangle(S::AbstractSingleton{N}, i::Int)::N where {N<:Real}
Return the box radius of a set with a single value in a given dimension.
Input
S
– set with a single value
Output
Zero.
LazySets.an_element
— Method.an_element(S::LazySet{N}) where {N<:Real}
Return some element of a convex set.
Input
S
– convex set
Output
An element of a convex set.
an_element(P::AbstractPointSymmetricPolytope{N})::Vector{N} where {N<:Real}
Return some element of a point symmetric polytope.
Input
P
– point symmetric polytope
Output
The center of the point symmetric polytope.
an_element(S::AbstractSingleton{N})::Vector{N} where {N<:Real}
Return some element of a set with a single value.
Input
S
– set with a single value
Output
The only element in the set.
LazySets.element
— Method.element(S::Singleton{N})::Vector{N} where {N<:Real}
Return the element of a singleton.
Input
S
– singleton
Output
The element of the singleton.
LazySets.element
— Method.element(S::Singleton{N}, i::Int)::N where {N<:Real}
Return the i-th entry of the element of a singleton.
Input
S
– singletoni
– dimension
Output
The i-th entry of the element of the singleton.
ZeroSet
LazySets.ZeroSet
— Type.ZeroSet{N<:Real} <: AbstractSingleton{N}
Type that represents the zero set, i.e., the set that only contains the origin.
Fields
dim
– the ambient dimension of this zero set
LazySets.dim
— Method.dim(P::AbstractPointSymmetricPolytope)::Int
Return the ambient dimension of a point symmetric set.
Input
P
– set
Output
The ambient dimension of the set.
dim(Z::ZeroSet)::Int
Return the ambient dimension of this zero set.
Input
Z
– a zero set, i.e., a set that only contains the origin
Output
The ambient dimension of the zero set.
LazySets.σ
— Method.σ(d::V, H::AbstractHyperrectangle{N}) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of a hyperrectangular set in a given direction.
Input
d
– directionH
– hyperrectangular set
Output
The support vector in the given direction. If the direction has norm zero, the vertex with biggest values is returned.
σ(d::AbstractVector{N}, S::AbstractSingleton{N})::Vector{N} where {N<:Real}
Return the support vector of a set with a single value.
Input
d
– directionS
– set with a single value
Output
The support vector, which is the set's vector itself, irrespective of the given direction.
σ(d::AbstractVector{N}, Z::ZeroSet)::Vector{N} where {N<:Real}
Return the support vector of a zero set.
Input
Z
– a zero set, i.e., a set that only contains the origin
Output
The returned value is the origin since it is the only point that belongs to this set.
Base.:∈
— Method.∈(x::AbstractVector{N}, H::AbstractHyperrectangle{N})::Bool where {N<:Real}
Check whether a given point is contained in a hyperrectangular set.
Input
x
– point/vectorH
– hyperrectangular set
Output
true
iff $x ∈ H$.
Algorithm
Let $H$ be an $n$-dimensional hyperrectangular set, $c_i$ and $r_i$ be the box's center and radius and $x_i$ be the vector $x$ in dimension $i$, respectively. Then $x ∈ H$ iff $|c_i - x_i| ≤ r_i$ for all $i=1,…,n$.
∈(x::AbstractVector{N}, S::AbstractSingleton{N})::Bool where {N<:Real}
Check whether a given point is contained in a set with a single value.
Input
x
– point/vectorS
– set with a single value
Output
true
iff $x ∈ S$.
Notes
This implementation performs an exact comparison, which may be insufficient with floating point computations.
∈(x::AbstractVector{N}, Z::ZeroSet{N})::Bool where {N<:Real}
Check whether a given point is contained in a zero set.
Input
x
– point/vectorZ
– zero set
Output
true
iff $x ∈ Z$.
Examples
julia> Z = ZeroSet(2);
julia> ∈([1.0, 0.0], Z)
false
julia> ∈([0.0, 0.0], Z)
true
Base.LinAlg.norm
— Method.norm(S::LazySet, [p]::Real=Inf)
Return the norm of a convex set. It is the norm of the enclosing ball (of the given $p$-norm) of minimal volume that is centered in the origin.
Input
S
– convex setp
– (optional, default:Inf
) norm
Output
A real number representing the norm.
norm(H::AbstractHyperrectangle, [p]::Real=Inf)::Real
Return the norm of a hyperrectangular set.
Input
H
– hyperrectangular setp
– (optional, default:Inf
) norm
Output
A real number representing the norm.
Notes
The norm of a hyperrectangular set is defined as the norm of the enclosing ball, of the given $p$-norm, of minimal volume that is centered in the origin.
LazySets.diameter
— Method.diameter(S::LazySet, [p]::Real=Inf)
Return the diameter of a convex set. It 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.
Input
S
– convex setp
– (optional, default:Inf
) norm
Output
A real number representing the diameter.
diameter(H::AbstractHyperrectangle, [p]::Real=Inf)::Real
Return the diameter of a hyperrectangular set.
Input
H
– hyperrectangular setp
– (optional, default:Inf
) norm
Output
A real number representing the diameter.
Notes
The diameter is defined as the maximum distance in the given $p$-norm between any two elements of the set. Equivalently, it is the diameter of the enclosing ball of the given $p$-norm of minimal volume with the same center.
LazySets.vertices_list
— Method.vertices_list(H::AbstractHyperrectangle{N})::Vector{Vector{N}} where {N<:Real}
Return the list of vertices of a hyperrectangular set.
Input
H
– hyperrectangular set
Output
A list of vertices.
Notes
For high dimensions, it is preferable to develop a vertex_iterator
approach.
vertices_list(S::AbstractSingleton{N})::Vector{Vector{N}} where {N<:Real}
Return the list of vertices of a set with a single value.
Input
S
– set with a single value
Output
A list containing only a single vertex.
LazySets.singleton_list
— Method.singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}
Return the vertices of a polytopic as a list of singletons.
Input
P
– a polytopic set
Output
List containing a singleton for each vertex.
LazySets.center
— Method.center(S::AbstractSingleton{N})::Vector{N} where {N<:Real}
Return the center of a set with a single value.
Input
S
– set with a single value
Output
The only element of the set.
LazySets.radius_hyperrectangle
— Method.radius_hyperrectangle(S::AbstractSingleton{N})::Vector{N} where {N<:Real}
Return the box radius of a set with a single value in every dimension.
Input
S
– set with a single value
Output
The zero vector.
LazySets.radius_hyperrectangle
— Method.radius_hyperrectangle(S::AbstractSingleton{N}, i::Int)::N where {N<:Real}
Return the box radius of a set with a single value in a given dimension.
Input
S
– set with a single value
Output
Zero.
LazySets.an_element
— Method.an_element(S::LazySet{N}) where {N<:Real}
Return some element of a convex set.
Input
S
– convex set
Output
An element of a convex set.
an_element(P::AbstractPointSymmetricPolytope{N})::Vector{N} where {N<:Real}
Return some element of a point symmetric polytope.
Input
P
– point symmetric polytope
Output
The center of the point symmetric polytope.
an_element(S::AbstractSingleton{N})::Vector{N} where {N<:Real}
Return some element of a set with a single value.
Input
S
– set with a single value
Output
The only element in the set.
LazySets.element
— Method.element(S::ZeroSet{N})::Vector{N} where {N<:Real}
Return the element of a zero set.
Input
S
– zero set
Output
The element of the zero set, i.e., a zero vector.
LazySets.element
— Method.element(S::ZeroSet{N}, ::Int)::N where {N<:Real}
Return the i-th entry of the element of a zero set.
Input
S
– zero seti
– dimension
Output
The i-th entry of the element of the zero set, i.e., 0.
LazySets.linear_map
— Method.linear_map(M::AbstractMatrix, P::AbstractPolytope{N}) where {N<:Real}
Concrete linear map of an abstract polytype.
Input
M
– matrixP
– abstract polytype
Output
The polytope in V-representation obtained by applying the linear map $M$ to the set $P$. If the given polytope is two-dimensional, a polygon instead of a general polytope is returned.
linear_map(M::AbstractMatrix, S::AbstractSingleton{N}) where {N<:Real}
Concrete linear map of an abstract singleton.
Input
M
– matrixS
– abstract singleton
Output
The abstract singleton of the same type of $S$ obtained by applying the linear map to the element in $S$.
linear_map(M::AbstractMatrix, Z::ZeroSet{N}) where {N<:Real}
Concrete linear map of a zero set.
Input
M
– matrixZ
– zero set
Output
The zero set whose dimension matches the output dimension of the given matrix.
Zonotopes
LazySets.Zonotope
— Type.Zonotope{N<:Real} <: AbstractPointSymmetricPolytope{N}
Type that represents a zonotope.
Fields
center
– center of the zonotopegenerators
– matrix; each column is a generator of the zonotope
Notes
Mathematically, a zonotope is defined as the set
where $c \in \mathbb{R}^n$ is its center and $\{g_i\}_{i=1}^p$, $g_i \in \mathbb{R}^n$, is the set of generators. This characterization defines a zonotope as the finite Minkowski sum of line elements. Zonotopes can be equivalently described as the image of a unit infinity-norm ball in $\mathbb{R}^n$ by an affine transformation.
Zonotope(center::AbstractVector{N}, generators::AbstractMatrix{N}) where {N<:Real}
Zonotope(center::AbstractVector{N}, generators_list::AbstractVector{T} ) where {N<:Real, T<:AbstractVector{N}}
Examples
A two-dimensional zonotope with given center and set of generators:
julia> Z = Zonotope([1.0, 0.0], 0.1*eye(2))
LazySets.Zonotope{Float64}([1.0, 0.0], [0.1 0.0; 0.0 0.1])
julia> dim(Z)
2
Compute its vertices:
julia> vertices_list(Z)
4-element Array{Array{Float64,1},1}:
[0.9, -0.1]
[1.1, -0.1]
[1.1, 0.1]
[0.9, 0.1]
Evaluate the support vector in a given direction:
julia> σ([1., 1.], Z)
2-element Array{Float64,1}:
1.1
0.1
Alternative constructor: A zonotope in two dimensions with three generators:
julia> Z = Zonotope(ones(2), [[1., 0.], [0., 1.], [1., 1.]])
LazySets.Zonotope{Float64}([1.0, 1.0], [1.0 0.0 1.0; 0.0 1.0 1.0])
julia> Z.generators
2×3 Array{Float64,2}:
1.0 0.0 1.0
0.0 1.0 1.0
LazySets.dim
— Method.dim(P::AbstractPointSymmetricPolytope)::Int
Return the ambient dimension of a point symmetric set.
Input
P
– set
Output
The ambient dimension of the set.
LazySets.σ
— Method.σ(d::V, Z::Zonotope) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of a zonotope in a given direction.
Input
d
– directionZ
– zonotope
Output
Support vector in the given direction. If the direction has norm zero, the vertex with $ξ_i = 1 \ \ ∀ i = 1,…, p$ is returned.
Base.:∈
— Method.∈(x::AbstractVector{N}, Z::Zonotope{N};
solver=GLPKSolverLP(method=:Simplex))::Bool where {N<:Real}
Check whether a given point is contained in a zonotope.
Input
x
– point/vectorZ
– zonotopesolver
– (optional, default:GLPKSolverLP(method=:Simplex)
) the backend used to solve the linear program
Output
true
iff $x ∈ Z$.
Examples
julia> Z = Zonotope([1.0, 0.0], 0.1*eye(2));
julia> ∈([1.0, 0.2], Z)
false
julia> ∈([1.0, 0.1], Z)
true
Algorithm
The element membership problem is computed by stating and solving the following linear program with the simplex method. Let $p$ and $n$ be the number of generators and ambient dimension respectively. We consider the minimization of $x_0$ in the $p+1$-dimensional space of elements $(x_0, ξ_1, …, ξ_p)$ constrained to $0 ≤ x_0 ≤ ∞$, $ξ_i ∈ [-1, 1]$ for all $i = 1, …, p$, and such that $x-c = Gξ$ holds. If a feasible solution exists, the optimal value $x_0 = 0$ is achieved.
Notes
This function is parametric in the number type N
. For exact arithmetic use an appropriate backend, e.g. solver=GLPKSolverLP(method=:Exact)
.
LazySets.an_element
— Method.an_element(S::LazySet{N}) where {N<:Real}
Return some element of a convex set.
Input
S
– convex set
Output
An element of a convex set.
an_element(P::AbstractPointSymmetricPolytope{N})::Vector{N} where {N<:Real}
Return some element of a point symmetric polytope.
Input
P
– point symmetric polytope
Output
The center of the point symmetric polytope.
LazySets.center
— Method.center(Z::Zonotope{N})::Vector{N} where {N<:Real}
Return the center of a zonotope.
Input
Z
– zonotope
Output
The center of the zonotope.
LazySets.vertices_list
— Method.vertices_list(Z::Zonotope{N})::Vector{Vector{N}} where {N<:Real}
Return the vertices of a zonotope.
Input
Z
– zonotope
Output
List of vertices.
Notes
This implementation computes a convex hull.
For high dimensions, it would be preferable to develop a vertex_iterator
approach.
LazySets.singleton_list
— Method.singleton_list(P::AbstractPolytope{N})::Vector{Singleton{N}} where {N<:Real}
Return the vertices of a polytopic as a list of singletons.
Input
P
– a polytopic set
Output
List containing a singleton for each vertex.
LazySets.order
— Method.order(Z::Zonotope)::Rational
Return the order of a zonotope.
Input
Z
– zonotope
Output
A rational number representing the order of the zonotope.
Notes
The order of a zonotope is defined as the quotient of its number of generators and its dimension.
LazySets.minkowski_sum
— Method.minkowski_sum(Z1::Zonotope, Z2::Zonotope)
Concrete Minkowski sum of a pair of zonotopes.
Input
Z1
– one zonotopeZ2
– another zonotope
Output
The zonotope obtained by summing the centers and concatenating the generators of $Z_1$ and $Z_2$.
LazySets.linear_map
— Method.linear_map(M::AbstractMatrix, Z::Zonotope)
Concrete linear map of a zonotope.
Input
M
– matrixZ
– zonotope
Output
The zonotope obtained by applying the linear map to the center and generators of $Z$.
LazySets.scale
— Method.scale(α::Real, Z::Zonotope)
Concrete scaling of a zonotope.
Input
α
– scalarZ
– zonotope
Output
The zonotope obtained by applying the numerical scale to the center and generators of $Z$.
LazySets.ngens
— Method.ngens(Z::Zonotope)::Int
Return the number of generators of a zonotope.
Input
Z
– zonotope
Output
Integer representing the number of generators.
LazySets.reduce_order
— Method.reduce_order(Z::Zonotope, r)::Zonotope
Reduce the order of a zonotope by overapproximating with a zonotope with less generators.
Input
Z
– zonotoper
– desired order
Output
A new zonotope with less generators, if possible.
Algorithm
This function implements the algorithm described in A. Girard's Reachability of Uncertain Linear Systems Using Zonotopes, HSCC. Vol. 5. 2005.