Modul 8

Aufgaben

Lösungen | Literatur
Die Module

Berechnung und Analyse des ebenen n-Ecks

Algorithmen aus der analytischen Geometrie/
computational geometry [1, 2]
In [1] wird eine interessante Kompaktnotation für den Flächeninhalt A eines ebenen n-Ecks vorgestellt, dessen Eckpunkte Pi; i = 1(1)n durch ihre kartesischen Koordinaten (xi, yi) gegeben sind (Bild 1, vgl. [2,3]).
Bild 1: Ebenes n-Eck
(a) konvex,     (b) konkav

In konventioneller Schreibweise ist

(1)
.(2)

Die Determinantendarstellung Gl. (2) wird nun komprimiert zu

,(3)

die Berechnung erfolgt wie in Gl. (3) eingetragen durch fortlaufende Anwendung der Sarrus-Regel für die Determinante zweiter Ordnung (Sarrus-Verallgemeinerung), so daß man hierdurch sofort Gl. (1) erhält.

Natürlich kann man Gl. (3) für n=3 und n=4 auch formal als auf den Koordinatenteil reduzierte Determinantendarstellungen (vgl. [4])

(4)
(5)

auffassen.

In Modul 2 und Modul 5 wurde bereits die "Zylindernotation" von Gl. (3) für n=4 bzw. n=3 benutzt und diskutiert. Dieser Ansatz soll nachstehend verallgemeinert und produktiv ausgelotet werden.

Zunächst ist klar, daß die mit Spalte 1 identische Abschlußspalte des ebenen rechteckförmigen Schemas

(6)

die zur Generierung der letzten beiden Summanden in Gl. (1) angefügt ist, entfallen kann, wenn man

(a)
Bewegungsrichtung des Lesekopfes bei feststehendem Datenzylinder
(b)
Bild 2: (a) Zylinderdarstellung von Gl. (6),
(b) zugehöriger Lesekopf

Für dieses Konzept soll im folgenden die formale Zylindernotation von Gl. (6) stehen:

.(7)

Damit hat man für Gl. (3)

.(8)

8.1.

Verifizieren Sie Gl. (1) unter Benutzung von Gl. (2) und Gl. (4) für den konvexen und konkaven Fall (Bild 1).

8.2.

Untersuchen Sie den Zusammenhang von Gl. (1) mit dem Pickschen Theorem [5,6,7]:

Besitzt das ebene n-Eck gemäß Bild 3 nur ganzzahlige Eckpunktkoordinaten

(xi, yi) ,(9)

vereinfacht sich die Flächeninhaltsberechnung gegenüber Gl. (1) wesentlich:

.(10)

Hierbei ist

     B - Anzahl der auf den Seiten des n-Ecks liegenden Gitterpunkte () des Koordinatensystems,
     I - Anzahl der im Inneren des n-Ecks liegenden Gitterpunkte () des Koordinatensystems.

Bild 3: Ebenes n-Eck, Picksches Theorem
  B=8, I=21, A=24

8.3.

Wir betrachten ein nichtüberschlagenes ebenes n-Eck gemäß Bild 1, dessen Eckpunkte Pi; i=1(1)n durch ihre kartesischen Koordinaten (xi, yi) gegeben sind.
Formulieren Sie unter Benutzung der Zylindernotation Gl.(8) ein möglichst einfaches Kriterium, mit dessen Hilfe für alle Pk allein aus den Koordinaten (x1, y1), (x2, y2), (x3, y3), ..., (xn, yn) durch Rechnung festgestellt wird:
Das n-Eck P1P2P3...Pn besitzt bei Pk eine   konvexe     Ecke.
konkave

8.4.

Wir betrachten ein überschlagenes ebenes n-Eck (Bild 4), dessen Eckpunkte Pi; i=1(1)n durch ihre kartesischen Koordinaten (xi, yi) gegeben sind.
Bild 4: Überschlagenes ebenes n-Eck

Konstruieren Sie unter Benutzung der Zylindernotation einen möglichst einfachen Filteralgorithmus, mit dessen Hilfe allein aus den Koordinaten (x1, y1), (x2, y2), (x3, y3), ..., (xn, yn) durch Rechnung alle Vierpunktkonstellationen des n-Ecks, die gemäß Bild 5 einen Seitenschnittpunkt (Überschlagspunkt) bilden, extrahiert werden (vgl. Modul 2, Aufgabe 2.5).


Bild 5: Vierpunktkonstellation mit Überschlagspunkt

Liefert der Filteralgorithmus keine solche Vierpunktkonstellation, ist das vorgelegte n-Eck nicht überschlagen, andernfalls überschlagen.

Beispiel:

Das Sechseck nach Bild 4 besitzt 2 Vierpunktkonstellationen mit Überschlagspunkt: Bild 6.


Bild 6: In Bild 4 enthaltene Vierpunktkonstellationen mit Überschlagspunkt

Aufgaben |  Lösungshinweise | Literatur
Die Module