Computational speed-up of 2D packing.
Efficient implementation of 2D nesting problem to minimize waste of metal.
Basque center for applied mathematics
Lantek’s goal was to find the optimal layout of 2D pieces on a large metal rectangular sheet to minimize the waste material in the sheet cutting through an efficient implementation of 2D nesting problem.
Challenges and goals
To design an efficient algorithm for the 2D nesting (packing) problem and to improve the current by boundary representations in order to develop a software that will speed up computations.
Mathematical and computational methods
A discrete curvature measure was used to find the best match between two objects. The algorithm is based on D-function and non-fitting polygon approach.
Results and Benefits
The boundary representation of the objects (so far polygons, later NURBS curves) is more efficient for the overlapping test than the pixel-to-pixel comparison of two areas. This allows for a computational speed-up of 2D packing, that will ultimately result in the reduction of the waste of material.