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 which both polygons are convex is treated. An optimization-based approach is used, in contrast to previous computational geometry methods. Optimality conditions of the math program are found and are used to develop an efficient algorithm which finds the best placement and to draw relationships between the two approaches. The problem becomes a parametric linear program with a nonlinear parameter corresponding to the orientation 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.