Sichtbarkeitspolygon

Das Sichtbarkeitspolygon $vis(p)$ eines Punktes $p$ ist ein Objekt des $\mathbb {R} ^{2}$ und ist derjenige Teil des Inneren eines einfachen Polygons $P$ , der vom Punkt $p$ aus sichtbar ist.

Es findet beispielsweise Anwendung bei Wegfindungsalgorithmen in der Robotik.

Algorithmus zur Bestimmung

Zur Bestimmung von $vis(p)$ wird als erstes ein willkürlich gewählter Punkt $R_{0}$ auf $\partial P$ (Rand des Polygons $P$ ) bestimmt, der mit Sicherheit von $p$ aus sichtbar ist. Dies ist in der Laufzeit ${\mathcal {O}}(n)$ möglich. Jetzt wird von $R_{0}$ 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_{0}$ 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 ${\mathcal {O}}(n)$ und linearem Speicherplatz ${\mathcal {O}}(n)$ .

Siehe auch

Sichtbarkeitsproblem

Literatur

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

Weblinks

Berechnung des Sichtbarkeitspolygons – Interaktives Java-Applet