Rb. Grinde et Tm. Cavalier, CONTAINMENT OF A SINGLE POLYGON USING MATHEMATICAL-PROGRAMMING, European journal of operational research, 92(2), 1996, pp. 368-386
Citations number
12
Categorie Soggetti
Management,"Operatione Research & Management Science","Operatione Research & Management Science
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.