Einleitung

Für die Translationsbewegungen eines polygonalen Roboters in einer Polygonszene kann die Minkowski-Summe benutzt werden, um den Raum der freien Konfigurationen des Roboters zu bestimmen. Mit Hilfe der Minkowski-Summe zwischen dem Roboter und den Hindernissen werden diese expandiert. Der Roboter kann dadurch auf einen einzigen Punkt beschränkt werden. Somit wird das Bahnplanungsproblem für einen polygonalen Roboter auf das eines Punktes reduziert. Weitere Informationen über die Minkowski-Summme sind in [KK01] und [BKO00] zu finden.

In den folgenden Abschnitten wird zunächst die Definition der Minkowski-Summe erläutert, danach werden die Schritte vorgestellt, die das Applet bei der Berechnung der Minkowski-Summe durchführt. Nach der Erklärung der Bedienung des Applets werden abschließend noch einige Quellenangaben für weiterführende Informationen aufgelistet.

Schnellstart des Applets:

Definition der Minkowski-Summe

Die Definition der Minkowski-Summe laut [KK01]:

Eigenschaften der Minkowski-Summe:


Schritte zur Berechnung der Minkowski-Summe

Sind die Polygone P1 und P2 konvex, kann die Minkowski-Summe direkt berechnet werden, ohne dass noch Zwischenschritte vorher durchgeführt werden müssen. Anschaulich bedeutet das, dass das Polygon P1 auf dem Rand von P2 entlang geschoben wird. Der Bereich, der dabei überdeckt wird, ist die Minkowski-Summe (vgl. Abbildung).

Ist eines der beiden Polygone nicht konvex, so muss es zuerst trianguliert werden. Anschließend wird die Minkowski-Summe von jedem Dreieck mit dem anderen Polygon berechnet. Auch hierfür gilt die Veranschaulichung der Abbildung, da es sich jetzt um die Berechnung der Minkowski-Summe von konvexen Polygonen handelt. Anschliessend müssen die Ergebnis-Polygone noch vereinigt werden.

Sind beide Polygone nicht konvex, so müssen beide zuerst trianguliert werden. Dann müssen die Minkowski-Summen von jedem Dreieck von P1 mit jedem Dreieck von P2 berechnet werden. Anschließend werden diese Teil-Minkowski-Summen vereinigt.

Insgesamt ergibt sich so für die Komplexität der Lösung nach [KK01]:

Für die algorithmische Komplexität des Problems gilt mit 'Divide and Conquer' laut [KK01]:

Zur Triangulierung der Polygone wurde in dem hier vorgestellten Applet die Triangulierung nach Seidel (siehe [SEI91]) verwendet. Diese wird in einem Applet veranschaulicht, das auf einer weiteren Webseite zu finden ist.


Ein Applet zur Berechnung der Minkowski-Summe

Starten des Applets:

Durch Klicken mit der linken Maustaste können die Eckpunkte der Polygone eingegeben werden. Die Minkowski-Summe wird berechnet, sobald der Polygoneditor zwei einfache, geschlossene Polygone enthält. Sie wird in beige dargestellt. Es ist auch möglich die Polygone im Nachhinein noch zu verändern, indem man mit der mit der Maus an den Eckpunkten oder an den Kanten zieht, während man die linke Maustaste gedrückt hält. Über das Kontextmenü, das mit der rechten Maustaste auf den Polygonen aufgerufen wird, kann man das Polygon löschen, skalieren und noch vieles mehr. Außerdem kann man über das Kontextmenü einen Referenzpunkt anzeigen lassen. Die Minkowski-Summe wird dann relativ zu diesem verschoben. Der Standard-Referenzpunkt ist der linkeste Punkt des linken Polygons. Um die Entstehung der Minkowski-Summe besser zu verstehen, kann man sich eine Visualisierung des Vorgangs anzeigen lassen. Dies lässt sich ebenfalls über das Kontextmenü einstellen.


Quellen

[KK01] Rolf Klein, Thomas Kamphans:
Vorlesungsskript: Bewegungsplanung für Roboter
Rheinische Friedrich-Wilhelms-Universität Bonn, Institut für Informatik I,
Sommersemester 2001
[BKO00] M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf:
Compututional Geometry, Algorithms and Applications
Second Edition, Springer Verlag, 2000
[SEI91] Raimund Seidel:
A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
http://www-tcs.cs.uni-sb.de/papers/trap.ps.gz
Comput. Geom. Theory and Appl. 1 (1991) 51-64.

...nach oben