A library to compute the 2D delaunay triangulation of a set of points, using the Bowyer-Watson algorithm. While not the fastest algorithm for triangulation, it's easy enough to understand.
- A C++17 compliant compiler
- CMake (version 3.x)
mkdir build
cd build
cmake ..
make#include "delaunay.h"
int main() {
std::vector<point> points = ...;
std::vector<triangle> triangles = delaunay::triangulate(points);
}- https://en.wikipedia.org/wiki/Bowyer-Watson_algorithm
- For an overview of the general algorithm
- https://math.stackexchange.com/questions/4001660
- For a discussion on points approaching collinearity and the more stringent requirements of the super triangle