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

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.

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

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

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

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.

isbounded(L::Line2D)

Check whether a 2D line is bounded.

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

isempty(L::Line2D)

Check whether a 2D line is empty.

Input

• L – 2D line

Output

false.

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.

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

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