Line

Line{N, VN<:AbstractVector{N}} <: AbstractPolyhedron{N}

Type that represents a line in the form

\[ \{y ∈ \mathbb{R}^n: y = p + λd, λ ∈ \mathbb{R}\}\]

where $p$ is a point on the line and $d$ is its direction vector (not necessarily normalized).

Fields

• p – point on the line
• d – direction

Examples

The line passing through the point $[-1, 2, 3]$ and parallel to the vector $[3, 0, -1]$:

julia> Line([-1, 2, 3.], [3, 0, -1.])
Line{Float64,Array{Float64,1}}([-1.0, 2.0, 3.0], [3.0, 0.0, -1.0])

dim(L::Line)

Return the ambient dimension of a line.

Input

• L – line

Output

The ambient dimension of the line.

ρ(d::AbstractVector, L::Line)

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

Input

• d – direction
• L – line

Output

The support function in the given direction.

σ(d::AbstractVector, L::Line)

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

Input

• d – direction
• L – line

Output

The support vector in the given direction.

∈(x::AbstractVector, L::Line)

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 $L : p + λd$ if and only if $x - p$ is proportional to the direction $d$.

an_element(L::Line)

Return some element of a line.

Input

• L – line

Output

An element on the line.

direction(L::Line)

Return the direction of the line.

Input

• L – line

Output

The line's field corresponding to the direction to the line.

Notes

The direction is not necessarily normalized. See normalize(::Line, ::Real) / normalize!(::Line, ::Real) for such operation.

rand(::Type{Line}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing)

Create a random line.

Input

• Line – type for dispatch
• N – (optional, default: Float64) numeric type
• dim – (optional, default: 2) dimension
• rng – (optional, default: GLOBAL_RNG) random number generator
• seed – (optional, default: nothing) seed for reseeding

Output

A random line.

Algorithm

All numbers are normally distributed with mean 0 and standard deviation 1.

isbounded(L::Line)

Determine whether a line is bounded.

Input

• L – line

Output

false.

isuniversal(L::Line; [witness::Bool]=false)

Check whether a line is universal.

Input

• P – line
• witness – (optional, default: false) compute a witness if activated

Output

• If witness is false: true if the ambient dimension is one, false otherwise

• If witness is true: (true, []) if the ambient dimension is one, (false, v) where $v ∉ P$ otherwise

isempty(L::Line)

Return if a line is empty or not.

Input

• L – line

Output

false.

constraints_list(H::AbstractHyperrectangle{N}) where {N}

Return the list of constraints of an axis-aligned hyperrectangular set.

Input

• H – hyperrectangular set

Output

A list of linear constraints.

constraints_list(P::Ball1{N}) where {N}

Return the list of constraints defining a ball in the 1-norm.

Input

• B – ball in the 1-norm

Output

The list of constraints of the ball.

Algorithm

The constraints can be defined as $d_i^T (x-c) ≤ r$ for all $d_i$, where $d_i$ is a vector with elements $1$ or $-1$ in $n$ dimensions. To span all possible $d_i$, the function Iterators.product is used.

constraints_list(x::Interval{N}) where {N}

Return the list of constraints of the given interval.

Input

• x – interval

Output

The list of constraints of the interval represented as two one-dimensional half-spaces.

constraints_list(L::Line{N, VN}) where {N, VN}

Return the list of constraints of a line.

Input

• L – line

Output

A list containing 2n-2 half-spaces whose intersection is L, where n is the ambient dimension of L.

constraints_list(U::Universe{N}) where {N}

Return the list of constraints defining a universe.

Input

• U – universe

Output

The empty list of constraints, as the universe is unconstrained.

constraints_list(P::HParallelotope{N, VN}) where {N, VN}

Return the list of constraints of the given parallelotope.

Input

• P – parallelotope in constraint representation

Output

The list of constraints of P.

constraints_list(cpa::CartesianProductArray{N}) where {N}

Return the list of constraints of a (polyhedral) Cartesian product of a finite number of sets.

Input

• cpa – Cartesian product array

Output

A list of constraints.

constraints_list(ia::IntersectionArray{N}) where {N}

Return the list of constraints of an intersection of a finite number of (polyhedral) sets.

Input

• ia – intersection of a finite number of (polyhedral) sets

Output

The list of constraints of the intersection.

Notes

We assume that the underlying sets are polyhedral, i.e., offer a method constraints_list.

Algorithm

We create the polyhedron from the constraints_lists of the sets and remove redundant constraints.

constraints_list(rm::ResetMap{N}) where {N}

Return the list of constraints of a polytopic reset map.

Input

• rm – reset map of a polytope

Output

The list of constraints of the reset map.

Notes

We assume that the underlying set X is a polytope, i.e., is bounded and offers a method constraints_list(X).

Algorithm

We fall back to constraints_list of a LinearMap of the A-matrix in the affine-map view of a reset map. Each reset dimension $i$ is projected to zero, expressed by two constraints for each reset dimension. Then it remains to shift these constraints to the new value.

For instance, if the dimension $5$ was reset to $4$, then there will be constraints $x₅ ≤ 0$ and $-x₅ ≤ 0$. We then modify the right-hand side of these constraints to $x₅ ≤ 4$ and $-x₅ ≤ -4$, respectively.

constraints_list(rm::ResetMap{N, S}) where {N, S<:AbstractHyperrectangle}

Return the list of constraints of a hyperrectangular reset map.

Input

• rm – reset map of a hyperrectangular set

Output

The list of constraints of the reset map.

Algorithm

We iterate through all dimensions. If there is a reset, we construct the corresponding (flat) constraints. Otherwise, we construct the corresponding constraints of the underlying set.

translate(L::Line, v::AbstractVector)

Translate (i.e., shift) a line by a given vector.

Input

• L – line
• v – translation vector

Output

A translated line.

Notes

See also translate! for the in-place version.

translate!(L::Line, v::AbstractVector)

Translate (i.e., shift) a line by a given vector storing the result in L.

Input

• L – line
• v – translation vector

Output

A translated line, modifying L in-place.

normalize(L::Line, p::Real=2.0)

Normalize the direction of a line.

Input

• L – line
• p – (optional, default: 2.0) vector p-norm used in the normalization

Output

A line whose direction has unit norm w.r.t the given p-norm.

Notes

See also normalize!(::Line, ::Real) for the in-place version.

normalize!(L::Line, p::Real=2.0)

Normalize the direction of a line storing the result in L.

Input

• L – line
• p – (optional, default: 2.0) vector p-norm used in the normalization

Output

A line whose direction has unit norm w.r.t the given p-norm.

distance(x::AbstractVector, L::Line, p::Real=2.0)

Compute the distance between point x and the line with respect to the given p-norm.

Input

• x – vector
• L – line
• p – (optional, default: 2.0) the p-norm used; p = 2.0 corresponds to the usual Euclidean norm

Output

A scalar representing the distance between x and the line L.

distance(x::AbstractSingleton, L::Line, p::Real=2.0)

Compute the distance between the singleton x and the line with respect to the given p-norm.

Input

• x – singleton, i.e. a set with one element
• L – line
• p – (optional, default: 2.0) the p-norm used; p = 2.0 corresponds to the usual Euclidean norm

Output

A scalar representing the distance between the element wrapped by x and the line L.

linear_map(M::AbstractMatrix, L::Line)

Concrete linear map of a line.

Input

• M – matrix
• L – line

Output

The line obtained by applying the linear map to the point and direction of L.