summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDane Springmeyer <dane@mapbox.com>2017-01-06 17:51:35 -0800
committerThiago Marcos P. Santos <thiago@mapbox.com>2017-03-15 15:42:42 +0200
commit60320d74ba577185d1d90a7f234e182ca06d7d76 (patch)
treeea69a19b9f1044cf911823fd5090652391867b25
parentedd127ee7658ceb7f5f2f740bce75db1cbf25c0e (diff)
downloadqtlocation-mapboxgl-60320d74ba577185d1d90a7f234e182ca06d7d76.tar.gz
compare polygon ring areas absolutelyqt-v1.0.1
- This ensures we actually keep the largest polygons - Adds testcase that fails without this patch
-rw-r--r--src/mbgl/tile/geometry_tile_data.cpp2
-rw-r--r--test/tile/geometry_tile_data.test.cpp46
2 files changed, 47 insertions, 1 deletions
diff --git a/src/mbgl/tile/geometry_tile_data.cpp b/src/mbgl/tile/geometry_tile_data.cpp
index f891e5aa04..ccc91b027a 100644
--- a/src/mbgl/tile/geometry_tile_data.cpp
+++ b/src/mbgl/tile/geometry_tile_data.cpp
@@ -127,7 +127,7 @@ void limitHoles(GeometryCollection& polygon, uint32_t maxHoles) {
polygon.begin() + 1 + maxHoles,
polygon.end(),
[] (const auto& a, const auto& b) {
- return signedArea(a) > signedArea(b);
+ return std::fabs(signedArea(a)) > std::fabs(signedArea(b));
});
polygon.resize(1 + maxHoles);
}
diff --git a/test/tile/geometry_tile_data.test.cpp b/test/tile/geometry_tile_data.test.cpp
index 6e118d6fd5..f7fe5816ea 100644
--- a/test/tile/geometry_tile_data.test.cpp
+++ b/test/tile/geometry_tile_data.test.cpp
@@ -3,6 +3,18 @@
using namespace mbgl;
+static double _signedArea(const GeometryCoordinates& ring) {
+ double sum = 0;
+
+ for (std::size_t i = 0, len = ring.size(), j = len - 1; i < len; j = i++) {
+ const GeometryCoordinate& p1 = ring[i];
+ const GeometryCoordinate& p2 = ring[j];
+ sum += (p2.x - p1.x) * (p1.y + p2.y);
+ }
+
+ return sum;
+}
+
TEST(GeometryTileData, classifyRings1) {
std::vector<GeometryCollection> polygons = classifyRings({
{ {0, 0}, {0, 40}, {40, 40}, {40, 0}, {0, 0} }
@@ -59,3 +71,37 @@ TEST(GeometryTileData, limitHoles2) {
ASSERT_EQ(polygon[0][0].x, 0);
ASSERT_EQ(polygon[1][0].x, 10);
}
+
+TEST(GeometryTileData, limitHoles3) {
+ // real world polygon with interior rings with negative areas
+ // that need to be sorted in `limitHoles` by comparing absolute
+ // area not signed
+ GeometryCollection polygon = {
+ { {7336,-248},{7304,-248},{7272,-168},{7176,-200},{7080,-136},{7048,-56},{7128,-8},{7176,-56},{7288,-56},{7316,0},{6918,0},{6904,-40},{6984,-72},{6952,-88},{6952,-168},{6888,-88},{6856,-88},{6856,-8},{6872,0},{6170,0},{6184,-40},{6136,-72},{6104,-56},{6132,0},{6028,0},{6104,-152},{6184,-200},{6206,-256},{6272,-256},{6264,-248},{6248,-120},{6280,-136},{6280,-232},{6288,-256},{6790,-256},{6792,-248},{6800,-256},{7058,-256},{7064,-248},{7096,-256},{7338,-256},{7336,-248} },
+ { {6344,-104},{6264,-8},{6392,-72},{6360,-200},{6344,-104} },
+ { {6744,-24},{6760,-72},{6728,-104},{6744,-24} },
+ { {6616,-104},{6648,-88},{6632,-72},{6664,-56},{6664,-120},{6616,-104} }
+ };
+
+ // make a copy for later testing
+ GeometryCollection original(polygon);
+
+ ASSERT_EQ(polygon.size(), 4u);
+ ASSERT_EQ(_signedArea(polygon.at(0)), 515360); // exterior
+ ASSERT_EQ(_signedArea(polygon.at(1)), -12288); // biggest interior ring
+ ASSERT_EQ(_signedArea(polygon.at(2)), -2048); // smallest interior ring
+ ASSERT_EQ(_signedArea(polygon.at(3)), -3072); // second largest interior ring
+
+ limitHoles(polygon, 2);
+
+ // output: polygon 1 has 1 exterior, 2 interior
+ ASSERT_EQ(polygon.size(), 3u);
+
+ // ensure we've kept the exterior ring
+ ASSERT_EQ(original.at(0), polygon.at(0));
+
+ // ensure we've kept the two largest interior rings
+ ASSERT_EQ(original.at(1), polygon.at(1));
+ ASSERT_EQ(original.at(3), polygon.at(2));
+
+}