Formen addieren: Meine Bachelorarbeit über Minkowski-Summen

Am 15. Juli 2019 habe ich meine Bachelorarbeit Berechnung der Minkowski-Summe für einfache Polygone abgegeben. Das Thema ist mathematisch, hat aber eine anschauliche Interpretation: Welche Form entsteht, wenn man eine Form über eine andere bewegt und alle erreichbaren Positionen sammelt?

Hier ist die Kurzfassung der Arbeit – mit dem Schwerpunkt auf der zentralen Algorithmusidee statt auf allen Definitionen und Beweisen.

Die Form, die durch Addition entsteht #

Für zwei Punktmengen A und B in der Ebene ist die Minkowski-Summe definiert als

A ⊕ B = {a + b | a ∈ A, b ∈ B}

Man wählt je einen Punkt aus beiden Formen, addiert ihre Koordinaten und erhält einen Punkt der Summe. Wiederholt man das für alle Paare, wird das Ergebnis ausgefüllt.

Diese Operation kommt überall dort vor, wo Geometrie und Algorithmen zusammentreffen: bei der Bewegungsplanung, bei Kollisionstests und bei CNC- oder 3D-Druckerbahnen. Ein Hindernis lässt sich beispielsweise um die Form eines Roboters „aufblasen“. Danach kann man den Roboter als Punkt behandeln.

Der einfache Fall: konvexe Polygone #

Für zwei konvexe Polygone gibt es einen naiven und einen effizienten Ansatz. Der naive Ansatz bildet jede mögliche Summe zweier Eckpunkte und berechnet anschließend die konvexe Hülle. Das erzeugt bei n beziehungsweise m Ecken zunächst n · m Kandidaten.

Der bessere Algorithmus nutzt aus, dass die Kanten eines konvexen Polygons bereits nach ihrer Richtung geordnet sind. Man beginnt bei den lexikografisch kleinsten Ecken und läuft an beiden Polygonen entlang. Bei jedem Schritt wird die nächste Kantenrichtung verglichen; die kleinere Richtung wird in das Ergebnis übernommen. Jede Eingabekante wird genau einmal verarbeitet. Dadurch entsteht eine Laufzeit von O(n + m).

Die Lehre daraus ist klein, aber wichtig: Die Geometrie liefert eine Ordnung, die wir ausnutzen können. Dann müssen wir nicht mehr alle möglichen Eckpunktpaare erzeugen und sortieren.

Warum konkave Polygone schwieriger sind #

Bei konkaven Polygonen funktioniert dieser Rundgang nicht mehr. Die Summe kann Einbuchtungen enthalten, und Kanten können sich schneiden oder überlappen. Eine lokale Entscheidung über die nächste Kante reicht nicht aus, um die endgültige Grenze zu bestimmen.

Der Hauptteil meiner Arbeit verwendet deshalb die Konvolutionsmethode. Ihre zentrale Idee ist, zunächst bewusst eine übervollständige Anordnung zu konstruieren und erst danach zu entscheiden, welche Teile zur Minkowski-Summe gehören.

Der Algorithmus in drei Ideen #

1. Randkanten kombinieren #

Man nimmt eine orientierte Kante aus Polygon P und eine orientierte Kante aus Polygon Q. Ihre Vektorsumme beschreibt ein verschobenes Kantenstück. Durch das Zusammenspiel der Kantenreihenfolgen entsteht eine Sammlung solcher Segmente: die Konvolution.

Diese Segmente sind noch nicht das Ergebnis. Sie sind Kandidaten für die spätere Grenze und können sich schneiden oder Regionen einschließen, die nicht Teil der Summe sind. Für zwei einfache Polygone mit n und m Ecken enthält die Konvolution höchstens O(nm) Segmente, bevor Schnittpunkte aufgelöst werden.

2. Eine planare Datenstruktur aufbauen #

An Schnittpunkten werden die Segmente geteilt und in einer DCEL (doubly connected edge list) gespeichert. Sie beschreibt Knoten, gerichtete Halbkanten, deren Zwillinge, die nächste Kante einer Fläche und die zugehörige Fläche.

Die DCEL ist die Verbindung zwischen Geometrie und Topologie. Statt für jeden Punkt komplizierte Fragen zu stellen, kann man die Begrenzung jeder Fläche ablaufen. Dabei müssen auch deckungsgleiche oder überlappende Segmente behandelt werden – besonders anspruchsvoll, wenn Koordinaten als Java-double gespeichert sind.

3. Die richtige Fläche über Windungszahlen auswählen #

Für jede Fläche wird die Windungszahl berechnet: vereinfacht gesagt, wie oft die orientierte Konvolution um einen Punkt dieser Fläche herumläuft.

Flächen mit positiver Windungszahl gehören zu P ⊕ Q. Ihre Grenzen werden über die DCEL verfolgt und zum Ausgabe-Polygon zusammengesetzt. Der Algorithmus versucht also nicht, die endgültige Grenze während der Konstruktion zu erraten. Er erzeugt mögliche Grenzen, beschriftet die Regionen und filtert die Anordnung mithilfe einer topologischen Invariante.

Die Geometrie schlägt Kanten vor; die Topologie entscheidet, welche Regionen bleiben.

Was die Implementierung schwierig machte #

Die mathematische Beschreibung ist ordentlich. Im Code stecken die Sonderfälle.

Ich habe die Algorithmen in Java 8 mit dem ADSToolbox-Framework der Universität Bayreuth implementiert und getestet. Einige praktische Erkenntnisse aus dieser Arbeit sind mir geblieben:

• Eingaben früh vereinheitlichen: Orientierung korrigieren und redundante Ecken entfernen.
• Redundante Objekte und Berechnungen vermeiden, weil die Konvolution schnell wächst.
• Datenstrukturen nach dem Zugriffsverhalten auswählen: Eine verkettete Liste kann aus einer linearen Operation unbemerkt eine quadratische machen.
• Gleitkomma-Vergleiche als Designproblem behandeln. Theoretisch gleiche Schnittpunkte können sich in einigen Bits unterscheiden.
• Nicht nur Koordinaten testen, sondern auch Topologie: Orientierung, Löcher und Flächenklassifikation.

Die Laufzeit der Konvolutionsmethode ist für zwei einfache Polygone durch O(n² · m²) beschränkt. Diese Schranke entsteht vor allem durch die potenziell quadratisch vielen Schnittpunkte der O(nm) Kandidatensegmente. Für den allgemeinen konkaven Fall ist die Methode robust, aber nicht die letzte mögliche Optimierung.

Rückblick #

Mir gefällt an diesem Projekt, dass die sichtbare Form aus mehreren Ebenen des Denkens entsteht: Vektoraddition, Kantenorientierung, planare Unterteilungen und Windungszahlen. Keine dieser Ideen reicht allein. Zusammen wird aus einer kontinuierlichen geometrischen Definition ein endlicher Algorithmus.

Der naheliegende nächste Schritt ist eine reduzierte Konvolution. Sie nutzt topologische Eigenschaften, um Segmente, die unmöglich zur Lösung beitragen können, gar nicht erst zu erzeugen. Weniger Segmente bedeuten weniger Schnittpunkte und weniger Verwaltungsaufwand.

Die vollständige Arbeit gibt es hier: Berechnung der Minkowski-Summe für einfache Polygone.

Im Rückblick bleibt für mich eine allgemeinere Lektion: Wenn eine direkte Konstruktion unübersichtlich wird, kann es besser sein, zunächst eine reichhaltige Zwischenrepräsentation aufzubauen und die Antwort anschließend mit der passenden Invariante daraus zu extrahieren.