You need to write a mini-program that would calculate the most economical layout of the material. Given: a figure of arbitrary shape and a rectangular sheet of material. It is necessary to expand the maximum possible amount of this figure on this sheet so that there is a distance of 2-3mm between them (can be adjusted). Which way to dig? What can be implemented? I would like to Python, as more or less I only know it.
- oneIt is desirable as a result to have the drawn layout in any format - Arkane
- A similar (simpler) question: Algorithm needed for packing rectangles in a fairly well-chosen way - jfs
- association: stackoverflow.com/questions/1213394/… - Nicolas Chabanovsky ♦
|
1 answer
In general, this task is intractable, and does not have an effective algorithm for solving in principle (it does not exist in nature). If your material has some special form, then you can still do something, and if the form is arbitrary, then you can try heuristics. Dig for these keywords: "planar cutting problem" or "Cutting stock problem". In Russian, I immediately say, you will find little useful information. In English, look for the Cutting stock problem problem on rectangular stripes 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 of minimum length (height) and with 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 as to be stated that I cannot write them here.
I answer the second question: you can implement on anything you know the algorithm. I am not aware of the finished libraries. In general, this is a serious scientific problem, which various institutions were engaged in (especially in Soviet times). You need to master programming fairly well in order to code everything correctly here.
Zealint Zealint
2,484 one 7 18
|