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

Return some element of a 2D line segment.

Input

• L – 2D line segment

Output

The first vertex of the line segment.

center(L::LineSegment)

Return the center of a 2D line segment.

Input

• L – 2D line segment

Output

The center of the line segment.

constraints_list(L::LineSegment)

Return a list of constraints defining a 2D line segment in 2D.

Input

• L – 2D line segment

Output

A vector of constraints defining the line segment.

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.

dim(L::LineSegment)

Return the ambient dimension of a 2D line segment.

Input

• L – 2D line segment

Output

The ambient dimension of the 2D line segment, which is $2$.

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(::Type{LineSegment}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing)

Create a random 2D line segment.

Input

• LineSegment – 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 2D line segment.

Algorithm

All numbers are normally distributed with mean 0 and standard deviation 1.

vertices_list(L::LineSegment)

Return the list of vertices of a 2D line segment.

Input

• L – 2D line segment

Output

The list of end points of the line segment.

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

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

Input

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

Output

true iff $x ∈ L$.

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

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

Input

• d – direction
• L – 2D line segment

Output

The support vector in the given direction.

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

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

Evaluate the support function of a 2D line segment in a given direction.

Input

• d – direction
• L – 2D line segment

Output

Evaluation of the support function in the given direction.

translate(L::LineSegment, v::AbstractVector)

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

Input

• L – 2D line segment
• v – translation vector

Output

A translated line segment.

Algorithm

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

intersection(LS1::LineSegment, LS2::LineSegment)

Compute the intersection of two line segments.

Input

• LS1 – line segment
• LS2 – line segment

Output

A singleton, line segment, or the empty set depending on the result of the intersection.

Notes

• If the line segments cross, or are parallel and have one 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, if there is no intersection, an 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.