Bibliothek für Geometrische Algorithmen in Haskell

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

Die Bibliothek benötigt GHC und Cabal.

• GitHub

Bug-Fixes, neue Algorithmen, etc. werde ich gerne in die Bibliothek aufnehmen, wenn Sie sie mir per Email senden.

1. M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf. Computational Geometry. Springer, 1997.
2. F. Preparata and M. Shamos.Computational Geometry: An Introduction. Springer, 1985.
3. J. O'Rourke.Computational Geometry in C. Cambridge University Press, 1994.