A new algorithm for the minimal-area convex enclosure problem

The problem of cutting parts from a piece of material occurs in a number of settings. When the pieces to be cut are non-rectangular, the problem is called the irregular pattern layout problem (or nesting problem). This problem occurs in sheet metal and apparel industries, for example. One possible approach is to combine individual pieces into low-waste ‘modules’ which are then arranged by a heuristic technique. In this spirit, the Minimal-Area Convex Enclosure Problem is solved in this paper. Given two simple polygons, the algorithm finds the relative position of one with respect to the other such that the area of their convex enclosure is minimized. The technique searches along the envelope (or no-fit-polygon), dynamically maintaining the convex enclosure vertices as well as an analytic representation of the area. The algorithm runs quickly and computational experience is included.