Minkoski Sums

Using Minkowski Sums for intersection testing of convex shapes

If the two convex shapes intersect, the origin lies within the Minkowski Sum. This is easily seen by moving either the red or blue shape to overlap, and the resulting green shape will intersect with (0,0), i.e., contains the origin. This is quite useful because testing whether a point is contained in a polygon is typically faster than testing whether two polygons intersect. Computing the Minkowski Sum isn’t neccessarily cheap though, but the result can be cached. It only has to be recomputed when either source shape changes, or is rotated. Translation is constant time, instead of translating the green shape (many vertices), one could translate the origin (a single vertex). The latter isn’t done is this demo. To optimize for rotation, I conjecture that a technique called rotating calipers can be leveraged.

Minkoski Sums also sit at the basis of the GJK algorithm for intersection testing, although that’s a story for another day.