A NEW ALGORITHM FOR THE MINIMAL-AREA CONVEX ENCLOSURE PROBLEM

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.