CONTAINMENT OF A SINGLE POLYGON USING MATHEMATICAL-PROGRAMMING

This paper investigates the polygon containment problem, to determine whether a given polygon can be translated and/or rotated to fit inside a fixed polygon. A primary application is the stock cutting problem, when pieces have irregular shapes and can be rotated. The case in whic h both polygons are convex is treated. An optimization-based approach is used, in contrast to previous computational geometry methods. Optim ality conditions of the math program are found and are used to develop an efficient algorithm which finds the best placement and to draw rel ationships between the two approaches. The problem becomes a parametri c linear program with a nonlinear parameter corresponding to the orien tation of the moving figure. All alternate-optimal placements with at least three contacts can be found. In addition, the algorithm provides an analytic description of the optimal objective as a function of the orientation of the moving polygon.