# Intersection of two sets

`LazySets.API.intersection`

— Method`intersection(S::AbstractSingleton, X::LazySet)`

Compute the intersection of a set with a single point with another set.

**Input**

`S`

– set with a single point`X`

– set

**Output**

If the sets intersect, the result is `S`

. Otherwise, the result is the empty set.

`LazySets.API.intersection`

— Method`intersection(L1::Line2D, L2::Line2D)`

Compute the intersection of two two-dimensional lines.

**Input**

`L1`

– line`L2`

– line

**Output**

Three outcomes are possible:

- If the lines are identical, the result is the first line.
- If the lines are parallel and not identical, the result is the empty set.
- Otherwise the result is the set with the unique intersection point.

**Algorithm**

We first check whether the lines are parallel. If not, we use Cramer's rule to compute the intersection point.

**Examples**

The line $y = x$ intersected with the line $y = -x + 1$ respectively with itself:

```
julia> intersection(Line2D([-1.0, 1], 0.0), Line2D([1.0, 1], 1.0))
Singleton{Float64, Vector{Float64}}([0.5, 0.5])
julia> intersection(Line2D([1.0, 1], 1.0), Line2D([1.0, 1], 1.0))
Line2D{Float64, Vector{Float64}}([1.0, 1.0], 1.0)
```

`LazySets.API.intersection`

— Method`intersection(H1::AbstractHyperrectangle, H2::AbstractHyperrectangle)`

Compute the intersection of two hyperrectangular sets.

**Input**

`H1`

– hyperrectangular set`H2`

– hyperrectangular set

**Output**

If the hyperrectangular sets do not intersect, the result is the empty set. Otherwise the result is the hyperrectangle that describes the intersection.

**Algorithm**

In each isolated direction `i`

we compute the rightmost left border and the leftmost right border of the hyperrectangular sets. If these borders contradict, then the intersection is empty. Otherwise the resulting hyperrectangle uses these borders in each dimension.

`LazySets.API.intersection`

— Method`intersection(X::Interval, hs::HalfSpace)`

Compute the intersection of an interval and a half-space.

**Input**

`X`

– interval`hs`

– half-space

**Output**

If the sets do not intersect, the result is the empty set. If the interval is fully contained in the half-space, the result is the original interval. Otherwise the result is the interval that describes the intersection.

**Algorithm**

We first handle the special case that the normal vector `a`

of `hs`

is close to zero. Then we distinguish the cases that `hs`

is a lower or an upper bound.

`LazySets.API.intersection`

— Method`intersection(X::Interval, hp::Hyperplane)`

Compute the intersection of an interval and a hyperplane.

**Input**

`X`

– interval`hp`

– hyperplane

**Output**

If the sets do not intersect, the result is the empty set. Otherwise the result is the singleton that describes the intersection.

`LazySets.API.intersection`

— Method`intersection(X::Interval, Y::LazySet)`

Compute the intersection of an interval and a convex set.

**Input**

`X`

– interval`Y`

– convex set

**Output**

If the sets do not intersect, the result is the empty set. Otherwise the result is the interval that describes the intersection, which may be of type `Singleton`

if the intersection is very small.

`LazySets.API.intersection`

— Method`intersection(P1::AbstractHPolygon, P2::AbstractHPolygon; [prune]::Bool=true)`

Compute the intersection of two polygons in constraint representation.

**Input**

`P1`

– polygon in constraint representation`P2`

– polygon in constraint representation`prune`

– (optional, default:`true`

) flag for removing redundant constraints

**Output**

If the polygons do not intersect, the result is the empty set. Otherwise the result is the polygon that describes the intersection.

**Algorithm**

We just combine the constraints of both polygons. To obtain a linear-time algorithm, we interleave the constraints. If there are two constraints with the same normal vector, we choose the tighter one.

Redundancy of constraints is checked with `remove_redundant_constraints!(::AbstractHPolygon)`

.

`LazySets.API.intersection`

— Method```
intersection(P1::AbstractPolyhedron{N}, P2::AbstractPolyhedron{N};
[backend]=default_lp_solver(N), [prune]::Bool=true) where {N}
```

Compute the intersection of two polyhedra.

**Input**

