2NA Polygon Simplification

The part clustering algorithm used by 2NA can be computationally expensive. In particular, the number of operations is proportional to the fourth power of the number of vertices of the polygons. For this reason, the polygons are simplified before they are nested. The simplified polygons are conservative approximations of the originals. In this context, conservative means that the original polygons are contained within the approximate ones.

Pictured below is a typical part:

After simplification, some additional area is filled in (shown in orange below). In a typical Boeing sheet metal application, this adds about 5% to the total part area. However, it reduces the number of vertices by about a factor of 10, allowing 2NA to run nearly 10000 times faster:

In general, nests must satisfy a minimum part separation. Because 2NA attempts to arrange parts so that they are just touching, half of the required part separation must be added to each part. Thus, the final step of polygon simplification is to add an offset to the simplified part: