Wie verbindet man zwei Kästen? Routing für Diagramm-Editoren

Wer einen Diagramm-Editor baut, stößt irgendwann auf ein gar nicht so triviales Problem: Zwei Kästen sollen mit einer rechtwinkligen Linie verbunden werden, und die Linie soll den anderen Kästen und Linien ausweichen. Der Editor ist interaktiv, also muss die Berechnung schnell sein. Im Idealfall so schnell, dass sie beim Verschieben eines Kastens in jedem Frame mitläuft. Die Linie soll einfach aussehen, also wenige Knicke haben. Der kürzeste Pfad muss sie dabei nicht sein, sie soll nur keine absurden Umwege gehen.

Vor ein paar Jahren stand ich selbst vor diesem Problem. Die bestehende Lösung, eine A* auf einem Gitter (also eine etwas bessere Breitensuche), war zum Performance-Engpass geworden, also habe ich recherchiert.

Dabei tauchte ein Algorithmus aus dem Jahr 1969 auf, geschrieben bei den Bell Labs in FORTRAN II für eine IBM 7094 und gedacht für das Verlegen von Leiterbahnen auf Platinen. David W. Hightower beschreibt ihn in A Solution to Line-Routing Problems on the Continuous Plane (DOI 10.1145/800260.809014).

Eine gute moderne Erklärung habe ich nicht gefunden, obwohl ich den Algorithmus sehr interessant finde. Er hat ein ähnliches Ziel wie die bekannte Breitensuche, geht es aber völlig anders an. Seitdem ist er mir im Hinterkopf geblieben, und nun bin ich endlich dazu gekommen, ihn zusammen mit Claude in Rust nachzubauen und hier mit vielen Bildern zu erklären, wie er funktioniert.

Warum er so viel schneller ist als die Breitensuche, kann man sich schon am ersten Bild klarmachen. Links färbt die Breitensuche einen Großteil des Spielfelds blau ein, 3687 Gitterzellen, bevor sie B erreicht. A* mit der Manhattan-Distanz als Schätzung kommt mit den 218 gelben Zellen aus, weil es gezielt auf B zuläuft, muss aber erst die Bucht vor dem großen Kasten in der Mitte auffüllen, bevor es den Weg außen herum findet. Rechts zeichnet Hightowers Algorithmus sieben Linien, und der Pfad, den er findet, ist mit dem Auge sogar leichter zu verfolgen.

Wer den Algorithmus gleich selbst ausprobieren will, findet unter surt91.github.io/hightower eine Demo, die im Browser (via WASM) läuft. Kästen und Endpunkte lassen sich mit der Maus verschieben, und der Pfad folgt sofort.

Das Problem und warum „kürzester Pfad" das falsche Ziel ist

Gegeben sind ein rechteckiges Spielfeld, eine Menge horizontaler und vertikaler Strecken als Hindernisse (ein Rechteck besteht einfach aus vier Strecken) und zwei Punkte A und B. Gesucht ist ein Pfad aus horizontalen und vertikalen Segmenten von A nach B, der kein Hindernis berührt.

Der Klassiker dafür ist der Algorithmus von C. Y. Lee aus dem Jahr 1961. Man legt ein Gitter über das Spielfeld, markiert die Zellen unter den Hindernissen als belegt und lässt von A aus eine Breitensuche laufen, bis sie B erreicht. Das findet garantiert den kürzesten Weg und ist in zehn Zeilen implementiert. Der Haken ist die Auflösung des Gitters. Hightower rechnet in seinem Paper eine 9 × 9 Zoll große Platine vor, gerastert auf ein Tausendstel Zoll: 81 Millionen Zellen, die man 1969 weder speichern noch durchsuchen konnte. Heute passt das locker in den Speicher, aber Laufzeit und Speicherbedarf wachsen weiterhin mit der Fläche statt mit der Anzahl der Hindernisse. Ein fast leeres, großes Diagramm ist für die Breitensuche genauso teuer wie ein sehr volles.

Der zweite Punkt ist die Optimalität. Für Leiterbahnen wollte Hightower nicht den kürzesten Weg, und für Diagramme will ich ihn auch nicht. Ein kürzester Weg auf dem Gitter zwängt sich gern durch die Lücke zwischen zwei Kästen und produziert dabei Stufen, wie links im nächsten Bild mit fünf Knicken und einer Länge von 104. Der Weg rechts ist mit 142 deutlich länger, kommt aber oben herum mit zwei Knicken aus und sieht in einem Diagramm besser aus.

