hgeometry

Geometric Algorithms, Data structures, and Data types.

https://fstaals.net/software/hgeometry

Version on this page:0.14
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

BSD-3-Clause licensed by Frank Staals
Maintained by [email protected]
This version can be pinned in stack with:hgeometry-0.14@sha256:33acdfc3096a72deef621e8cd080eeab9cb13b07bb95dc30c120042cd767f5c6,15167

Module documentation for 0.14

HGeometry

GitHub Workflow Status Hackage API docs coverage

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.

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.

Changes

#+STARTUP: showeverything

* Changelog

** 0.14

- Allow the associated/extra data of linesegments and intervals to
differ when testing for intersections.
- Intersection testing between line segments and rectangles
- Testing if lines and/or line segments intersect no longer requires a
Fractional constraint; Num is sufficient. However, in turn we now do
need Ord rather than just Eq. That seemed a worthwile tradeoff though.
- Cleaning up the public API by hiding several internal modules.
- Introduced the 'HasSquaredEuclideanDistance' class describing
geometry types for which we can compute the squared distance from a
point to a geometry, and added instances for some of the basic
geometries.
- Fixed a bug in computing lengths to open line segments.
- Removed some proxy arguments, in e.g. Data.Geometry.Point.coord,
rather than take a Proxy to specify which coordinate we want, use
type applications.
- Support for GHC 9.0 and 9.2
- Better support for open-ended line segments in the Bentley Ottmann
line segment intersection algorithm.

** 0.13

- Moved 'intersects' from the HasIntersectionWith class into a new
class IsIntersectableWith. This allows separate (weaker) constraints
for checking *if* geometries intersect rather than computing exact
intersections.
- New BezierSpline features.
- "Zoom to fit" transformation.
- Many fixes related to PlaneGraph/PlanarSubdivison; i.e. bugs in
which order the vertices/darts where reported when traversing a
face. The polygon representing the outer boundary now is some area
inside a bounding polygon.
- Fixed a bug in the DelaunayTriangulation.
- Preliminary implementations for updating planar subdivisions
(e.g. subdividing edges).

** 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
patterns instead.
- Added an OpenLineSegment pattern/constructor
- 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.
- Added an Ellipse type (mostly so that hgeometry-ipe can read
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.
- Added arrangement data type
- Various Bugfixes
- Added Camera data type with some world to screen transformations.
- Additional read/show instances
- 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
[linear](https://hackage.haskell.org/package/linear), this gives significant
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
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.