A Review of Methods to Compute Minkowski Operations for Geometric Overlap Detection
Wesley Cox, Lyndon While, Mark A Reynolds · IEEE Transactions on Visualization and Computer Graphics · 2020
This article provides an extensive review of algorithms for constructing Minkowski sums and differences of polygons and polyhedra, both convex and non-convex, commonly known as no-fit polygons and configuration space obstacles. The Minkowski difference is a set operation, which when applied to shapes defines a method for efficient overlap detection, providing an important tool in packing and motion-planning problems. This is the first complete review on this specific topic, and aims to unify algorithms spread over the literature of separate disciplines.