Cover und Escape-Linien

Hightowers Algorithmus arbeitet mit zwei Begriffen, die wir zuerst definieren. Die Abbildungen in diesem und den nächsten drei Abschnitten zeigen alle dieselbe Szene, neun Kästen in einem Feld von 100 × 100 Einheiten.

Für einen Punkt p nennt Hightower das nächste Hindernis, das p in einer der vier Richtungen den Weg versperrt, ein Cover. Es gibt also ein oberes und ein unteres Cover, beide horizontal, und zwei seitliche, ein linkes und ein rechtes, beide vertikal. Links im nächsten Bild sind die Cover von A schwarz gezeichnet und alle anderen Strecken grau. Das obere Cover ist die Unterkante des Kastens, an dem A klebt, das untere die Oberkante des Kastens darunter, das rechte die linke Seite des schmalen Kastens rechts von A. Nach links gibt es kein Cover, da kommt bis zum Rand nichts.

Die Escape-Linie durch p ist dann die längste waagerechte (oder senkrechte) Strecke durch p, die zwischen den Covern Platz hat. Sie ist alles, was p in dieser Richtung „sieht". In meiner Implementierung endet sie eine Einheit vor dem Cover, damit der Pfad später automatisch Abstand zu den Hindernissen hält. Wenn in einer Richtung kein Cover existiert, endet die Linie am Rand des Spielfelds. Rechts im Bild sind die beiden Escape-Linien von A blau. Die waagerechte läuft vom linken Rand bis kurz vor das rechte Cover, die senkrechte vom unteren Cover hoch bis zu A selbst, weil das obere Cover direkt über A liegt.

Das Schöne an dieser Definition ist, dass man sie ohne Gitter ausrechnen kann. Ich halte die horizontalen Hindernisse in einem B-Tree, dessen Schlüssel die y-Koordinate ist, und die vertikalen in einem zweiten mit der x-Koordinate als Schlüssel. Das obere Cover eines Punktes findet man, indem man im ersten Baum bei der y-Koordinate des Punktes einsteigt (das ist eine Bisektion, der B-Tree erledigt sie in logarithmischer Zeit) und von dort aus nach oben von Zeile zu Zeile springt, bis eine Strecke in der Zeile die x-Koordinate des Punktes überdeckt. Im Baum stehen nur Zeilen, in denen überhaupt eine Strecke liegt, leere Zeilen werden also übersprungen. Das untere und die seitlichen Cover findet man genauso, nur in die anderen Richtungen. Die Kosten hängen damit von der Anzahl der Hindernisse ab und von sonst nichts, insbesondere nicht von der Größe des Spielfelds.

Wie eine Linie um die Ecke kommt

Über seine Escape-Linien kommt ein Punkt nur geradeaus voran. Um ein Hindernis herum führt erst eine neue Linie, die von einem Punkt auf einer der alten abzweigt, und für die Wahl dieses Punktes hat Hightower zwei Prozesse. Vorweg eine Bemerkung, die der nächste Abschnitt ausführt: Die Suche läuft von beiden Enden aus. Von A und von B wächst je ein Netz aus Escape-Linien, und ein Pfad ist gefunden, sobald eine Linie des einen Netzes eine Linie des anderen kreuzt. Beide Prozesse arbeiten von dem Punkt aus, an dem ein Netz gerade steht. Hightower nennt ihn den Objektpunkt Z. Im ersten Zug ist Z der Startpunkt des Netzes, danach der jeweils jüngste Escape-Punkt.

