Intersection and containment detection for convex polygons I need to check if two convex polygons intersect of not, in a efficient way. The description of the intersection itself is not required.
I know the method of separating axis, but it takes $NM$ tests for polygons of sizes $N$ and $M$.
I also know the efficient methods based on rotating calipers (Toussaint), &quot;edge chasing&quot; (O'Rourke), sweepline (Shamos &amp; Hoey), Voronoi diagrams (Yang &amp; al.), which all take $N+M$ tests.
Unfortunately, all these are designed with the idea that the polygons do intersect and the focus is on computing the intersection. For this reason, they don't really describe what happens when the polygon outlines in fact do not intersect and how to cope.
I also know about the optimal approach from &quot;Detection is easier than computation&quot; (Chazelle), which takes $Log(N+M)$ tests but it is too sophisticated and complicated for my purposes.
So what I am after is a practical procedure not taking more than $N+M$ tests and able to tell if the polygons intersect of not, or if one is wholly inside the other.
I have found a suitable answer: this can be done by an extension of rotating calipers, using the separating axis principle and looking at the polygons as intersections of half-spaces.
I have found a suitable answer: this can be done by an extension of rotating calipers, using the separating axis principle and looking at the polygons as intersections of half-spaces.