#2 parity with js: mapbox/delaunator@b1f360c
diff --git a/examples/utils.hpp b/examples/utils.hpp index fd8c622..02c32df 100644 --- a/examples/utils.hpp +++ b/examples/utils.hpp
@@ -8,7 +8,7 @@ namespace utils { -std::string read_file(const char* filename) { +inline std::string read_file(const char* filename) { std::ifstream input_file(filename); if(input_file.good()) { std::string json_str( @@ -22,7 +22,7 @@ } } -std::vector<double> get_geo_json_points(std::string const& json) { +inline std::vector<double> get_geo_json_points(std::string const& json) { rapidjson::Document document; if(document.Parse(json.c_str()).HasParseError()) { throw std::runtime_error("Cannot parse JSON"); @@ -40,8 +40,22 @@ return coords; } -std::vector<double> get_array_points(std::string const& json) { - std::vector<double> points; +template <typename T> +inline T get_json_value(const rapidjson::Value &v); + +template <> +inline double get_json_value(const rapidjson::Value &v) { + return v.GetDouble(); +} + +template <> +inline size_t get_json_value(const rapidjson::Value &v) { + return static_cast<size_t>(v.GetUint64()); +} + +template <typename T> +inline std::vector<T> get_array_points(std::string const& json) { + std::vector<T> points; rapidjson::Document document; if(document.Parse(json.c_str()).HasParseError()) { throw std::runtime_error("Cannot parse JSON"); @@ -51,10 +65,10 @@ } points.reserve(static_cast<std::size_t>(document.Size())); for(rapidjson::SizeType i = 0; i < document.Size(); i++) { - points.push_back(document[i].GetDouble()); + // points.push_back(document[i].GetDouble()); + points.push_back(get_json_value<T>(document[i])); } return points; - } } // end ns utils
diff --git a/include/delaunator.hpp b/include/delaunator.hpp index b5ef4b9..9dfc3fe 100644 --- a/include/delaunator.hpp +++ b/include/delaunator.hpp
@@ -168,6 +168,8 @@ Delaunator(std::vector<double> const& in_coords); + double get_hull_area(); + private: std::vector<std::size_t> m_hash; std::vector<DelaunatorPoint> m_hull; @@ -401,6 +403,16 @@ } } +double Delaunator::get_hull_area() { + double hull_area = 0; + size_t e = m_hull_entry; + do { + hull_area += (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); + return 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; @@ -409,7 +421,7 @@ } std::size_t Delaunator::legalize(std::size_t a) { - std::size_t b = halfedges[a]; + const std::size_t b = halfedges[a]; /* if the pair of triangles doesn't satisfy the Delaunay condition * (p1 is inside the circumcircle of [p0, pl, pr]), flip them, @@ -426,17 +438,21 @@ * \||/ \ / * pr pr */ - std::size_t a0 = a - a % 3; - std::size_t b0 = b - b % 3; + const std::size_t a0 = a - a % 3; + const std::size_t b0 = b - b % 3; - std::size_t al = a0 + (a + 1) % 3; - std::size_t ar = a0 + (a + 2) % 3; - std::size_t bl = b0 + (b + 2) % 3; + const std::size_t al = a0 + (a + 1) % 3; + const std::size_t ar = a0 + (a + 2) % 3; + const std::size_t bl = b0 + (b + 2) % 3; - std::size_t p0 = triangles[ar]; - std::size_t pr = triangles[a]; - std::size_t pl = triangles[al]; - std::size_t p1 = triangles[bl]; + const std::size_t p0 = triangles[ar]; + const std::size_t pr = triangles[a]; + const std::size_t pl = triangles[al]; + const std::size_t p1 = triangles[bl]; + + // if (b == INVALID_INDEX) { + // return ar; + // } const bool illegal = in_circle( coords[2 * p0],
diff --git a/test/delaunator.test.cpp b/test/delaunator.test.cpp index 695a04d..3fdec00 100644 --- a/test/delaunator.test.cpp +++ b/test/delaunator.test.cpp
@@ -1,5 +1,6 @@ #include "../examples/utils.hpp" #include <catch.hpp> +#include <cmath> #include <delaunator.hpp> namespace { @@ -13,6 +14,22 @@ (i2 != delaunator::INVALID_INDEX) && (d.halfedges[i2] != i))); } } + + SECTION("validate triangulation") { + double hull_area = d.get_hull_area(); + double triangles_area = 0.0; + + for (size_t i = 0; i < d.triangles.size(); i += 3) { + const double ax = coords[2 * d.triangles[i]]; + const double ay = coords[2 * d.triangles[i] + 1]; + const double bx = coords[2 * d.triangles[i + 1]]; + const double by = coords[2 * d.triangles[i + 1] + 1]; + const double cx = coords[2 * d.triangles[i + 2]]; + const double cy = coords[2 * d.triangles[i + 2] + 1]; + triangles_area += std::fabs((by - ay) * (cx - bx) - (bx - ax) * (cy - by)); + } + REQUIRE(triangles_area == Approx(hull_area)); + } } } // namespace @@ -20,7 +37,7 @@ std::string points_str = utils::read_file("./test/test-files/playgrounds-1356-epsg-3857.geojson"); std::string triangles_str = utils::read_file("./test/test-files/playgrounds-1356-triangles.json"); std::vector<double> coords = utils::get_geo_json_points(points_str); - std::vector<double> triangles = utils::get_array_points(triangles_str); + std::vector<size_t> triangles = utils::get_array_points<size_t>(triangles_str); delaunator::Delaunator delaunator(coords); SECTION("length of triangles is the same") { @@ -29,7 +46,7 @@ SECTION("values are the same") { for (std::size_t i = 0; i < triangles.size(); i++) { - REQUIRE(delaunator.triangles[i] == Approx(triangles[i])); + REQUIRE(delaunator.triangles[i] == triangles[i]); } } } @@ -48,3 +65,8 @@ std::vector<double> coords = { 382, 302, 382, 328, 382, 205, 623, 175, 382, 188, 382, 284, 623, 87, 623, 341, 141, 227 }; validate(coords); } + +TEST_CASE("mapbox/delaunator/issues/13", "[Delaunator]") { + std::vector<double> coords = { 4, 1, 3.7974166882130675, 2.0837249985614585, 3.2170267516619773, 3.0210869309396715, 2.337215067329615, 3.685489874065187, 1.276805078389906, 3.9872025288851036, 0.17901102978375127, 3.885476929518457, -0.8079039091377689, 3.3940516818407187, -1.550651407188842, 2.5792964886320684, -1.9489192990517052, 1.5512485534497125, -1.9489192990517057, 0.44875144655029087, -1.5506514071888438, -0.5792964886320653, -0.8079039091377715, -1.394051681840717, 0.17901102978374794, -1.8854769295184561, 1.276805078389902, -1.987202528885104, 2.337215067329611, -1.6854898740651891, 3.217026751661974, -1.021086930939675, 3.7974166882130653, -0.08372499856146409 }; + validate(coords); +}