Computational Geometry in Haskell

HGeometry is a library for computing with geometric objects in Haskell. It defines basic geometric types and primitives, and implements many algorithms, including:

Geometry is inherently visual and the rest of this website is devoted to illustrations and animations that highlight how the various algorithms work.

\( O(n) \) Inflate

Polygons can be inflated like a balloon. A partially inflated polygon is smaller than the original polygon and have the property that each point on the wavefront are equidistant to the point of origin. Increasing the distance to the wavefront gives the impression of the polygon spreading like water in a mold.

\( O(k) \) Visibility

Finding the visible parts of a polygon from a given point is a cornerstone in computational geometry. There exists many algorithms but one is of special interest. This algorithm is output-sensitive, meaning that the runtime is dependent not on the size of the input polygon but on the size of the visible area.

The animation shows how a polygon is first triangulated, then the triangles are processed and marked in grey while the visibility polygon is outlined in green. The number of processed triangles is limited to those that intersect the final visibility polygon.

\( O(n \log n) \) Convex Hull

A convex hull of a set of points is the smallest convex polygon that contains it. You can think of it as a rubber band that stretches around a collection of points.

So, how is this useful? Well, there are many fast algorithms that only work on convex polygons. For example, there's a fast algorithm for finding the two corners that are furthest away from each other. By first finding the convex hull, we can then use the fast algorithm to find the two extreme points in the set.

Wikipedia article.

\( O(n \log n) \) Closest Pair

The closest pair problem for points in the Euclidean plane was among the first geometric problems that were treated at the origins of the systematic study of the computational complexity of geometric algorithms.

Wikipedia article.

\( O(n \log n) \) Random, Monotone Polygons

Monotone polygons have the property that all rays in a certain direction only intersect the polygon in at most two places. These kinds of polygons play a key role in many algorithms such as triangulation and being able to quickly generate random samples helps immensely with testing.

Wikipedia article.

\( O((n+k) \log n) \) Line segment intersection

Using a brute-force search, finding intersections of \(n\) lines would take \(O(n^2)\) time. Since we often want to find intersections, the Bentley-Ottmann algorithm which significantly improved the efficiency.

When is this used? Well, to give good error messages, HGeometry will check polygons for self-intersections immediately when they're created. This leads to mistakes being spotted sooner rather than later.

Wikipedia article

Fast Z-Hashing Triangulation

Finding points inside an arbitrary bounding box is made significantly faster with Z-hashing. By first sorting a polygon's vertices by their z-hash, the polygon can be triangulated in near linear time. While other algorithms offer stronger guarantees about worst-case behavior, z-order hashing has the lowest constant-factor overhead and is, in practice, the fastest known triangulation algorithm.

Wikipedia article

\( O(n) \) Single-Source Shortest Path

Finding the shortest path from a specific corner to all other corners is a key step in many other algorithms. It's used for computing visibility polygons, inflated polygons, and minimum-link distances.

The animation shows the shortest internal path from a green point on the side of a polygon to all other corner points.

DOI: 10.1007/BF01840360

SVG interoperability

SVG images can be conveniently imported as polygons in hgeometry. This makes testing and experimentation much easier.

The animation loads the letter 'S' from an SVG image and shows what a triangulation would look like at a low and high polygon count.

Efficient and uniform sampling

Picking a random point in a polygon has many uses, especially in testing. Sampling can be difficult to get right since it has to be both uniform (ie. not favoring any points over others) and efficient.

In the animation, 100 red points are randomly selected from the area of each letter.