Geometric Algorithms, Data structures, and Data types.

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. Note that HGeometry is still highly experimental, don't be surprised to find bugs.

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.

HGeometry Packages

HGeometry is split into a few smaller packages. In particular:

• hgeometry : defines the actual geometric data types, data structures, and algorithms,

• hgeometry-combinatorial : defines the non-geometric (i.e. combinatorial) data types, data structures, and algorithms.

• hgeometry-ipe : defines functions for working with ipe files.

• hgeometry-svg : defines functions for working with svg files.

• hgeometry-web : defines functions for building an interactive viewer using miso.

• hgeometry-interactive : defines functions for building an interactive viewer using reflex-sdl2.

In addition there are hgeometry-examples and hgeometry-showcase packages that define some example applications, and a hgometry-test package that contains all testcases. The latter is to work around a bug in cabal.

Available Geometric Algorithms

Apart from some basic geometric primitives such as intersecting line segments, testing if a point lies in a polygon etc, HGeometry implements some more advanced geometric algorithms. In particuar, the following algorithms are currently available:

• two O(n log n) time algorithms for convex hull in ℝ²: the typical Graham scan, and a divide and conquer algorithm,
• an O(n) expected time algorithm for smallest enclosing disk in ℝ²,
• the well-known Douglas Peucker polyline line simplification algorithm,
• an O(n log n) time algorithm for computing the Delaunay triangulation (using divide and conquer),
• an O(n log n) time algorithm for computing the Euclidean Minimum Spanning Tree (EMST), based on computing the Delaunay Triangulation,
• an O(log 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/εᵈn log n) time algorithm for constructing a Well-Separated pair decomposition,
• the classic (optimal) O(n log n) time divide and conquer algorithm to compute the closest pair among a set of n points in ℝ²,
• an O(nm) time algorithm to compute the discrete Fréchet distance of two sequences of points (curves) of length n and m, respectively.
• an O(n) time single-source shortest path algorithm on triangulated polygons.
• an O(n log n) time algorithm for generating random convex polygons.
• an O(n) time algorithm for finding the convex hull of a simple polygon.

Available Geometric Data Structures

HGeometry also contains an implementation of some geometric data structures. In particular,

• 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.
• An O(n log n) size planar point location data structure supporting O(log n) queries.

There is also support for working with planar subdivisions. As a result, [hgeometry-combinatorial] also includes a data structure for working with planar graphs. In particular, it has an EdgeOracle data structure, that can be built in O(n) time that can test if the planar graph contains an edge in constant time.

Avoiding Floating-point issues

All geometry types are parameterized by a numerical type r. It is well known that Floating-point arithmetic and Geometric algorithms don't go well together; i.e. because of floating point errors one may get completely wrong results. Hence, I strongly advise against using Double or Float for these types. In several algorithms it is sufficient if the type r is Fractional. Hence, you can use an exact number type such as Data.RealNumber.Rational or Data.Ratio.Rational.

Working with additional data

In many applications we do not just have geometric data, e.g. Point d rs or Polygon rs, but instead, these types have some additional properties, like a color, size, thickness, elevation, or whatever. Hence, we would like that our library provides functions that also allow us to work with ColoredPolygon rs etc. The typical Haskell approach would be to construct type-classes such as PolygonLike and define functions that work with any type that is PolygonLike. However, geometric algorithms are often hard enough by themselves, and thus we would like all the help that the type-system/compiler can give us. Hence, we choose to work with concrete types.

To still allow for some extensibility our types will use the Ext (:+) type, as defined in the hgeometry-combinatorial package. For example, our LineSegment data type, has an extra type parameter p that allows the vertices of the line segment to carry some extra information of type p (for example a color, a size, or whatever). Polylines, Polylygons, Boxes, etc have similar such parameters.

In all places this extra data is accessable by the (:+) type in Data.Ext, which is essentially just a pair.