Algorithm to resort curves for “shortest walk” through them

Grasshopper
1

Hi all,

I have CNC draw plotter with table 9x1.5m.
And I want to draw on it couple templates for metal constructions.
I have algoritm to convert dxf file to plotter’s file, it is not a problem, but before converting, curves in *.dxf should be resorted for “shortest walk” for pen for minimisation movements of the plotter and drawing time.
It seems the logic should be about below:
First point of the plotter is 0,0. So I need to find the nearest start/end point from all curves to 0,0, take first curve by first finded point, draw it from first point to the end, then find next nearest point of remaining curves and do the same and ect to the end.
But I do not know how to make in grashopper.
It seems it should be easy and it should be without kangaroo or galapagos. But I’m not sure.
May be do you have any ideas how to make algoritm of resorting curves for “shortest walk” through them?
I attached dxf file what I want to plot on the plotter.

Paraboloid_lekalo.dxf (924.6 KB)

2

Since you already know the tool position to be at the origin, you can simply:

  1. Find the closest curve to the tool position (i.e., origin).
  2. Determine which endpoint of the nearest curve is closest to the tool position.
  3. Push the curve into a container, like a list.
  4. Set the other, farthest curve endpoint as the next tool position and repeat until all curves have been visited.

For lots of curves, you might want to optimise this using something like spatial binning or clustering first. In RhinoCommon, you’ve access to an R-tree that can speed nearest neighbour searches up quite a bit.

3

To find the ultimate shortest route will be hard (you will have to solve the Chinese Postman Problem for that.
Looking at your dxf, most of the curves are long, going from one side of the material to the other. So I would keep it simple:
Sort curves midpoints in x and y direction (1 component) in GH
Next is to go from one curve to closest point on next curve.
You will have some slack movements, but over all will not be bad.

4

Sorting CNC curves by just x then y is usually only good for very simple cases. It ignores the actual travel distance between toolpaths, pen-up moves, machine dynamics, and contour relationships.

Haha, true, but as someone who has implemented that once in Python, I wouldn’t recommend it. It took me about 3 weeks to write an non-optimized version, but I learned a hell of a lot about graphs.

5

Here’s an example of what I wrote about above using some Python magic:

Screenshot 2026-05-10 at 13.58.11
Screenshot 2026-05-10 at 13.58.112564×538 147 KB

The “shortest walk” between curves is drawn in dark blue.

num_curves = len(C)

visited = []
indices = []
flip = []

current_pt = O
iterations = 0

while len(visited) < num_curves and iterations < num_curves:
    closest = num_curves + 1
    closest_pt = None
    closest_dd = float("inf")
    reverse = False

    for i, crv in enumerate(C):

        if i in visited:
            continue

        start_pt = crv.PointAtStart
        end_pt = crv.PointAtEnd

        dd_start = current_pt.DistanceToSquared(start_pt)
        dd_end = current_pt.DistanceToSquared(end_pt)

        if dd_start < closest_dd:
            closest_dd = dd_start
            closest = i
            closest_pt = end_pt
            reverse = False

        if dd_end < closest_dd:
            closest_dd = dd_end
            closest = i
            closest_pt = start_pt
            reverse = True

    if closest == num_curves + 1:
        break

    visited.append(closest)
    indices.append(closest)
    flip.append(reverse)

    current_pt = closest_pt
    iterations += 1

I = indices
F = flip

Performance isn’t too bad for this amount of curves (~192ms).

sort-and-flip-curves-for-shortest-walk.gh (42.0 KB)

6

WOW! This is very very very magnificent!
Thanks a lot and thanks again!