Intersection of two sets

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\}.\]

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

Extended help

intersection(cup::UnionSet, X::LazySet)

Output

The union of the pairwise intersections, expressed as a UnionSet. If one of those sets is empty, only the other set is returned.

Extended help

intersection(P::AbstractPolyhedron, rm::ResetMap)

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(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(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 set and a half-space, in-place.

Input

• X – star set
• H – half-space

Output

The modified star set.

_bound_intersect_2D(Z::Zonotope, L::Line2D)

Evaluate the support function in the direction [0, 1] of the intersection between the given zonotope and line.

Input

• Z – zonotope
• L – vertical 2D line

Output

The support function in the direction [0, 1] of the intersection between the given zonotope and line.

Notes

The algorithm assumes that the given line is vertical and that the intersection between the given sets is not empty.

Algorithm

This function implements [Algorithm 8.2, 1].

[1] Colas Le Guernic. Reachability Analysis of Hybrid Systems with Linear Continuous Dynamics. Computer Science [cs]. Université Joseph-Fourier - Grenoble I, 2009. English. fftel-00422569v2f