python – It is necessary to calculate what is the maximum number of shapes that can fit on a rectangle. What can be implemented?


It is necessary to write a mini-program that would calculate the most economical layout of the material. Given: a free-form figure and a rectangular sheet of material. It is necessary to decompose the maximum possible number of this figure on this sheet so that there is a distance of 2-3 mm between them (can be adjusted). In which direction to dig? What can be implemented? I would like to use Python, since I more or less know only it.


In general, this problem is difficult to solve, and does not have an effective solution algorithm in principle (it does not exist in nature). If your material has some special form, then something else can be done, and if the form is arbitrary, then you can try heuristics. Dig for keywords like "planar nesting problem" or "Cutting stock problem". In Russian, I immediately say – you will find little that is useful. In English, look for the Cutting stock problem on rectangular strips with infinite length (or height). There, the essence of almost all heuristics is that an attempt is made to place N figures on a rectangular strip with a minimum length (height) and a fixed height (length). Accordingly, if your width (height) is already set in advance, then the problem of the maximum number N is solved by binary search. The heuristics themselves are so voluminous in presentation that I can’t describe them here.

I answer the second question: you can implement it on anything, when you know the algorithm. Ready-made libraries are not personally known to me. In general, this is a serious scientific problem, which was dealt with by various institutions (especially in Soviet times), you need to be quite proficient in programming in order to code everything here correctly.

Scroll to Top