Prozess I ist der Normalfall. Betrachten wir das obere Cover des aktuellen Punktes Z. Wenn die horizontale Escape-Linie von Z über das Ende dieses Covers hinausreicht, gehen wir seitlich bis eine Einheit hinter das Ende. Von dort aus kommt eine neue vertikale Escape-Linie an dem Cover vorbei nach oben. Der Punkt hinter dem Ende ist ein Escape-Punkt e, und seine neue Linie wandert ins Netz. Ein Kandidat zählt allerdings nur dann als Escape-Punkt, wenn seine neue Linie wirklich über das Cover hinausreicht, um dessen Ende er herumgeht. Das Gleiche probiert der Algorithmus mit dem unteren Cover, wobei die vier Enden der beiden horizontalen Cover in der Reihenfolge ihrer euklidischen Nähe zu Z an die Reihe kommen. Erst wenn keines davon einen Ausweg bietet, sind die beiden seitlichen Cover dran, wieder nach Nähe sortiert. Wo das Ziel liegt, spielt bei dieser Auswahl keine Rolle, und ob das Cover überhaupt im Weg ist, auch nicht.

Das nächste Bild zeigt diesen Schritt in drei Ausschnitten für den ersten Zug. Im ersten Ausschnitt ist das obere Cover von Z orange, also die Unterkante des Kastens, an dem Z klebt. Im zweiten ist der Kandidat e orange eingekreist, eine Einheit links vom linken Ende dieses Covers, auf der waagerechten Escape-Linie von Z. Sein rechtes Ende wäre auch ein Kandidat, aber dorthin reicht die Escape-Linie nicht, das rechte Cover ist vorher im Weg. Im dritten kommt die neue senkrechte Linie durch e dazu, die links am Kasten vorbei nach oben läuft.

Prozess II greift, wenn Prozess I an Z scheitert, etwa weil Z in einer Tasche sitzt. Dann zieht sich das Netz auf die Escape-Linien von Z zurück. Es geht von deren Enden aus Einheit für Einheit auf Z zu, zieht an jeder Position die Escape-Linie quer dazu und versucht von dort aus Prozess I. Diese Linien nenne ich Sondenlinien, weil sie nur dann im Netz bleiben, wenn ihre Position zum Escape-Punkt wird. Sobald das irgendwo klappt, wird die Position zum Escape-Punkt (bei Hightower ein Process II escape point), und die Suche geht normal weiter. Kommt der Rückzug wieder bei Z an, ohne dass sich etwas ergeben hat, gibt dieses Netz auf, und das andere zieht allein weiter. Erst wenn beide aufgegeben haben, ist die Suche gescheitert.

Im nächsten Bild sitzt Z in so einer Tasche, die oben bis auf eine Lücke zwischen den Strecken d und d' geschlossen ist. Links scheitert Prozess I. Der Kandidat e hinter dem Ende des oberen Covers d kommt mit seiner senkrechten Linie (gestrichelt) nicht an d vorbei, weil darunter die kurze Strecke r hängt. In der Mitte hat sich das Netz an das obere Ende der senkrechten Escape-Linie von Z zurückgezogen, den linken blauen Punkt. Von dort aus liegt der Kandidat hinter d oberhalb von r, und seine Linie führt durch die Lücke. Rechts ist der fertige Pfad zu sehen.

Beide Prozesse folgen einer Regel, die den Algorithmus terminieren lässt und ihn gleichzeitig unvollständig macht: Eine Escape-Linie wird nie zweimal benutzt. Jedes Netz merkt sich alle Linien, die es je gezeichnet hat, und ein Kandidat, dessen Linie schon existiert, wird verworfen. Weil die Koordinaten ganzzahlig sind, gibt es nur endlich viele verschiedene Escape-Linien (jede ist ein maximales freies Intervall in einer Zeile oder Spalte). Irgendwann geht dem Algorithmus also der Nachschub aus, und er gibt auf.

Zwei Netze wachsen aufeinander zu

Die beiden Netze von A und B kommen abwechselnd an die Reihe. Ein Zug besteht darin, die Escape-Linie durch den aktuellen Punkt zu zeichnen, sie gegen alle senkrecht dazu stehenden Linien des anderen Netzes zu testen und dann den nächsten Escape-Punkt zu suchen. Kreuzen sich zwei Linien, läuft der Pfad vom Kreuzungspunkt entlang der einen Linie zu ihrem Escape-Punkt, von dort zu dessen Vorgänger, und so weiter bis A, und auf der anderen Seite genauso bis B.

Das ist schon die ganze Rekonstruktion. Jeder Escape-Punkt liegt auf einer Escape-Linie seines Vorgängers, teilt sich mit ihm also eine x- oder y-Koordinate, und die Kette ist damit automatisch rechtwinklig. In meiner Implementierung bilden die Escape-Punkte einen Baum mit Elternzeigern. Das macht Hightowers first improvement, den ersten Aufräumschritt aus dem Paper, überflüssig. Hightower hatte flache Listen und musste erst herausfinden, welche Punkte zwischen welchen liegen.

