Line segment (LineSegment)

LineSegment{N, VN<:AbstractVector{N}} <: AbstractZonotope{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, Vector{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. If it is desired to remove the endpoints, pass the options markershape=:none and seriestype=:shape.

Membership is checked with ∈ (in):

julia> [0., 0] ∈ s && [.25, .25] ∈ s && [1., 1] ∈ s && [.5, .25] ∉ s
true

We can check whether the intersection with another line segment is empty, and optionally compute a witness (which is the unique common point in this case):

julia> sn = LineSegment([1., 0], [0., 1.])
LineSegment{Float64, Vector{Float64}}([1.0, 0.0], [0.0, 1.0])

julia> isdisjoint(s, sn)
false

julia> isdisjoint(s, sn, true)
(false, [0.5, 0.5])

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::LineSegment)

Algorithm

The output is the first vertex of the line segment.

constraints_list(X::LazySet)

Compute a list of linear constraints of a polyhedral set.

Input

• X – polyhedral set

Output

A list of the linear constraints of X.

Extended help

constraints_list(L::LineSegment)

Algorithm

$L$ is defined by 4 constraints. In this algorithm, the first two constraints are returned by halfspace_right and halfspace_left, and the other two are obtained by considering a vector parallel to the line segment passing through one of the vertices.

generators(L::LineSegment)

Return an iterator over the (single) generator of a 2D line segment.

Input

• L – 2D line segment

Output

An iterator over the generator of L, if any.

genmat(L::LineSegment)

Return the generator matrix of a 2D line segment.

Input

• L – 2D line segment

Output

A matrix with at most one column representing the generator of L.

halfspace_left(L::LineSegment)

Return a half-space describing the 'left' of a two-dimensional 2D line segment through two points.

Input

• L – 2D 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 2D line segment through two points.

Input

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

ngens(L::LineSegment)

Return the number of generators of a 2D line segment.

Input

• L – 2D line segment

Output

The number of generators.

Algorithm

A line segment has either one generator, or zero generators if it is a degenerated line segment of length zero.

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{LineSegment}; [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.

∈(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::LineSegment)

Algorithm

Let $L = (p, q)$ be the line segment with extreme points $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.

σ(d::AbstractVector, X::LazySet)

Compute a support vector of a set in a given direction.

Input

• d – direction
• X – set

Output

A support vector of X in direction d.

Notes

A convenience alias support_vector is also available.

Extended help

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

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

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::LineSegment, v::AbstractVector)

Algorithm

We add the vector to both defining points of the line segment.

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(LS1::LineSegment, LS2::LineSegment)

Output

A Singleton, a LineSegment, or an EmptySet depending on the result of the intersection.

Notes

• If the line segments cross, or are parallel and have a single point in common, that point is returned.

• If the line segments are parallel and have a line segment in common, that segment is returned.

• Otherwise, there is no intersection and the empty set is returned.

Extended help

isdisjoint(L1::LineSegment, L2::LineSegment, [witness]::Bool=false)

Algorithm

The algorithm is inspired from here, which itself is the special 2D case of a 3D algorithm from Goldman [Gol90].

We first check if the two line segments are parallel, and if so, if they are collinear. In the latter case, we check membership of any of the end points in the other line segment. Otherwise the lines are not parallel, so we can solve an equation of the intersection point, if it exists.