How Do You Connect Two Boxes? Orthogonal Routing in Microseconds

Anyone who builds a diagram editor runs into a surprisingly tricky problem sooner or later: two boxes need to be connected by an orthogonal line, and the line has to avoid the other boxes and lines. The editor is interactive, so the computation has to be fast. Ideally so fast that it can run in every frame while a box is being dragged. The line should look simple, so it should have few bends. It does not have to be the shortest path, it just should not take absurd detours.

A few years ago I faced this problem myself. The existing solution, a breadth-first search (or A*), had become a performance bottleneck, so I did some research.

What turned up was an algorithm from 1969, written at Bell Labs in FORTRAN II for an IBM 7094 and intended for laying out traces on circuit boards. David W. Hightower describes it in A Solution to Line-Routing Problems on the Continuous Plane (DOI 10.1145/800260.809014).

I could not find a good modern explanation, even though I find the algorithm very interesting. It has a similar goal as the well-known breadth-first search, but goes about it in a completely different way. It has stayed in the back of my mind ever since, and now I have finally gotten around to rebuilding it in Rust together with Claude and to explaining here, with lots of pictures, how it works.

Why it is so much faster than the breadth-first search can already be seen in the first picture. On the left, the breadth-first search colors a large part of the board blue, 3687 grid cells, before it reaches B. A* with the Manhattan distance as its estimate gets by with the 218 yellow cells because it heads straight for B, but it first has to fill up the bay in front of the large box in the middle before it finds the way around the outside. On the right, Hightower's algorithm draws seven lines, and the path it finds is even easier to follow with the eye.

If you want to try the algorithm yourself right away, there is a demo at surt91.github.io/hightower that runs in the browser (via WASM). Boxes and endpoints can be dragged with the mouse, and the path follows immediately.

The problem, and why "shortest path" is the wrong goal

We are given a rectangular board, a set of horizontal and vertical segments as obstacles (a rectangle is simply four segments), and two points A and B. We are looking for a path of horizontal and vertical segments from A to B that does not touch any obstacle.

The classic approach is the algorithm by C. Y. Lee from 1961. You lay a grid over the board, mark the cells under the obstacles as occupied, and run a breadth-first search from A until it reaches B. This is guaranteed to find the shortest path and takes ten lines to implement. The catch is the resolution of the grid. In his paper, Hightower works through the example of a 9 × 9 inch circuit board rasterized to a thousandth of an inch: 81 million cells, which in 1969 could neither be stored nor searched. Today that fits into memory easily, but run time and memory still grow with the area instead of with the number of obstacles. A nearly empty, large diagram is just as expensive for the breadth-first search as a very full one.

The second point is optimality. Hightower did not want the shortest path for circuit traces, and I do not want it for diagrams either. A shortest path on the grid likes to squeeze through the gap between two boxes and produces steps along the way, as on the left of the next picture, with five bends and a length of 104. The path on the right is considerably longer at 142, but it goes around the top with two bends and looks better in a diagram.

Covers and escape lines

Hightower's algorithm works with two concepts, which we define first. The figures in this section and the next three all show the same scene, nine boxes on a board of 100 × 100 units.

For a point p, Hightower calls the nearest obstacle that blocks p's way in one of the four directions a cover. So there is an upper and a lower cover, both horizontal, and two side covers, a left and a right one, both vertical. On the left of the next picture, the covers of A are drawn in black and all other segments in gray. The upper cover is the bottom edge of the box that A sits against, the lower cover is the top edge of the box below, and the right cover is the left side of the narrow box to the right of A. There is no cover to the left, since nothing comes before the edge of the board.

The escape line through p is then the longest horizontal (or vertical) segment through p that fits between the covers. It is everything p "sees" in that direction. In my implementation it ends one unit before the cover, so that the path automatically keeps its distance from the obstacles later on. If there is no cover in a direction, the line ends at the edge of the board. On the right of the picture, the two escape lines of A are blue. The horizontal one runs from the left edge to just before the right cover, the vertical one from the lower cover up to A itself, because the upper cover lies directly above A.

