Path Optimisation for Project Scribble
This was an interesting sub-problem that I discovered in the Project Scribbles: when deciding what route to take, the pathing is important. There are a few factors to take into account. If you're cutting, then cutting internal holes before external ones are important, if you're drawing, less so, but your gondola design might mean you want to work in one particular direction to reduce smudging. Either way, you generally want to travel the least amount of distance.
Using the SVG extraction scripts, it will produce something like this (with pen up movements in green), Some quick calculations (and the unit involved here is irrelevant), will show that the
| Pen Up Movement | 7,566 | 51% |
| Pen Down Movement | 7,144 | 49% |
| Total Movement | 14,710 |
Let's assume all the pen down movements are needed (reducing this will effectively change the picture, even if some of those movements might be 'too small' to work on the plotter), then at the moment 51% of the time is spent moving without making essential marks, which means smudges etc.
The easiest optimisation to do is a simple closest-next-start. Lets assume each path can be run in either direction, we start on one path, and then we look at all other paths to see which is the next closest end. Note we look at both ends. Does it matter which path we start with? Yes, but this is simple mode, so we're just going to start with the first path in the SVG and go from there.
With the example above, it produces an output:
| Pen Up Movement | 2,223 | 23% |
| Pen Down Movement | 7,144 | 49% |
| Total Movement | 9,457 |
An immediate reduction down over 5k of unit distance - only traveling 64% of what it would have traveled previously. Not only that but as each travel path is shorter, there is less smudging etc.
Does this always end in a reduction? Its pretty easy to produce path combinations which will provide longer solutions then the original, and there is plenty of academic mathematical work online for producing better solutions.
In this above diagram, we show where the algorithm will initially have a short jump, but because it doesn't take into account the entire system, it will follow by a long pen-up-move, where several more-optimal paths do exist (i.e going to the vertical is always more optimal either way around).
However, as a general rule, a simple optimisation for most pictures will probably suffice, and if the code is abstracted correctly, then adding in new optimisation routes later for 'fun' are always possible without impacting any other component.