|
|
|
| Studentische Arbeiten | Oliver Berthold |
|
|
|
Gegeben sei ein beliebiges (ggf. überschlagenenes) n-Eck durch Angabe der Koordinaten x und y der n Eckpunkte im zweidimensionalen kartesischen Koordinatensystem.
Es ist ein Algorithmus zu entwickeln, der auf den im Modul 8 vorgestellten Algorithmen basiert und folgendes mit möglichst geringem Rechenaufwand leistet:
Für jede der n Ecken soll ermittelt werden, ob diese von außen konvex oder konkav sind. Explizit wird gefordert, daß diese Klassifikation auch dann richtig erfolgt, wenn sich einzelne Seiten des n-Ecks überschneiden. Dabei ist eine allgemeingültige Regel aufzustellen, die bei einer mehrfach überschnittenen Figur Innen und Außen bezüglich jeder Seite eindeutig definiert.
Gegebenenfalls vorhandene Überschneidungen von Seiten sollen ermittelt werden; es werden Aussagen darüber erwartet, welche Seiten wie oft geschnitten werden.
Ermittlung der kartesischen Koordinaten der Schnittpunkte.
Algorithmus zur Berechnung des Schnittpunktes zweier Strecken
Algorithmus zur Ermittlung von Eigenschaften der Ecken, 1. Version
Algorithmus zur Ermittlung von Eigenschaften der Ecken, 2. Version