Tech Talks, Projekte und Forschung

Tech-Talk: Vertex Visibility Algorithm of a simple Polygon

Redaktion IMVS | 17. April 2025

Im Techtalk vom 09.04.2025 stellt Prof. Dr. Christoph Stamm den von ihm implementierten und teilweise auch entwickelten Algorithmus für die Vertex-Visibility in einfachen Polygonen vor. Das Lösen von komplexen geometrischen Problemen begleitet Christoph schon seit Beginn seiner Karriere, wodurch ein beachtliches Know-how entstanden ist. Der vorgestellte Algorithmus ist optimal, da er lediglich die minimale Anzahl an Schritten zur Erstellung des Graphen durchführt. Einsatz findet der Algorithmus beispielsweise in der Robotik für die Berechnung eines Pfades oder für das Berechnen eines minimalen Subsets an Knoten (minimum dominating set), von denen aus ein Raum komplett überblickbar ist.

Der Vertex-Visibility-Graph

Der Algorithmus verarbeitet beliebige, aber nur “simple” Polygone. Damit ein Polygon als “simple” gilt, darf es keine Löcher oder schneidende Kanten aufweisen. Als Resultat erzeugt der Algorithmus einen Graphen, der die Sichtbarkeit aller Knoten definiert. Für einen Knoten ist ein anderer Knoten nur dann sichtbar, wenn eine Kante innerhalb des Polygons und ohne Schneiden von anderen Kanten gelegt werden kann. Teil des Vertex-Visibility-Graphen ist ein Hamilton-Kreis, welcher die Kontur des Polygon repräsentiert. Die folgende Abbildung zeigt Beispiele zweier Polygone und deren Vertex-Visibility-Graphen.

Der Algorithmus in groben Zügen

Ein erster naiver Ansatz für die Lösung des Problems wäre, dass für jedes Knotenpaar geprüft wird, ob die direkte Verbindung dieser beiden Knoten vollständig innerhalb des Polygons (inklusive Rand) verläuft. Die Zeitkomplexität dieses Verfahrens ist O(n³), wobei n die Anzahl Knoten bzw. Kanten des Polygons ist. Vertex-Visibility-Graphen enthalten mindestens 2n – 3 und maximal n(n – 1)/2 Kanten. Für eine optimale Lösung des Problems in linearer Zeit in der Anzahl Kanten des Sichtbarkeitsgraphen braucht es also einen sehr ausgeklügelten Ansatz.

Der vorgestellte Ansatz basiert dabei auf drei wesentlichen Schritten: 

  • die Triangulation des Polygons
  • die Erstellung einer Vertex-Visibility-Map für einen Startknoten
  • und die iterative Überführung der Vertex-Visibility-Map des Knoten i zum Knoten i + 1.

Der Umgang mit kollinearen Knoten

Mindestens drei Punkte, welche auf einer Geraden liegen, werden als kollinear bezeichnet. In Beschreibungen von geometrischen Algorithmen werden kollineare Punkte meistens ausgeschlossen, weil sie viele Zusammenhänge oft sehr stark verkomplizieren und vom eigentlichen Verfahren ablenken. In praktischen Beispielen, nicht zuletzt durch unsere rechtwinklige Bauweise, sind sie aber sehr oft vertreten und erschweren das Lösen der vermeintlich einfachen Aufgabenstellungen sehr stark.

Liegen in einem Polygon mehr als zwei Eckpunkte auf einer Geraden, so enthält das Polygon kollineare Punkte. Zwei Sichtbarkeitsansätze im Umgang mit kollinearen Punkten werden oft angewandt: Entweder werden kollineare Zwischenpunkte als konvex betrachtet und alle kollinearen Punkte sehen sich gegenseitig oder kollineare Zwischenpunkte sind konkav (reflex) und blockieren die Sichtbarkeit. Christoph wählte für seine Implementierung einen neuen, dritten Ansatz: Nur kollineare Zwischenpunkte, welche innerhalb eines simplen Sichtbarkeitspolygons liegen, werden als konvex behandelt. Im nachfolgenden Beispiel ist das Sichtbarkeitspolygon von Eckpunkt 11 gelb dargestellt. Die Eckpunkte 11, 10, 1, 8, 3, 6 und 5 liegen alle auf einer vertikalen Geraden und sind somit kollinear, aber nur der Zwischenpunkt 10 wird als konvex betrachtet, während der Eckpunkt 1 den vertikalen Sichtstrahl von 11 aus blockiert und somit sicherstellt, dass das Sichtbarkeitspolygon nicht degeneriert.

Triangulation

Die Triangulation stellt den ersten Schritt des Verfahrens dar, wird hier aber als gegeben betrachtet. Durch Einfügen von Diagonalen zwischen ausgewählten Polygoneckpunkten wird das Polygon in Dreiecke unterteilt. Ein komplexer theoretischer Algorithmus von Chazelle findet eine Triangulation in linearer Zeit. Die nachfolgende Abbildung zeigt die eingefügten roten Diagonalen, welche das blaue Polygon triangulieren. Damit die Dreiecke einer Triangulation nicht zu spitzwinklig werden, wird oft das Verfahren von Delaunay genutzt, um eine beliebige Triangulation zu verbessern.

Für die Speicherung eines triangulierten Polygons eignet sich eine Doubly Connected Edge List  (DCEL) gut, da sie das Navigieren zwischen Eckpunkten, Kanten und Flächen einfach und effizient ermöglicht.

Vertex Visibility Map

