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)
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.06741998624632421
 0.13483997249264842
 0.20225995873897262
 0.26967994498529685
 0.3370999312316211

σ(d::AbstractVector{N}, B::Ball2{N}) 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))
Ball2{Float64}([1.0, 1.0], 0.7071067811865476)
julia> ∈([.5, 1.6], B)
false
julia> ∈([.5, 1.5], B)
true

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)
BallInf{Float64}([0.0, 0.0], 1.0)
julia> dim(B)
2
julia> ρ([1., 1.], B)
2.0

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

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

σ(d::AbstractVector{N}, B::Ball1{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

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.

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)
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.013516004434607558
 0.05406401773843023
 0.12164403991146802
 0.21625607095372093
 0.33790011086518895

σ(d::AbstractVector{N}, B::Ballp{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.)
Ballp{Float64}(1.5, [1.0, 1.0], 1.0)
julia> ∈([.5, -.5], B)
false
julia> ∈([.5, 1.5], B)
true

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<: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 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(Matrix{Float64}(I, 3, 3))
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.5773502691896258
 0.5773502691896258
 0.5773502691896258

A two-dimensional ellipsoid with given center and shape matrix:

julia> E = Ellipsoid(ones(2), Diagonal([2.0, 0.5]))
Ellipsoid{Float64}([1.0, 1.0], [2.0 0.0; 0.0 0.5])

σ(d::AbstractVector{N}, E::Ellipsoid{N}) 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,

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

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

Return the center of the ellipsoid.

Input

• E – ellipsoid

Output

The center of the ellipsoid.

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::AbstractVector{N}, ∅::EmptySet{N}) where {N<:Real}

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.

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.

norm(S::EmptySet, [p]::Real=Inf)

Return the norm of an empty 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 – empty set

• p – (optional, default: Inf) norm

Output

An error.

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.

radius(S::EmptySet, [p]::Real=Inf)

Return the radius of an empty set. It is the radius of the enclosing ball (of the given $p$-norm) of minimal volume with the same center.

Input

• S – empty set

• p – (optional, default: Inf) norm

Output

An error.

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.

diameter(S::EmptySet, [p]::Real=Inf)

Return the diameter of an empty 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 – empty set

• p – (optional, default: Inf) norm

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.)
HalfSpace{Float64}([0.0, -1.0], 0.0)

LinearConstraint

Alias for HalfSpace

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{N}, hs::HalfSpace{N}) where {N<: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.

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

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.

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 point

• q – 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])
HalfSpace{Float64}([0.0, -1.0], 0.0)

julia> halfspace_left([0.0, 0.0], [-1.0, 0.0])
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

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 point

• q – 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{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.)
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{N}, hp::Hyperplane{N}) where {N<: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.

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

an_element(hp::Hyperplane{N})::Vector{N} where {N<:Real}

Return some element of a hyperplane.

Input

• hp – hyperplane

Output

An element on the hyperplane.

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

Examples

There is also a constructor from lower and upper bounds with keyword arguments high and low. The following two 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> Hyperrectangle(c, r)
Hyperrectangle{Float64}([1.0, 1.0], [0.1, 0.2])
julia> Hyperrectangle(low=l, high=h)
Hyperrectangle{Float64}([1.0, 1.0], [0.1, 0.2])

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.

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.

We can create intervals in different ways, the simpler way is to pass a pair of numbers:

julia> x = Interval(0.0, 1.0)
Interval{Float64,IntervalArithmetic.Interval{Float64}}([0, 1])

or a 2-vector:

julia> x = Interval([0.0, 1.0])
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 = Interval(IntervalArithmetic.Interval(0.0, 1.0))
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)
Interval{Rational{Int64},IntervalArithmetic.AbstractInterval{Rational{Int64}}}([0//1, 2//1])

dim(x::Interval)::Int

Return the ambient dimension of an interval.

Input

• x – interval

Output

The integer 1.

σ(d::AbstractVector{N}, x::Interval{N}) where {N<:Real}

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

Input

• d – direction

• x – interval

Output

Support vector in the given direction.

∈(v::AbstractVector, x::Interval)

Return whether a vector is contained in the interval.

Input

• v – one-dimensional vector

• x – interval

Output

true iff x contains v's first component.

∈(v::N, x::Interval) where {N}

Return whether a number is contained in the interval.

Input

• v – scalar

• x – interval

Output

true iff x contains v.

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(x::Interval{N})::Vector{N} where {N<:Real}

Return some element of an interval.

Input

• x – interval

Output

The left border (low(x)) of the interval.

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.

center(x::Interval)

Return the interval's center.

Input

• x – interval

Output

The center, or midpoint, of $x$.

low(x::Interval)

Return the lower component of an interval.

Input

• x – interval

Output

The lower (lo) component of the interval.

high(x::Interval)

Return the higher or upper component of an interval.

Input

• x – interval

Output

The higher (hi) component of the interval.

+(x::Interval, y::Interval)

Return the sum of the intervals.

Input

• x – interval

• y – interval

Output

The sum of the intervals as a new Interval set.

-(x::Interval, y::Interval)

Return the difference of the intervals.

Input

• x – interval

• y – interval

Output

The difference of the intervals as a new Interval set.

    *(x::Interval, y::Interval)

Return the product of the intervals.

Input

• x – interval

• y – interval

Output

The product of the intervals as a new Interval set.

Line{N<:Real} <: LazySet{N}

Type that represents a line in 2D of the form $a⋅x = b$ (i.e., a special case of a Hyperplane).

Fields

• a – normal direction

• b – constraint

Examples

The line $y = -x + 1$:

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

dim(L::Line)::Int

Return the ambient dimension of a line.

Input

• L – line

Output

The ambient dimension of the line, which is 2.

σ(d::AbstractVector{N}, L::Line{N}) where {N<:Real}

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

Input

• d – direction

• L – line

Output

The support vector in the given direction, which is defined the same way as for the more general Hyperplane.

∈(x::AbstractVector{N}, L::Line{N})::Bool where {N<:Real}

Check whether a given point is contained in a line.

Input

• x – point/vector

• L – line

Output

true iff x ∈ L.

Algorithm

The point $x$ belongs to the line if and only if $a⋅x = b$ holds.

an_element(L::Line{N})::Vector{N} where N<:Real

Return some element of a line.

Input

• L – line

Output

An element on the line.

Algorithm

If the $b$ value of the line is zero, the result is the origin. Otherwise the result is some $x = [x1, x2]$ such that $a·[x1, x2] = b$. We first find out in which dimension $a$ is nonzero, say, dimension 1, and then choose $x1 = 1$ and accordingly $x2 = \frac{b - a1}{a2}$.

LineSegment{N<:Real} <: AbstractPointSymmetricPolytope{N}

Type that represents a line segment in 2D between two points $p$ and $q$.

Fields

• p – first point

• q – second point

Examples

A line segment along the $x = y$ diagonal:

julia> s = LineSegment([0., 0], [1., 1.])
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.])
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])

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.

