Using Circle Covering to Tackle Nesting Representations Limitations

Abstract

The development of effective and efficient Nesting algorithms have a strong dependence on the geometrical representation methods available for irregular outlines. Current geometrical representations are based on discretized matrixes, rectangular bounding boxes, polygons and mathematical expressions of basic objects. State of the art algorithms use polygonal representations and rely on no-fit-polygons (NFP) to ensure feasible layouts. NFP computation is usually done in a pre-processing phase, for a set of discrete orientations, since its very computationally expensive to do at runtime. Efficient overlapping detection algorithms based on these geometrical representations suffer from limitations on the placement orientations of the pieces, since the representations are strongly tied to specific orientations, and changing them is not trivial. A major challenge is to find geometrical representations that are independent of piece orientations. These representations will allow collision detec