Part contour simplification, with a twist

 Many vector graphic algorithms have a cost proportional to the number of segments of the shapes involved. Thus, many different polygon simplification algorithms have been developed over the years. The main idea is to represent the original shape, but reduce the total number of edges of the shape's contour. 

A favourite of mine is the Douglas-Peucker algorithm. It uses an error parameter that allows the user to tune the acceptable error introduced by the simplification. That works well in many scenarios, but as you may guess, it does not work well for some of my needs.

Free form 2D nesting packs groups of parts inside bins, in my case, those bins are rectangles. The rules are that any two parts cannot overlap. Nesting libraries will determine where to place each part inside a bin and what rotation to apply to the part. The number of parts and the number of edges per part have a big influence on the time required to perform the nesting operation. So, being able to simplify the parts has the potential of speeding up the nesting operation. But there is a catch: this simplification cannot accept any new edge or point inside the original area of the part. So we cannot use many of the simplifications available in the literature. 

What is needed is a simplification similar to the way an artist may draw a sketch of a shape, focusing on the main features but perhaps using only a handful of strokes. That sketch can later be refined to make the shape closer and closer to the real thing. If we allow a certain deviation from the original shape, but only when such a deviation places lines and points slightly outside of the original area, we are on the right path to create an algorithm that can be helpful to simplify the shapes that we will use for 2D nesting operations.

Today's helper is Alibaba´s AI, called Kimi K2. I asked it to develop such an algorithm for me, but the initial result was both revealing and wrong. I only asked for the contour points of the simplified shape not to be inside the original shape. But that restriction was met by Kimi's code, only for me to realize it was a necessary condition, but not enough. 

If you look at the rightmost side of the contour, you can see there is a red color segment that is drawn inside the dotted line contour that represents the original area of the part. This happened because the algorithm discarded some of the original points of the contour, so now this segment goes between two points of the original contour, but the result crosses inside the original area.

Once I reframe the problem, adding this new restriction, that not only new points but also new edges cannot be placed over the original area of the part, the AI was able to offer a good solution, like the example in the picture below:

You can see that now the red line is always outside of the dotted contour (but close), and the number of points of the contour has been reduced from 977 originally to only 35 after the simplification. Nesting parts that have been simplified this way is going to be faster. In my tests, the runtime is divided by three.  As the allowed error is small, the parts are nested the same way they would if I used the original parts.