Der Sichtbarkeitsgraph einer Polygonszene

Einleitung

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:

Definition des Sichtbarkeitsgraphen

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) ).


Abbildung 1: Der sichtbarkeitsgraph kann (i) O(n2) viele Kanten enthalten, aber auch (ii) nur O(n) viele.

Wie die Abbildung 1 (ii) zeigt, kann die Komplexität auch viel kleiner sein.

Konstruktion des Sichtbarkeitsgraphen

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: Sichtbarkeitsinformationen können von a an f weitergereicht werden

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).



Wahl der Bearbeitungsreihenfolge

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:

  1. slope(p,q) < slope(p,r) ⇒ (p,q) vor (p,r) bearbeiten
  2. 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.


Abbildung 3: Arrangement von Punkten (i) und die dazugehörigen dualen Geraden (ii).

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:

{(a*,e*), (b*,c*), (c*,b*), (d*,e*), (e*,d*)}

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.


Horizontbäume

Die Horizontbäume werden folgendermaßen konstruiert:

Aus den beiden Horizontbäumen lässt sich für eine Gerade e schnell bestimmen, welche Gerade diese begrenzt. Dazu müssen ihre Verlängerungen in den Horizontbäumen betrachtet werden. Die kürzere von den beiden gibt an, von welcher Gerade sie begrenzt wird. Abbildung 4 zeigt, wie die Horizontbäume aufgebaut und aktualisiert werden:


Abbildung 4: Aufbau des oberen und unteren Horizontbaumes, sowie die Entwicklung der Sweepkurve

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).



Ein Applet zur Berechnung des Sichtbarkeitsgraphen

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.


Quellen

[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

...nach oben