Speeding up nesting calculations

Algorithms for free-form nesting has a cost that depends on the complexity of the polygons that represent the parts to be placed. The more complex (the more points) these polygons are, the longer the computing time.

One might accept a slight waste of material if that can speed up the nesting significantly. The obvious idea is to simplify the polygons and for that task, there is a considerable amount of algorithms available.

However, there is a bit of a catch in our case: If the simplification process renders a new polygon that is slightly smaller than the original one, this could be a problem as the actual part will not fit in the space allocated for it by the nesting software.

The simplification performed by the red arrow creates a new polygon that, while it has fewer points, it cannot contain the original polygon inside and so it would be a bad idea to use the new for nesting purposes. On the other hand, the green arrow simplification does create a new polygon with fewer points that can hold the original polygon inside.

In a simplification algorithm that removes existing points (as the one above), a restriction has to be added only allowing the removal of a vertex if it is creating a concavity.

Using Visvalingam algorithm, the area of the triangle created by three consecutive vertices of the polygon is evaluated. For example, the green triangle formed by vertices 1,2, and 3. On each iteration, all such triangles are calculated and the mid-vertex of the smaller one becomes the candidate to be removed.

However, if we look at the partial view of a polygon (assuming the numbers are printed outside of the object inner surface), we can see that while green and orange triangles lie outside of the polygon inner surface, the light brown one is actually inside of the polygon.

For the general application that does not make a difference, but if we want our simplification not to reduce the material spot allocated to each polygon during nesting, we need to add the restriction that only vertices 2 and 4 from the above scenario can be actually removed. That simplification will still create a simplified polygon that can hold the original one inside.

The bad news is that restriction may not allow a significant reduction of the number of points on our polygons, so, unfortunately, a big speed-up factor is not happening here.

In order to achieve a better result, a new algorithm needs to be developed, and this one will not only remove existing polygon vertices but it should also be able to create new ones while still fulfilling the goal of never to create a too-small simplified polygon. But that seems to be the work for another rainy day.