nesting

Graphical algorithm to find a possible solutions to 2D nesting problems.

#Definition of nesting problems

Irregular Strip Packing problems are a type of Cutting and Packing problems where the small pieces have non-regular and complex shapes, usually known as irregular shapes. In these problems, also known as Nesting problems, the small pieces cannot overlap each other and must be placed inside a stock sheet. The goal is to minimise the unused stock space inbetween the placed pieces, this is, the overall waste.

#Geometry processing as nesting algorithms bottleneck

Most nesting algorithms improve existing solutions iteratively, searching the neighbourhood of the given solutions, by moving some pieces to different places. Main bottleneck constraining these moves is the computational cost of geometry processing.

Polygonal representations of the layout (stock sheet with placed pieces) have a greater computational cost when solving problems with complex shapes, due to repetitive and slow trigonometric calculations. Raster representations, despite being less precise, can be rendered by the GPU on an period of time that is practically independent of the shapes complexity.

This approach uses a raster representation of the layout, generated by the GPU, in order to reduce run time.

#Implementation

Current implementation generates a feasible layout for a problem, iteratively placing the pieces one by one according to a minimizing waste criteria. Layout is rendered in the graphical device (using OpenGL) and the image produced is processed. The image processing step detects feasible placements for a piece (using OpenCV). Also, generated images of the layout are stored and reused, saving rendering time as well.