Der triviale Fall funktioniert dabei von selbst. Im ersten Zug zeichnet jedes Netz beide Escape-Linien durch seinen Startpunkt. Stehen A und B in derselben freien Zeile oder Spalte, oder lassen sie sich mit einem einzigen Knick verbinden, dann kreuzen sich diese ersten Linien bereits.

Die Animation unten spielt den Lauf in der Beispielszene Ereignis für Ereignis ab, das Netz von A in Blau, das von B in Grün. Bei jedem neuen Escape-Punkt leuchtet das Cover orange auf, um dessen Ende er herumgeht. Im ersten Zug zeichnet A seine beiden Escape-Linien und schlüpft links um sein oberes Cover herum, das ist der Schritt aus dem Bild zu Prozess I. Im zweiten Zug zeichnet B seine Linien und weicht vier Einheiten nach rechts aus, um das Ende des Kastens unter ihm herum. Dann wandert A in zwei weiteren Zügen nach links, wobei jede neue senkrechte Linie unter dem großen Kasten oben links endet, während B an seiner neuen senkrechten Linie nach oben geht, bis hinter die Oberkante des Kastens links von ihm. Im sechsten Zug zeichnet B die waagerechte Linie durch diesen Punkt, und sie trifft die senkrechte Linie von A. Der orange Kreis markiert die Kreuzung, danach erscheint der rote Pfad. Insgesamt hat der Lauf sechs Züge und acht Linien gebraucht.

Nachbearbeitung

Der Pfad, den man aus den Bäumen abliest, ist gültig, aber nicht immer schön. Prozess I richtet sich nach dem nächsten Cover-Ende und nicht nach dem Ziel, und Escape-Linien sind maximal lang. Beides führt dazu, dass der Pfad gern einen Umweg macht und wieder zurückkommt, in der Beispielszene den Haken rechts von B. Das nächste Cover-Ende von B ist die rechte obere Ecke des Kastens unter ihm, gut vier Einheiten entfernt, also weicht B als Erstes nach rechts aus, obwohl dieser Kasten gar nicht im Weg liegt. Erst der zweite Escape-Punkt geht nach oben, und seine horizontale Linie trifft die senkrechte Linie von A. Der Pfad läuft deshalb von B vier Einheiten nach rechts, dann hoch und wieder zurück nach links, wo er auch direkt über B hätte hochlaufen können.

Hightower nennt die Reparatur second improvement. Sie läuft zweimal, einmal von A nach B und einmal über die umgekehrte Liste. Zuerst wird das erste Segment so weit verlängert, wie die Hindernisse es zulassen; trifft die Verlängerung ein späteres, quer dazu liegendes Pfadsegment, fällt alles dazwischen weg. Dann schiebt man über jedes Segment einen Tastpunkt, vom Anfang des Segments aus Einheit für Einheit, und schießt von dort Linien quer zum Segment ab. Trifft eine davon ein späteres, parallel liegendes Segment, wird der Pfad dort abgekürzt, und das nächste Segment ist an der Reihe. Das Tasten entfernt Haken wie den bei B, und es repariert eine Eigenart von Prozess II: Der Rückzug startet immer am fernen Ende einer Linie, sodass der Rohpfad in einem Gang gern von Wand zu Wand pendelt. Im nächsten Bild ist links der Rohpfad mit dem Haken zu sehen, wie er aus den Escape-Punkten kommt, rechts derselbe Pfad nach der Nachbearbeitung.

Der Test aus dem Paper

Woher weiß ich, dass der Nachbau das tut, was Hightower beschrieben hat? Ob die Pfade gültig sind, ist leicht zu prüfen, aber ob es Hightowers Pfade sind, nicht. Das Paper ist nicht ganz trivial zu lesen und die Ablaufdiagramme sind komplex genug, dass man sie durchaus auf zwei unterschiedliche Arten lesen kann. Für diese Frage liefert das Paper selbst eine Probe mit. Im Anhang sind Lösungen für Platinen, Diagramme und Labyrinthe abgebildet, darunter eine rechtwinklige Fassung des Heckenlabyrinths von Hampton Court mit dem Pfad, den das Programm 1969 gefunden hat. Ich habe die Wände aus dem Scan nachgezeichnet und den Router darauf losgelassen. Sein Pfad im nächsten Bild nimmt dieselbe Route wie Hightowers Plot.

