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(L::Line2D)

Return some element of a 2D line.

Input

• L – 2D line

Output

An element on the line.

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

constraints_list(L::Line2D)

Return the list of constraints of a 2D line.

Input

• L – 2D line

Output

A list containing two half-spaces.

dim(L::Line2D)

Return the ambient dimension of a 2D line.

Input

• L – 2D line

Output

The ambient dimension of the line, which is 2.

isbounded(L::Line2D)

Check whether a 2D line is bounded.

Input

• L – 2D line

Output

false.

isempty(L::Line2D)

Check whether a 2D line is empty.

Input

• L – 2D line

Output

false.

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

Check whether a 2D line is universal.

Input

• L – 2D line
• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: false
• If witness option is activated: (false, v) where $v ∉ L$

Algorithm

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

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

Create a random line.

Input

• Line2D – 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. Additionally, the constraint a is nonzero.

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

Check whether a given point is contained in a 2D line.

Input

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

Output

true iff x ∈ L.

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‖²}.\]

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

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

Input

• d – direction
• L – 2D line

Output

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

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

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

Input

• L – 2D line
• v – translation vector
• share – (optional, default: false) flag for sharing unmodified parts of the original set representation

Output

A translated line.

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(L1::Line2D, L2::Line2D)

Compute the intersection of two two-dimensional lines.

Input

• L1 – line
• L2 – line

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)