Emptiness check of intersection of two sets

[schillic]

Add a function is_intersection_empty(S1, S2; witness=false) that returns true if the sets S1 and S2 do not intersect. If the flag witness is set, also produce a witness, i.e., a point (vector) x such that x ∈ S1 ∩ S2 if the intersection is nonempty. The table below tracks the current combinations that we support:

↓ ∩ →	Ball1	Ball2	Ballp	HRect	Polygon	Zonotope	Singleton
Ball1							x
Ball2							x
Ballp							x
HRect				x			x
Polygon							x
Zonotope							x
Singleton	x	x	x	x	x	x	x

Related: #139

[schillic]

Possibly helpful: Boolean operations on polygons

[schillic]

For convex polygons this is not too complicated, but also not trivial.

• Sutherland-Hodgman (not efficient),

• rotating calipers,

• sweep lines approach: cryptic description and good description,

• separating axes theorem and algorithm outline and example for rectangles

• edge chase and nice example slides (my current favorite)

[mforets]

borrowing your table from #69, we should complete:

↓ ∩ →	Ball1	Ball2	Ballp	HR/BInf	Polygon	Singleton
Ball1
Ball2
Ballp
HR/BInf
Polygon
Zonotope
Singleton

[schillic]

You will be disappointed. EDIT: I moved the table to the top.

[mforets]

For zonotopes we will find good information both in A. Girard and in M. Althoff dissertations.

[schillic]

Today I got a very elegant alternative to solve this problem: X ∩ Y = ∅ ⇔ 0 ∉ (X ⊕ -Y) This means that if we can decide the membership, we get this check for free. However, for Minkowski sum the membership check is an open task in #77.

[mforets]

Do we have an operator for -Y? For polytopes it could be seen as the linear map that transforms each vertex to its opposite wrt the origin.

[schillic]

Do we have an operator for -Y?

No, but conceptually it should be really simple: Add a lazy operation, say, Negative, and implement all methods by calling the method for the wrapped set and multiplying the result by -1. It is just an annoying task, and I do not think it is worthwile because membership of Minkowski sum is really complicated.

[schillic]

Closing this as "too meta". We now have the function isdisjoint for quite some set types already.