# HGeometry

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:

• 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 (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:

• two $$O(n \log n)$$ time algorithms for convex hull in $$\mathbb{R}^2$$: the typical Graham scan, and a divide and conqueror algorithm,
• an $$O(n)$$ expected time algorithm for smallest enclosing disk in $$\mathbb{R}^2$$,
• the well-known Douglas Peucker polyline line simplification algorithm,
• an $$O(n \log n)$$ time algorithm for computing the Delaunay triangulation (using divide and conqueror).
• an $$O(n \log n)$$ time algorithm for computing the Euclidean Minimum Spanning Tree (EMST), based on computing the Delaunay Triangulation.
• an $$O(\log^2 n)$$ time algorithm to find extremal points and tangents on/to a convex polygon.
• An optimal $$O(n+m)$$ time algorithm to compute the Minkowski sum of two convex polygons.
• An $$O(1/\varepsilon^dn\log n)$$ time algorithm for constructing a Well-Separated pair decomposition.
• The classic (optimal) (O(nn)) time divide and conquer algorithm to compute the closest pair among a set of (n) points in (^2).

It also has some geometric data structures. In particular, HGeometry contans an implementation of

• A one dimensional Segment Tree. The base tree is static.
• A one dimensional Interval Tree. The base tree is static.
• A KD-Tree. The base tree is static.

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.

## Getting HGeometry

The easiest way to get HGeometry is from Hackage. The source code for HGeometry can be found on github.

See github.