Das Labyrinth ist eine gute Probe, weil es fast nur aus Taschen besteht. In der Beispielszene oben kam der Algorithmus mit Prozess I aus, hier braucht er 49 Züge, zieht 75 Escape-Linien und probiert dazwischen 146 Sondenlinien von Prozess II. Über dem Plot im Original-Paper steht übrigens „Total Time .0005". Vermutlich sind damit Stunden gemeint, also knapp zwei Sekunden auf der Maschine von damals. Mein Laptop braucht 134 Mikrosekunden, gut vier Größenordnungen weniger.

Wo es kaputt geht

Der Algorithmus kann einen Pfad übersehen, der existiert. Hightower führt das vor allem auf die Regel zurück, dass keine Escape-Linie zweimal benutzt wird, und beschreibt den Fall selbst: Wenn das Netz eine Escape-Linie benutzt hat, um durch eine schmale Öffnung in eine Box zu gelangen, kommt es durch dieselbe Öffnung nicht wieder heraus. Er schreibt dazu, in allen seinen Experimenten sei ein Pfad gefunden worden, wenn einer existierte. Ich habe das nachgeprüft, indem ich zufällige Szenen aus Kästen mit kleinen Öffnungen erzeugt und jede Antwort gegen die Breitensuche abgeglichen habe. Von 16782 lösbaren Szenen hat der Algorithmus 297 nicht gelöst, also knapp 2 Prozent.

Ein Teil davon geht auf den Spielfeldrand zurück: Das Paper sieht den Rückzug in Prozess II nur von Linienenden vor, die an einem Cover enden, und eine Linie, die bis zum Rand läuft, bietet deshalb keine Rückzugspositionen. Damit dieser Effekt keine Rolle spielt, habe ich die Suche mit einer geschlossenen Mauer um jede Szene wiederholt, sodass keine Escape-Linie je den Rand erreicht. Von 119110 lösbaren Szenen bleiben dann 318 ungelöst. Die kleinste davon hat neun Strecken (abgesehen von der Mauer) und ist im nächsten Bild zu sehen. An ihr sieht man, dass die Regel nicht allein schuld ist.

Im Bild füllen die blauen Linien von A den Raum und die grünen von B den Rest, aber sie treffen sich nie. Der einzige Weg aus dem Raum führt durch den Schlitz in der rechten Wand, so wie der grau gestrichelte Pfad der Breitensuche, und vor dem Schlitz liegt eine kleine Tasche. Keines der beiden Netze bekommt von seinen Escape-Punkten aus eine Linie in diese Tasche, die es weiterverfolgt. Jedes Netz sucht nur von seinem jüngsten Punkt aus, und eine Linie, die einmal gezeichnet ist, kommt als Kandidat nicht wieder infrage. Vollständige Linienverfahren gab es damals übrigens schon. K. Mikami und K. Tabuchi hatten 1968 eines veröffentlicht, das von jedem Gitterpunkt jeder Linie neue Linien zieht und deshalb keine Position auslässt, dafür aber wieder ein Gitter und ein Vielfaches an Linien braucht.

Für die Praxis ist Hightower damit eine schnelle Heuristik, die einen vollständigen Algorithmus als Fallback braucht. Außerdem lohnt es sich, Pfade nur dann neu zu berechnen, wenn sich innerhalb ihrer Bounding Box etwas geändert hat.

Der Nachfolger: Sichtbarkeitsgraph und A*

Was hat sich seit 1969 durchgesetzt? Interessanterweise keine bessere Variante der Liniensuche, sondern eine Kombination aus Hightowers Grundidee und klassischer Graphsuche. Die Einsicht, dass nur die Kanten der Hindernisse zählen und das Gitter dazwischen Verschwendung ist, hat überlebt.

