Sichtbarkeitspolygon

Sichtbarkeitspolygon vis(p) in Rot eines Polygons

Das Sichtbarkeitspolygon vis(p) eines Punktes p ist ein Objekt des $\R^2$ und ist der Teil in einem einfachen Polygon P der von einem Punkt p aus sichtbar ist.

Es findet beispielsweise Anwendung bei Wegfindungsalgorithmen in der Robotik.

Algorithmus zur Bestimmung

Als erstes wird ein willkürlich gewählter Punkt R₀ auf $\partial P$ (Rand des Polygons P) bestimmt, der mit Sicherheit von p aus sichtbar ist. Dies ist in O(n) möglich. Jetzt wird von R₀ aus P gegen den Uhrzeigersinn durchlaufen. In einem Stapelspeicher S werden dabei die schon besuchten Stücke des $\partial P$ gespeichert, welche möglicherweise von p aus sichtbar sind.

Wenn der Scan wieder bei R₀ angekommen ist, enthält S genau die von p aus sichtbaren Teile von $\partial P$. Jetzt müssen noch künstliche Kanten in S eingefügt werden, damit das Sichtbarkeitspolygon geschlossen ist.

Dieser Algorithmus bestimmt das Sichtbarkeitspolygon mit linearer Laufzeit O(n) und linearem Speicherplatz O(n).

Siehe auch

• Sichtbarkeitsproblem

Weblinks

• Berechnung des Sichtbarkeitspolygons - Interaktives Java Applet

Literatur

• Rolf Klein: Konstruktion des Sichtbarkeitspolygons in Algorithmische Geometrie. Springer Verlag Berlin Heidelberg München 2005, ISBN 3540209565, S. 182-184.