The nice thing about this definition is that it can be computed without a grid. I keep the horizontal obstacles in a B-tree keyed by their y coordinate, and the vertical ones in a second one keyed by their x coordinate. To find the upper cover of a point, you enter the first tree at the point's y coordinate (that is a bisection, which the B-tree does in logarithmic time) and from there jump upward from row to row until a segment in the row covers the point's x coordinate. The tree only contains rows in which there is a segment at all, so empty rows are skipped. The lower and side covers work the same way, just in the other directions. The cost therefore depends on the number of obstacles and nothing else, in particular not on the size of the board.

How a line gets around the corner

Via its escape lines, a point can only move straight ahead. The way around an obstacle starts with a new line that branches off from a point on one of the old ones, and Hightower has two processes for choosing that point. First a remark that the next section expands on: the search runs from both ends. A network of escape lines grows from A and one from B, and a path is found as soon as a line of one network crosses a line of the other. Both processes work from the point where a network currently stands. Hightower calls it the object point Z. In the first turn, Z is the starting point of the network, after that it is always the most recent escape point.

Process I is the normal case. Consider the upper cover of the current point Z. If Z's horizontal escape line reaches past the end of this cover, we move sideways to one unit beyond that end. From there, a new vertical escape line gets past the cover going up. The point beyond the end of the cover is an escape point e, and its new line goes into the network. A candidate only counts as an escape point, however, if its new line really reaches past the cover whose end it goes around. The algorithm tries the same with the lower cover, where the four ends of the two horizontal covers take their turn in order of their Euclidean distance to Z. Only if none of them offers a way out do the two side covers get their turn, again sorted by distance. Where the target lies plays no role in this choice, and neither does whether the cover is in the way at all.

The next picture shows this step in three close-ups for the first turn. In the first close-up, Z's upper cover is orange, that is, the bottom edge of the box that Z sits against. In the second, the candidate e is circled in orange, one unit to the left of the left end of this cover, on Z's horizontal escape line. Its right end would also be a candidate, but the escape line does not reach that far, because the right cover is in the way first. In the third, the new vertical line through e is added, running up past the left side of the box.

Process II takes over when Process I fails at Z, for example because Z sits in a pocket. Then the network retreats onto Z's escape lines. Starting from their ends, it moves toward Z unit by unit, draws the escape line across it at every position, and tries Process I from there. I call these lines probe lines, because they only stay in the network if their position becomes an escape point. As soon as that works anywhere, the position becomes an escape point (in Hightower's terms a Process II escape point) and the search continues normally. If the retreat arrives back at Z without anything turning up, this network gives up, and the other one carries on alone. Only when both have given up has the search failed.

In the next picture, Z sits in such a pocket, which is closed at the top except for a gap between the segments d and d'. On the left, Process I fails. The candidate e beyond the end of the upper cover d cannot get past d with its vertical line (dashed), because the short segment r hangs below it. In the middle, the network has retreated to the upper end of Z's vertical escape line, the left blue dot. From there, the candidate beyond d lies above r, and its line leads through the gap. On the right, the finished path can be seen.

Both processes follow one rule that makes the algorithm terminate and at the same time makes it incomplete: an escape line is never used twice. Each network remembers all the lines it has ever drawn, and a candidate whose line already exists is discarded. Because the coordinates are integers, there are only finitely many different escape lines (each one is a maximal free interval in a row or column). So at some point the algorithm runs out of supply and gives up.

Two networks grow toward each other

The two networks of A and B take turns. A turn, in Hightower's terms one run of the Escape Algorithm, consists of drawing the escape line through the current point, testing it against all lines of the other network that are perpendicular to it, and then looking for the next escape point. If two lines cross, the path runs from the crossing point along one line to its escape point, from there to that point's predecessor, and so on back to A, and on the other side likewise to B.

