# hgeometry

Geometric Algorithms, Data structures, and Data types.

https://fstaals.net/software/hgeometry

 Version on this page: 0.12.0.4 LTS Haskell 20.26: 0.14 Stackage Nightly 2022-11-17: 0.14 Latest on Hackage: 0.14@rev:1

See all snapshots `hgeometry` appears in

Maintained by
This version can be pinned in stack with:`hgeometry-0.12.0.4@sha256:a7cb518dbcd3b40410a042ba6006f6b7db6396310cf18df0cca4e157dfcd1c8f,14528`
Depends on 34 packages(full list with versions):
Used by 1 package in lts-18.6(full list with versions):

# 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
1. 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`.

In many applications we do not just have geometric data, e.g. `Point d r`s or `Polygon r`s, 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 r`s 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.

## Changes

#+STARTUP: showeverything

* Changelog

** 0.12

- New website: https://hgeometry.org/
- Switch polygon implementation from a circular seq to a circular vector.
- Hide polygon implementation details.
- Enforce CCW polygon order by default.
- Fix bug in Data.Geometry.Polygon.Convex.extremes/maxInDirection.
- Fix bug in pointInPolygon in case of degenerate situations.
- Fix Read/Show instances for Point and Polygon such that 'read.show = id'.
- Improved numerical robustness.
- Random generation of monotone polygons. Thanks to @1ndy.
- Random and uniform generation of convex polygons.
- More IsIntersectableWith instances
- Updated Show/Read instances for LineSegments
- New algorithm: Visibility polygon in O(n log n) time.
- New algorithm: Earclip triangulation in O(n^2) time worst case, O(n)
time expected case.
- New algorithm: Single-source shortest path in O(n) time.
- New algorithm: Planar point locator in O(log n) time.
- New algorithm: Point set diameter in O(n log n) time.
- New algorithm: Convex hull of a polygon in O(n) time.
- New algorithm: Diameter of a convex polygon in O(n) time.
- New algorithm: Check if a point lies inside a convex polygon in O(n)
time.
- New algorithm: Discrete Frechet distance in O(n^2) time.

** 0.11

- Removed Functor instance from Triangle and replaced it with Bifunctor/Bifoldable/Bitraversable
- Testing if a point lies above/below a line is now in a typeclass,
moreover there now is also an instance of this typeclass for
planes. Hence, we can test if a point in R^3 lies above or below a
plane.
- Bugfixes in the incomingEdges and outgoingEdges functions in
Planar/Plane graphs and Planar subdivisions
- Added separate data types for Sides and Corners of Rectangles.
- More functionality for working with Halfspaces
- Fixed a bug in computing the intersection of overlapping
linesegments
- PolyLine.fromPoints now returns a Maybe PolyLine rather than a
Polyine. Use fromPointsUnsafe for the old behavior.
- Interval now no longer exports its constructor. Use the provided
- The corners and sides functions in Box now return specific types
representing those rather than four tuples.
- Added a BezierSpline module and data type (Thanks to Maarten).
- Added a QuadTree implementation. It can be built from a set of
points, and to represent the zeroset of some function.
- Added a Naive implementation of Convex hull in R^3. Note however
that it works only for points in general position. In particular, no
four points should be coplanar.
- Added a Data.Geometry.Directions module that defines cardinal and
InterCardinal directions.
ellipses)
- Added FunctorWithIndex, FoldableWithIndex, and TraversableWithIndex
instances for Vector, and removed specifically exporting imap; we
can now just use those functions from the Lens package.

** 0.10

- renamed the smallest enclosing ball to RIC
- improved tangency finding on convex hulls/chains
- changes to how we order points in ccwCmpAround and cwCmpAround;
these will report EQ if points appear at the same angle from the
center point.
- new functions ccwCmpAroundWith and cwCmpAroundWith that allow you to
specify the direction corresponding to "zero".
- bugfixes, in particular triangulating a polygon with holes now works properly.
- removed some unused dependencies
- we are no longer depending on ghc-plugins; as a result hgeometry
now also compiles with ghcjs
- more ToJSON/FromJSON instances.
- removed the 'point2' and 'point3' functions in favor of the pattern
synonyms Point2 and Point3.

** 0.9

- Implemented 2D Linear Programming using randomized incremental
construction (in \(O(n)\) expected time). This allows us to solve
the following problems
- testing starshapedness of simple polygons in expected linear time
- testing if we can separate a set of red and a set of blue points
in expected linear time.
- Data types for halfspaces

** 0.8

- Compatibility with GHC 8.6
- Added \(O(n\log n)\) time closest pair algorithm.
- Various Bugfixes
- Added Camera data type with some world to screen transformations.
- Updated some of the show instances for Ipe related types.

** 0.7

- Compatibility with GHC 8.0-8.4
- Implemented more Algorithms and Data Structures. This includes
* Polygon triangulation
- A new implementation of PlanarSubdivision that now also supports disconnected
subdivsions.
- Performance improvements by changing to a different Vector
implementation. For low dimensional vectors (of dimension at most four) we
now essentially use the types from
speedups on several small benchmarks.
- bugfixes.

** 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.

- 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

** 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