Das Sichtbarkeitspolygon eines Punktes ist ein Objekt des und ist derjenige Teil des Inneren eines einfachen Polygons , der vom Punkt aus sichtbar ist.

Sichtbarkeitspolygon vis(p) in Rot eines Polygons

Es findet beispielsweise Anwendung bei Wegfindungsalgorithmen in der Robotik.

Algorithmus zur Bestimmung

Bearbeiten

Zur Bestimmung von   wird als erstes ein willkürlich gewählter Punkt   auf   (Rand des Polygons  ) bestimmt, der mit Sicherheit von   aus sichtbar ist. Dies ist in der Laufzeit   möglich. Jetzt wird von   aus   gegen den Uhrzeigersinn durchlaufen. In einem Stapelspeicher   werden dabei die schon besuchten Stücke des   gespeichert, welche möglicherweise von   aus sichtbar sind.

Wenn der Scan wieder bei   angekommen ist, enthält S genau die von   aus sichtbaren Teile von  . Jetzt müssen noch künstliche Kanten in   eingefügt werden, damit das Sichtbarkeitspolygon geschlossen ist.

Dieser Algorithmus bestimmt das Sichtbarkeitspolygon mit linearer Laufzeit   und linearem Speicherplatz  .

Siehe auch

Bearbeiten

Literatur

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