That is already the whole reconstruction. Every escape point lies on an escape line of its predecessor, so it shares an x or y coordinate with it, and the chain is therefore automatically orthogonal. In my implementation, the escape points form a tree with parent pointers. That makes Hightower's first improvement, the first clean-up step from the paper, unnecessary. Hightower had flat lists and first had to figure out which points lie between which.

The trivial case works on its own. In the first turn, each network draws both escape lines through its starting point. If A and B are in the same free row or column, or if they can be connected with a single bend, these first lines already cross.

The animation below plays back the run in the example scene event by event, A's network in blue, B's in green. At every new escape point, the cover whose end it goes around lights up in orange. In the first turn, A draws its two escape lines and slips around the left end of its upper cover; that is the step from the picture of Process I. In the second turn, B draws its lines and steps four units to the right, around the end of the box below it. Then A moves left in two more turns, with every new vertical line ending below the large box at the top left, while B goes up along its new vertical line to just beyond the top edge of the box to its left. In the sixth turn, B draws the horizontal line through this point, and it hits A's vertical line. The orange circle marks the crossing, after which the red path appears. In total, the run took six turns and eight lines.

Post-processing

The path read off the trees is valid, but not always pretty. Process I goes for the nearest cover end and not for the target, and escape lines are maximally long. Both lead to the path liking to make a detour and come back again, in the example scene the hook to the right of B. B's nearest cover end is the upper right corner of the box below it, a good four units away, so B first steps to the right, even though this box is not in the way at all. Only the second escape point goes up, and its horizontal line hits A's vertical line. The path therefore runs four units to the right of B, then up and back to the left, where it could have gone straight up above B.

Hightower calls the repair the second improvement. It runs twice, once from A to B and once over the reversed list. First, the first segment is extended as far as the obstacles allow; if the extension hits a later path segment lying across it, everything in between is dropped. Then a probe point is moved along each segment, unit by unit from the start of the segment, and from there lines are shot out across the segment. If one of them hits a later parallel segment, the path is shortcut there, and the next segment takes its turn. The probing removes hooks like the one at B, and it repairs a quirk of Process II: the retreat always starts at the far end of a line, so the raw path likes to zigzag from wall to wall in a corridor. On the left of the next picture is the raw path with the hook, as it comes out of the escape points, and on the right the same path after post-processing.

The test from the paper

How do I know that the rebuild does what Hightower described? Whether the paths are valid is easy to check, but whether they are Hightower's paths is not. The paper is not trivial to read, and the flowcharts are complex enough that they can quite reasonably be read in two different ways. For this question, the paper brings its own test. The appendix shows solutions for circuit boards, diagrams and mazes, among them an orthogonal version of the Hampton Court hedge maze with the path the program found in 1969. I traced the walls from the scan and let the router loose on them. Its path in the next picture takes the same route as Hightower's plot.

The maze is a good test because it consists almost entirely of pockets. In the example scene above, the algorithm got by with Process I; here it needs 49 turns, draws 75 escape lines and tries 146 probe lines of Process II in between. Above the plot in the original paper, by the way, it says "Total Time .0005". Presumably this means hours, so just under two seconds on the machine of the time. My laptop needs 134 microseconds, a good four orders of magnitude less.

Where it breaks

The algorithm can miss a path that exists. Hightower attributes this mainly to the rule that no escape line is used twice, and describes the case himself: if the network has used an escape line to get into a box through a narrow opening, it cannot get out again through the same opening. He adds that in all his experiments a path was found whenever one existed. I checked this by generating random scenes of boxes with small openings and comparing every answer against the breadth-first search. Of 16782 solvable scenes, the algorithm failed to solve 297, just under 2 percent.

Some of these are due to the edge of the board: the paper only provides for the retreat in Process II from line ends that end at a cover, so a line that runs all the way to the edge offers no retreat positions. To keep this effect out of the picture, I repeated the search with a closed wall around every scene, so that no escape line ever reaches the edge. Of 119110 solvable scenes, 318 then remain unsolved. The smallest of them has nine segments (not counting the wall) and can be seen in the next picture. It shows that the rule is not solely to blame.

