https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=SichtbarkeitspolygonSichtbarkeitspolygon - Versionsgeschichte2026-06-08T20:59:39ZVersionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale KopieMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=Sichtbarkeitspolygon&diff=1768623&oldid=previmported>Terzverwandt: Halbgeviertstriche2020-11-16T18:41:37Z<p>Halbgeviertstriche</p>
<p><b>Neue Seite</b></p><div>[[Datei:Sichtbarkeits Polygon.svg|mini|Sichtbarkeitspolygon vis(p) in Rot eines Polygons]]<br />
Das '''Sichtbarkeitspolygon <math>vis(p)</math>''' eines ''[[Punkt (Geometrie)|Punktes]]'' <math>p</math> ist ein Objekt des <math>\R^2</math> und ist derjenige Teil des Inneren eines einfachen ''[[Polygon]]s'' <math>P</math>, der vom Punkt <math>p</math> aus sichtbar ist.<br />
<br />
Es findet beispielsweise Anwendung bei [[Pathfinding|Wegfindungsalgorithmen]] in der [[Robotik]].<br />
<br />
== Algorithmus zur Bestimmung ==<br />
Zur Bestimmung von <math>vis(p)</math> wird als erstes ein willkürlich gewählter [[Punkt (Geometrie)|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 [[Landau-Symbole|Laufzeit]] <math>\mathcal{O}(n)</math> möglich. Jetzt wird von <math>R_0</math> aus <math>P</math> gegen den Uhrzeigersinn durchlaufen.<br />
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.<br />
<br />
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.<br />
<br />
Dieser Algorithmus bestimmt das Sichtbarkeitspolygon mit linearer Laufzeit <math>\mathcal{O}(n)</math> und linearem Speicherplatz <math>\mathcal{O}(n)</math>.<br />
<br />
== Siehe auch ==<br />
* [[Sichtbarkeitsproblem]]<br />
<br />
== Literatur ==<br />
* Rolf Klein: ''Konstruktion des Sichtbarkeitspolygons'' in ''Algorithmische Geometrie.'' Springer Verlag Berlin Heidelberg München 2005, ISBN 3540209565, S. 182–184.<br />
<br />
== Weblinks ==<br />
* [http://www.geometrylab.de/applet-5-de#VisPolygon2Applet Berechnung des Sichtbarkeitspolygons] – Interaktives Java-Applet<br />
<br />
[[Kategorie:Algorithmische Geometrie]]<br />
[[Kategorie:Robotik]]</div>imported>Terzverwandt