[English] [Sitemap] [Über geometrylab.de]
	Startseite > Algorithmische Geometrie > Grundlagen > Sichtbarkeit in einfachen Polygonen

Sichtbarkeit in einfachen Polygonen

• Kern eines Polygons
• Sichtbarkeitspolygon eines Polygons
  

Bedienung der Applets

Einfach bedeutet hier:

• Das Polygon hat mindestens 3 Eckpunkte.
• Die Kanten schneiden (berühren) sich nur in den Eckpunkten.
  
• Das Polygon ist geschlossen. (Das Polygon hat n Eckpunkteund Kanten.)

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

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

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.

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

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

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.

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

Der Algorithmus verfährt nach folgendem Schema:
Zunächst wird ein Randpunkt R₀ 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 R₀ 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 R₀ ist ebenfalls in linearer Zeit machbar.

Literatur

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