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 zwei praktische Vorteile:
- 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.
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.
Dazu wird B zunächst so beschrieben, dass sein Referenzpunkt im Ursprung liegt. Anschließend wird die Form am Ursprung punktgespiegelt. Die Menge aller kollidierenden Positionen des Referenzpunkts ist dann
\[ F=A\oplus(-B). \]Im Inneren von \(F\) überlappen sich die Polygone. Auf dem Rand berühren sie sich. Eine Position außerhalb von \(F\) ist kollisionsfrei.
Mathematische Herleitung mit frei wählbarem Referenzpunkt
Wir wählen für \(B\) einen festen Referenzpunkt \(r\), beispielsweise eine Ecke oder den Schwerpunkt, und beschreiben 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. \]\(A\) und das platzierte Polygon kollidieren, wenn Punkte \(a\in A\) und \(\widetilde b\in\widetilde B\) existieren mit
\[ a=\widetilde b+t. \]Nach der gesuchten Position \(t\) umgestellt ergibt sich
\[ t=a-\widetilde b=a+(-\widetilde b). \]Die Punkte \(-\widetilde b\) bilden die am Ursprung punktgespiegelte Form \(-\widetilde B\). Durchlaufen \(a\) und \(\widetilde b\) ihre jeweiligen Polygone, erhalten wir alle kollidierenden Positionen des Referenzpunkts:
\[ F_r=A\oplus(-\widetilde B)=A\oplus\bigl(-(B-r)\bigr). \]Der gewählte Referenzpunkt verschiebt das Verbotsgebiet \(F_r\). Die tatsächlichen Kollisionslagen der beiden Polygone bleiben dabei unverändert.
Kollisionsprüfung
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.
Reproduzierbare Testfälle: Nesting auf einer Ronde
Wie wird aus der schnellen Kollisionsprüfung nun ein vollständiges Nesting? Dafür haben wir mehrere reproduzierbare Testfälle aufgebaut. Im ersten Beispiel sollen auf einer kreisförmigen Ronde mit 500 mm Durchmesser möglichst viele Zeichen untergebracht werden. Der Zeichensatz umfasst 18 Typen – C, E, F, H, K, L, N, S, T, V, X, Y, Z, 1, 2, 3, 5 und 7 – mit einer nominalen Zeichenhöhe von 30 mm. Zum Rand bleiben 5 mm frei, zwischen zwei Zeichen mindestens 3 mm. Spiegelungen sind nicht erlaubt.
Von jedem Zeichentyp stehen 25 Exemplare zur Verfügung. Alle Typen müssen jedoch nicht gleich oft vorkommen: Entscheidend ist die Gesamtzahl der platzierten Zeichen; verbleibende Lücken dürfen mit passenden Zeichen weiter aufgefüllt werden.
Eine bewusst einfache Referenz
Als Vergleich dient eine leicht nachvollziehbare Anfangslösung. Sie setzt die Zeichen ohne Drehung in einem 5-mm-Raster von links nach rechts und von unten nach oben und hält dieselben Rand- und Bauteilabstände ein.
Heuristische Optimierung mit vorberechneten Verbotsgebieten
Aufgabenteilung: Die Minkowski-Summe optimiert die Anordnung nicht selbst. Ihre vorberechneten Verbotsgebiete machen aber die vielen geometrischen Zulässigkeitsprüfungen innerhalb der Heuristik schnell und zuverlässig.
Für die Optimierung werden die No-Fit Polygons der 18 Zeichentypen und aller ganzzahligen Drehwinkel von 0 bis 359 Grad vorberechnet. Das ergibt 18 × 18 × 360 = 116 640 Verbotsgebiete, die in einer Datenbank gespeichert werden. Bei einem Platzierungsversuch muss die Software die Konturen deshalb nicht jedes Mal von Grund auf neu miteinander verrechnen.
Der gezeigte Lauf kombiniert freie Verschiebungen und Drehungen mit mehreren Bewegungen: SlideToContact schiebt ein Zeichen gezielt bis zum Kontakt. Mehrteilige Austauschschritte und ein Repair-Swap versuchen, ungünstige lokale Konstellationen aufzulösen. Threshold Accepting erlaubt zeitweise auch eine Verschlechterung, damit die Suche lokale Optima verlassen kann. Der übergeordnete Shake-and-Compact-Gedanke bleibt dabei erhalten: Austausch und Versatz lockern die Anordnung, kontaktorientierte Bewegungen verdichten sie anschließend wieder.
| Kennzahl | Einfache Referenz | Heuristische Optimierung |
|---|---|---|
| Platzierte Zeichen | 177 | 193 |
| Netto-Materialausnutzung | 36.87 % | 41.05 % |
| Belegte Prozessfläche | 59.86 % | 65.98 % |
| Netto-Zeichenfläche | 72 383 mm² | 80 601 mm² |
| Position und Drehung | 5-mm-Raster, 0° | freie Verschiebung, 1°-Schritte |
| Geometrische Validierung | bestanden | bestanden |
Zu den Kennzahlen: Die Netto-Materialausnutzung setzt nur die tatsächlich gefüllte Zeichenfläche ins Verhältnis zur gesamten Ronde; Innenräume, Rand und Abstände zählen nicht als Produktmaterial. Die belegte Prozessfläche berücksichtigt zusätzlich den Rand und die um den halben Teileabstand erweiterten Konturen und beschreibt damit die geometrisch gebundene Fertigungsfläche.
Einordnung: Die im Beitrag gezeigten heuristischen Ergebnisse stammen aus kurzen, zeitlich begrenzten Testrechnungen. Sie sind geometrisch validiert und zeigen das Verbesserungspotential, beweisen aber kein globales Optimum.
Nesting mit zusätzlichen Nebenbedingungen
In der Fertigung ist nicht jede geometrisch freie Stelle tatsächlich nutzbar. Spannmittel, Materialfehler oder vorhandene Bohrungen können feste Verbotszonen erzeugen; ein freizuhaltender Korridor kann außerdem die Stabilität der verbleibenden Platte sichern. Im Vergleichstest besitzt die 500-mm-Ronde deshalb eine zentrale Sperrzone mit 100 mm Durchmesser und einen 20 mm breiten radialen Reststeg. Die Zeichen halten zu beiden Zonen zusätzlich 3 mm Abstand.
Auch die zulässigen Positionen eines Zeichens \(B\) lassen sich mit Minkowski-Operationen beschreiben. Liegt der Referenzpunkt im Container \(C\), während \(O\) die vereinigten festen Hindernisse bezeichnet, ergibt sich vereinfacht
\[ F_{\mathrm{erlaubt}}=(C\ominus B)\setminus\bigl(O\oplus(-B)\bigr). \]Die Erosion \(C\ominus B\) beschreibt die Positionen, an denen das Zeichen vollständig innerhalb der Ronde bleibt. Davon wird das durch die Minkowski-Summe erzeugte Verbotsgebiet der festen Hindernisse abgezogen.
Die Optimierung bringt 14 zusätzliche Zeichen unter, eine Steigerung um 8.7 %. Die Netto-Materialausnutzung wächst von 33.47 auf 36.70 %, die einschließlich Rand, Abständen und Sperrzonen belegte Prozessfläche von 61.76 auf 66.49 %.
Rechtecke in einer kreisförmigen Ronde
Die vergleichsweise niedrige Netto-Materialausnutzung der Zeichen ist nicht allein eine Eigenschaft des Algorithmus. Buchstaben besitzen Aussparungen, Innenräume und unregelmäßige Außenkonturen. Ein zusätzlicher Test mit vollständig gefüllten Rechtecken trennt diesen Geometrieeffekt besser von der eigentlichen Platzierungsstrategie.
Der Test verwendet dieselbe 500-mm-Ronde mit vier Rechteckgrößen A bis D. Außenrand und Teileabstand betragen jeweils 5 mm.
Referenz und optimierter Rebuild
Die Referenz folgt einer vollständig vorgegebenen Regel: A–B–C–D in zyklischer Folge, ausschließlich 0° und Platzierung von links nach rechts und von unten nach oben im 1-mm-Raster.
Der Sequence-Rebuild baut die Anordnung mit 0°- und 90°-Drehungen neu auf und behält mindestens die Rechteckmischung der Referenz bei. Der Testlauf findet 149 Rechtecke: sechs zusätzliche Teile und 3 700 mm² mehr Nettofläche.
| Kennzahl | Rechteckreferenz | Optimierter Rebuild |
|---|---|---|
| Platzierte Rechtecke | 143 | 149 |
| Verteilung | A 36, B 35, C 35, D 37 | A 37, B 36, C 35, D 41 |
| Netto-Rechteckfläche | 121 100 mm² | 124 800 mm² |
| Netto-Materialausnutzung | 61.68 % | 63.56 % |
| Belegte Prozessfläche | 172 304 mm² beziehungsweise 87.76 % | 177 594 mm² beziehungsweise 90.45 % |
| Position und Drehung | 1-mm-Raster, ausschließlich 0° | 0.25-mm-Raster, 0° und 90° |
| Geometrische Validierung | bestanden | bestanden |
Das Packen ungleich großer Rechtecke in einen Kreis ist auch ein eigenständiges Forschungsthema. Veröffentlichungen vergleichen unter anderem feste und um 90° drehbare Orientierungen sowie die Ziele Stückzahl und Gesamtfläche. Beispiele sind die offene Arbeit Packing unequal rectangles and squares in a fixed size circular container und eine neuere Skyline-Heuristik mit Shake- und lokalen Suchoperatoren.
Weiterführende Informationen
- GWR: Scanner als Messinstrument – Konturen flacher Bauteile aus realen Vorlagen gewinnen
- 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.