Rb. Grinde et Tm. Cavalier, A NEW ALGORITHM FOR THE MINIMAL-AREA CONVEX ENCLOSURE PROBLEM, European journal of operational research, 84(3), 1995, pp. 522-538
Citations number
16
Categorie Soggetti
Management,"Operatione Research & Management Science
The problem of cutting parts from a piece of material occurs in a numb
er of settings. When the pieces to be cut are non-rectangular, the pro
blem is called the irregular pattern layout problem (or nesting proble
m). This problem occurs in sheet metal and apparel industries, for exa
mple. One possible approach is to combine individual pieces into low-w
aste 'modules' which are then arranged by a heuristic technique. In th
is spirit, the Minimal-Area Convex Enclosure Problem is solved in this
paper. Given two simple polygons, the algorithm finds the relative po
sition of one with respect to the other such that the area of their co
nvex enclosure is minimized. The technique searches along the envelope
(or no-fit-polygon), dynamically maintaining the convex enclosure ver
tices as well as an analytic representation of the area. The algorithm
runs quickly and computational experience is included.