Methoden der algorithmischen Geometrie

Methoden der algorithmischen Geometrie

Mike H¨ftle u 28. Juli 2006

Inhaltsverzeichnis

1 Einleitung 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Sweep-Verfahren 2.1 Methodenbeschreibung . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Nebenpfad: Sweep-Verfahren . . . . . . . . . . . . . . . . 2.2 Anwendung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Voronoi-Diagramm 3.1 Methodenbeschreibung 3.2 Methodenbeschreibung 3.3 Beispiel . . . . . . . . 3.4 Anwendung . . . . . . 2 2 3 3 3 5 6 6 7 8 9 10 10 11 11 12 13 14 15 15 15 16 16

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

4 Delaunay-Triangulation 4.1 Methodenbeschreibung . . . . . . . . . . . . . . . 4.2 Methodenbeschreibung . . . . . . . . . . . . . . . 4.2.1 Nebenpfad: Radial Sweep . . . . . . . . . 4.2.2 Nebenpfad: Recursive Split . . . . . . . . 4.2.3 Nebenpfad: Incremental Delete and Build 4.3 Anwendung . . . . . . . . . . . . . . . . . . . . . 5 Literatur und Methoden 5.1 Literatur zum Sweep-Verfahren . . . . 5.1 Literatur zu Voronoi-Diagrammen . . 5.1 Literatur zur Delaunay-Triangulation . 5.1 Methoden . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

1

1

1.1

Algorithmische Geometrie

Einleitung

Als Algorithmische Geometrie wird ein Teilgebiet der Informatik bezeichnet, das sich mit der Speicherung und Verarbeitung geometrischer Daten besch¨ftigt. a Im Gegensatz zur Bildverarbeitung, deren Grundelemente Bildpunkte (Pixel) sind, arbeitet die algorithmische Geometrie mit geometrischen Strukturelementen wie Punkten, Linien, Kreisen, Polygonen und K¨rpern. o

Anwendungsgebiete der algorithmischen Geometrie sind z.B.: Anwendungsgebiete der Algorithmischen Geometrie • Die effiziente Speicherung geometrischer Informationen mit Hilfe von Datenbanken • Die Suche in geometrischen R¨umen sowie die Segmentierung von a R¨umen (Clustern) und das Sortieren von Objekten im Raum a • Die L¨sung von Problemstellungen der analytischen Geometrie (z. B. o Schnitte von geometrischen Objekten) • Die Berechnung zusammenh¨ngender Kurven und Fl¨chen aus Punkta a wolken • Die Lineare Optimierung Die Methoden der algorithmischen Geometrie werden insbesondere im Computer Aided Design (CAD), in der Computergrafik und bei Geoinformationssystemen eingesetzt. Auch bei der Planung von Bewegungsabl¨ufen f¨r robotische a u Systeme werden Verfahren der Algorithmischen Geometrie angewendet.

---

2

2.1

Sweep-Verfahren

Methodenbeschreibung

Das Sweep-Verfahren ist eine der vielseitigsten Techniken in der algorithmischen Geometrie, mit der viele Probleme gel¨st werden k¨nnen. Gelegentlich o o wird es auch als Scan-Verfahren bezeichnet. Das Verfahren wandelt ein statisches, d-dimensional r¨umliches in ein dynamisches, (d-1)-dimensional zeitliches a Problem um.

Methodenbeschreibungder einfachsten Anwendungen des Sweep-Verfahrens ist die Bestimmung Eine des Maximums einer Menge von Objekten q1 , …, qn . Um das maximale Objekt zu bestimmen, wird jedes Objekt genau einmal betrachtet und gepr¨ft, u ob es gr¨ßer ist als das gr¨ßte der bis dahin uberpr¨ften Objekte ist. o o u ¨ Der Algorithmus hat somit eine Laufzeit von O(n). Das Sweep-Verfahren macht in diesem Fall aus einem r¨umlich 1-dimensionalen Problem eine Folge von 0a dimensionalen Problemen, n¨mlich der Bestimmung des Maximums zweier aha len. Besonders erfolgreich wird das Sweep-Verfahren bei 2-dimensionalen Problemen eingesetzt. Hierzu werden die Objekte in der Reihenfolge betrachtet, wie sie von einer wandernden Geraden (sweep line) ber¨hrt werden, welche die u Ebene (z.B. senkrecht) durchstreift. Das Sweep-Verfahren kann beispielsweise dazu benutzt werden, das dichteste Paar von Objekten in einer Ebene zu finden, etwa dasjenige mit minimalem euklidischen Abstand MinDist. Das Vorgehen des Sweep-Verfahrens zur Bestima mung eines dichtesten Paares von Objekten wird hier erl¨utert. Soll das dichteste Punktepaar im Raum bestimmt werden, so wird dies mit einer Sweep-Ebene (sweep plane) durchgef¨hrt. Die SSS enth¨lt in diesem u a Fall alle Objekte im Abstand MinDist rechts von der Sweep-Ebene. 2.1.1 Nebenpfad: Sweep-Verfahren

Das Vorgehen des Sweep-Verfahrens zur Bestimmung eines dichtesten Paares von Objekten ist in der Abbildung dargestellt.

Abbildung: Sweep-Verfahren zur Suche des dichtesten Punktepaares (nach Klein 1997, S. 58)

---