Effiziente Algorithmen zur Innen- / Außenerkennung

Karl-Ingo Friese, Leibniz Universität Hannover, Studienarbeit
11/1996

Obwohl viele der Begriffe und Sätze die im folgenden vorgestellt werden, für allgemeine stetige Kurven in der Ebene gelten, ist es eine Unterklasse dieser allgemeinen Kurven, die den Schwerpunkt dieser Arbeit bildet - die Polygonzüge.

Dies hat mehrere Gründe. Zum einen sind Polygonzüge wohl die einfachste Klasse von zweidimensionalen Kurven. Im Gegensatz zu allgemeinen Kurven (man denke z.B. an NURBS- oder Bezier-Kurven, die jedoch bei der Darstellung mit dem Computer meistens polygonal approximiert werden) treten zum Beispiel erheblich weniger numerische Probleme auf, so daß die Umsetzung der Algorithmen in einer Programmiersprache nicht davon behindert wird. Außerdem spielen Polygonzüge in der Computergraphik eine große Rolle, so daß sie nicht zuletzt auch praktischen Nutzen besitzen.

Interessierten, die sich nicht nur auf Polygonzüge beschränken möchten, sondern einen allgemeineren Überblick über Ebene Kurven unter Gesichtspunkten der Computergraphik erhalten möchten, sei die Arbeit von Thomas Rausch empfohlen:<cite> Rausch, Thomas, 1995: Computergraphik und geometrische Probleme in der Ebene, Universität Hannover. </cite>

Neben den unterschiedlichen Innen-/Außenbegriffen, ihrer algorithmischen Implementierung (= Test) und Laufzeit- / Optimierungsuntersuchungen, wird insbesondere ein Algorithmus zur Überprufung des Geometrischen Innen-/Außenproblems angegeben, der bis dahin nicht allgemein untersucht worden ist.

Kontakt: Franz-Erich Wolter