delaunator cpp

delaunator-cpp

Eine wirklich schnelle C++-Bibliothek für die Delaunay-Triangulation von 2D-Punkten.

delaunator-cpp ist eine C++-Portierung von https://github.com/mapbox/delaunator, eine JavaScript-Implementierung des sehr schnellen 2D-Delaunay-Algorithmus.

Merkmale

• Wahrscheinlich die schnellste C++-Open-Source-2D-Delaunay-Implementierung
• Beispiel für die Triangulation von GeoJson-Punkten

Verwendung

examples/basic.cpp

# include < delaunator.hpp >
# include < cstdio >

int main () {
    /* x0, y0, x1, y1, ... */
    std::vector< double > 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
        );
    }
}

Weitere Beispiele finden Sie hier

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

Die Bibliothek ist für 1 Mio. einheitliche Punkte etwa 10 % schneller als die JS-Version (Details).