Bibliothek für Geometrische Algorithmen in Haskell

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

Anmerkung: Dieser Artikel wurde im November 2016 an das neue Blog-Format angepasst.

 "Geometrische Algorithmen in Haskell" "Missbrauchserkennung mit Künstlicher Intelligenz"