Wie hilft die Minkowski-Summe einer Nesting-Software, in kurzer Zeit Tausende mögliche Positionen zu prüfen, ohne bei jedem Versuch zwei komplexe Bauteilkonturen vollständig miteinander zu vergleichen?
Ein wichtiges geometrisches Werkzeug bei Packungsalgorithmen wie Nesting und Bin Packing ist die Minkowski-Summe. Sie kann aus zwei Konturen ein sogenanntes Verbotsgebiet erzeugen. Liegt der Referenzpunkt eines verschobenen Bauteils in diesem Gebiet, überlappen sich die Teile. Liegt er außerhalb, ist die Position kollisionsfrei.
Der Clou: Aus einem Polygon-gegen-Polygon-Test wird bei fester Orientierung ein Punkt-in-Polygon-Test.
Warum das in der Praxis relevant ist
Beim Nesting sollen Bauteile möglichst gut auf Blechen, Platten, Textilien oder anderen Flächen angeordnet werden. Das gilt für neues Ausgangsmaterial ebenso wie für vorhandene Restflächen. Eine Optimierung prüft dafür sehr viele mögliche Positionen. Je komplexer die Konturen sind, desto aufwendiger werden wiederholte direkte Kollisionsprüfungen.
Ein vorberechnetes Verbotsgebiet fasst diese geometrische Information kompakt zusammen. Das bringt drei praktische Vorteile:
- Eine zentrale Kollisionsprüfung wird auf eine einfachere geometrische Abfrage reduziert.
- Verbotsgebiete können für wiederkehrende Kombinationen aus Bauteil und Orientierung erneut verwendet werden.
- Die Berechnung schafft eine belastbare Grundlage für heuristische und optimierende Nesting-Verfahren.
Die Minkowski-Summe optimiert die Materialausnutzung noch nicht selbst. Sie liefert jedoch ein wichtiges geometrisches Werkzeug, mit dem ein Nesting-Algorithmus zulässige und unzulässige Positionen effizient unterscheiden kann.
Minkowski-Summe: die geometrische Idee
Die Minkowski-Summe kombiniert zwei Formen durch Verschiebung: Man setzt die Form B gedanklich mit ihrem Bezugspunkt an jeden Punkt von A. Die gesamte dabei überstrichene Fläche ist die Minkowski-Summe.
Mathematisch wird diese Idee mit einer einzigen Definition beschrieben:
\[ A\oplus B=\{\,a+b\mid a\in A,\;b\in B\,\}. \]In Worten: Jeder Punkt aus A wird mit jedem Punkt aus B addiert. Die Polygone werden dabei als gefüllte Flächen einschließlich ihres Randes betrachtet.
Der Schritt zum Kollisionsgebiet
Wir wollen prüfen, bei welchen Positionen das bewegliche Polygon B mit dem festen Polygon A kollidiert.
Referenzpunkt und Position
Dazu wählen wir für \(B\) einen festen Referenzpunkt \(r\), beispielsweise eine Ecke oder den Schwerpunkt. Anschließend beschreiben wir die Form relativ zu diesem Punkt:
\[ \widetilde B=B-r. \]Für den Referenzpunkt selbst gilt \(r-r=(0,0)\). Seine gewünschte Position in der Ebene bezeichnen wir mit \(t\). Bei fester Orientierung lautet die platzierte Form daher
\[ \widetilde B+t. \]Dabei bleibt \(r\) fest mit der Geometrie von \(B\) verbunden, während \(t\) bei der Platzierung variiert.
Welche Positionen führen zu einer Kollision?
\(A\) und \(B\) kollidieren, wenn Punkte \(a\in A\) und \(\widetilde b\in\widetilde B\) existieren mit
\[ a=\widetilde b+t. \]Stellen wir diese Gleichung nach der gesuchten Position \(t\) um, erhalten wir
\[ t=a-\widetilde b=a+(-\widetilde b). \]Warum erscheint die punktgespiegelte Form?
Die Punkte \(-\widetilde b\) bilden gemeinsam die Form \(-\widetilde B\). Sie entsteht durch eine Punktspiegelung am Ursprung, also durch eine Drehung um 180 Grad. Durchlaufen \(a\) und \(\widetilde b\) ihre jeweiligen Polygone, erhalten wir alle kollidierenden Positionen des Referenzpunkts. Somit gilt
\[ F_r=A\oplus(-\widetilde B)=A\oplus\bigl(-(B-r)\bigr). \]Im Inneren von \(F_r\) überlappen sich die Polygone. Auf dem Rand berühren sie sich. Dagegen ist eine Position außerhalb von \(F_r\) kollisionsfrei.
Das Verbotsgebiet hängt vom gewählten Referenzpunkt \(r\) ab. Ein anderer Referenzpunkt verschiebt auch \(F_r\). Die tatsächlichen Kollisionslagen der beiden Polygone bleiben jedoch dieselben.
Ist das Gebiet einmal konstruiert, wird die laufende Kollisionsprüfung besonders anschaulich:
Entscheidend ist, dass der Punkt-in-Polygon-Test immer mit demselben Referenzpunkt arbeitet, für den das Gebiet berechnet wurde.
Ob eine reine Randberührung erlaubt ist, wird in der praktischen Software als eigene Toleranz- und Abstandsregel festgelegt. Für verschiedene Drehwinkel des bewegten Bauteils werden entsprechende Verbotsgebiete separat berechnet.
Wie wird die Minkowski-Summe berechnet?
Für konvexe Polygone gibt es sehr schnelle Algorithmen. Ihr Rechenaufwand wächst nur linear mit der Gesamtzahl der Kanten. Dadurch lassen sich auch umfangreichere Konturen effizient verarbeiten. Bei nichtkonvexen Formen ist die Berechnung aufwendiger. Häufig werden sie zunächst in konvexe Teilpolygone zerlegt, deren Minkowski-Summen anschließend geometrisch vereinigt werden.
Fertige Open-Source-Implementierungen stehen ebenfalls zur Verfügung: In C++ bieten beispielsweise CGAL und die eigenständige Bibliothek Clipper2 entsprechende Funktionen. Für Python stellt pyclipper eine Anbindung an die Clipper-Bibliothek bereit.
Eine Operation, mehrere Anwendungen
Die Minkowski-Summe ist weniger abstrakt, als ihre mathematische Definition zunächst vermuten lässt. Je nach Wahl der zweiten Form beantwortet sie unterschiedliche praktische Fragen:
- Polygon plus Kreisscheibe: Es entsteht ein geometrischer „Halo“ mit konstanter Breite. Typische Anwendungen sind Sicherheitsabstände, CAD-Offsets oder Pufferzonen in Geoinformationssystemen.
- Hindernis plus gespiegelte Roboterform: Es entsteht ein Gebiet, in dem der Referenzpunkt des Roboters nicht liegen darf. Dadurch kann die Wegplanung den ausgedehnten Roboter als Punkt behandeln.
- Bauteil plus gespiegeltes Bauteil: Es entsteht ein Kollisionsgebiet für Nesting und No-Fit Polygons.
Beispiel: Amrum mit zwei Pufferzonen
Der Umriss von Amrum einschließlich des Kniepsands ist deutlich nichtkonvex. Die Wahl einer Kreisscheibe als zweite Form \(B\) ist ein wichtiger Spezialfall der Minkowski-Summe: Es entsteht eine Pufferzone mit konstantem Abstand zur Ausgangskontur. Dabei zeigen die Radien von 500 Metern und zwei Kilometern anschaulich: Mit wachsendem Abstand rundet die Pufferzone schmale Buchten ab oder schließt sie vollständig.
In allen Fällen übersetzt die Minkowski-Summe eine Fragestellung über Abstand, Bewegung oder Kollision in eine neue geometrische Menge. Genau diese Transformation macht sie zu einem wichtigen Werkzeug der Computational Geometry.
Einordnung
Die Minkowski-Summe ist kein vollständiger Nesting-Algorithmus. Sie löst aber eine zentrale geometrische Teilaufgabe: Aus der möglichen Überlappung zweier Bauteile entsteht ein klar beschriebenes Gebiet für deren relative Position. Darauf können unterschiedliche Optimierungsverfahren aufbauen. Ihr Ziel ist es, den Verschnitt zu reduzieren, Restflächen besser zu nutzen und kollisionsfreie Anordnungen zu finden.
Wie sich die Konturen flacher Bauteile aus realen Vorlagen gewinnen lassen, zeigt der GWR-Beitrag Scanner als Messinstrument.
Weiterführende Informationen
- Wikipedia: Minkowski-Summe – Definition und grundlegende Eigenschaften
- Wikipedia: Minkowski addition – Algorithmen und Anwendung in der Bewegungsplanung
Hinweis: Bei der Ausarbeitung dieses Beitrags kamen KI-gestützte Werkzeuge zum Einsatz. Anschließend haben wir mathematische Aussagen, Implementierungen und Messergebnisse fachlich geprüft und mit reproduzierbaren Rechnungen validiert.