The library is a starting point for the implementation of geometric
algorithms in the purely functional programming language
Haskell.
It contains many of the data structures and algorithms, that are
treated in introductory textbooks [1,2,3].
The library was implemented as a part of my diploma thesis.
The library contains
- basic datastructures for points, segments, rays, polygons, etc.
- datastructures for orthogonal range queries: kd-trees and rangetrees
- algorithms for twodimensional convex hulls: Jarvis March, Grahams Scan, Merge-Hull, the algorithm of Kirkpatrick and Seidel and Chan's algorithm
- algorithms for the triangulation of simple polygons: the algorithm of Garey, Johnson, Preparata and Tarjan and two output-sensitive algorithms of Toussaint
- the quad-edge data structure (QEDS) for subdivisions
- algorithms for Delaunay-triangulations and Voronoi-diagrams in two dimensions: the divide & conquer-algorithms of Stolfi and Guibas and a randomised incremental algorithms of Boissonnat and Teillaud.
- some applications in two dimensions: all next neighbours, the next post office, the largest empty circle, the closest pair of points
What is not implemented:
- data structures for primitive objects, like tetrahedra, iso-oriented objects, affine transformations, bounding boxes
- Arrangements, Trapezoidal Maps, Intersections
- higher dimensional algorithms for convex hulls, voronoi-diagrams, arrangements, etc.
- data structures like incidence graphs, bsp-trees, segment trees, etc.
- exact arithmetic/robust algorithms
- performance measurements (which algorithm/datastructure ist the best)
- optimization of primitive functions, like point-in-polygon-tests.
The library needs GHC and
Cabal to build.
I will incorporate patches for new compilers, new algorithms, bug-fixes, extensions, etc. if you
email them to me.
