HGeometry

HGeometry is a library for computing with geometric objects such as points, line segments, and polygons, in Haskell. It defines basic geometric types and primitive operations on these types (for example functions to test or compute the intersection of two line segments), and it implements some geometric data structures and algorithms. The main two focusses are:

1. To provide idiomatic implementations of geometric algorithms and data structures that have good asymptotic running time guarantees, and
2. Strong type safety.

Please note that first aspect --implementing good algorithms and data structures-- is much of a work in progress. Only a few algorithms have been implemented, and most likely they can use some improvements.

HGeometry Packages

HGeometry currently consists of three packages:

• hgeometry-combinatorial,

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

• hgeometry,

  which defines the actual geometric algorithms and data structures, and

• hgeometry-examples

  which defines some examples that showcase using hgeometry.

The hgeometry package itself actually consists of several libraries:

• hgeometry

  The main library that defines the actual algorithms and data structures.

• hgeometry:vector

  Defines length annotated Vector types and typeclasses. The hgeometry-point library depends on this.

• hgeometry:point

  Defines types and typeclasses representing points in space, and basic operations on points.

• hgeometry:kernel

  Defines other geometric "constant complexity" geometric types and primitives. For example lines, halfspaces, line segments, balls, circles, rectangles etc.

• hgeometry:polygon

  Defines types for representing Polygons, in particular Simple polygons, Convex polygons, and polygons with holes, as well as a typeclasses that capture some basic operations involving polygons.

• hgeometry:polyLine

  Defines a type for representing PolyLines, as well as a typeclass that captures some basic operations of this type.

• hgeometry:spline

  Defines bezier splines.

• hgeometry:ipe

  Defines functions for reading, writing, and manipulating ipe files and the geometric objects therein.

• hgeometry:svg

  Defines functions for writing the geometry types to svg files.

Examples

The hgeometry-examples provides some examples of using the library.

Available Geometric Algorithms and Data Structures

This is a brief overview of some of the main available algorithms in HGeometry. Refer to the haddocks for more details. HGeometry contains algorithms for

• Solving LP-type Problems in expected linear time. In particular, this we can

  • solve 2D Linear Programming problems, and
  • compute the smallest enclosing disk of a set of points in $\mathbb{R}^2$.

  It should be fairly easy to extend these algorithms to higher dimensions, and/or implement other LP-type problems.

• Computing the lower envelope of a set of $n$ planes in $\mathbb{R}^3$. This then also allows us to compute

  • the convex hull of a set of $n$ points in $\mathbb{R}^3$,
  • the Voronoi diagram of a set of $n$ points in $\mathbb{R}^2$, as well as compute the
  • Delaunay triangulation of $n$ points in $\mathbb{R}^2$.

  Currently we provide only a naive $O(n^4)$ time implementation for this, but work is ongoing to implement $O(n\log n)$ time algorithms (both expected and worst case).

• Computing the convex hull of $n$ points in $\mathbb{R}^2$. In particular,

  • worst case optimal $O(n\log n)$ time implementations of Graham scan and Divide and Conquer,
  • an output sensitive $O(nh)$ time Jarvis March, and
  • a QuickHull implementation (which has worst case complexity $O(n^2)$ )

  Furtheremore, an optimal linear time algorithm for when the points are the vertices of a convex polygon.

• Computing the closest pair among $n$ points in $\mathbb{R}^2$

  • $O(n\log n)$ time using divide and conquer

• Computing the intersections among a set of $n$ line segments in $\mathbb{R}^2$.

  • The algorithm runs in $O((n+k)\log n)$ time, where $k$ is the output size.
  • Alternatively, one can of course also compute all intersections in $O(n^2)$ time (which may be better if $k$ is large).

• Computing the Minkowski sum of two convex polygons. The algorithm runs in optimal $O(n+m)$ time, where $n$ and $m$ are the sizes of the polygons.

• Testing if a point lies in a polygon. In particular,

  • in linear time for simple polygons, and
  • in $O(\log n)$ time for convex polygons.

• Computing tangents and extremal points in a polygon In particular,

  • in $O(\log n)$ time for convex polygons, and
  • in linear time in simple polygons.

• Computing a simplification of a polyline. In particular, an implementation of

  • the Imai-Iri algorithm, and
  • the well-known Douglas Peucker algorithm.

• Computing the shortest path tree of a point in a triangulated simple polygon in $O(n)$ time.

• Computing the visibility polygon of a point inside a simple polygon. We currently provide a naive $O(n^2)$ time implementation.

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

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

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 most algorithms it is sufficient if the type r is Fractional. Hence, you can use an exact number type such as Data.Ratio.Rational or HGeometry.Number.Real.Rational (which is essentially just a Rational with a friendlier Show instance).

Interval Arithmetic (to speed up our computations) is one of the things on the main things on the TODO list.

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. We use typeclasses to make sure it is easy to use the functions with custom geometric types that store such additional fields. For example, the 2d convex hull algorithms have type:

convexHull :: (Ord r, Num r, Point_ point 2 r) => NonEmpty point -> ConvexPolygon point

In many cases you may not want to explicitly declare a new specific point type, but just "attach" an additional value (e.g. a color) to a point. You may want to use the Ext type (typically seen as (:+) from Heometry.Ext in such cases.

Build Instructions

HGeometry heavily relies on typeclasses to support polymorphic inputs. Therefore, if you are using this package, it is recommended to compile your package with GHC options -fspecialise-aggressively -fexpose-all-unfoldings to make sure GHC sufficiently specializes the calls. You can do so by adding the following to your executable/library stanza in your cabal file:

    ghc-options: -fspecialise-aggressively -fexpose-all-unfoldings

Not doing so may significantly impact the performance of your compiled code.