HGeometry provides some basic geometry types, and geometric algorithms and data structures for them. The main two focusses are: (1) Strong type safety, and (2) implementations of geometric algorithms and data structures with good asymptotic running time guarantees. Design choices showing these aspects are for example:
Point d rparameterized by a type-level natural number
d, representing d-dimensional points (in all cases our type parameter
rrepresents the (numeric) type for the (real)-numbers):
PolyLine d p rare stored in a
Data.LSeqwhich enforces that a polyline is a proper polyline, and thus has at least two vertices.
Please note that aspect (2), implementing good algorithms, is much work in progress. Only a few algorithms have been implemented, some of which could use some improvements. Currently, HGeometry provides the following algorithms:
It also has some geometric data structures. In particular, HGeometry contans an implementation of
HGeometry also includes a datastructure/data type for planar graphs. In particular, it has a `EdgeOracle’ data structure, that can be built in \(O(n)\) time that can test if the graph contains an edge in constant time.
Current work is on implementing tools for efficient polygon intersection and map overlay.