replace quicksort fn
diff --git a/src/delaunator.cpp b/src/delaunator.cpp index 3ff83f0..a42db06 100644 --- a/src/delaunator.cpp +++ b/src/delaunator.cpp
@@ -1,5 +1,6 @@ #include "delaunator.h" +#include <algorithm> #include <cstdio> #include <limits> #include <tuple> @@ -103,90 +104,14 @@ return diff3; } } - // std::deque<long int>::iterator insert_node( - // const deque<DelaunatorPoint> &hull, - // const vector<double> &coords, - // long int i, - // std::deque<long int>::iterator prev - // ) { - // return hull.emplace(prev + 1, { - // .i = i, - // .x = coords[2 * i], - // .y = coords[2 * i + 1], - // .t = 0 - // }); - // } - // size_t insert_node( - // deque<DelaunatorPoint> &hull, - // const vector<double> &coords, - // long int i - // ) { - // DelaunatorPoint p = { - // .i = i, - // .x = coords[2 * i], - // .y = coords[2 * i + 1], - // .t = 0 - // }; - // size_t pos = hull.insert(hull.end(), p) - hull.begin(); - // return pos; - // } - void quicksort( - unsigned long int ids[], - const vector<double> &coords, - unsigned int left, - unsigned int right, - double &cx, - double &cy - ) { - long int i; - long int j; - unsigned long int temp; - - if (right - left <= 20) { - for (i = left + 1; i <= right; i++) { - // printf("i=%lu\n", i); - temp = ids[i]; - j = i - 1; - while ( - j >= left && - compare(coords, ids[j], temp, cx, cy) > 0 - ) { - // printf("j=%lu\n", j); - ids[j + 1] = ids[j]; - j--; - } - ids[j + 1] = temp; - } - } else { - throw runtime_error("not implemented"); - }// else { - // const median = (left + right) >> 1; - // i = left + 1; - // j = right; - // swap(ids, median, i); - // if (compare(coords, ids[left], ids[right], cx, cy) > 0) swap(ids, left, right); - // if (compare(coords, ids[i], ids[right], cx, cy) > 0) swap(ids, i, right); - // if (compare(coords, ids[left], ids[i], cx, cy) > 0) swap(ids, left, i); - - // temp = ids[i]; - // while (true) { - // do i++; while (compare(coords, ids[i], temp, cx, cy) < 0); - // do j--; while (compare(coords, ids[j], temp, cx, cy) > 0); - // if (j < i) break; - // swap(ids, i, j); - // } - // ids[left + 1] = ids[j]; - // ids[j] = temp; - - // if (right - i + 1 >= j - left) { - // quicksort(ids, coords, i, right, cx, cy); - // quicksort(ids, coords, left, j - 1, cx, cy); - // } else { - // quicksort(ids, coords, left, j - 1, cx, cy); - // quicksort(ids, coords, i, right, cx, cy); - // } - // } - } + struct sort_to_center { + double cx; + double cy; + vector<double> &coords; + bool operator() (long int i, long int j) { + return compare(coords, i, j, cx, cy) < 0; + } + }; bool in_circle( double ax, double ay, @@ -218,7 +143,8 @@ double max_y = -1 * max_double; double min_x = max_double; double min_y = max_double; - unsigned long int ids[n]; + vector<long int> ids; + ids.reserve(n); for (long int i = 0; i < n; i++) { const double x = coords[2 * i]; const double y = coords[2 * i + 1]; @@ -228,7 +154,8 @@ if (y < min_y) min_y = y; if (x > max_x) max_x = x; if (y > max_y) max_y = y; - ids[i] = i; + // ids[i] = i; + ids.push_back(i); } const double cx = (min_x + max_x) / 2; const double cy = (min_y + max_y) / 2; @@ -304,7 +231,15 @@ tie(m_center_x, m_center_y) = circumcenter(i0x, i0y, i1x, i1y, i2x, i2y); // sort the points by distance from the seed triangle circumcenter - quicksort(ids, coords, 0, n - 1, m_center_x, m_center_y); + // cerr << ids << endl; + const sort_to_center s = { + .cx = m_center_x, + .cy = m_center_y, + .coords = coords + }; + sort(ids.begin(), ids.end(), s); + // quicksort(ids, coords, 0, n - 1, m_center_x, m_center_y); + // cerr << ids << endl; m_hash_size = ceil(sqrt(n)); m_hash.reserve(m_hash_size); @@ -324,8 +259,6 @@ hash_edge(e); m_hull[e].t = 2; - // cout << "m_hash " << m_hash << endl; - const size_t max_triangles = 2 * n - 5; triangles.reserve(max_triangles * 3); halfedges.reserve(max_triangles * 3); @@ -486,7 +419,7 @@ legalize(a); return legalize(br); } - + return ar; } size_t Delaunator::insert_node(size_t i, size_t prev) {
diff --git a/test-files/map-mercator.geojson b/test-files/map-mercator.geojson index ea1544e..4e84be9 100644 --- a/test-files/map-mercator.geojson +++ b/test-files/map-mercator.geojson
@@ -2,10 +2,10 @@ "type": "FeatureCollection", "crs": { "type": "name", "properties": { "name": "urn:ogc:def:crs:EPSG::900913" } }, "features": [ -{ "type": "Feature", "properties": { }, "geometry": { "type": "Point", "coordinates": [ 1469272.557697656564415, 6881014.160288135521114 ] } }, -{ "type": "Feature", "properties": { }, "geometry": { "type": "Point", "coordinates": [ 1474776.023734191432595, 6912659.089998200535774 ] } }, -{ "type": "Feature", "properties": { }, "geometry": { "type": "Point", "coordinates": [ 1501376.109577432041988, 6908531.490470800548792 ] } }, -{ "type": "Feature", "properties": { }, "geometry": { "type": "Point", "coordinates": [ 1502293.35391685529612, 6879485.419722434133291 ] } }, -{ "type": "Feature", "properties": { }, "geometry": { "type": "Point", "coordinates": [ 1489299.059108373941854, 6894314.203209755942225 ] } } +{ "type": "Feature", "id": 0, "properties": { }, "geometry": { "type": "Point", "coordinates": [ 1469272.557697656564415, 6881014.160288135521114 ] } }, +{ "type": "Feature", "id": 1, "properties": { }, "geometry": { "type": "Point", "coordinates": [ 1474776.023734191432595, 6912659.089998200535774 ] } }, +{ "type": "Feature", "id": 2, "properties": { }, "geometry": { "type": "Point", "coordinates": [ 1501376.109577432041988, 6908531.490470800548792 ] } }, +{ "type": "Feature", "id": 3, "properties": { }, "geometry": { "type": "Point", "coordinates": [ 1502293.35391685529612, 6879485.419722434133291 ] } }, +{ "type": "Feature", "id": 4, "properties": { }, "geometry": { "type": "Point", "coordinates": [ 1489299.059108373941854, 6894314.203209755942225 ] } } ] }