Mathematische Computergrafik und geometrische Algorithmen

Konvexität und Polygone

0.2 Die Konvexe Hülle

Die konvexe Hülle einer Menge ist die kleineste konvexe Menge, die enthält.

Zur intuitiven Vorstellung:
beschreibt die Punkte in einer Ebene als inneres Gebiet eines elastischen Bandes, das um diese Punkte gelegt
und dann zusammengezogen wird.
Der Rand (das Band selbst) um die konvexe Hülle herum entspricht dem kleinsten konvexen Polygon,
das sämtliche Punkte in der Ebene umfasst.

0.3 Durchschnitt konvexer Mengen

Sei der Durchschnitt konvexer Mengen    mit wie folgt definiert:
   , mit    konvex und

0.4 Bemerkung

Die meisten geometrischen Objekte umfassen unendliche viele Punkte.
Somit existieren unendlich viele Mengen mit der Eigenschaft .
Deswegen ist die Definition in (0.3) für algorithmische Untersuchungen, die nach endlicher Zeit ein Ergebnis liefern sollen, unbrauchbar.
Das motiviert den folgenden Abschnitt 1.0

1.0 Prüfen auf Konvexität

1.1. Polygone

a) Ein Polygon ist durch einen geschlossenen Streckenzug definiert.
b) In der Regel schneidet sich dabei der Streckenrand nicht selbst.
c) Orientieren wir den Streckenzug gegen den Uhrzeigersinn, so bezeichnen wir den Inhalt links vom Rand als Fläche.

Wir betrachten zuerst Problemstellungen im Vektrorraum , d.h. in der ebenen Geometrie:

Ein Polygon heißt konvex, wenn seine sämtlichen Diagonalen im Inneren verlaufen.

Bei Polygonen können wir uns beim Inklusionstest (siehe 1.2) anstelle beliebiger Punktepaare
und zugehöriger Verbindungsstrecken auf die Diagonalen beschränken:

Anstatt alle Diagonalpunkte, ob sie innere Punkte sind (dafür gibt es keinen effizienten Algorithmus) fordern wir:
i) mindestens ein Punkt jeder Diagonale (z.B. der Mittelpunkt) liegt im Inneren von
ii) alle Diagonalschnittpunkte mit den Poygonkanten ergeben lediglich Polygonpunkte

1.2 Inklusionsabfragen in Polygonen

"Geometrisches Suchenöder "Lokalisierung von Punkten".

Sei eine Partition des Raumes in mehrere Unterräume für eine beliebige Punktmenge gegeben.
Ziel ist die Berechnung, welcher Punkt in welchem Unterraum liegt.

1.2.1 Punkt-im-Polygon-Test

Im zweidim. Raum lautet die Inklusionsfrage: Ëntscheide, ob ein beliebiger Punkt X innerhalb, außerhalb oder auf dem Rand liegt".
Es wird sich zeigen, dass Zeit- und Speicherkomplexität davon abhängt, ob das Polygon konvex und ob Vorarbeit für das Polygon erlaubt ist oder nicht.

1.2.2 Jordansche Theorem

Seien beliebige Polygone (bzw. geschlossene Kurven) gegeben, dann sagt das Jordansche Theorem,
das jedes Polygon die Ebene in zwei disjunkte Regionen «Inneres» und «Äußeres» teilt.
Ist die Anzahl der echten Schnittpunkte eines beliebigen im Punkt startetenden Teststrahls mit den Grenzstrecken ungerade,
so liegt innerhalb von (; andernfalls ist ein äußerer Punkt).

Bermerkung
Probleme ergeben sich, wenn Eckpunte von Polygonkanten direkt auf dem Teststrahl liegen.
Als Teststrahl wählen wir einen Strahl parallel zur x-Achse.
Ein Schnittpunkt des Teststrahls wird gezählt, falls sich der tieferliegende Eckpunkt (kleinerer y-Wert)
der jeweiligen Polygonkante unterhalb des Teststrahls befindet.
Vollständig auf dem Teststrahl liegende Polygonkanten werden nicht gezählt.

Zum Algorithmus

%----------------------------
% Punkt-in-Polygon-Test nach Jordan
%
% INPUT: P = P1, ..., Pn
% X
% % OUTPUT: Die Lage von X, es gibt 3 Möglichkeiten:
% X liegt innerhalb / auf / ausserhalb von P
%
%----------------------------