# 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.Seq2 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.

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.

## Changelog

#### 0.6

• Implemented more Algorithms and Data Structures. This includes
• Bentley-Ottmannn line-segment intersection,
• Well-Separated Pair decompositions,
• extremal point/tangents for Convex hulls,
• Minkowski sum for convex polygons,
• one dimensional segment trees,
• one dimensional interval trees, and a
• KD-tree.
• Several bug fixes, including a very stupid bug in Box
• Separate ConvexPolygon type.
• More thorough testing for some of the algorithms.
• Started work on a proper representation for planar subdivsions. This includes a representation of planar graphs that support querying if two vertices are connected by an edge in $$O(1)$$ time.
• Dropped support for GHC 7.8

#### 0.5

• Implemented several algorithms, including Delaunay Triangulation, EMST, and Douglas Peucker.
• Revamped the data types for Intersections

#### 0.4

• Major rewrite from scratch, providing much stronger type-level guarantees. Incompatible with older versions.
• Convex Hull and Smallest enclosing disk algorithms.
• HGeometry now includes some very experimental and preliminary support for reading and writing Ipe7 files.

#### 0.2 & 0.3

• Internal releases.

### 0.1.1

• Fixed a bug in point on n the line segment test
• Generalized the types of inCircle, inDisc, onCircle, onDisc etc. We now need only that the type representing precision model implements the typeclass Num instead of Floating’.

### 0.1

• Initial release.