# Line segment (LineSegment)

`LazySets.LineSegmentModule.LineSegment`

— Type`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])
```

`LazySets.API.an_element`

— Method`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.

`LazySets.API.center`

— Method`center(L::LineSegment)`

Return the center of a 2D line segment.

**Input**

`L`

– 2D line segment

**Output**

The center of the line segment.

`LazySets.API.constraints_list`

— Method`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.

`LazySets.API.dim`

— Method`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$.

`LazySets.generators`

— Method`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.

`LazySets.genmat`

— Methodgenmat(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`

.

`LazySets.halfspace_left`

— Method`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`

.

`LazySets.halfspace_right`

— Method`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`

.

`LazySets.ngens`

— Method`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.

`Base.rand`

— Method```
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.

`LazySets.API.vertices_list`

— Method`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.

`Base.:∈`

— Method`∈(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.

- A necessary condition for $x ∈ (p, q)$ is that the three points are aligned, thus their cross product should be zero.
- 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.

`LazySets.API.σ`

— Method`σ(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$.

`LazySets.API.ρ`

— Method`ρ(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.

`LazySets.API.translate`

— Method`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.

`LazySets.API.intersection`

— Method`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.

`Base.isdisjoint`

— Method`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.

Undocumented implementations:

Inherited from `LazySet`

:

`area`

`complement`

`concretize`

`constraints`

`convex_hull`

`diameter`

`eltype`

`eltype`

`high`

`isoperation`

`low`

`norm`

`radius`

`reflect`

`singleton_list`

`surface`

`vertices`

`affine_map`

`exponential_map`

`is_interior_point`

`sample`

`scale`

`≈`

`==`

`isequivalent`

`⊂`

Inherited from `ConvexSet`

:

Inherited from `AbstractPolyhedron`

:

Inherited from `AbstractPolytope`

:

Inherited from `AbstractCentrallySymmetricPolytope`

:

Inherited from `AbstractZonotope`

: