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 R0 auf ∂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 R0 aus P gegen den Uhrzeigersinn durchlaufen. In einem Stapelspeicher S werden dabei die schon besuchten Stücke des ∂P gespeichert, welche möglicherweise von p aus sichtbar sind.

Wenn der Scan wieder bei R0 angekommen ist, enthält S genau die von p aus sichtbaren Teile von ∂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