Compaction Algorithms for Non-Convex Polygons and Their Applications

Abstract

Given a two-dimensional, non-overlapping layout of convex and non-convex polygons, compaction refers to a simultaneous motion of the polygons that generates a more densely packed layout. In industrial two-dimensional packing applications, compaction can improve the material utilization of already tightly packed layouts. Efficient algorithms for compacting a layout of non-convex polygons are not previously known. This dissertation offers the first systematic study of compaction of non-convex polygons. We start by formalizing the compaction problem as that of planning a motion that minimizes some linear objective function of the positions. Based on this formalization, we study the complexity of compaction and show it to be PSPACE-hard. The major contribution of this dissertation is a position-based optimization model that allows us to calculate directly new polygon positions that constitute a locally optimum solution of the objective via linear programming. This model yields the first practically efficient algorithm for translational compaction-compaction in which the polygons can only translate. This compaction algorithm runs in almost real time and improves the material utilization of production quality human-generated layouts from the apparel industry. Several algorithms are derived directly from the position-based optimization model to solve related problems arising from manual or automatic layout generation. In particular, the model yields an algorithm for separating overlapping polygons using a minimal amount of motion. This separation algorithm together with a database of human-generated markers can automatically generate markers that approach human performance. Additionally, we provide several extensions to the position-based optimization model. These extensions enables the model to handle small rotations, to offer the flexible control of the distances between polygons and to find optimal solution to two-dimensional packing of non-convex polygons. This dissertation also includes a compaction algorithm based on existing physical simulation approaches. Although our experimental results showed that it is not practical for compacting tightly packed layouts, this algorithm is of interest because it shows that the simulation can speed up significantly if we use geometrical constraints to replace physical constraints. It also reveals the inherent limitations of physical simulation algorithms in compacting tightly packed layouts. Most of the algorithms presented in this dissertation have been implemented on a SUN SparcStationTM and have been included in a software package licensed to a CAD company.