Common Set Representations

Ball2{N<:AbstractFloat} <: AbstractPointSymmetric{N}

Type that represents a ball in the 2-norm.

Fields

• center – center of the ball as a real vector

• radius – 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

dim(S::AbstractPointSymmetric)::Int

Return the ambient dimension of a point symmetric set.

Input

• S – set

Output

The ambient dimension of the set.

σ(d::AbstractVector{N}, B::Ball2)::AbstractVector{<:AbstractFloat} where {N<:AbstractFloat}

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

Input

• d – direction

• B – 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.

∈(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/vector

• B – 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

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.

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.

BallInf{N<:Real} <: AbstractHyperrectangle{N}

Type that represents a ball in the infinity norm.

Fields

• center – center of the ball as a real vector

• radius – 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

dim(P::AbstractPointSymmetricPolytope)::Int

Return the ambient dimension of a point symmetric set.

Input

• P – set

Output

The ambient dimension of the set.

σ(d::AbstractVector{N}, H::AbstractHyperrectangle{N}
 )::AbstractVector{N} where {N<:Real}

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

Input

• d – direction

• H – hyperrectangular set

Output

The support vector in the given direction. If the direction has norm zero, the vertex with biggest values is returned.

∈(x::AbstractVector{N}, H::AbstractHyperrectangle{N})::Bool where {N<:Real}

Check whether a given point is contained in a hyperrectangular set.

Input

• x – point/vector

• H – 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$.

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.

norm(H::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the norm of a hyperrectangular set.

Input

• H – hyperrectangular set

• p – (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.

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 set

• p – (optional, default: Inf) norm

Output

A real number representing the norm.

radius(H::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the radius of a hyperrectangular set.

Input

• H – hyperrectangular set

• p – (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 norm

• p – (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.

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 set

• p – (optional, default: Inf) norm

Output

A real number representing the radius.

diameter(H::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the diameter of a hyperrectangular set.

Input

• H – hyperrectangular set

• p – (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.

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 set

• p – (optional, default: Inf) norm

Output

A real number representing the diameter.

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.

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.

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.

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.

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.

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 vector

• radius – 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

dim(P::AbstractPointSymmetricPolytope)::Int

Return the ambient dimension of a point symmetric set.

Input

• P – set

Output

The ambient dimension of the set.

σ(d::AbstractVector{N}, B::Ball1)::AbstractVector{N} where {N<:Real}

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

Input

• d – direction

• B – ball in the 1-norm

Output

Support vector in the given direction.

∈(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/vector

• B – 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

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.

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.

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.

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.

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 scalar

• center – center of the ball as a real vector

• radius – 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.:5, B)
5-element Array{Float64,1}:
 0.013516
 0.054064
 0.121644
 0.216256
 0.3379

dim(S::AbstractPointSymmetric)::Int

Return the ambient dimension of a point symmetric set.

Input

• S – set

Output

The ambient dimension of the set.

σ(d::AbstractVector{N}, B::Ballp)::AbstractVector{N} where {N<:AbstractFloat}

Return the support vector of a Ballp in a given direction.

Input

• d – direction

• B – ball in the p-norm

Output

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

Algorithm

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

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

∈(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/vector

• B – 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

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.

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{N<:Real} <:  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.

Fields

• center – center of the ellipsoid

• shape 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])

σ(d::AbstractVector{N},
           E::Ellipsoid{N})::AbstractVector{<:AbstractFloat} where {N<:AbstractFloat}

Return the support vector of an ellipsoid in a given direction.

Input

• d – direction

• E – 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,

center(E::Ellipsoid{N})::Vector{N} where {N<:AbstractFloat}

Return the center of the ellipsoid.

Input

• E – ellipsoid

Output

The center of the ellipsoid.

∈(x::AbstractVector{N}, E::Ellipsoid{N})::Bool where {N<:AbstractFloat}

Check whether a given point is contained in an ellipsoid.

Input

• x – point/vector

• E – 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{N<:Real} <: LazySet{N}

Type that represents the empty set, i.e., the set with no elements.

∅

An EmptySet instance of type Float64.

dim(∅::EmptySet)

Return the dimension of the empty set, which is -1 by convention.

Input

• ∅ – an empty set

Output

-1 by convention.

σ(d, ∅)

Return the support vector of an empty set.

Input

• ∅ – an empty set

Output

An error.

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

an_element(∅::EmptySet)

Return some element of an empty set.

Input

• ∅ – empty set

Output

An error.

HalfSpace{N<:Real} <: LazySet{N}

Type that represents a (closed) half-space of the form $a⋅x ≤ b$.

Fields

• a – normal direction

• b – constraint

Examples

The set $y ≥ 0$ in the plane:

julia> HalfSpace([0, -1.], 0.)
LazySets.HalfSpace{Float64}([0.0, -1.0], 0.0)

dim(hs::HalfSpace)::Int

Return the dimension of a half-space.

Input

• hs – half-space

Output

The ambient dimension of the half-space.

σ(d::AbstractVector{<:Real}, hs::HalfSpace)::AbstractVector{<:Real}

Return the support vector of a half-space.

Input

• d – direction

• hs – half-space

Output

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

1. The direction has norm zero.

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

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.

∈(x::AbstractVector{N}, hs::HalfSpace{N})::Bool where {N<:Real}

Check whether a given point is contained in a half-space.

Input

• x – point/vector

• hs – half-space

Output

true iff $x ∈ hs$.

Algorithm

We just check if $x$ satisfies $a⋅x ≤ b$.

Hyperplane{N<:Real} <: LazySet{N}

Type that represents a hyperplane of the form $a⋅x = b$.

Fields

• a – normal direction

• b – constraint

Examples

The plane $y = 0$:

julia> Hyperplane([0, 1.], 0.)
LazySets.Hyperplane{Float64}([0.0, 1.0], 0.0)

dim(hp::Hyperplane)::Int

Return the dimension of a hyperplane.

Input

• hp – hyperplane

Output

The ambient dimension of the hyperplane.

σ(d::AbstractVector{<:Real}, hp::Hyperplane)::AbstractVector{<:Real}

Return the support vector of a hyperplane.

Input

• d – direction

• hp – hyperplane

Output

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

1. The direction has norm zero.

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

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.

∈(x::AbstractVector{N}, hp::Hyperplane{N})::Bool where {N<:Real}

Check whether a given point is contained in a hyperplane.

Input

• x – point/vector

• hp – hyperplane

Output

true iff $x ∈ hp$.

Algorithm

We just check if $x$ satisfies $a⋅x = b$.

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 vector

• radius – radius of the ball as a real vector, i.e., half of its width along each coordinate direction

Hyperrectangle(;kwargs...)

Construct a hyperrectangle from keyword arguments.

Input

• kwargs – keyword arguments; two combinations are allowed:

  1. center, radius – vectors

  2. high, low – vectors (if both center and radius 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])

dim(P::AbstractPointSymmetricPolytope)::Int

Return the ambient dimension of a point symmetric set.

Input

• P – set

Output

The ambient dimension of the set.

σ(d::AbstractVector{N}, H::AbstractHyperrectangle{N}
 )::AbstractVector{N} where {N<:Real}

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

Input

• d – direction

• H – hyperrectangular set

Output

The support vector in the given direction. If the direction has norm zero, the vertex with biggest values is returned.

∈(x::AbstractVector{N}, H::AbstractHyperrectangle{N})::Bool where {N<:Real}

Check whether a given point is contained in a hyperrectangular set.

Input

• x – point/vector

• H – 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$.

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.

norm(H::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the norm of a hyperrectangular set.

Input

• H – hyperrectangular set

• p – (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.

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 set

• p – (optional, default: Inf) norm

Output

A real number representing the norm.

radius(H::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the radius of a hyperrectangular set.

Input

• H – hyperrectangular set

• p – (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(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 set

• p – (optional, default: Inf) norm

Output

A real number representing the radius.

diameter(H::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the diameter of a hyperrectangular set.

Input

• H – hyperrectangular set

• p – (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.

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 set

• p – (optional, default: Inf) norm

Output

A real number representing the diameter.

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.

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.

center(H::Hyperrectangle{N})::Vector{N} where {N<:Real}

Return the center of a hyperrectangle.

Input

• H – hyperrectangle

Output

The center of the hyperrectangle.

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.

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.

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.

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.

LinearConstraint{N<:Real}

Type that represents a linear constraint (a half-space) of the form $a⋅x ≤ b$.

Fields

• a – normal direction

• b – constraint

Examples

The set $y ≥ 0$ in the plane:

julia> LinearConstraint([0, -1.], 0.)
LazySets.LinearConstraint{Float64}([0.0, -1.0], 0.0)

Line{N<:Real}

Type that represents a line in 2D of the form $a⋅x = b$.

Fields

• a – normal direction

• b – constraint

Examples

The line $y = -x + 1$:

julia> Line([1., 1.], 1.)
LazySets.Line{Float64}([1.0, 1.0], 1.0)

intersection(L1::Line{N}, L2::Line{N})::Vector{N} where {N<:Real}

Return the intersection of two 2D lines.

Input

• L1 – first line

• L2 – second line

Output

If the lines are parallel or identical, the result is an empty vector. Otherwise the result is the only intersection point.

Examples

The line $y = -x + 1$ intersected with the line $y = x$:

julia> intersection(Line([-1., 1.], 0.), Line([1., 1.], 1.))
2-element Array{Float64,1}:
 0.5
 0.5
julia> intersection(Line([1., 1.], 1.), Line([1., 1.], 1.))
0-element Array{Float64,1}

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 – 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_list::Vector{LinearConstraint{<:Real}}) – default constructor

• HPolygon() – constructor with no constraints

dim(P::AbstractPolygon)::Int

Return the ambient dimension of a polygon.

Input

• P – polygon

Output

The ambient dimension of the polygon, which is 2.

σ(d::AbstractVector{<:Real}, P::HPolygon{N})::Vector{N} where {N<:Real}

Return the support vector of a polygon in a given direction.

Input

• d – direction

• P – 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.

∈(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/vector

• P – polygon in constraint representation

Output

true iff $x ∈ P$.

Algorithm

This implementation checks if the point lies on the outside of each edge.

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

vertices_list(P::AbstractHPolygon{N})::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a polygon in constraint representation.

Input

• P – polygon in constraint representation

Output

List of vertices.

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.

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.

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.

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 representation

• constraint – linear constraint to add

Output

Nothing.

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 – list of linear constraints

• ind – 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_list::Vector{LinearConstraint{<:Real}}, ind::Int) – default constructor

• HPolygonOpt(constraints_list::Vector{LinearConstraint{<:Real}}) – constructor without index

• HPolygonOpt(H::HPolygon{<:Real}) – constructor from an HPolygon

dim(P::AbstractPolygon)::Int

Return the ambient dimension of a polygon.

Input

• P – polygon

Output

The ambient dimension of the polygon, which is 2.

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

• P – 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.

∈(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/vector

• P – polygon in constraint representation

Output

true iff $x ∈ P$.

Algorithm

This implementation checks if the point lies on the outside of each edge.

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

vertices_list(P::AbstractHPolygon{N})::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a polygon in constraint representation.

Input

• P – polygon in constraint representation

Output

List of vertices.

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.

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.

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.

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 representation

• constraint – linear constraint to add

Output

Nothing.

VPolygon{N<:Real} <: AbstractPolygon{N}

Type that represents a polygon by its vertices.

Fields

• vertices_list – 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_list::Vector{Vector{N}}; apply_convex_hull::Bool=true, algorithm::String="monotone_chain")

dim(P::AbstractPolygon)::Int

Return the ambient dimension of a polygon.

Input

• P – polygon

Output

The ambient dimension of the polygon, which is 2.

σ(d::AbstractVector{<:Real}, P::VPolygon{N})::Vector{N} where {N<:Real}

Return the support vector of a polygon in a given direction.

Input

• d – direction

• P – 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.

∈(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/vector

• P – 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

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.

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.

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.

tohrep(P::VPolygon{N})::AbstractHPolygon{N} where {N<:Real}

Build a constraint representation of the given polygon.

Input

• P – polygon in vertex representation

Output

The same polygon but in constraint representation, an AbstractHPolygon.

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.

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> jump2pi(0.0)
0.0
julia> jump2pi(-0.5)
5.783185307179586
julia> jump2pi(0.5)
0.5

<=(u::AbstractVector{N}, v::AbstractVector{N})::Bool where {N<:AbstractFloat}

Compares two 2D vectors by their direction.

Input

• u – first 2D direction

• v – 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 direction

• v – 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.

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?

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.

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

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-representation

• constraint – 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.

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.

σ(d::AbstractVector{<:Real}, P::HPolytope)::Vector{<:Real}

Return the support vector of a polyhedron (in H-representation) in a given direction.

Input

• d – direction

• P – polyhedron in H-representation

Output

The support vector in the given direction.

Algorithm

This implementation uses GLPKSolverLP as linear programming backend.

∈(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/vector

• P – 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.

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

dim(P::AbstractPointSymmetricPolytope)::Int

Return the ambient dimension of a point symmetric set.

Input

• P – set

Output

The ambient dimension of the set.

σ(d::AbstractVector{N}, H::AbstractHyperrectangle{N}
 )::AbstractVector{N} where {N<:Real}

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

Input

• d – direction

• H – 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 – direction

• S – set with a single value

Output

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

∈(x::AbstractVector{N}, H::AbstractHyperrectangle{N})::Bool where {N<:Real}

Check whether a given point is contained in a hyperrectangular set.

Input

• x – point/vector

• H – 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/vector

• S – 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.

norm(H::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the norm of a hyperrectangular set.

Input

• H – hyperrectangular set

• p – (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.

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 set

• p – (optional, default: Inf) norm

Output

A real number representing the norm.

diameter(H::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the diameter of a hyperrectangular set.

Input

• H – hyperrectangular set

• p – (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.

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 set

• p – (optional, default: Inf) norm

Output

A real number representing the diameter.

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.

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.

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.

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.

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.

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.

element(S::Singleton{N})::Vector{N} where {N<:Real}

Return the element of a singleton.

Input

• S – singleton

Output

The element of the singleton.

element(S::Singleton{N}, i::Int)::N where {N<:Real}

Return the i-th entry of the element of a singleton.

Input

• S – singleton

• i – dimension

Output

The i-th entry of the element of the singleton.

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

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.

σ(d::AbstractVector{N}, H::AbstractHyperrectangle{N}
 )::AbstractVector{N} where {N<:Real}

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

Input

• d – direction

• H – 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 – direction

• S – 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.

∈(x::AbstractVector{N}, H::AbstractHyperrectangle{N})::Bool where {N<:Real}

Check whether a given point is contained in a hyperrectangular set.

Input

• x – point/vector

• H – 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/vector

• S – 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/vector

• Z – 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

norm(H::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the norm of a hyperrectangular set.

Input

• H – hyperrectangular set

• p – (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.

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 set

• p – (optional, default: Inf) norm

Output

A real number representing the norm.

diameter(H::AbstractHyperrectangle, [p]::Real=Inf)::Real

Return the diameter of a hyperrectangular set.

Input

• H – hyperrectangular set

• p – (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.

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 set

• p – (optional, default: Inf) norm

Output

A real number representing the diameter.

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.

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.

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.

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.

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.

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.

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.

element(S::ZeroSet{N}, ::Int)::N where {N<:Real}

Return the i-th entry of the element of a zero set.

Input

• S – zero set

• i – dimension

Output

The i-th entry of the element of the zero set, i.e., 0.

Zonotope{N<:Real} <: AbstractPointSymmetricPolytope{N}

Type that represents a zonotope.

Fields

• center – center of the zonotope

• generators – 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

dim(P::AbstractPointSymmetricPolytope)::Int

Return the ambient dimension of a point symmetric set.

Input

• P – set

Output

The ambient dimension of the set.

σ(d::AbstractVector{<:Real}, Z::Zonotope)::AbstractVector{<:Real}

Return the support vector of a zonotope in a given direction.

Input

• d – direction

• Z – zonotope

Output

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

∈(x::AbstractVector{N}, Z::Zonotope{N})::Bool where {N<:Real}

Check whether a given point is contained in a zonotope.

Input

• x – point/vector

• Z – zonotope

Output

true iff $x ∈ Z$.

Algorithm

This implementation poses the problem as a linear equality system and solves it using Base.:. A zonotope centered in the origin with generators $g_i$ contains a point $x$ iff $x = ∑_{i=1}^p ξ_i g_i$ for some $ξ_i \in [-1, 1]~~ ∀ i = 1,…, p$. Thus, we first ask for a solution and then check if it is in this Cartesian product of intervals.

Other algorithms exist which test the feasibility of an LP.

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

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.

center(Z::Zonotope{N})::Vector{N} where {N<:Real}

Return the center of a zonotope.

Input

• Z – zonotope

Output

The center of the zonotope.

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.

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.

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.

minkowski_sum(Z1::Zonotope, Z2::Zonotope)

Concrete Minkowski sum of a pair of zonotopes.

Input

• Z1 – one zonotope

• Z2 – another zonotope

Output

The zonotope obtained by summing the centers and concatenating the generators of $Z_1$ and $Z_2$.

linear_map(M::AbstractMatrix, Z::Zonotope)

Concrete linear map of a zonotopes.

Input

• M – matrix

• Z – zonotope

Output

The zonotope obtained by applying the linear map to the center and generators of $Z$.

scale(α::Real, Z::Zonotope)

Concrete scaling of a zonotope.

Input

• α – scalar

• Z – zonotope

Output

The zonotope obtained by applying the numerical scale to the center and generators of $Z$.