HGeometry

Computational Geometry in Haskell

GitHubDiscordAPI ReferenceLandscapeCorrectness

What is Computational Geometry?

Richard Feynman, a physicist and Nobel laureate, famously asked for a "map of the cat." He was attending a biology class at a whim and need information about a cat's anatomy but didn't know any of the terminology. Well, this page is a map of computational geometry.

To keep the number of algorithms managable, foundational concepts are favoured over heuristics. The cross or checkmark indicate whether the algorithm has been implemented in HGeometry.

Random Polygon Generation

Random Convex Polygon
\(O(n \log n)\)
✓

Paper: Generating Random Convex Polygons

Random Monotone Polygon
\(O(n \log n)\)
✓

Paper: Heuristics For The Generation of Random Polygons.

Random Star-shaped Polygon
\(O(n \log n)\)
✗

Paper: Heuristics For The Generation of Random Polygons.

2-Opt Moves
\(O(?)\)
✗

Paper: Heuristics For The Generation of Random Polygons.

Random Growth
\(O(?)\)
✗

Paper: Heuristics For The Generation of Random Polygons.

Skeleton holes
\(O(?)\)
✗

2D Interpolation

Linear
\(O(n)\)
?
Angular
\(O(?)\)
?
Edge+angle
\(O(?)\)
?

Paper: 2-D shape blending: An intrinsic solution to the vertex path problem

SciHub: 2-D shape blending: An intrinsic solution to the vertex path problem

DOI: 10.1145/166117.166118

Least-work
\(O(?)\)
?

Paper: A physically based approach to 2-D shape blending (1992)

Star-skeleton
\(O(?)\)
?

Paper: Shape Blending Using the Star-Skeleton Representation (1995)

As-rigid-as-possible
\(O(?)\)
?

Paper: As-rigid-as-possible shape interpolation (2000)

Guaranteed intersection-free
\(O(?)\)
?

Paper: Guaranteed Intersection-Free Polygon Morphing (2001)

Visibility

Linear Visibility
\(O(n)\)
✗

Paper: Corrections to Lee's visibility polygon algorithm (1987)

SciHub: Corrections to Lee's visibility polygon algorithm (1987)

DOI: 10.1007/BF01937271

Naive Visibility
\(O(n^2)\)
✗

Wikipedia article: Visibility polygon

Sweep Visibility
\(O(n \log n)\)
✗

Paper: Worst-case optimal algorithms for constructing visibility polygons with holes (1986)

SciHub: Worst-case optimal algorithms for constructing visibility polygons with holes (1986)

DOI: 10.1145/10515.10517

Output-sensitive visibility
\(O(k)\)
✗

Paper: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons (1987)

SciHub: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons (1987)

DOI: 10.1007/BF01840360

Minimum-link path
\(O(n)\)
✗

Paper: A linear time algorithm for minimum link paths inside a simple polygon (1986)

SciHub: A linear time algorithm for minimum link paths inside a simple polygon (1986)

DOI: 10.1016/0734-189X(86)90127-1

Visibility window
\(O(n)\)
✗

Paper: A linear time algorithm for minimum link paths inside a simple polygon (1986)

SciHub: A linear time algorithm for minimum link paths inside a simple polygon (1986)

DOI: 10.1016/0734-189X(86)90127-1

Single-source shortest path
\(O(n)\)
✓

Paper: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons (1987)

SciHub: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons (1987)

DOI: 10.1007/BF01840360

Shortest path
\(O(n \log n)\)
✗

Paper: An Optimal Algorithm for Euclidean Shortest Paths in the Plane

Convex related

Polygon Kernel
\(O(n)\)
✗

Paper: An Optimal Algorithm For Finding The Kernel Of A Polygon (1979)

SciHub: An Optimal Algorithm For Finding The Kernel Of A Polygon (1979)

DOI: 10.1145/322139.322142

Wikipedia article: Star-shaped Polygon

Polygon Convex Hull
\(O(n)\)
✓

Paper: Online Construction of the Convex Hull of a Simple Polyline

Wikipedia article: Convex hull of a Simple Polygon

Point Set Convex Hull
\(O(n \log n)\)
✓
Convex point locator
\(O(\log n)\)
✓
Convex extremes
\(O(\log n)\)
✓
Convex Minkowski sum
\(O(n + m)\)
✓
Convex intersection
\(O(\log n + \log m)\)
✗

Paper: Optimal detection of intersections between convex polyhedra

Optimal Convex Decomposition
\(O(nr^2)\)
✗
ACD Lien/Amato
\(O(nr)\)
✗

Paper: Approximate Convex Decomposition of Polygons

ACD Hertel/Mehlhorn
\(O(n)\)
✗

Paper: Fast Triangulation of the Plane with Respect to Simple Polygons (1985)

SciHub: Fast Triangulation of the Plane with Respect to Simple Polygons (1985)

DOI: 10.1016/S0019-9958(85)80044-9

Triangulation

Triangulation with holes
\(O(n \log n)\)
✓
Triangulation without holes
\(O(n \log^\star n)\)
✗

Paper: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons (1991)

Linear Triangulation without holes
\(O(n)\)
✗

Paper: Triangulating a simple polygon in linear time (1990)

SciHub: Triangulating a simple polygon in linear time (1990)

DOI: 10.1109/fscs.1990.89541

Constrained Delaunay Triangulation
\(O(n^2)\)
✗
Constrained Delaunay Triangulation
\(O(n\log n)\)
✗

Paper: Constrained Delaunay triangulations (1989)

Delaunay Triangulation
\(O(n \log n)\)
✓

Paper: Two algorithms for constructing a Delaunay triangulation (1980)

SciHub: Two algorithms for constructing a Delaunay triangulation (1980)

DOI: 10.1007/BF00977785

Compatible triangulation
\(O(?)\)
✗

Uncategorized

Segment intersections
\(O((n+k)\log n)\)
✓

Wikipedia article: Bentley–Ottmann algorithm

Segment intersections
\(O(n\log n+k)\)
✗

Paper: An optimal algorithm for finding segments intersections (1995)

DOI: 10.1145/220279.220302

Douglas Peucker's simplification
\(O(n)\)
✓
Euclidean Minimum Spanning Tree
\(O(n \log n)\)
✓
2D closest pair
\(O(n \log n)\)
✓
Polygon point locator
\(O(n)\)
✓
Planar point location
\(O(\log n)\)
✗
Boolean operations
\(O(nm)\)
✗

Paper: Clipping simple polygons with degenerate intersections

SciHub: Clipping simple polygons with degenerate intersections

DOI: 10.1016/j.cagx.2019.100007

Boolean operations
\(O((n+k) \log n)\)
✗

Paper: A simple algorithm for Boolean operations on polygons.

SciHub: A simple algorithm for Boolean operations on polygons.

DOI: 10.1016/j.advengsoft.2013.04.004