Welfenlab - Leibniz 
                        Universität Hannover Welfenlab Leibniz Universität Hannover

Effiziente Algorithmen zur Innen- / Außenerkennung

Karl-Ingo Friese, Leibniz Universität Hannover, Studienarbeit
01/1997

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

Top | Last Change 26.04.2009 | Editorial Responsibility 
| Imprint | © FG Graphische Datenverarbeitung