SVGNest: A browser-based vector nesting tool.
(requires SVG and webworker support). Mobile warning: running the demo is CPU intensive.
Given a square piece of material and some letters to be laser-cut:
We want to pack all the letters into the square, using as little material as possible. If a single square is not enough, we also want to minimize the number of squares used.
SVGnest is a free and open-source alternative that solves this problem with the orbital approach outlined in [E.K. Burke et al. 2006], using a genetic algorithm for global optimization. It works for arbitrary containers and concave edge cases, and performs on-par with existing commercial software.
It also features part-in-part support, for placing parts in the holes of other parts.
Make sure all parts have been converted to outlines, and that no outlines overlap. Upload the SVG file and select one of the outlines to be used as the bin.
All other outlines are automatically processed as parts for nesting.
While good heuristics exist for the rectangular bin packing problem, in the real world we are concerned with irregular shapes.
The strategy is made of two parts:
The key concept here is the "No Fit Polygon".
Given polygons A and B, we want to "orbit" B around A such that they always touch but do not intersect.
The resulting orbit is the NFP. The NFP contains all possible placements of B that touches the previously placed parts. We can then choose a point on the NFP as the placement position using some heuristics.
Similarly we can construct an "Inner Fit Polygon" for the part and the bin. This is the same as the NFP, except the orbiting polygon is inside the stationary one.
When two or more parts have already been placed, we can take the union of the NFPs of the previously placed parts.
This means that we need to compute O(nlogn) NFPs to complete the first packing. While there are ways to mitigate this, we take the brute-force approach which has good properties for the optimization algo.
Now that we can place the parts, we need to optimize the insertion order. Here's an example of a bad insertion order:
If the large "C" is placed last, the concave space inside it won't be utilized because all the parts that could have filled it have already been placed.
To solve this, we use the "first-fit-decreasing" heuristic. Larger parts are placed first, and smaller parts last. This is quite intuitive, as the smaller parts tend to act as "sand" to fill the gaps left by the larger parts.
While this strategy gives us a good start, we want to explore more of the solution space. We could simply randomize the insertion order, but we can probably do better with a genetic algorithm. (If you don't know what a GA is, this article is a very approachable read)
In our GA the insertion order and the rotation of the parts form the gene. The fitness function follows these rules:
The third one is rather arbitrary, as we can also optimize for rectangular bounds or a minimal concave hull. In real-world use the material to be cut tends to be rectangular, and those options tend to result in long slivers of un-used material.
Because small mutations in the gene cause potentially large changes in overall fitness, the individuals of the population can be very similar. By caching NFPs new individuals can be evaluated very quickly.
Performs similarly to commercial software, after both have run for about 5 minutes.