Table of Contents
An essential part of an image processing pipeline for pen plotters is path planning. Depending on the input lines, output size and speed of the plotter this can save hours of plotting time without any effect on the quality of the result.
The images below have been generated by placing 1000 short black lines randomly in a square. Highlighted in red are the travel paths between these lines.
While the example uses only single line segments, my implementation uses polylines as primitives as these can be drawn by a plotter without lifting the pen.
Unoptimized
Travel distance (red): ~21530 units
Greedy Path Planning
A greedy algorithm makes the locally optimal choice at each step.
For path planning this means that we start with some line (e.g. the first one in the image), then find the line closest to its end point and continue from there until we've drawn all lines of the image.
There are ways to find better paths but an algorithm likes this is a good compromise between computing time and the optimality of the output path.
Travel distance (red): ~1304 units
- 6.1% compared to unoptimized ordering
Line Flipping
A small further improvement can be made by considering both the start and end points of the other lines when searching for the closest next line, then reversing it if necessary.
This search can be sped up by using a data structure supporting fast (sub-linear time) nearest-neighbor queries, for example R-trees.
Just iterating over the remaining lines and picking the closest one (linear time) is a reasonable starting point.
Travel distance (red): ~913 units
- 4.2% compared to unoptimized ordering
- 70.0% compared to greedy ordering without flipping
How Much Better Can We Get?
Finding an optimal path is very hard. I suspect it's NP-hard but I'm not yet sure how to reduce a (known to be NP-hard) TSP (traveling salesperson problem) instance to it. We can however reduce the path-planning problem to a TSP instance and then use a high-quality TSP solver to find the best path (or something close to the best path).
The TSP asks for the optimal Hamiltonian circuit (a closed path visiting each point once) on a set of points connected by edges with different weights.
To go from lines to points, we can convert each line to three points (start, middle, end) where the middle point is connected to start and end with zero-cost edges while the cost of its edges to all other points is very high. This should guarantee that these three points are always traversed as either start->middle->end or end->middle->start.
Adding one additional point with zero-cost edges to all other points allows us to split the Hamiltonian circuit back into a path that should still be optimal.
From this converted input data, the
Concorde TSP solver
(
linkern
)
finds a path that's significantly better than the greedy solution.
Travel distance (red): ~619 units
- 2.9% compared to unoptimized ordering
- 67.5% compared to greedy ordering with flipping
In defense of the greedy algorithm, I'll mention that although we're comparing unoptimized Haskell code to (probably highly) optimized C, the running time of the TSP solver is twice as long.