Plotter path optimisation

Path optimisation is the step that puts the lines of a plotter drawing in a better order, and turns some of them round, so that the pen spends less time moving in the air between them. Finding the best order is a version of the travelling salesman problem, so in practice plotter software such as vpype uses a fast rule that gives a good order rather than the best one.

The problem

A pen plotter draws lines in exactly the order it receives them. After each line it lifts the pen and moves to the start of the next (see Plotter Art and the note on HP-GL). A program that generates a drawing usually writes its lines in the order it computed them, which can send the pen back and forth across the sheet thousands of times. A single drawing in Olof Broström's Unverified Air, no. 11, has 4,218 lines in three pens.¹

The travelling salesman problem asks for "the shortest possible route that visits each city exactly once and returns to the origin city". It is NP-hard, which in practice means that no known method finds the best route quickly once there are many cities.² For a plotter, each line is a city with two doors: the pen can start at either end.

Greedy nearest neighbour

The simplest useful rule is the nearest-neighbour algorithm: from where you are, always go to the nearest place not yet visited.³ Adapted to lines, it reads: start where the pen is. Among the lines not yet drawn, find the one with an end closest to the pen. If that is the line's far end, reverse the line. Draw it, and repeat from where it ends. The algorithm "quickly yields a short tour, but usually not the optimal one", and for some arrangements it gives a route much longer than the best.³

The cost of the rule grows with the square of the number of lines: a drawing of 10,000 lines needs some 50 million checks.

New drawing

In the tools

The plotter program vpype sorts lines with the command linesort: "By default, a fast, greedy algorithm is used", and it reverses a line "if it can further optimize the pen-up distance". An option, --two-opt, runs a further optimisation after the greedy pass.⁴ The plotter driver saxi "minimizes pen-up travel time by reordering & reversing paths".⁵ Its author, Jeremy Rose, says he worked out the optimisation from his own experiments, and that saxi had it a couple of years before vpype; he thinks vpype may well have arrived at the same, fairly obvious, method independently.⁶ The AxiDraw software has five settings, from "Strictly preserve file order" to "Full; Also allow path reversal"; by default it only joins paths that meet.⁷

When not to sort

Sorting changes how a drawing is made, and some artists treat that as part of the work. For the Art Blocks project Time Between the Lines is Thread Through the Mind (2024), the artist Matto asks those who plot it to "maintain the drawing order for canonical outputs - avoid reordering or optimizing the paths during plotting".⁸

Fills made of hatching and curves from flow fields are two common sources of many short lines, and so of long pen-up journeys.