Intersection of two sets

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.

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)

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.

intersection(x::Interval, y::Interval)

Compute the intersection of two intervals.

Input

• x – interval
• y – interval

Output

If the intervals do not intersect, the result is the empty set. Otherwise the result is the interval that describes the intersection.

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.

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.

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.

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

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.

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

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.

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.

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.

intersection(U::Universe, X::LazySet)

Compute the intersection of a universe and a set.

Input

• U – universe
• X – set

Output

The set X.

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.

    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.

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.

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.

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.

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.

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.

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.

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.