Der Standard für Diagramm-Editoren ist heute Orthogonal Connector Routing von Wybrow, Marriott und Stuckey (Graph Drawing 2009), implementiert in der Bibliothek libavoid, die unter anderem Inkscape benutzt. Die Konstruktion ist einfach. Man nimmt die horizontalen und vertikalen Geraden durch alle Hindernisseiten, um eine Einheit nach außen verschoben, dazu die Geraden durch Start und Ziel. Ihre Schnittpunkte bilden die Knoten eines Graphen, die freien Stücke dazwischen die Kanten. Im nächsten Bild sind das die dünnen blauen Linien und die kleinen Punkte darauf, für die Szene aus dem ersten Bild 88 Knoten und 152 Kanten. Jeder rechtwinklige Pfad lässt sich auf dieses dünne Gitter schieben, ohne länger zu werden, also findet eine Suche darauf immer einen Pfad, wenn es einen gibt, und mit A* auch den kürzesten. Weil A* eine Kostenfunktion bekommt, kann man Knicke gleich mit bestrafen. Im Bild sind beide Pfade 60 Einheiten lang, ohne Strafe also gleich gut, und A* hat links zufällig einen mit drei Knicken erwischt. Mit einer Strafe von 20 Einheiten pro Knick nimmt es rechts den mit zwei. Der blinde Fleck von oben ist damit weg, und die Frage „kürzester oder ruhiger Pfad?" lässt sich über einen Parameter in die eine oder andere Richtung schieben.

Der Preis ist die Größe des Graphen. Sie wächst im schlimmsten Fall quadratisch mit der Zahl der Hindernisse, und mit ihr der Aufwand von A*. Bei 20 Rechtecken spielt das keine Rolle, bei 320 durchaus.

Wie schnell ist es?

Ich habe alle drei Router auf denselben Szenen mit zufällig platzierten Rechtecken laufen lassen: Hightower, den Sichtbarkeitsgraphen mit A* und die Breitensuche. Die Zahlen sind Mediane über 41 Szenen pro Konfiguration, gemessen auf einem gewöhnlichen Laptop. Im linken Diagramm wächst die Kantenlänge des Spielfelds bei 20 Rechtecken von 64 auf 2048 Einheiten, im rechten bleibt das Feld bei 256 × 256 Einheiten, und die Zahl der Rechtecke steigt von 0 auf 320.

Die linke Kurve ist der Grund für diesen Artikel. Bei 20 Rechtecken braucht Hightower ein bis fünf Mikrosekunden pro Route, und es ist ihm egal, ob das Spielfeld 64 oder 2048 Einheiten breit ist. Dem Sichtbarkeitsgraphen ist es ebenso egal, er liegt konstant bei etwa 20 Mikrosekunden, also rund zehnmal über Hightower. Die Breitensuche skaliert mit der Fläche und landet bei 2048 Einheiten Kantenlänge bei gut 90 Millisekunden, was für einen interaktiven Editor mit vielen Kanten zu langsam wäre.

Rechts sieht man, wo die beiden gitterfreien Verfahren ihren Preis zahlen. Mit der Anzahl der Hindernisse wachsen die Kosten bei Hightower, weil jede Cover-Abfrage durch mehr Zeilen läuft und Prozess II mehr Linien probiert. Beim Sichtbarkeitsgraphen wächst die Knotenzahl quadratisch, und A* muss entsprechend mehr davon anfassen. Bei 160 Rechtecken auf 256 × 256 Einheiten ist die Szene so voll, dass der Sichtbarkeitsgraph so lange braucht wie die Breitensuche, bei 320 Rechtecken doppelt so lange, während Hightower bei knapp 50 Mikrosekunden bleibt. Ein Diagramm-Editor hätte in dieser Szene allerdings andere Sorgen. Dazu kommt, dass Hightower bei 160 Rechtecken 36 lösbare Zufallsszenen nicht gelöst hat, bei 320 noch 13. Die Messung zieht so lange neue Szenen, bis 41 davon von allen drei Routern gelöst sind.

Für den Editor ergibt sich daraus eine einfache Arbeitsteilung: Hightower für die vielen Kanten, die er in ein paar Mikrosekunden erledigt, und der Sichtbarkeitsgraph für die wenigen, bei denen Hightower aufgibt.

Der Rust Code inklusive einer wiederverwendbaren lib-Crate liegt auf GitHub unter github.com/surt91/hightower, zusammen mit der Demo vom Anfang.