# RGeometry

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

Naive Visibility
$$O(n^2)$$
Linear Visibility
$$O(n)$$
Sweep Visibility
$$O(n \log n)$$
Output-sensitive visibility
$$O(k)$$
$$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)$$
Point Set Convex Hull
$$O(nh)$$
Point Set Convex Hull
$$O(n \log h)$$
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)$$