Rotational polygon overlap minimization and compaction |
| |
Authors: | Victor J Milenkovic |
| |
Institution: | Department of Mathematics and Computer Science, University of Miami, P.O. Box 249085, Coral Gables, FL 33146, USA |
| |
Abstract: | An effective and fast algorithm is given for rotational overlap minimization: given an overlapping layout of polygons P1, P2, P3, …, Pk in a container polygon Q, translate and rotate the polygons to diminish their overlap to a local minimum. A (local) overlap minimum has the property that any perturbation of the polygons increases the overlap. Overlap minimization is modified to create a practical algorithm for compaction: starting with a non-overlapping layout in a rectangular container, plan a non-overlapping motion that diminishes the length or area of the container to a local minimum. Experiments show that both overlap minimization and compaction work well in practice and are likely to be useful in industrial applications. |
| |
Keywords: | Layout Packing or nesting of irregular polygons Containment Minimum enclosure Compaction Linear programming |
本文献已被 ScienceDirect 等数据库收录! |
|