 |
|
|
|
|
Ein Sichtbarkeitsgraph einer polygonalen Szene spiegelt die Sichtbarkeitsbeziehung zwischen den einzelnen Ecken der Szene wieder. Er kann unter anderem für die Bahnplanung eines Punktförmigen Roboters innerhalb dieser Szene benutzt werden. Durch Hinzufügen des Startpunktes s und des Zielpunktes t zum Sichtbarkeitsgraphen, kann mit Hilfe des Dijkstra Algorithmus (Dijkstra, 1959) der kürzeste Weg zwischen s und t bestimmt werden. Dies ist möglich, da der Weg über konvexe Hindernisecken gehen muss.
| Schnellstart des Applets: |
|
Laut [KK01] ist der Sichtbarkeitsgraph folgendermaßen definiert:
Sei L eine Menge sich nicht kreuzender Liniensegmente in der Ebene.
Dann ist der Sichtbarkeitsgraph von L ein Graph VisG(L)=(V,E) mit
V = {alle Punkte der Liniensegmente in L}
E = {(p,q); p,q ∈ V, Segment(p,q) kreuzt kein Liniensegment}
Der Sichtbarkeitsgraph einer Menge von Polygonen entsteht
aus VisG(L) mit L={alle Kanten der Pi} durch
Entfernen aller im Inneren eines Polygons liegenden Sichtbarkeitskanten.
Die Konstruktion des Sichtbarkeitsgraphen ist nicht einfach und
hat mindestens die Komplexität O(n2), da der Sichtbarkeitsgraph
selber mindestens O(n2) hat ( vgl. Abbildung 1 (i) ).
Wie die Abbildung 1 (ii) zeigt, kann die Komplexität auch viel kleiner sein.
Eine naive Berechnung des Sichtbarkeitsgraphen, lässt sich in Zeit O(n3) realisieren. Dazu muss zwischen einer möglichen Sichtbarkeitskante, gegeben durch zwei Punkte der polygonalen Szene, und jedem Segment der Hindernisse auf Schnitt getestet werden. Existiert kein Schnitt, so gehört die Sichtbarkeitskante zum Sichtbarkeitsgraphen. Es existieren aber deutlich effizientere Verfahren zur Berechnung des Sichtbarkeitsgraphen. Im Weiteren wird ein Verfahren zur Konstruktion des Sichtbarkeitsgraphen vorgestellt, welches die Rechenzeit O(n2) und Speicherplatzbedarf O(n) benötigt.
Die Idee der Konstruktion des Sichtbarkeitsgraphen beruht auf einem radialen Sweep. Dabei werden für jeden Punkt radial von Süden nach Norden die Sichtbarkeitskanten berechnet. Hierbei wird für den Punkt das jeweils aktuell sichtbare Segment zwischengespeichert. Durch eine geschickte Weitergabe von Sichtbarkeitsinformationen (siehe Abbildung 2 ) zwischen den einzelnen Punkten lässt sich dieses Verfahren noch weiter verbessern. Hierzu wird der radiale Sweep zwischen den einzelnen Punkten synchronisiert, so dass sich eine Bearbeitungsreihenfolge der potentiellen Sichtbarkeitskanten anhand der Steigung ergibt. Diese wird in nächsten Abschnitt näher beschrieben.
Abbildung 2 zeigt die Abarbeitung des Sichtbarkeitssegmentes(f,a). Da dass Segment(c,d) aktuell von a aus sichtbar ist, wird es nach der Abarbeitung von Segment(f,a) auch von f aus sichtbar. Bei der Initialisierung des radialen Sweeps wird von jedem Punkt aus ein Strahl nach Süden geschossen und ein Zeiger auf das von dem Punkt aus nächste sichtbare Segment gesetzt. Dieser wird auf null gesetzt, falls sich unter dem Punkt kein Segment befindet. Anschließend werden die potentiellen Sichtbarkeitskanten (pi,qj) (pi,qj ∈ V, insgesamt O(n2); i,j ∈ N) anhand der Bearbeitungsreihefolge bearbeitet. Existiert kein Schnittpunkt zwischen dem Segment(pq) und dem von p aus sichtbaren Segment, so wird das Segment in den Sichtbarkeitsgraph eingefügt. Insgesamt ergibt sich eine Laufzeit von O(n2).
Die Wahl der Bearbeitungsreihenfolge hängt von der Steigung slope(p,q) des Segmentes zwischen p und q ab. Dabei müssen zwei Typen von Bedingungen erfüllt werden:
- slope(p,q) < slope(p,r) ⇒ (p,q) vor (p,r) bearbeiten
- slope(a,c) < slope(f,a) < slope(a,d) ⇒ (a,c) vor (f,a) vor (a,d) bearbeiten; mit p,q,r,a,c,d,f ∈ V
Zur Wahl der Bearbeitungsreihenfolge wird eine Eigenschaft der dualen Geraden von Punkten genutzt. Eine duale Gerade zu einem Punkt ist wie folgt definiert:
Punkt p = (px, py) → Gerade p* = {y = pxx - py)
Seien p = (px, py) und q = (qx, qy) o.E. mit px < qx) gegeben. Dann gilt für die Steigung des Segments:
slope(p,q) = (qy - py) /
(qxx - py) = x
es ist nichts anderes, als die X-Koordinate des Schnittpunkts der
zu p und q dualen Geraden p* und q*.
Die Abbildung 3
zeigt ein Arrangement der Punkte und die dazugehörigen dualen
Geraden.
An der Graphik erkennt man, dass die Steigung des Segmentes(e,d)
kleiner ist als von dem Segment(e,c) und es gilt:
slope(e,d) < slope(e,c). Weitere Beobachtung ist,
dass die X-Koordinate des Schnittpunkts zwischen e* und
d* kleiner als die zwischen e* und c* ist.
Also wird das Punktepaar (e,d) vor (e,c) bearbeitet.
Das Problem der Bearbeitungsreihenfolge wird nun auf die Suche der Reihenfolge der Schnittpunkte, die mit der X-Ordnung längs jeder Geraden verträglich ist, reduziert. Dieses Problem lässt sich mit einem topologischen Sweep [EG86] lösen. Der topologische Sweep in der Ebene wird mit einer Kurve durchgeführt, die topologisch einer Geraden entspricht. Die Sweepkurve schneidet jede Gerade höchstens in einem Punkt. Diese Kurve kann als eine Liste dargestellt werden, die für jede Gerade festhält, von welcher anderen sie begrenzt wird. In unserem Beispiel würde der Init-Zustand folgendermaßen aussehen:
Aus der Liste lässt sich ablesen, dass die Geraden b* und c* sowie die Geraden d* und e* benachbart und somit Kandidaten für den nächsten Elementarschnitt sind. Nach der Bearbeitung des Schnittpunktes muss die Liste aktualisiert werden. Dazu werden obere und untere Horizontbäume benutzt.
Die Horizontbäume werden folgendermaßen konstruiert:
Wird ein Schnittpunkt von der Sweepkurve
überschritten, so müssen die Horizontbäume aktualisiert werden.
Die Markierung der Kante, die nur bis zum Schnittpunkt markiert
war, wird bis zur nächsten markierten Kante verlängert. Die Suche
nach dem nächsten Schnittpunkt kann O(n) Schritte erfordern.
Insgesamt ergibt sich die Laufzeit für die Konstruktion des
Sichtbarkeitsgraphen O(n2).
| Starten des Applets: |
|
Durch Klicken mit der linken Maustaste werden
die Eckpunkte der Polygone eingefügt. Wird das Polygon geschlossen,
wird das Innere des Polygons grau markiert. Durch das anfassen des
grauen Bereichs mit der linken Maustaste kann das Polygon
verschoben werden. Genauso können auch die Punkte und
Liniensegmente verschoben werden, um das Polygon zu verändern.
Ein Klick mit der rechten Maustaste öffnet ein Kontextmenü.
Dieses bietet viele Möglichkeiten. So kann z.B. ein Punkt, Segment
oder das Polygon gelöscht, verschoben oder vergrößert werden. Über
das Kontextmenü können auch der Start bzw. Zielpunkt eingefügt
oder entfernt werden.
Wurde die Szene erstellt, so kann der Sichtbarkeitsgraph angezeigt
werden. Dazu muss "Show Visibility Graph" ausgewählt worden
sein. Die Kanten des Sichtbarkeitsgraphen werden als rote Linien
dargestellt. Die Hinderniskanten gehören auch zum
Sichtbarkeitsgraphen, werden aber wegen der Übersichtlichkeit blau
angezeigt. Werden Polygone, Start- oder Zielpunkte verschoben,
wird der Sichtbarkeitsgraph automatisch aktualisiert. Sollen neue
Polygone gezeichnet werden, so empfiehlt es sich wegen der
Darstellungsfehler, die Anzeige für den Sichtbarkeitsgraphen
auszuschalten. Soll ein Bounding Polygon in der Szene benutzt
werden, so muss das Feld "Include Bounding Polygon"
ausgewählt sein, damit er in die Berechnung des
Sichtbarkeitsgraphen einbezogen wird.
| [KK01] |
Rolf Klein, Tom Kamphans: Vorlesungsskript: Bewegungsplanung für Roboter Rheinische Friedrich-Wilhelms-Universität Bonn, Institut für Informatik I, Sommersemester 2001 |
| [EG86] |
H. Edelsbrunner and Leonidas J. Guibas.: Topologically sweeping an arrangement. In Proc. 18th Annu. ACM Sympos. Theory Comput., pages 389-403, 1986 |
Dieses Dokument als PDF PDF
