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.

isdisjoint(X::LazySet, Y::LazySet, [witness]::Bool=false)

Check whether two sets do not intersect, and otherwise optionally compute a witness.

Input

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

Output

• If witness option is deactivated: true iff $X ∩ Y = ∅$
• If witness option is activated:
  • (true, []) iff $X ∩ Y = ∅$
  • (false, v) iff $X ∩ Y ≠ ∅$ and $v ∈ X ∩ Y$

Algorithm

This is a fallback implementation that computes the concrete intersection, intersection, of the given sets.

A witness is constructed using the an_element implementation of the result.

isdisjoint(Z1::AbstractZonotope, Z2::AbstractZonotope,
           [witness]::Bool=false; [solver]=nothing)

Check whether two zonotopic sets do not intersect, and otherwise optionally compute a witness.

Input

• Z1 – zonotopic set
• Z2 – zonotopic set
• witness – (optional, default: false) compute a witness if activated
• solver – (optional, default: nothing) the backend used to solve the linear program

Output

• If witness option is deactivated: true iff $Z1 ∩ Z2 = ∅$
• If witness option is activated:
  • (true, []) iff $Z1 ∩ Z2 = ∅$
  • (false, v) iff $Z1 ∩ Z2 ≠ ∅$ and $v ∈ Z1 ∩ Z2$

Algorithm

The algorithm is taken from [1].

$Z1 ∩ Z2 = ∅$ iff $c_1 - c_2 ∉ Z(0, (g_1, g_2))$ where $c_i$ and $g_i$ are the center and generators of zonotope Zi and $Z(c, g)$ represents the zonotope with center $c$ and generators $g$.

[1] L. J. Guibas, A. T. Nguyen, L. Zhang: Zonotopes as bounding volumes. SODA

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

Check whether two line segments do not intersect, and otherwise optionally compute a witness.

Input

• L1 – line segment
• L2 – line segment
• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: true iff $L1 ∩ L2 = ∅$
• If witness option is activated:
  • (true, []) iff $L1 ∩ L2 = ∅$
  • (false, v) iff $L1 ∩ L2 ≠ ∅$ and $v ∈ L1 ∩ L2$

Algorithm

The algorithm is inspired from here, which again is the special 2D case of a 3D algorithm from [1].

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.

[1] Ronald Goldman. Intersection of two lines in three-space. Graphics Gems

isdisjoint(P::AbstractPolyhedron, X::LazySet, [witness]::Bool=false;
           [solver]=nothing, [algorithm]="exact")

Check whether a polyhedral set and another set do not intersect, and otherwise optionally compute a witness.

Input

• P – polyhedral set
• X – set (see the Notes section below)
• witness – (optional, default: false) compute a witness if activated
• solver – (optional, default: nothing) the backend used to solve the linear program
• algorithm – (optional, default: "exact") algorithm keyword, one of: * "exact" (exact, uses a feasibility LP) *"sufficient" (sufficient, uses half-space checks)

Output

• If witness option is deactivated: true iff $P ∩ X = ∅$
• If witness option is activated:
  • (true, []) iff $P ∩ X = ∅$
  • (false, v) iff $P ∩ X ≠ ∅$ and $v ∈ P ∩ X$

Notes

For algorithm == "exact", we assume that constraints_list(X) is defined. For algorithm == "sufficient", witness production is not supported.

For solver == nothing, we fall back to default_lp_solver(N).

Algorithm

For algorithm == "exact", see isempty(P::HPoly, ::Bool).

For algorithm == "sufficient", we rely on the intersection check between the set X and each constraint in P. This requires one support-function evaluation of X for each constraint of P. With this algorithm, the method may return false even in the case where the intersection is empty. On the other hand, if the algorithm returns true, then it is guaranteed that the intersection is empty.