Im zweiten Schritt des Algorithmus wird eine Visibility-Map für einen Startknoten in linearer Zeit in der Anzahl Eckpunkte des Polygons erstellt (siehe nächste Abbildung). Die Map partitioniert das Polygon in Dreiecke (keine Triangulation), so dass alle Punkte eines Dreiecks die gleichen Eckpunkte auf dem kürzesten Pfad zum Startknoten enthält. Aus der Visibility-Map lässt sich anschliessend sehr einfach die Visibility vom Startpunkt zu allen anderen Polygoneckpunkten bestimmen.

Datenstrukturmässig ist eine Visibility-Map eine Erweiterung einer DCEL, da neben dem Polygon und Diagonalen auch Extensions gespeichert werden müssen. Extensions erweitern Diagonalen und/oder Polygonkanten, um die Aufteilung des Polygons in Sichtbarkeitsdreiecke zu ermöglichen. In der nachfolgenden Abbildung werden Extension entweder in hellblau oder orange dargestellt.

Die kürzesten Pfade der Eckpunkte zum Startknoten werden zusätzlich in einer baumförmigen Datenstruktur gespeichert (siehe nächste Abbildung), wobei deren Teilbäume als Trichter (Funnel) bezeichnet werden. Ein Trichter besteht aus einem Scheitelpunkt (apex) und einer unteren und einer oberen Hülle. Die beiden Hüllen sind immer nach aussen hin konvex. In den beiden nachfolgenden Abbildungen sind die oberen Hüllen blau und die unteren Hüllen rot dargestellt.

Mithilfe dieser Trichter ist es nun einfach zu bestimmen, ob ein Knoten x im sichtbaren Bereich eines Scheitelpunkts liegt. Befindet sich der Knoten x im Dreieck, das vom Scheitelpunkt und seinen direkten Nachbarknoten des Trichters aufgespannt wird, so sehen sich x und der Scheitelpunkt. Falls der Scheitelpunkt von x aus nicht sichtbar ist, so wird entweder in der oberen oder unteren Hülle der nächstliegende Tangentialknoten v gesucht, welche auf dem kürzesten Weg von x zum Scheitelpunkt apex liegt (siehe nächste Abbildung).

Die baumförmige Datenstruktur der Trichter wird mithilfe von verketteten Arrays modelliert, wodurch die tangentialen Knoten mittels exponentieller Suche auffindbar sind. Im Original-Paper wird dazu ein viel komplizierterer Finger-Search-Tree verwendet, welcher jedoch nicht notwendig ist, da die in den Arrays gespeicherten Hüllen auf raffinierte Art mehrfach verwendet werden können. 

Die exponentielle Suche beginnt an beiden Enden einer Hülle. Die Schrittweite der Suche wird so lange verdoppelt, bis das gesuchte Element übersprungen ist. Anschliessend wird eine binäre Suche im eingegrenzten Bereich durchgeführt. Im nachfolgenden Beispiel (einseitige exponentielle Suche) wird bei 5 gestartet und der Wert 42 gesucht. Die binäre Suche findet dann im Bereich [32,61] statt. Der Vorteil der exponentiellen Suche gegenüber der binären Suche liegt darin, dass Werte ganz in der Nähe zum Startwert in konstanter Zeit gefunden werden können.

Iterative Anpassung der Visibility-Map

Im dritten Schritt des Algorithmus wird die Visibility-Map für den Startknoten so umgebaut, dass sie zur Visibility-Map ihren direkten Nachbarknotens im Gegenuhrzeigersinn wird. Dieser Schritt wird n – 2 mal wiederholt, bis die Visibility-Maps aller Knoten erzeugt und somit auch der vollständige Visibility-Graph erstellt worden ist.

Damit der Gesamtalgorithmus optimal ist, dürfen in diesem dritten Schritt des Algorithmus in jeder Iteration nur Visibility-Map-Knoten besucht werden, an denen effektiv Änderungen vorgenommen werden. In der nachfolgenden Abbildung wird die schematisch dargestellte Visibility-Map von s zu einer Visibility-Map von t umgebaut. Dabei werden die relevanten Map-Knoten von t nach s im Gegenuhrzeigersinn abgelaufen und Diagonalen/Extentsions gelöscht und hinzugefügt. Die Polygoneckpunkte in den beiden seitlichen, grossen, runden Taschen werden dabei nicht abgelaufen, weil sich die Visibility-Map dort nicht verändert.

Laufzeit

Die Laufzeit für den Algorithmus setzt sich aus den Laufzeiten der drei Teilschritte zusammen:

  • Triangulation: O(n)
  • Erstellen der Visibility-Map für einen Startknoten: O(n)
  • iteratives Anpassen der Visibility-Map (m = Anzahl Kanten des Sichtbarkeitsgraphen): O(m)

Totale Laufzeit: O(n + m)Da m im Bereich zwischen O(n) und O(n²) liegt, ist die Laufzeitkomplexität des Verfahrens O(m) und somit optimal.

Blog Beitrag: Andri Wild (andri.wild@fhnw.ch), MSE Student und Assistent am IMVS

Kontaktperson

Prof. Dr. Christoph Stamm

Dozent für Informatik

Adresse:

Bahnhofstrasse 6 IMVS, 5.2B01

Telefon: +41 56 202 78 32(direkt)

zurück zu allen Beiträgen

Kommentare

Keine Kommentare erfasst zu Tech-Talk: Vertex Visibility Algorithm of a simple Polygon

Neuer Kommentar

×