`P1`

– polyhedron`P2`

– polyhedron`backend`

– (optional, default:`default_lp_solver(N)`

) the LP solver used for the removal of redundant constraints; see the*Notes*section below for details`prune`

– (optional, default:`true`

) flag for removing redundant constraints

**Output**

An `HPolyhedron`

resulting from the intersection of `P1`

and `P2`

, with the redundant constraints removed, or an empty set if the intersection is empty. If one of the arguments is a polytope, the result is an `HPolytope`

instead.

**Notes**

The default value of the solver backend is `default_lp_solver(N)`

and it is used to run a feasiblity LP to remove the redundant constraints of the intersection.

If you want to use the `Polyhedra`

library, pass an appropriate backend. For example, use `default_polyhedra_backend(P)`

for the default Polyhedra library, or use `CDDLib.Library()`

for the CDD library.

There are some shortcomings of the removal of constraints using the default Polyhedra library; see e.g. #1038 and Polyhedra#146. It is safer to check for emptiness of intersection before calling this function in those cases.

**Algorithm**

This implementation unifies the constraints of the two sets obtained from the `constraints_list`

method.

`LazySets.API.intersection`

— Method```
intersection(P1::Union{VPolygon, VPolytope}, P2::Union{VPolygon, VPolytope};
[backend]=nothing, [prunefunc]=nothing)
```

Compute the intersection of two polytopes in vertex representation.

**Input**

`P1`

– polytope in vertex representation`P2`

– polytope in vertex representation`backend`

– (optional, default:`nothing`

) the backend for polyhedral computations`prunefunc`

– (optional, default:`nothing`

) function to prune the vertices of the result

**Output**

A `VPolytope`

.

**Notes**

If `prunefunc`

is `nothing`

, this implementation sets it to `(X -> removevredundancy!(X; ztol=_ztol(eltype(P1))))`

.

`LazySets.API.intersection`

— Method`intersection(P1::VPolygon, P2::VPolygon; apply_convex_hull::Bool=true)`

Compute the intersection of two polygons in vertex representation.

**Input**

`P1`

– polygon in vertex representation`P2`

– polygon in vertex representation`apply_convex_hull`

– (default, optional:`true`

) if`false`

, skip the computation of the convex hull of the resulting polygon

**Output**

A `VPolygon`

, or an `EmptySet`

if the intersection is empty.

**Algorithm**

This function applies the Sutherland–Hodgman polygon clipping algorithm. The implementation is based on the one found in rosetta code.

`LazySets.API.intersection`

— Method`intersection(cup::UnionSet, X::LazySet)`

Compute the intersection of a union of two sets and another set.

**Input**

`cup`

– union of two sets`X`

– set

**Output**

The union of the pairwise intersections, expressed as a `UnionSet`

. If one of those sets is empty, only the other set is returned.

`LazySets.API.intersection`

— Method`intersection(cup::UnionSetArray, X::LazySet)`

Compute the intersection of a union of a finite number of sets and another set.

**Input**

`cup`

– union of a finite number of sets`X`

– set

**Output**

The union of the pairwise intersections, expressed as a `UnionSetArray`

.

`LazySets.API.intersection`

— Method`intersection(U::Universe, X::LazySet)`

Compute the intersection of a universe and a set.

**Input**

`U`

– universe`X`

– set

**Output**

The set `X`

.

`LazySets.API.intersection`

— Method`intersection(P::AbstractPolyhedron, rm::ResetMap)`

Compute the intersection of a polyhedral set and a polyhedral reset map.

**Input**

`P`

– polyhedral set`rm`

– polyhedral reset map

**Output**

A polyhedron.

**Notes**

This method assumes that `rm`

is polyhedral, i.e., has a `constraints_list`

method defined.

`LazySets.API.intersection`

— Method` intersection(X::CartesianProductArray, Y::CartesianProductArray)`

Compute the intersection between Cartesian products of a finite number of sets with identical decomposition.

**Input**

`X`

– Cartesian product of a finite number of sets`Y`

– Cartesian product of a finite number of sets

**Output**

The decomposed set that represents the concrete intersection of `X`

and `Y`

.

**Algorithm**

This algorithm intersects the corresponding blocks of the sets.

