#2 parity with js: mapbox/delaunator@760be6b
diff --git a/README.md b/README.md index 67b6a49..4eabb27 100644 --- a/README.md +++ b/README.md
@@ -48,16 +48,16 @@ ``` Run on (4 X 2300 MHz CPU s) -2018-09-19 09:40:29 +2018-09-23 08:36:08 ------------------------------------------------------------ Benchmark Time CPU Iterations ------------------------------------------------------------ -BM_45K_geojson_nodes 23 ms 23 ms 32 -BM_2K_uniform 1 ms 1 ms 970 -BM_100K_uniform 63 ms 63 ms 10 -BM_200K_uniform 142 ms 141 ms 4 -BM_500K_uniform 415 ms 412 ms 2 -BM_1M_uniform 1016 ms 1010 ms 1 +BM_45K_geojson_nodes 22 ms 22 ms 33 +BM_uniform/2000 1 ms 1 ms 953 +BM_uniform/100000 61 ms 61 ms 9 +BM_uniform/200000 140 ms 140 ms 4 +BM_uniform/500000 409 ms 408 ms 2 +BM_uniform/1000000 998 ms 995 ms 1 ``` Library is ~10% faster then JS version for 1M uniform points ([details](https://github.com/delfrrr/delaunator-cpp/pull/8#issuecomment-422690056))
diff --git a/include/delaunator.hpp b/include/delaunator.hpp index 03dc496..17ac031 100644 --- a/include/delaunator.hpp +++ b/include/delaunator.hpp
@@ -256,18 +256,24 @@ } } + const double i0x = coords[2 * i0]; + const double i0y = coords[2 * i0 + 1]; + min_dist = std::numeric_limits<double>::max(); // find the point closest to the seed for (std::size_t i = 0; i < n; i++) { if (i == i0) continue; - const double d = dist(coords[2 * i0], coords[2 * i0 + 1], coords[2 * i], coords[2 * i + 1]); + const double d = dist(i0x, i0y, coords[2 * i], coords[2 * i + 1]); if (d < min_dist && d > 0.0) { i1 = i; min_dist = d; } } + double i1x = coords[2 * i1]; + double i1y = coords[2 * i1 + 1]; + double min_radius = std::numeric_limits<double>::max(); // find the third point which forms the smallest circumcircle with the first two @@ -275,7 +281,7 @@ if (i == i0 || i == i1) continue; const double r = circumradius( - coords[2 * i0], coords[2 * i0 + 1], coords[2 * i1], coords[2 * i1 + 1], coords[2 * i], coords[2 * i + 1]); + i0x, i0y, i1x, i1y, coords[2 * i], coords[2 * i + 1]); if (r < min_radius) { i2 = i; @@ -287,22 +293,14 @@ throw std::runtime_error("not triangulation"); } - if (orient( - coords[2 * i0], coords[2 * i0 + 1], // - coords[2 * i1], - coords[2 * i1 + 1], // - coords[2 * i2], - coords[2 * i2 + 1]) // - ) { - std::swap(i1, i2); - } + double i2x = coords[2 * i2]; + double i2y = coords[2 * i2 + 1]; - const double i0x = coords[2 * i0]; - const double i0y = coords[2 * i0 + 1]; - const double i1x = coords[2 * i1]; - const double i1y = coords[2 * i1 + 1]; - const double i2x = coords[2 * i2]; - const double i2y = coords[2 * i2 + 1]; + if (orient(i0x, i0y, i1x, i1y, i2x, i2y)) { + std::swap(i1, i2); + std::swap(i1x, i2x); + std::swap(i1y, i2y); + } std::tie(m_center_x, m_center_y) = circumcenter(i0x, i0y, i1x, i1y, i2x, i2y);