Solving two-dimensional puzzles using the Convex Hull Hierarchy

The 2D nesting problem can be described as finding the positions and orientations of different polygonal pieces such that the newly computed orientations optimize a selected objective function. In applications such as sheet metal cutting and cutting shapes from cloth, the objective function is to minimize wastage. This paper focusses on solving 2D puzzles whose pieces have straight edges. This is a subset of the 2D nesting problem. We approach this using a novel geometric data structure called the convex hull hierarchy. The hull hierarchy exploits features of the polygons such as convex regions and concave regions termed as protrusions and cavities. We first identify initial cavities using convex hulls of the polygons and then define protrusions based on cavities. This process is performed recursively and we finally have a tree structure where each node defines a new polygon, which is either a cavity or a protrusion. We then use the hierarchy trees generated for each polygon to perform matching using criteria like polygon area, perimeter and tree isomorphism. With a few examples we then show how our algorithm can be applied to fit together different classes of puzzles.