How to prove that two intersecting simple polygons must either have intersecting edges or one must be contained in the other.

Question

I am a computer scientist who is building a 2D collision detection engine that can detect whether or not two arbitrary simple polygons collide/overlap/intersect. Intuitively, one can identify that, for a collision to occur, there must be either an intersection between their edges or one of the polygons must be completely contained in the other. See visual example here

However, I would like to formalise this 'intuition' (which is hopefully correct) using set theory and topology.

The two simple polygons can be represented by two simply connected subsets $A,B$ of $\mathbb{R}^2$.

The conjecture I came up with goes as follows:

$A \cap B = \emptyset \iff \partial A \cap \partial B = \emptyset \land A \not\subset B \land B \not\subset A $

Or in words: A and B do not intersect if and only if their boundaries (i.e. edges) do not intersect and neither one is a subset of the other.

I feel like this is such a simple statement that a proof must already exists somewhere. But my lack of knowledge in this branch of mathematics does not allow me to search effectively for one.

Can someone point me to a proof (if it exists)? I would like be able to reference it.

PS: The closest thing i found is this post, but here they are limited to convex shapes. My conjecture, meanwhile, should hold true for any pair of non-convex simple polygons.

Answer 1

Since you are in two dimensions, here is a (probably overkill) proof. By the Jordan curve theorem, the boundary of one of your polygons divides the plane into two regions. The boundary of the other polygon is a continuous curve, which if it does not intersect the first boundary, must lie completely in one of the two regions. But these possibilities can be ruled out as one of the polygons being contained in the other (or the two being completely disjoint).

Answer 2

Parthi's answer is exactly right (but only for a better-expressed question).

Consider the sets $$ A = \{(x, y) \mid x^2 + y^2 < 1 \}\\ A = \{(x, y) \mid (x-2)^2 + y^2 <= 1 \} $$ These are simply connected, and their boundaries (the unit circle at the origin and the unit circle at $(2, 0)$ intersect at $(1,0)$. But $A \cap B$ is empty.

In generalizing "(filled) polygons" to "simply connected sets", you overshot a bit. At the very least, you probably want simply-connected closed sets, so that they contain their boundaries to avoid this example. Indeed, you probably want to say that each of $A$ and $B$ is a "Jordan curve, together with the bounded component of its complement".

As a computer scientist who used to do topology, let me just advise that this stuff is probably trickier than you think. (There is, for instance, and entire book called "Counterexamples in Topology" filled with apparently reasonable statements that are false.)

One challenge with your definition, even in the amended form above, is that testing whether two segments intersect is no easier than testing whether two numbers are equal, because of the ugly case where you have, say, two different-size squares that share a vertical edge -- you have to test for equality of (probably) floating-point numbers, whose challenges I'm sure you know all about. Transverse intersections are comparatively better, although if one of the edges is very short (like $(0,x)$ and $(0, y)$ where $x$ and $y$ are adjacent floats), even that can be a problem.

Most CS folks know about the wonders and perils of floating-point numbers; when you combine those with the wonders and perils of topology, things get difficult.

Answer 3

Let $A, B \subsetneq \mathbb R^2$ be nonempty closed sets (as are polygons). The interior $A^o$ of $A$ is union of all open sets contained in $A$; the boundary is $\partial A = A\setminus A^o$. We will also assume that the boundaries are curves, i.e. that there are continuous functions $\gamma_A, \gamma_B : [0,1] \to \mathbb R^2$ such that $\mathrm{Im}(\gamma_A) = \partial A$, $\mathrm{Im}(\gamma_B) = \partial B$, $\gamma_A(0) = \gamma_A(1)$, and $\gamma_B(0) = \gamma_B(1)$.

The direction $\implies$ is obvious. To prove $\impliedby$, assume for the sake of contradiction that $A\cap B \ne \varnothing$. Because the boundaries do not intersect, any $x \in A\cap B$ must be in one of the following sets: $$ A^o\cap B^o,\quad A^o\cap\partial B,\quad \partial A\cap B^o. $$ If the first case is true, then $x$ is contained in an open set contained in $A\cap B$; so if it's true for all $x$ then $A\cap B$ is open; but $A\cap B$ is also closed, which is a contradiction because there are no nontrivial clopen sets in $\mathbb R^2$.

So WLOG there is some $x \in A^o\cap \partial B$, and $U = \gamma_B^{-1}(A^o)$ is a nonempty open set. If $U \ne [0,1]$ then $(a, b)\cup(b, a) \subseteq U$ for some $a, b$ with $b \not\in U$. Then $\gamma_B(b) = \lim_{t\to b}\gamma_B(t)$ is in the closure of $A^o$, namely $A$, but also not in $A^o$, so it's actually in $\partial A\cap\partial B$. This is a contradiction, so $U = [0,1]$.

Thus $\partial B \subseteq A^o$, and I hope you will allow me to make the leap that this means $B \subseteq A$, which is a contradiction to the initial hypotheses. Thus $A\cap B$ is empty.