Sichtbarkeitspolygon
Das Sichtbarkeitspolygon <math>vis(p)</math> eines Punktes <math>p</math> ist ein Objekt des <math>\R^2</math> und ist derjenige Teil des Inneren eines einfachen Polygons <math>P</math>, der vom Punkt <math>p</math> aus sichtbar ist.
Es findet beispielsweise Anwendung bei Wegfindungsalgorithmen in der Robotik.
Algorithmus zur Bestimmung
Zur Bestimmung von <math>vis(p)</math> wird als erstes ein willkürlich gewählter Punkt <math>R_0</math> auf <math>\partial P</math> (Rand des Polygons <math>P</math>) bestimmt, der mit Sicherheit von <math>p</math> aus sichtbar ist. Dies ist in der Laufzeit <math>\mathcal{O}(n)</math> möglich. Jetzt wird von <math>R_0</math> aus <math>P</math> gegen den Uhrzeigersinn durchlaufen. In einem Stapelspeicher <math>S</math> werden dabei die schon besuchten Stücke des <math>\partial P</math> gespeichert, welche möglicherweise von <math>p</math> aus sichtbar sind.
Wenn der Scan wieder bei <math>R_0</math> angekommen ist, enthält S genau die von <math>p</math> aus sichtbaren Teile von <math>\partial P</math>. Jetzt müssen noch künstliche Kanten in <math>S</math> eingefügt werden, damit das Sichtbarkeitspolygon geschlossen ist.
Dieser Algorithmus bestimmt das Sichtbarkeitspolygon mit linearer Laufzeit <math>\mathcal{O}(n)</math> und linearem Speicherplatz <math>\mathcal{O}(n)</math>.
Siehe auch
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