Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


24. Elementare geometrische Methoden



Punkte, Linien und Polygone

Die Mehrzahl der Programme, die wir untersuchen wollen, operiert mit einfachen geometrischen Objekten, die in einem zweidimensionalen Raum definiert sind (obwohl wir auch einige Algorithmen für höhere Dimensionen betrachten werden). Das grundlegende Objekt ist der Punkt, den wir als ein Paar ganzer Zahlen ansehen: die »Koordinaten« des Punktes im üblichen kartesischen System. Eine Linie ist ein Paar von Punkten, von denen wir annehmen, daß sie durch einen geraden Linienabschnitt (d. h. eine Strecke) miteinander verbunden sind. Ein Polygon ist eine Liste von Punkten: Wir nehmen an, daß aufeinanderfolgende Punkte durch Linien miteinander verbunden sind und daß der erste Punkt mit dem letzten verbunden ist, so daß eine geschlossene Figur entsteht.

Um mit diesen geometrischen Objekten arbeiten zu können, müssen wir festlegen, wie wir sie darstellen wollen. Gewöhnlich benutzen wir für Polygone eine Darstellung als Feld, obwohl eine verkettete Liste oder eine andere Darstellungsform verwendet werden kann, wenn dies zweckmäßiger ist. Die meisten unserer Programme benutzen die sehr einfachen Darstellungen:

    type point = record x,y: integer end;
         line = record p1,p2: point end;
    var  polygon: array[0..Nmax] of point;

Beachten Sie, daß Punkte auf ganzzahlige Koordinaten beschränkt sind. Eine real-Darstellung könnte gleichfalls benutzt werden. Die Verwendung ganzzahliger Koordinaten führt zu etwas einfacheren und effizienteren Algorithmen und ist keine so starke Einschränkung, wie es scheinen könnte. Wie in Kapitel 2 erwähnt wurde, können bei vielen Computersystemen ganz erhebliche Zeiteinsparungen erzielt werden, wenn nach Möglichkeit mit ganzen Zahlen gearbeitet wird, da Operationen mit ganzen Zahlen gewöhnlich viel effizienter sind als Operationen mit Gleitkommazahlen. Wenn es daher ausreichend ist, nur mit ganzen Zahlen zu operieren, ohne daß dadurch zusätzliche Komplikationen auftreten, werden wir dies tun.

Kompliziertere geometrische Objekte werden wir mit Hilfe dieser elementaren Komponenten darstellen. Zum Beispiel stellen wir Polygone als Felder von Punkten dar. Beachten Sie, daß die Verwendung von Feldern von Linien dazu führen würde, daß jeder Punkt im Polygon zweimal aufgenommen würde (obwohl dies für manche Algorithmen trotzdem die natürliche Darstellungsweise sein könnte). Ebenso ist es bei manchen Anwendungen von Nutzen, mit jedem Punkt oder jeder Linie verknüpfte zusätzliche Informationen mit aufzunehmen; dies läßt sich realisieren, indem den Records ein Feld info angefügt wird.

Abbildung 24.1
Abbildung 24.1 Beispiele von Punktmengen für geometrische Algorithmen.

Wir wollen die in Abbildung 24.1 dargestellten Punktmengen verwenden, um die Arbeitsweise verschiedener geometrischer Algorithmen zu veranschaulichen. Die sechzehn Punkte auf der linken Seite sind jeweils mit einem Buchstaben markiert, um bei der Erläuterung der Beispiele auf sie Bezug nehmen zu können; sie haben die ganzzahligen Koordinaten, die in Abbildung 24.2 angegeben sind. (Die Buchstaben, die wir benutzen, wurden in der Reihenfolge zugewiesen, in der wir die Punkte in der Eingabe erwarten.) In den Programmen gibt es gewöhnlich keinen Grund, Punkte mittels ihres Namens zu referieren; sie werden einfach in einem Feld gespeichert, und die Bezugnahme erfolgt über deren Index. Die Reihenfolge, in der die Punkte im Feld erscheinen, kann in manchen der Programme von Bedeutung sein; tatsächlich ist es das Ziel einiger geometrischer Algorithmen, die Punkte in einer bestimmten Reihenfolge zu »sortieren«. Auf der rechten Seite von Abbildung 24.1 befinden sich 128 zufällig erzeugte Punkte mit ganzzahligen Koordinaten zwischen 0 und 1000.

Abbildung 24.2
Abbildung 24.2 Koordinaten der Punkte in dem kleinen Beispiel einer Punktmenge (Abbildung 24.1 links).

Ein typisches Programm enthält ein Feld p[1..N] von Punkten und liest einfach N Paare ganzer Zahlen ein, wobei es das erste Paar den Koordinaten x und y von p[1] zuweist, das zweite Paar dem Punkt p[2] usw. Wenn p ein Polygon darstellt, ist es manchmal zweckmäßig, »Marken«-Werte p[0] = p[N] und p[N + 1] = p[1] zu verwenden.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]