HGeometry

Build Status Hackage

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 $^$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.