GitHub - abellgithub/delaunator-cpp: A really fast C++ library for Delaunay triangulation of 2D points (original) (raw)

delaunator-cpp

A really fast C++ library forDelaunay triangulation of 2D points.

delaunator-cpp was originally a a C++ port from https://github.com/mapbox/delaunator, a JavaScript implementation of very fast 2D Delaunay algorithm. It has since diverged from that source.

Features

• A fast C++ open source 2D Delaunay implementation
• Example showing triangulation of GeoJson points

Usage

examples/basic.cpp

#include <delaunator.hpp> #include

int main() { /* x0, y0, x1, y1, ... */ std::vector coords = {-1, 1, 1, 1, 1, -1, -1, -1};

//triangulation happens here
delaunator::Delaunator d(coords);

for(std::size_t i = 0; i < d.triangles.size(); i+=3) {
    printf(
        "Triangle points: [[%f, %f], [%f, %f], [%f, %f]]\n",
        d.coords[2 * d.triangles[i]],        //tx0
        d.coords[2 * d.triangles[i] + 1],    //ty0
        d.coords[2 * d.triangles[i + 1]],    //tx1
        d.coords[2 * d.triangles[i + 1] + 1],//ty1
        d.coords[2 * d.triangles[i + 2]],    //tx2
        d.coords[2 * d.triangles[i + 2] + 1] //ty2
    );
}

}

See more examples here

Benchmarks

Run on (4 X 2300 MHz CPU s)
2018-09-29 09:27:28
------------------------------------------------------------
Benchmark                     Time           CPU Iterations
------------------------------------------------------------
BM_45K_geojson_nodes         22 ms         22 ms         32
BM_uniform/2000               1 ms          1 ms        982
BM_uniform/100000            63 ms         62 ms          9
BM_uniform/200000           140 ms        140 ms          4
BM_uniform/500000           400 ms        399 ms          2
BM_uniform/1000000          994 ms        993 ms          1

Library is ~10% faster then JS version for 1M uniform points (details)