Sichtbarkeitspolygon

Sichtbarkeitspolygon vis(p) in Rot eines Polygons

Das Sichtbarkeitspolygon $vis(p)$ eines Punktes $p$ ist ein Objekt des ${ℝ}^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 $𝒪(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 $𝒪(n)$ und linearem Speicherplatz $𝒪(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