RGeometry

Computational Geometry in Rust

HomeGitHubDiscordAPI ReferenceLandscapeCorrectness

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)\)
paperwikiapi
⬤
Monotone Polygons
\(O(n \log n)\)
paperwikiapi
⬤
Star-shaped Polygons
\(O(n \log n)\)
paperwikiapi
⬤
2-Opt Moves
\(O(n^4)\)
paperwikiapi
⬤
Random Growth
\(O(?)\)
paper
⬤
Skeleton holes
\(O(?)\)
paperwiki

2D Interpolation

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

Visibility

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

Convex

⬤
Polygon Kernel
\(O(n)\)
paperscihubdoiwiki
⬤
Polygon Convex Hull
\(O(n)\)
paperwikiapi
⬤
Point Set Convex Hull
\(O(n \log n)\)
paperwikiapi
⬤
Point Set Convex Hull
\(O(nh)\)
doiwiki
⬤
Point Set Convex Hull
\(O(n \log h)\)
doi
⬤
Convex point locator
\(O(\log n)\)
paperapi
⬤
Convex extremes
\(O(\log n)\)
⬤
Convex Minkowski sum
\(O(n + m)\)
⬤
Convex intersection
\(O(\log n + \log m)\)
paper
⬤
Optimal Convex Decomposition
\(O(nr^2)\)
⬤
ACD Lien/Amato
\(O(nr)\)
paper
⬤
ACD Hertel/Mehlhorn
\(O(n)\)
paperscihubdoi

Triangulation

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

Misc

⬤
Segment intersections
\(O((n+k)\log n)\)
wiki
⬤
Segment intersections
\(O(n\log n+k)\)
paperdoi
⬤
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)\)
wikiapi
⬤
Planar point location
\(O(\log n)\)
⬤
Boolean operations
\(O(nm)\)
paperscihubdoiwiki
⬤
Boolean operations
\(O((n+k) \log n)\)
paperscihubdoiwiki