Nächste Seite: Konvexität-und-Einfachheit-Test
Aufwärts: Darstellung von Polygonen
Vorherige Seite: Konvexität-Test
  Inhalt
Dass man einen beliebigen Strahl ausgehend vom zu untersuchenden Punkt
wählen kann, um Innen und Außen zu unterscheiden, sieht
man wie folgt mit einem polaren Scanline-Argument ein:
- Die Ecken werden bezüglich ihres Winkels (Polarkoordinaten!)
aufsteigend sortiert und geben die Haltepunkte während des Scans an.
- Zwischen zwei Haltepunkten schneidet wohl jeder Strahl ausgehend
vom Punkt die gleiche Anzahl von Kanten.
- An einem Haltepunkt bleibt die Anzahl gleich, wird um zwei erhöht
oder um zwei erniedrigt.
Also ist die Summe der geschnittenen Kanten modulo 2 für jeden
Strahl ausgehend von gleich!
Berücksichtigt man weiterhin die Orientierung der Kanten, so zeigt
man leicht, dass die Windungszahl bei einem Umlauf konstant bleibt.
© 2004/2005, A. Formella & D. Fellner, Universität Braunschweig