Sichtbarkeitspolygon

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

Sichtbarkeitspolygon vis(p) in Rot eines Polygons

Es findet beispielsweise Anwendung b​ei Wegfindungsalgorithmen i​n der Robotik.

Algorithmus zur Bestimmung

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

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

Dieser Algorithmus bestimmt das Sichtbarkeitspolygon mit linearer Laufzeit ${\displaystyle {\mathcal {O}}(n)}$ und linearem Speicherplatz ${\displaystyle {\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