Rotational polygon overlap minimization
Victor Milenkovic · 1997
An effective and fast algorithm is given for rotational overlap minimization: given an overlapping layout of polygons PI, P2, P3,..., Pk in a container polygon C, translate and rotate the polygona to a layout that mtilmizes an overlap measure.A (local) overlap minimum has the property that any perturbation of the polygons increases the chosen measure of overlap.Experiments show that the algorithm works well in practice.It is shown how to apply overlap minimization to create algorithms for other layout tasks: wmpaction, containment, and minimal enclosure.Compact ion: starting with anon-overlapping layout in a rectangular container, plan a non-overlapping motion that minimizes the length or area of the container.Containment: place the polygons into a (possibly non-convex container) without overlapping.Minimal enclosure:tind a non-overlapping layout inside a minimum-length, fixed-width rectangle or inside a minimum area rectangle.All of these algorithms have important industrial applications.