`LazySets.API.intersection`

— Method`intersection(L::LinearMap, X::LazySet)`

Compute the intersection of a lazy linear map and a set.

**Input**

`L`

– linear map`X`

– set

**Output**

The set obtained by the computing the concrete linear map `L.M * L.X`

and intersecting with `X`

.

`LazySets.API.intersection`

— Method```
intersection(cpa::Union{CartesianProduct,CartesianProductArray},
P::AbstractPolyhedron)
```

Compute the intersection of a Cartesian product of a finite number of polyhedral sets with a polyhedron.

**Input**

`cpa`

– Cartesian product of a finite number of polyhedral sets`P`

– polyhedron

**Output**

A Cartesian product of a finite number of polyhedral sets. See the *Algorithm* section below for details about the structure.

**Notes**

The restriction to polyhedral sets in `cpa`

only applies to the blocks that are actually intersected with `P`

(see the *Algorithm* section below for details). All other blocks are not considered by the intersection and remain identical.

**Algorithm**

The underlying idea of the algorithm is to exploit the unconstrained dimensions of `P`

. Without loss of generality, assume that `cpa`

has the structure $X × Y × Z$ such that only the dimensions of $Y$ are constrained in $P$. By denoting a suitable projection of $P$ to the dimensions of $Y$ with $P|_Y$, we have the following equivalence:

\[ (X × Y × Z) ∩ P = X × (Y ∩ P|_Y) × Z\]

Note that $Y$ may still consist of many blocks. However, due to the structural restriction of a Cartesian product, we cannot break down this set further even if $P|_Y$ is still unconstrained in some dimensions of blocks in $Y$. This would require a restructuring of the dimensions. Consider this example:

\[ Y := [0, 1] × [1, 2] × [2, 3] P|_Y := x₁ + x₃ ≤ 2 Y ∩ P|_Y = 0 ≤ x₁ ∧ 1 ≤ x₂ ≤ 2 ∧ 2 ≤ x₃ ∧ x₁ + x₃ ≤ 2\]

Even though the constraints of dimension $x₂$ are decoupled from the rest, due to the last constraint, the Cartesian product cannot be broken down further. In particular, the result $Y ∩ P|_Y$ is a polyhedron in this implementation.

Now we explain the implementation of the above idea. We first identify the dimensions in which `P`

is constrained. Then we identify the block dimensions of $X × Y × Z$ such that $Y$ has minimal dimension. Finally, we convert $Y$ to a polyhedron and intersect it with a suitable projection of `P`

.

`LazySets.API.intersection`

— Method`intersection(LS::LineSegment, L2::Line2D)`

Compute the intersection of a line segment and a line in two dimensions.

**Input**

`LS`

– line segment`L2`

– two-dimensional line

**Output**

If the sets do not intersect, the result is the empty set. Otherwise the result is the singleton or line segment that describes the intersection.

`LazySets.API.intersection`

— Method```
intersection(Z::AbstractZonotope{N}, H::HalfSpace{N};
[backend]=default_lp_solver(N), [prune]::Bool=true) where {N}
```

Compute the intersection between a zonotopic set and a half-space.

**Input**

`Z`

– zonotopic set`H`

– half-space`backend`

– (optional, default:`default_lp_solver(N)`

) the LP solver used for the removal of redundant constraints`prune`

– (optional, default:`true`

) flag for removing redundant constraints

**Output**

If the sets do not intersect, the output is the empty set. If the zonotopic set is fully contained in the half-space, the zonotopic set is returned. Otherwise, the output is the concrete intersection between `Z`

and `H`

.

**Algorithm**

First there is a disjointness test. If that is negative, there is an inclusion test. If that is negative, then the concrete intersection is computed.

`LazySets.API.intersection`

— Method`intersection(X::Star, H::HalfSpace)`

Compute the intersection between a star and a half-space.

**Input**

`X`

– star`H`

– half-space

**Output**

A star set representing the intersection between a star and a half-space.

`LazySets.intersection!`

— Method`intersection!(X::Star, H::HalfSpace)`

Compute the intersection between a star set and a half-space, in-place.

**Input**

`X`

– star set`H`

– half-space

**Output**

The modified star set.