Line2D

Line2D{N, VN<:AbstractVector{N}} <: AbstractPolyhedron{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 (non-zero)
• b – constraint

Examples

The line $y = -x + 1$:

julia> Line2D([1., 1.], 1.)
Line2D{Float64, Vector{Float64}}([1.0, 1.0], 1.0)

The alternative constructor takes two 2D points (AbstractVectors) p and q and creates a canonical line from p to q. See the algorithm section below for details.

julia> Line2D([1., 1.], [2., 2])
Line2D{Float64, Vector{Float64}}([-1.0, 1.0], 0.0)

Algorithm

Given two points $p = (x₁, y₁)$ and $q = (x₂, y₂)$, the line that passes through these points is

\[ℓ:~~y - y₁ = \dfrac{(y₂ - y₁)}{(x₂ - x₁)} ⋅ (x-x₁).\]

The particular case $x₂ = x₁$ defines a line parallel to the $y$-axis (vertical line).

an_element(X::LazySet)

Return some element of a nonempty set.

Input

• X – set

Output

An element of X unless X is empty.

Extended help

an_element(L::Line2D)

Algorithm

The algorithm is a 2D specialization of the Hyperplane algorithm.

If the $b$ value of the line is zero, the result is the origin. Otherwise the result is some $x = (x_1, x_2)ᵀ$ such that $a·x = b$. We first find out the dimension $i$ in which $a = (a_1, a_2)ᵀ$ is nonzero and then choose $x_i = \frac{b}{a_i}$ and $x_{3-i} = 0$.

constrained_dimensions(L::Line2D)

Return the indices in which a 2D line is constrained.

Input

• L – 2D line

Output

A vector of ascending indices i such that the line is constrained in dimension i.

Examples

A line with constraint $x_i = 0$ ($i ∈ \{1, 2\}$) is only constrained in dimension $i$.

isuniversal(X::LazySet, witness::Bool=false)

Check whether a set is universal.

Input

• X – set
• witness – (optional, default: false) compute a witness if activated

Output

• If the witness option is deactivated: true iff $X = ℝ^n$
• If the witness option is activated:
  • (true, []) iff $X = ℝ^n$
  • (false, v) iff $X ≠ ℝ^n$ for some $v ∉ X$

Extended help

isuniversal(L::Line2D, [witness]::Bool=false)

Algorithm

Witness production falls back to isuniversal(::Hyperplane).

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

Create a random set of the given set type.

Input

• T – set type
• 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 set of the given set type.

Extended help

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

Algorithm

All numbers are normally distributed with mean 0 and standard deviation 1. Additionally, the constraint a is nonzero.

∈(x::AbstractVector, X::LazySet)

Check whether a point lies in a set.

Input

• x – point/vector
• X – set

Output

true iff $x ∈ X$.

Extended help

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

Algorithm

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

project(x::AbstractVector, L::Line2D)

Project a point onto a 2D line.

Input

• x – point/vector
• L – 2D line

Output

The projection of x onto L.

Algorithm

The projection of $x$ onto a line of the form $a⋅x = b$ is

\[ x - \dfrac{a (a⋅x - b)}{‖a‖²}.\]

translate(X::LazySet, v::AbstractVector)

Compute the translation of a set with a vector.

Input

• X – set
• v – vector

Output

A set representing $X + \{v\}$.

Extended help

translate(L::Line2D, v::AbstractVector; [share]::Bool=false)

Notes

The normal vector of the line (vector a in a⋅x = b) is shared with the original line if share == true.

Algorithm

A line $a⋅x = b$ is transformed to the line $a⋅x = b + a⋅v$. In other words, we add the dot product $a⋅v$ to $b$.

intersection(X::LazySet, Y::LazySet)

Compute the intersection of two sets.

Input

• X – set
• Y – set

Output

A set representing the intersection $X ∩ Y$.

Notes

The intersection of two sets $X$ and $Y$ is defined as

\[ X ∩ Y = \{x \mid x ∈ X \text{ and } x ∈ Y\}.\]

Extended help

intersection(L1::Line2D, L2::Line2D)

Output

Three outcomes are possible:

• If the lines are identical, the result is the first line.
• If the lines are parallel and not identical, the result is the empty set.
• Otherwise the result is the set with the unique intersection point.

Algorithm

We first check whether the lines are parallel. If not, we use Cramer's rule to compute the intersection point.

Examples

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

julia> intersection(Line2D([-1.0, 1], 0.0), Line2D([1.0, 1], 1.0))
Singleton{Float64, Vector{Float64}}([0.5, 0.5])

julia> intersection(Line2D([1.0, 1], 1.0), Line2D([1.0, 1], 1.0))
Line2D{Float64, Vector{Float64}}([1.0, 1.0], 1.0)