Geometry Lab [English] [Sitemap] [Über geometrylab.de]

Sichtbarkeit in einfachen Polygonen

Im folgenden werden zwei Applets vorgestellt:

Bedienung der Applets

Beide Applets beinhalten einen Editor, mit dem auf einer Zeichenfläche ein einfaches Polygon erstellt werden kann. 

Einfach bedeutet hier:

Im Editor kann das Polygon zunächst aus beliebigen einzelnen Eckpunkten und Kanten/Segmenten zusammengefügt werden.

Sobald ein Linienzug zu einem einfachen Polygon geschlossen wird, verschwinden alle übriggebliebenen Punkte und Segmente, und nur das einfache Polygon bleibt übrig.

In diesem geschlossenen Polygon wird nun der Kern bzw. das Sichtbarkeitspolygon eingezeichnet.

Auch nach dem Schließen des Polygons kann dessen Gestalt weiterverändert werden; der Editor erlaubt neben dem Verschieben von Eckpunkten, Kanten oder des gesamten Polygons auch das Rotieren, Skalieren oder Scheren des Polygons in einem Kontextmenü, das sich bei einem Klick auf das Polygon mit der rechten Maustaste öffnet.
Eckpunkte und Kanten können auch gelöscht und neue hinzugefügt werden.

Nach jeder Veränderung des Polygons wird dieses - sofern geschlossen -jeweils neu gezeichnet, so dass Änderungen des Kerns / des Sichtbarkeitspolygons sofort sichtbar werden.


Berechnung des Kerns

Dieses Applet stellt den Kern eines Polygons dar.

Der Kern eines Polygons ist definiert als die Menge aller Punkte innerhalb des Polygons, von denen aus das gesamte Polygon sichtbar ist.
Etwas formeller:

           ker( P) = {  p element Pvis(p)= P  }.

Der Kern hat - sofern er überhaupt existiert - Polygongestalt. Anschaulich gesprochen ist der Kern der Bereich des Polygons, von dem aus man "in alle Ecken gucken" kann.

(Applet kann nicht gestartet werden)

Das geschlossene Polygon wird in grau dargestellt.
Der Kern des Polygons wird in grün   gezeichnet.

Algorithmus und Laufzeit

Grob gesehen ermittelt der Algorithmus den Kern als Durchschnitt aller Halbebenen H+(k), wobei H+ (k) diejenige Halbebene zur Linken von k ist, die das Innere des Polygons enthält; der Durchschnitt ist in O(n) berechenbar. Dabei werden die Geraden, die die Halbebenen definieren, ermittelt und nach Winkeln geordnet, was ebenfalls in O(n) machbar ist. Man erhält dann:
Theorem   Der Kern eines einfachen Polygons mit n Ecken lässt sich in Zeit O(n) und linearem Speicherplatz berechnen.


Berechnung des Sichtbarkeitspolygons

Dieses Applet zeichnet das Sichtbarkeitspolygon eines Bezugspunktes in einem Polygon.

Das Sichtbarkeitspolygon vis(p) eines Punktes p im Polygon P ist definiert als die Menge aller vom Bezugspunkt p aus sichtbaren Punkte.

Diese Menge hat also Polygongestalt. Anschaulich kann man das Sichtbarkeitspolygon mit dem Lichtschein einer rundum leuchtenden Lichtquelle vergleichen, die sich am Bezugspunkt befindet. Das Sichtbarkeitspolygon stellt dann die Bereiche des polygonalen Raumes dar, die vom Lichtkegel erfasst werden.

(Applet kann nicht gestartet werden)

Das geschlossene Polygon wird in grau dargestellt.
Das Sichtbarkeitspolygon wird in  gelb gezeichnet.
Der Bezugspunkt für das Sichtbarkeitspolygon ist in rot dargestellt.

Algorithmus und Laufzeit

Der Algorithmus verfährt nach folgendem Schema:
Zunächst wird ein Randpunkt R0 ermittelt, der auf jeden Fallvom Bezugspunkt p aus sichtbar ist.
Dann wird der Rand im Gegenuhrzeigersinn durchlaufen und es werden diejenigen Stücke des Randes ermittelt, die von p aus sichtbar sind.
Nach Erreichen des Startpunktes R0 werden diese Stücke mittels zusätzlicher Geraden zum Sichtbarkeitspolygon vis(p ) zusammengesetzt.
Theorem   Das Sichtbarkeitspolygon eines Punktes p  in einem einfachen Polygon P mit n Kanten lässt sich optimal in linearer Zeit und in linearem Speicherplatz bestimmen.

Es ist leicht einzusehen, dass der Algorithmus mit linearer Rechenzeit auskommt: Der Rand des Polygons wird nur einmal durchlaufen, und die Bestimmung des Randpunktes R0 ist ebenfalls in linearer Zeit machbar.



Literatur

Rolf Klein. Algorithmische Geometrie, Kapitel 4: Durchschnitte und Sichtbarkeit. Addison-Wesley, Bonn, 1997.

 

© Universität Bonn, Informatik Abt. I - - Letzte Änderung 09-02-2009 10:23