True Shape Nesting 01: Burke and Lee

Petrenko [1] presents the classification of nesting algorithms and gives a retrospective of research in this area, starting with Chebyshev (!). While it feels very interesting to check carefully what Chebyshev contributed to 2D nesting in the 19-th century [4], such a discussion would probably bring us too far from the subject, so let's leave it for another day.

First off, irregular nesting is an NP-hard problem, which places it in the same category as, say, bend sequence simulation in sheet metal. The NP-hardness effectively means that there is no "right" way to nest, although there are acceptable layouts that are "good enough." In our series, we will be looking for a nesting algorithm capable of finding adequate packing for the sake of material consumption assessment. In reality, specialized nesting software can go beyond geometric packing issues and take into account manufacturability know-how.

E. Burke et al. [2] presents an irregular shape nesting algorithm that can deal with exact arcs, part-in-part packing, and part rotations. At the last stage, the algorithm refines the obtained result with a global optimizer. They do not use the idea of NFP ("No Fit Polygon"), which has become a standard tool for solving 2D nesting. Instead, the authors claim that being no-NFP gives their algorithm the advantage of accurate processing for highly concave pieces. A good deal of this paper by E. Burke is devoted to the primitive intersection algorithm. However, what remains unclear is how it is guaranteed that all intersections will be resolved. Well, okay, am I looking for a theorem in an engineering paper?

What I enjoyed about E. Burke's paper is how well it's written. When reading a scientific paper, it is always visible when the authors have stamped yet another article only to get published and when their involvement extends beyond that. However, I was hoping to discover some insights in the top-notch "Computer-Aided Design" journal as well, and this is how I came across the study by Lee et al. [3].

Lee et al. approximate the input primitives with polylines, which looks like a reasonable simplification. Although it's clear that such polygonization comes at a price of inducing a discretization error, we can at least start with such an approach for the sake of simplicity. Then, the polygon intersection job can likely be done with the Intf package of OpenCascade.

Both papers leave a flavor of attractive simplicity, so it probably makes sense to give them a go.

References

1. Петренко Семен Васильевич. Оптимизация размещения двумерных геометрических объектов на анизотропном материале с использованием методов математического программирования : Дис. ... канд. техн. наук : 05.13.18 Уфа, 2005 115 с. РГБ ОД, 61:06-5/520 (full text).

2. Burke, Edmund; Hellier, Robert; Kendall, Graham; Whitwell, Glenn (2006). A New Bottom-Left-Fill Heuristic Algorithm for the Two-Dimensional Irregular Packing Problem. Operations Research, 54(3), 587–601. doi:10.1287/opre.1060.0293 (full text).

3. Wen-Chen Lee, Heng Ma, Bor-Wen Cheng (2008). A heuristic for nesting problems of irregular shapes. Comput. Aided Des. 40(5), 625-633 (full text).

4. П. Л. Чебышев, О кройке одежды, УМН, 1946, том 1, выпуск 2, 38–42 (full text).

Want to discuss this? Jump in to our forum.