HGeometry

HGeometry is a library for computing with geometric objects in Haskell. It defines basic geometric types and primitives, and it implements some geometric data structures and algorithms. The main two focusses are:

  1. Strong type safety, and
  2. implementations of geometric algorithms and data structures that have good asymptotic running time guarantees.

Design choices showing these aspects are for example:

  • we provide a data type Point d r parameterized by a type-level natural number d, representing \(d\)-dimensional points (in all cases our type parameter r represents the (numeric) type for the (real)-numbers):
newtype Point (d :: Nat) (r :: *) = Point { toVec :: Vector d r }
  • the vertices of a PolyLine d p r are stored in a Data.LSeq which enforces that a polyline is a proper polyline, and thus has at least two vertices.

Please note that aspect two, implementing good algorithms, is much work in progress. Only a few algorithms have been implemented, some of which could use some improvements.