I have a couple questions related to this thread from 2015, where there is a discussion of the nearest neighbor algorithm used to determine the order in which polygons are printed. Ghostkeeper comments:
"The first is the order in which to draw polygons, which includes infill and walls and such. For these it first finds the point on each polygon that is closest to the starting position of the path. Then it treats the polygons as points so it can execute a simple nearest neighbor algorithm: Just keep going to whichever polygon is nearest to your current position that you haven't visited yet."
1.) Is this still how the Cura software determines the order in which to print polygons on a layer-by-layer basis?
2.) I am confused by Ghostkeeper's statement and would like clarification. After the slicing step, Cura knows all of the intersection points (or nodes) that the slicing plane made with the model, and it also knows which points are grouped together into polygons. It also knows the order in which the points in each polygon need to be printed, but the actual printing of the loop doesn't matter because the loop starts and ends at the same point. Does Ghostkeeper truly mean that, (a) for each layer, given some starting point, all loops are represented by the point on the loop that is closest to the initial starting point, proceeding with a simple nearest neighbor solution? Or does it mean that, (b) for a given starting point, all nodes on all untraversed polygons are checked for the smallest distance from the starting point, then representing that second polygon as a single point at the node, and so on and so forth until there are no polygons left?
If (a), it seems like this solution would be highly dependent on starting node, so how is the starting node picked? Does the algorithm cycle through all potential starting nodes?
If (b), I think this would make more sense and yield a better answer, but be potentially costly in testing each "current point's" distance from every node in every other untraveled polygon.
3.) Finally, if the bit of code isn't too large, or there is a comment directly in the code that explains it further, could someone provide that in the comments, along with what file it's located in? I am writing an academic paper for that has a small section in which I would like to cite how one or more popular tool path generation programs solve this problem for the 3D printing use-case.