RGeometry

Computational Geometry in Rust

GitHubDiscordAPI ReferencePlaygroundLandscapeCorrectness

Overview of Computation Geometry

This page is a summary of all the algorithms that belong in the RGeometry library. Green dots mark algorithms that have already been implemented and clicking on them will reveal a link to the API documentation.

If you know of any noteworthy algorithms that are not on this list, please open a ticket on GitHub.

Polygonization

Convex Polygons
\(O(n \log n)\)
Monotone Polygons
\(O(n \log n)\)
Star-shaped Polygons
\(O(n \log n)\)
2-Opt Moves
\(O(n^4)\)
Random Growth
\(O(?)\)
Skeleton holes
\(O(?)\)

2D Interpolation

Linear
\(O(n)\)
Angular
\(O(?)\)
Edge+angle
\(O(?)\)
Least-work
\(O(?)\)
Star-skeleton
\(O(?)\)
As-rigid-as-possible
\(O(?)\)
Guaranteed intersection-free
\(O(?)\)

Visibility

Linear Visibility
\(O(n)\)
Naive Visibility
\(O(n^2)\)
Sweep Visibility
\(O(n \log n)\)
Output-sensitive visibility
\(O(k)\)
Minimum-link path
\(O(n)\)
Visibility window
\(O(n)\)
Single-source shortest path
\(O(n)\)
Shortest path
\(O(n \log n)\)

Convex

Polygon Kernel
\(O(n)\)
Polygon Convex Hull
\(O(n)\)
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)\)
Optimal Convex Decomposition
\(O(nr^2)\)
ACD Lien/Amato
\(O(nr)\)
ACD Hertel/Mehlhorn
\(O(n)\)

Triangulation

Ear clipping
\(O(n \log n)\)
Monotone Triangulation
\(O(n \log n)\)
Trapezoidal Triangulation
\(O(n \log^\star n)\)
Randomised Linear Triangulation
\(O(n)\)
Linear Triangulation
\(O(n)\)
Constrained Delaunay Triangulation
\(O(n^2)\)
Constrained Delaunay Triangulation
\(O(n\log n)\)
Constrained Delaunay Triangulation
\(O(n\log n)\)
Delaunay Triangulation
\(O(n \log n)\)
Compatible triangulation
\(O(?)\)

Misc

Segment intersections
\(O((n+k)\log n)\)
Segment intersections
\(O(n\log n+k)\)
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)\)
Boolean operations
\(O((n+k) \log n)\)