σ(d::AbstractVector{N}, L::LineSegment{N}) where {N<:Real}

Return the support vector of a line segment in a given direction.

Input

• d – direction

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

∈(x::AbstractVector{N}, L::LineSegment{N})::Bool where {N<:Real}

Check whether a given point is contained in a line segment.

Input

• x – point/vector

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

1. A necessary condition for $x ∈ (p, q)$ is that the three points are aligned, thus their cross product should be zero.

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

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.

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.

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 constructor

• HPolygon() – constructor with no constraints

• HPolygon(S::LazySet) – constructor from another set

σ(d::AbstractVector{N}, P::HPolygon{N};
  [linear_search]::Bool=(length(P.constraints) < BINARY_SEARCH_THRESHOLD)
 ) where {N<:Real}

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

Input

• d – direction

• P – polygon in constraint representation

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

Output

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

Algorithm

Comparison of directions is performed using polar angles; see the overload of <= for two-dimensional vectors.

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

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 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::Vector{LinearConstraint{<:Real}}, [ind]::Int) – default constructor with optional index

• HPolygonOpt(S::LazySet) – constructor from another set

σ(d::AbstractVector{N}, P::HPolygonOpt{N};
  [linear_search]::Bool=(length(P.constraints) < BINARY_SEARCH_THRESHOLD)
 ) where {N<:Real}

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

Input

• d – direction

• P – optimized polygon in constraint representation

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

Output

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

Algorithm

Comparison of directions is performed using polar angles; see the overload of <= for two-dimensional vectors.

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

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

σ(d::AbstractVector{N}, P::VPolygon{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.

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 representation

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

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> import LazySets.jump2pi

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

<=(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, atan, which for two arguments implements the atan2 function.

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

σ(d::AbstractVector{N}, P::HPolytope{N}) where {N<: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.

addconstraint!(P::HPolytope{N},
               constraint::LinearConstraint{N})::Nothing 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.

tosimplehrep(P::HPolytope)

Return the simple H-representation $Ax ≤ b$ of a polytope.

Input

• P – polytope

Output

The tuple (A, b) where A is the matrix of normal directions and b are the offsets.

VPolytope{N<:Real} <: AbstractPolytope{N}

Type that represents a convex polytope in V-representation.

Fields

• vertices – the list of vertices

dim(P::VPolytope)::Int

Return the dimension of a polytope in V-representation.

Input

• P – polytope in V-representation

Output

The ambient dimension of the polytope in V-representation. If it is empty, the result is $-1$.

Examples

julia> v = VPolytope();

julia> dim(v) > 0
false

julia> v = VPolytope([ones(3)])
VPolytope{Float64}(Array{Float64,1}[[1.0, 1.0, 1.0]])

julia> dim(v) == 3
true

σ(d::AbstractVector{N}, P::VPolytope{N}; algorithm="hrep") where {N<:Real}

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

Input

• d – direction

• P – polyhedron in V-representation

• algorithm – (optional, default: 'hrep') method to compute the support vector

Output

The support vector in the given direction.

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

Return the list of vertices of a polytope in V-representation.

Input

• P – polytope in vertex representation

Output

List of vertices.

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

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(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}, Z::ZeroSet{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}, 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

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.

linear_map(M::AbstractMatrix, Z::ZeroSet{N}) where {N<:Real}

Concrete linear map of a zero set.

Input

• M – matrix

• Z – zero set

Output

The zero set whose dimension matches the output dimension of the given matrix.

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 0.0; 0.0 0.1])
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.]])
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

σ(d::AbstractVector{N}, Z::Zonotope{N}) where {N<: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};
  solver=GLPKSolverLP(method=:Simplex))::Bool where {N<:Real}

Check whether a given point is contained in a zonotope.

Input

• x – point/vector

• Z – zonotope

• solver – (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 0.0; 0.0 0.1]);

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

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.

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

Return the center of a zonotope.

Input

• Z – zonotope

Output

The center of the zonotope.

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

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

ngens(Z::Zonotope)::Int

Return the number of generators of a zonotope.

Input

• Z – zonotope

Output

Integer representing the number of generators.

reduce_order(Z::Zonotope, r)::Zonotope

Reduce the order of a zonotope by overapproximating with a zonotope with less generators.

Input

• Z – zonotope

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