In the picture, A's blue lines fill the room and B's green ones the rest, but they never meet. The only way out of the room leads through the slot in the right wall, like the gray dashed path of the breadth-first search, and in front of the slot lies a small pocket. Neither network gets a line from its escape points into this pocket that it then follows up. Each network only searches from its most recent point, and a line that has been drawn once is not considered as a candidate again. Complete line-search methods, by the way, already existed back then. K. Mikami and K. Tabuchi had published one in 1968 that draws new lines from every grid point of every line and therefore leaves out no position, but in return it needs a grid again and many times as many lines.

In practice, Hightower is therefore a fast heuristic that needs a complete algorithm as a fallback. It also pays off to recompute paths only when something has changed within their bounding box.

The successor: visibility graph and A*

What has prevailed since 1969? Interestingly, not a better variant of the line search, but a combination of Hightower's basic idea and classic graph search. The insight that only the edges of the obstacles matter and that the grid in between is wasted has survived.

Today's standard for diagram editors is Orthogonal Connector Routing by Wybrow, Marriott and Stuckey (Graph Drawing 2009), implemented in the library libavoid, which Inkscape uses, among others. The construction is simple. You take the horizontal and vertical lines through all obstacle sides, shifted outward by one unit, plus the lines through start and target. Their intersections form the nodes of a graph, the free pieces between them the edges. In the next picture, these are the thin blue lines and the small dots on them, 88 nodes and 152 edges for the scene from the first picture. Every orthogonal path can be pushed onto this sparse grid without getting longer, so a search on it always finds a path if one exists, and with A* also the shortest one. Because A* takes a cost function, bends can be penalized at the same time. In the picture, both paths are 60 units long, so without a penalty they are equally good, and on the left A* happened to pick one with three bends. With a penalty of 20 units per bend, it takes the one with two on the right. The blind spot from above is gone, and the question "shortest or calm path?" can be pushed one way or the other with a parameter.

The price is the size of the graph. In the worst case it grows quadratically with the number of obstacles, and with it the effort for A*. With 20 rectangles that does not matter, with 320 it certainly does.

How fast is it?

I ran all three routers on the same scenes with randomly placed rectangles: Hightower, the visibility graph with A*, and the breadth-first search. The numbers are medians over 41 scenes per configuration, measured on an ordinary laptop. In the left chart, the side length of the board grows from 64 to 2048 units with 20 rectangles; in the right one, the board stays at 256 × 256 units and the number of rectangles rises from 0 to 320.

The left curve is the reason for this article. With 20 rectangles, Hightower needs one to five microseconds per route, and it does not care whether the board is 64 or 2048 units wide. The visibility graph does not care either; it stays at a constant 20 microseconds or so, about ten times Hightower. The breadth-first search scales with the area and ends up at over 90 milliseconds at a side length of 2048 units, which would be too slow for an interactive editor with many edges.

On the right you can see where the two grid-free methods pay their price. With the number of obstacles, Hightower's cost grows because every cover query runs through more rows and Process II tries more lines. In the visibility graph, the number of nodes grows quadratically, and A* has to touch correspondingly more of them. At 160 rectangles on 256 × 256 units, the scene is so full that the visibility graph takes as long as the breadth-first search, at 320 rectangles twice as long, while Hightower stays at just under 50 microseconds. A diagram editor would have other worries in this scene, though. On top of that, at 160 rectangles Hightower failed to solve 36 solvable random scenes, at 320 still 13. The measurement keeps drawing new scenes until 41 of them are solved by all three routers.

For the editor, this results in a simple division of labor: Hightower for the many edges it handles in a few microseconds, and the visibility graph for the few where Hightower gives up.

The Rust code, including a reusable library crate, is on GitHub at github.com/surt91/hightower, together with the demo from the beginning.