2NA Part Clustering

The 2NA part clustering algorithm is the heart of the software. The purpose of this algorithm is to pack two irregular polygons together into the smallest possible rectangle. This problem is a contrained minimization problem, i.e. minimize rectangle area subject to the constraint that the rectangle encloses both polygons and the polygons are disjoint.

Adamowicz and Albano ("Nesting two-dimensional shapes in rectangular modules," Computer Aided Design 8, pp. 27-33, 1976) proposed factoring the constraints out of the problem by means of the no-fit, or configuration space polygon. Suppose that one of the two shape polygons is fixed in space and that the orientation of the other shape polygon is fixed. As the second polygon is translated around the plane, it will either intersect the fixed polygon or not. The no-fit polygon is defined to be the locus of points traced by the movable polygon as it just touches the fixed one.

In this picture, the orange polygon is fixed in place, while the blue one is allowed to translate, but not rotate. The trajectory of the blue polygon's lower left corner as the polygon maintains contact with the orange polygon is the white polygon. This movie shows the relationship of the blue polygon to the orange polygon as it traverses the no-fit polygon.

Part clustering is accomplished by solving an unconstrained optimization problem in two variables. The two variables are position along the no-fit polygon and orientation of a rectangle enclosing both polygons. The optimization problem is to minimize the area of this rectangle. In 2NA, this optimization problem is solved using one of the pattern search methods due to Dennis and Torczon at the Center for Research in Parallel Computation at Rice ("On the convergence of the multdirectional search algorithm," SIAM J. Optimization 1, pp. 123-145, 1991).