#2 parity with js: mapbox/delaunator#32
diff --git a/README.md b/README.md
index 4eabb27..c747122 100644
--- a/README.md
+++ b/README.md
@@ -48,16 +48,16 @@
```
Run on (4 X 2300 MHz CPU s)
-2018-09-23 08:36:08
+2018-09-26 09:28:34
------------------------------------------------------------
Benchmark Time CPU Iterations
------------------------------------------------------------
-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
+BM_45K_geojson_nodes 24 ms 24 ms 29
+BM_uniform/2000 1 ms 1 ms 887
+BM_uniform/100000 66 ms 66 ms 9
+BM_uniform/200000 158 ms 155 ms 4
+BM_uniform/500000 441 ms 439 ms 2
+BM_uniform/1000000 1062 ms 1058 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/generate-reference-triangles/package-lock.json b/generate-reference-triangles/package-lock.json
index 8b052b6..559cc3a 100644
--- a/generate-reference-triangles/package-lock.json
+++ b/generate-reference-triangles/package-lock.json
@@ -4,9 +4,9 @@
"lockfileVersion": 1,
"dependencies": {
"delaunator": {
- "version": "2.0.3",
- "resolved": "https://registry.npmjs.org/delaunator/-/delaunator-2.0.3.tgz",
- "integrity": "sha512-jHi7rPdAk9AqKFj+AZBchYgckSlVANdY8OMxhPmS24pRDFsJWuNoRyPxvPxOwaS6DWhy4/OOCthiuQmXI3QtKQ=="
+ "version": "3.0.1",
+ "resolved": "https://registry.npmjs.org/delaunator/-/delaunator-3.0.1.tgz",
+ "integrity": "sha512-UDOXpkVpycXOQyGQajsyz72MfTMJfkWZ7/cfElX08MNtes1TkZVFKow6BxzNba4TU7Y56nnG2Ajr/+wpeS4y8Q=="
}
}
}
diff --git a/generate-reference-triangles/package.json b/generate-reference-triangles/package.json
index 83ec286..679b7fd 100644
--- a/generate-reference-triangles/package.json
+++ b/generate-reference-triangles/package.json
@@ -3,6 +3,6 @@
"private": true,
"main": "index.js",
"dependencies": {
- "delaunator": "2.0.3"
+ "delaunator": "3.0.1"
}
}
diff --git a/include/delaunator.hpp b/include/delaunator.hpp
index 4bfb240..e16e0c3 100644
--- a/include/delaunator.hpp
+++ b/include/delaunator.hpp
@@ -180,6 +180,10 @@
std::vector<double> const& coords;
std::vector<std::size_t> triangles;
std::vector<std::size_t> halfedges;
+ std::vector<std::size_t> hull_prev;
+ std::vector<std::size_t> hull_next;
+ std::vector<std::size_t> hull_tri;
+ std::size_t hull_start;
Delaunator(std::vector<double> const& in_coords);
@@ -187,18 +191,12 @@
private:
std::vector<std::size_t> m_hash;
- std::vector<DelaunatorPoint> m_hull;
- std::size_t m_hull_entry;
double m_center_x;
double m_center_y;
std::size_t m_hash_size;
- std::size_t remove_node(std::size_t node);
std::size_t legalize(std::size_t a);
- std::size_t insert_node(std::size_t i);
- std::size_t insert_node(std::size_t i, std::size_t prev);
std::size_t hash_key(double x, double y);
- void hash_edge(std::size_t e);
std::size_t add_triangle(
std::size_t i0,
std::size_t i1,
@@ -213,9 +211,11 @@
: coords(in_coords),
triangles(),
halfedges(),
+ hull_prev(),
+ hull_next(),
+ hull_tri(),
+ hull_start(),
m_hash(),
- m_hull(),
- m_hull_entry(),
m_center_x(),
m_center_y(),
m_hash_size() {
@@ -309,27 +309,29 @@
// initialize a hash table for storing edges of the advancing convex hull
m_hash_size = static_cast<std::size_t>(std::llround(std::ceil(std::sqrt(n))));
- m_hash.reserve(m_hash_size);
- for (std::size_t i = 0; i < m_hash_size; i++) {
- m_hash.push_back(INVALID_INDEX);
- }
+ m_hash.resize(m_hash_size);
+ std::fill(m_hash.begin(), m_hash.end(), INVALID_INDEX);
- // initialize a circular doubly-linked list that will hold an advancing convex hull
- // doubly-linked list is stored as plain vector
- // vertices are linked via ineces of next/prev vertice
- m_hull.reserve(coords.size());
- std::size_t e = insert_node(i0);
- m_hull_entry = e;
- hash_edge(e);
- m_hull[e].t = 0;
+ // initialize arrays for tracking the edges of the advancing convex hull
+ hull_prev.resize(n);
+ hull_next.resize(n);
+ hull_tri.resize(n);
- e = insert_node(i1, e);
- hash_edge(e);
- m_hull[e].t = 1;
+ hull_start = i0;
- e = insert_node(i2, e);
- hash_edge(e);
- m_hull[e].t = 2;
+ size_t hull_size = 3;
+
+ hull_next[i0] = hull_prev[i2] = i1;
+ hull_next[i1] = hull_prev[i0] = i2;
+ hull_next[i2] = hull_prev[i1] = i0;
+
+ hull_tri[i0] = 0;
+ hull_tri[i1] = 1;
+ hull_tri[i2] = 2;
+
+ m_hash[hash_key(i0x, i0y)] = i0;
+ m_hash[hash_key(i1x, i1y)] = i1;
+ m_hash[hash_key(i2x, i2y)] = i2;
std::size_t max_triangles = n < 3 ? 1 : 2 * n - 5;
triangles.reserve(max_triangles * 3);
@@ -354,108 +356,89 @@
check_pts_equal(x, y, i2x, i2y)) continue;
// find a visible edge on the convex hull using edge hash
- const std::size_t start_key = hash_key(x, y);
- std::size_t key = start_key;
- std::size_t start = INVALID_INDEX;
- do {
- start = m_hash[key];
- key = (key + 1) % m_hash_size;
- } while (
- (start == INVALID_INDEX || m_hull[start].removed) &&
- (key != start_key));
+ std::size_t start = 0;
- start = m_hull[start].prev;
- e = start;
- while (!orient(
- x, y, //
- m_hull[e].x,
- m_hull[e].y, //
- m_hull[m_hull[e].next].x, //
- m_hull[m_hull[e].next].y) //
- ) {
- e = m_hull[e].next;
+ size_t key = hash_key(x, y);
+ for (size_t j = 0; j < m_hash_size; j++) {
+ start = m_hash[(key + j) % m_hash_size];
+ if (start != INVALID_INDEX && start != hull_next[start]) break;
+ }
+ start = hull_prev[start];
+ size_t e = start;
+ size_t q;
+
+ while (q = hull_next[e], !orient(x, y, coords[2 * e], coords[2 * e + 1], coords[2 * q], coords[2 * q + 1])) { //TODO: does it works in a same way as in JS
+ e = q;
if (e == start) {
- e = INVALID_INDEX; //TODO: will it work correct?
+ e = INVALID_INDEX;
break;
}
}
- // likely a near-duplicate point; skip it
- if (e == INVALID_INDEX) continue;
-
- const bool walk_back = e == start;
+ if (e == INVALID_INDEX) continue; // likely a near-duplicate point; skip it
// add the first triangle from the point
std::size_t t = add_triangle(
- m_hull[e].i,
+ e,
i,
- m_hull[m_hull[e].next].i,
+ hull_next[e],
INVALID_INDEX,
INVALID_INDEX,
- m_hull[e].t);
+ hull_tri[e]);
- m_hull[e].t = t; // keep track of boundary triangles on the hull
- e = insert_node(i, e);
-
- // recursively flip triangles from the point until they satisfy the Delaunay condition
- m_hull[e].t = legalize(t + 2);
+ hull_tri[i] = legalize(t + 2);
+ hull_tri[e] = t;
+ hull_size++;
// walk forward through the hull, adding more triangles and flipping recursively
- std::size_t q = m_hull[e].next;
- while (orient(
- x, y, //
- m_hull[q].x,
- m_hull[q].y, //
- m_hull[m_hull[q].next].x,
- m_hull[m_hull[q].next].y //
- )) {
- t = add_triangle(
- m_hull[q].i, i, m_hull[m_hull[q].next].i, m_hull[m_hull[q].prev].t, INVALID_INDEX, m_hull[q].t);
- m_hull[m_hull[q].prev].t = legalize(t + 2);
- m_hull_entry = remove_node(q);
- q = m_hull[q].next;
+ std::size_t next = hull_next[e];
+ while (
+ q = hull_next[next],
+ orient(x, y, coords[2 * next], coords[2 * next + 1], coords[2 * q], coords[2 * q + 1])) {
+ t = add_triangle(next, i, q, hull_tri[i], INVALID_INDEX, hull_tri[next]);
+ hull_tri[i] = legalize(t + 2);
+ hull_next[next] = next; // mark as removed
+ hull_size--;
+ next = q;
}
- if (walk_back) {
- // walk backward from the other side, adding more triangles and flipping
- q = m_hull[e].prev;
- while (orient(
- x, y, //
- m_hull[m_hull[q].prev].x,
- m_hull[m_hull[q].prev].y, //
- m_hull[q].x,
- m_hull[q].y //
- )) {
- t = add_triangle(
- m_hull[m_hull[q].prev].i, i, m_hull[q].i, INVALID_INDEX, m_hull[q].t, m_hull[m_hull[q].prev].t);
+
+ // walk backward from the other side, adding more triangles and flipping
+ if (e == start) {
+ while (
+ q = hull_prev[e],
+ orient(x, y, coords[2 * q], coords[2 * q + 1], coords[2 * e], coords[2 * e + 1])) {
+ t = add_triangle(q, i, e, INVALID_INDEX, hull_tri[e], hull_tri[q]);
legalize(t + 2);
- m_hull[m_hull[q].prev].t = t;
- m_hull_entry = remove_node(q);
- q = m_hull[q].prev;
+ hull_tri[q] = t;
+ hull_next[e] = e; // mark as removed
+ hull_size--;
+ e = q;
}
}
- hash_edge(e);
- hash_edge(m_hull[e].prev);
+
+ // update the hull indices
+ hull_prev[i] = e;
+ hull_start = e;
+ hull_prev[next] = i;
+ hull_next[e] = i;
+ hull_next[i] = next;
+
+ m_hash[hash_key(x, y)] = i;
+ m_hash[hash_key(coords[2 * e], coords[2 * e + 1])] = e;
}
}
double Delaunator::get_hull_area() {
std::vector<double> hull_area;
- size_t e = m_hull_entry;
+ size_t e = hull_start;
do {
- hull_area.push_back((m_hull[e].x - m_hull[m_hull[e].prev].x) * (m_hull[e].y + m_hull[m_hull[e].prev].y));
- e = m_hull[e].next;
- } while (e != m_hull_entry);
+ hull_area.push_back((coords[2 * e] - coords[2 * hull_prev[e]]) * (coords[2 * e + 1] + coords[2 * hull_prev[e] + 1]));
+ e = hull_next[e];
+ } while (e != hull_start);
return sum(hull_area);
}
-std::size_t Delaunator::remove_node(std::size_t node) {
- m_hull[m_hull[node].prev].next = m_hull[node].next;
- m_hull[m_hull[node].next].prev = m_hull[node].prev;
- m_hull[node].removed = true;
- return m_hull[node].prev;
-}
-
std::size_t Delaunator::legalize(std::size_t a) {
const std::size_t b = halfedges[a];
@@ -508,14 +491,14 @@
// edge swapped on the other side of the hull (rare); fix the halfedge reference
if (hbl == INVALID_INDEX) {
- std::size_t e = m_hull_entry;
+ std::size_t e = hull_start;
do {
- if (m_hull[e].t == bl) {
- m_hull[e].t = a;
+ if (hull_tri[e] == bl) {
+ hull_tri[e] = a;
break;
}
- e = m_hull[e].next;
- } while (e != m_hull_entry);
+ e = hull_next[e];
+ } while (e != hull_start);
}
link(a, hbl);
link(b, halfedges[ar]);
@@ -529,30 +512,6 @@
return ar;
}
-std::size_t Delaunator::insert_node(std::size_t i) {
- std::size_t node = m_hull.size();
- DelaunatorPoint p = {
- i,
- coords[2 * i],
- coords[2 * i + 1],
- 0,
- node,
- node,
- false
- };
- m_hull.push_back(p);
- return node;
-}
-
-std::size_t Delaunator::insert_node(std::size_t i, std::size_t prev) {
- std::size_t node = insert_node(i);
- m_hull[node].next = m_hull[prev].next;
- m_hull[node].prev = prev;
- m_hull[m_hull[node].next].prev = node;
- m_hull[prev].next = node;
- return node;
-}
-
std::size_t Delaunator::hash_key(double x, double y) {
const double dx = x - m_center_x;
const double dy = y - m_center_y;
@@ -561,10 +520,6 @@
m_hash_size;
}
-void Delaunator::hash_edge(std::size_t e) {
- m_hash[hash_key(m_hull[e].x, m_hull[e].y)] = e;
-}
-
std::size_t Delaunator::add_triangle(
std::size_t i0,
std::size_t i1,
