Benutzer:Particle~dewiki/Sichtbarkeitspolygon

Sichtbarkeitspolygon vis(p) in Rot eines Polygons

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

Es findet z.B. Anwendung bei Wegfindungsalgorithmen in der Robotik.

Algorithmus zur Bestimmung

Bestimmung eines willkürlichen Punktes $R_{0}$ auf $\partial P$ (Rand des Polygons $P$) der mit Sicherheit von $p$ aus sichtbar ist. Dies ist in $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 zusammenhängend ist.

Literatur

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

[[Kategorie:Algorithmische Geometrie]] [[Kategorie:Robotik]]