Bibliothek für Geometrische Algorithmen in Haskell
October 21, 1998
In meiner Diplomarbeit habe ich 1998 die Potentiale der funktionalen Programmierung bei der Implementierung von geometrischen Algorithmen untersucht. Den Source-Code habe ich veröffentlicht.
Die Bibliothek wurde in der rein funktionalen Programmiersprache Haskell geschrieben. Sie enthält viele der Datenstrukturen und Algorithmen, die in einführenden Lehrbüchern behandelt werden [1,2,3] und wurde im Rahmen meiner Diplomarbeit implementiert.
Die Bibliothek enthält
- Grundlegende Datenstrukturen für Punkte, Strecken, Strahlen, Polygone, etc.
- Datenstrukturen für orthogonale Bereichsabfragen: KD-Bäume und Bereichsbäume (Rangetrees)
- Zweidimensionale konvexe Hüllen: Jarvis March, Grahams Scan, Merge-Hull, der Algorithmus von Kirkpatrick und Seidel und Chan-Algorithmus
- Triangulation von einfachen Polygonen: der Algorithmus von Garey, Johnson, Preparata und Tarjan und zwei ausgabesensitive Algorithmen von Toussaint
- Die Quad-edge Datenstruktur (QEDS)
- Delaunay-Triangulationen und Voronoi-Diagramme in 2D: der Divide & Conquer-Algorithmus von Stolfi und Guibas und ein randomisierter inkrementeller Algorithmus von Boissonnat und Teillaud
- Anwendungen in zwei Dimensionen: alle nächsten Nachbarn, das nächste Postamt, der größten leeren Kreis, das dichteste Punktepaar
Was fehlt?
- Datenstrukturen für primitive Objekte wie Tetraeder, iso-orientierte Objekte, affine Transformationen, Bounding-es
- Arrangements, Trapezoidal Maps, Intersections
- Höherdimensionale Algorithmen für konvexe Hüllen, Voronoi-Diagramme, Arrangements, etc.
- Datenstrukturen wie Inzidenz-Graphen, BSP-Bäume, Segment-Bäume, etc.
- Performance-Messungen (Welcher Algorithmus / Datenstruktur ist der/die beste?)
- Performance-Optimierung von primitiven Funktionen, wie z. B. Point-in-Polygon-Tests
Verfügbarkeit / Download
Die Bibliothek benötigt GHC und Cabal.
Bug-Fixes, neue Algorithmen, etc. werde ich gerne in die Bibliothek aufnehmen, wenn Sie sie mir per Email senden.
Literatur
- M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf. Computational Geometry. Springer, 1997.
- F. Preparata and M. Shamos.Computational Geometry: An Introduction. Springer, 1985.
- J. O'Rourke.Computational Geometry in C. Cambridge University Press, 1994.
Anmerkung: Dieser Artikel wurde im November 2016 an das neue Blog-Format angepasst.