True Shape Nesting 02: polygon data structure

So we agreed that a polygonal part representation is probably not that bad, at least as a starting point for further experiments. Such experiments I decided to conduct in the Mobius library, which has historically been my companion software for prototyping new geometric algorithms from scratch.

The first puzzle piece is probably a data structure intended to represent an irregular polygon in two dimensions. Such a data structure aims at representing the nested part or, at least, its polygonal shape if we choose to maintain analytical curves (circular arcs) in their exact form. Here's an example of a data structure as documented by one of the commercial nesting suppliers (guess which one):

We should agree on some restrictions, no matter if the contour we are introducing is polygonal or curved:

• A contour should be closed.

• It should be permitted for a contour to contain inner contours (to represent holes).

• There is only one outer contour.

• The outer contour is traversed counterclockwise (CCW), while the inner contours are all clockwise (CW).

• The allowed rotation angles should be associated with a part, as different parts may come with their own orientation restrictions on nesting.

• An optional priority weight might be associated with each part.

With a polygon data structure in hands, we shall be able to perform the following operations:

• Intersect with another polygon.

• Compute the bounding rectangle.

• Compute the center of gravity.

• Rotate around the center of gravity by the given angle (CCW for positive angles and CW for negative).

• Compute area with and without holes.

• Translate along 2D axes.

• Offset by the given distance.

• Construct a "No Fit Polygon" (NFP) w.r.t. another polygon.

• Classify a point as belonging to the polygon or falling outside.

These operations are basically taken from the top of my head, and the list may look excessive. For example, we might never need an NFP construction algorithm if it happens that naive nesting approaches are just good enough. At the same time, such operations as offsets look pretty much like must-haves because, in practice, people tend to set a small safety proximity between the nested pieces. To be honest, a good deal of the functionalities listed above came to mind while reading the FAQ section of the NestLib library.

Putting together a decent polygon structure is probably not a one-hour exercise, although, at the same time, there's not much we require to get started. In the frames of our small Mobius ecosystem, to get the first visuals, I added a couple of commands named make-polygon and add-polygon-pole.

Want to discuss this? Jump in to our forum.