From 4344812ef5ef3b5b67e9f313e0c3cc87b3e95c46 Mon Sep 17 00:00:00 2001 From: Asheem Mamoowala Date: Thu, 26 Apr 2018 07:43:38 -0700 Subject: [core] Streaming TileCover for polygonal regions (#11267) A per-tile streaming algorithm for tile cover on points, lines, and polygons. Works for individual zoom levels, and not zoom ranges. --- test/util/tile_cover.test.cpp | 232 +++++++++++++++++++++++++++++++++++++++--- test/util/tile_range.test.cpp | 8 +- 2 files changed, 223 insertions(+), 17 deletions(-) (limited to 'test') diff --git a/test/util/tile_cover.test.cpp b/test/util/tile_cover.test.cpp index 933c18b5ea..7defa761af 100644 --- a/test/util/tile_cover.test.cpp +++ b/test/util/tile_cover.test.cpp @@ -2,6 +2,8 @@ #include #include +#include + #include using namespace mbgl; @@ -22,8 +24,8 @@ TEST(TileCover, Antarctic) { TEST(TileCover, WorldZ0) { EXPECT_EQ((std::vector{ - { 0, 0, 0 }, - }), + { 0, 0, 0 }, + }), util::tileCover(LatLngBounds::world(), 0)); } @@ -37,15 +39,15 @@ TEST(TileCover, Pitch) { transform.setPitch(40.0 * M_PI / 180.0); EXPECT_EQ((std::vector{ - { 2, 1, 2 }, { 2, 1, 1 }, { 2, 2, 2 }, { 2, 2, 1 }, { 2, 3, 2 } - }), + { 2, 1, 2 }, { 2, 1, 1 }, { 2, 2, 2 }, { 2, 2, 1 }, { 2, 3, 2 } + }), util::tileCover(transform.getState(), 2)); } TEST(TileCover, WorldZ1) { EXPECT_EQ((std::vector{ - { 1, 0, 0 }, { 1, 0, 1 }, { 1, 1, 0 }, { 1, 1, 1 }, - }), + { 1, 0, 0 }, { 1, 0, 1 }, { 1, 1, 0 }, { 1, 1, 1 }, + }), util::tileCover(LatLngBounds::world(), 1)); } @@ -59,21 +61,44 @@ TEST(TileCover, SingletonZ1) { util::tileCover(LatLngBounds::singleton({ 0, 0 }), 1)); } +TEST(TileCoverStream, Arctic) { + auto bounds = LatLngBounds::hull({ 84, -180 }, { 70, 180 }); + auto zoom = 3; + util::TileCover tc(bounds, zoom); + auto results = util::tileCover(bounds, zoom); + std::vector t; + while(tc.hasNext()) { + t.push_back(*tc.next()); + }; + EXPECT_EQ(t.size(), results.size()); +} + +TEST(TileCoverStream, WorldZ1) { + auto zoom = 1; + util::TileCover tc(LatLngBounds::world(), zoom); + std::vector t; + while(tc.hasNext()) { + t.push_back(*tc.next()); + }; + EXPECT_EQ((std::vector{ + { 1, 0, 0 }, { 1, 1, 0 }, { 1, 0, 1 }, { 1, 1, 1 }, + }), t); +} + static const LatLngBounds sanFrancisco = LatLngBounds::hull({ 37.6609, -122.5744 }, { 37.8271, -122.3204 }); TEST(TileCover, SanFranciscoZ0) { EXPECT_EQ((std::vector{ - { 0, 0, 0 }, - }), + { 0, 0, 0 }, + }), util::tileCover(sanFrancisco, 0)); } TEST(TileCover, SanFranciscoZ10) { EXPECT_EQ((std::vector{ - { 10, 163, 395 }, { 10, 163, 396 }, { 10, 164, 395 }, { 10, 164, 396 }, - - }), + { 10, 163, 395 }, { 10, 163, 396 }, { 10, 164, 395 }, { 10, 164, 396 }, + }), util::tileCover(sanFrancisco, 10)); } @@ -85,11 +110,192 @@ TEST(TileCover, SanFranciscoZ0Wrapped) { util::tileCover(sanFranciscoWrapped, 0)); } +TEST(TileCover, GeomPoint) { + auto point = Point{ -122.5744, 37.6609 }; + + EXPECT_EQ((std::vector{ {2 ,0 ,1 } }), + util::tileCover(point, 2)); +} + +TEST(TileCover, GeomMultiPoint) { + auto points = MultiPoint{ { -122.5, 37.76 }, { -122.4, 37.76} }; + + EXPECT_EQ((std::vector{ + {20, 167480, 405351}, {20, 167772, 405351} }), + util::tileCover(points, 20)); +} + +TEST(TileCover, GeomLineZ10) { + auto lineCover = util::tileCover(LineString{ + {-121.49368286132812,38.57903714667459}, + {-122.4422836303711,37.773157169570695} + }, 10); + EXPECT_EQ((std::vector{ + { 10, 166, 392}, {10, 165, 393}, {10, 166, 393}, + {10, 164, 394}, {10, 165, 394}, {10,163,395}, {10, 164, 395} + }),lineCover); + +} + +TEST(TileCover, WrappedGeomLineZ10) { + auto lineCover = util::tileCover(LineString{ + {-179.93342914581299,38.892101707724315}, + {-180.02394485473633,38.89203490311832} + }, 10); + EXPECT_EQ((std::vector{ { 10, -1, 391 }, { 10, 0, 391 } }), + lineCover); + + lineCover = util::tileCover(LineString{ + {179.93342914581299,38.892101707724315}, + {180.02394485473633,38.89203490311832} + }, 10); + EXPECT_EQ((std::vector{ { 10, 1023, 391 }, { 10, 1024, 391 } }), + lineCover); +} + +TEST(TileCover, GeomMultiLineString) { + auto geom = MultiLineString{ + { { -122.5, 37.76 }, { -122.4, 37.76} }, + { { -122.5, 37.72 }, { -122.4, 37.72} } }; + + EXPECT_EQ((std::vector{ + {14, 2616, 6333}, {14, 2617, 6333}, {14, 2618, 6333}, + {14, 2619, 6333}, {14, 2620, 6333}, {14, 2621, 6333}, + {14, 2616, 6335}, {14, 2617, 6335}, {14, 2618, 6335}, + {14, 2619, 6335}, {14, 2620, 6335}, {14, 2621, 6335}}), + util::tileCover(geom, 14)); +} + +TEST(TileCover, GeomPolygon) { + auto polygon = Polygon{ + { + {5.09765625,53.067626642387374}, + {2.373046875,43.389081939117496}, + {-4.74609375,48.45835188280866}, + {-1.494140625,37.09023980307208}, + {22.587890625,36.24427318493909}, + {31.640625,46.13417004624326}, + {17.841796875,54.7246201949245}, + {5.09765625,53.067626642387374}, + },{ + {19.6875,49.66762782262194}, + {22.8515625,43.51668853502906}, + {13.623046875,45.089035564831036}, + {16.34765625,39.095962936305476}, + {5.185546875,41.244772343082076}, + {8.701171874999998,50.233151832472245}, + {19.6875,49.66762782262194} + } + }; + + auto results = util::tileCover(polygon, 8); + + EXPECT_NE(std::find(results.begin(), results.end(), UnwrappedTileID{8, 134, 87}), results.end()); + EXPECT_NE(std::find(results.begin(), results.end(), UnwrappedTileID{8, 139, 87}), results.end()); + // Should have a hole + EXPECT_EQ(std::find(results.begin(), results.end(), UnwrappedTileID{8, 136, 87}), results.end()); +} + +TEST(TileCover, GeomMultiPolygon) { + auto multiPolygon = MultiPolygon{ + {{ + {5.09765625,53.067626642387374}, + {2.373046875,43.389081939117496}, + {-4.74609375,48.45835188280866}, + {-1.494140625,37.09023980307208}, + {22.587890625,36.24427318493909}, + {31.640625,46.13417004624326}, + {17.841796875,54.7246201949245}, + {5.09765625,53.067626642387374}, + }},{{ + {59.150390625,45.460130637921004}, + {65.126953125,41.11246878918088}, + {69.169921875,47.45780853075031}, + {63.896484375,50.064191736659104}, + {59.150390625,45.460130637921004} + }} + }; + auto results = util::tileCover(multiPolygon, 8); + + EXPECT_EQ(424u, results.size()); + EXPECT_NE(std::find(results.begin(), results.end(), UnwrappedTileID{8, 139, 87}), results.end()); + EXPECT_NE(std::find(results.begin(), results.end(), UnwrappedTileID{8, 136, 87}), results.end()); + EXPECT_NE(std::find(results.begin(), results.end(), UnwrappedTileID{8, 174, 94}), results.end()); +} + +TEST(TileCover, GeomSanFranciscoPoly) { + auto sanFranciscoGeom = Polygon{ + { + {-122.5143814086914,37.779127216982424}, + {-122.50811576843262,37.72721239056709}, + {-122.50313758850099,37.70820178063929}, + {-122.3938751220703,37.707454835665274}, + {-122.37567901611328,37.70663997801684}, + {-122.36297607421874,37.71343018466285}, + {-122.354736328125,37.727280276860036}, + {-122.36469268798828,37.73868429065797}, + {-122.38014221191408,37.75442980295571}, + {-122.38391876220702,37.78753873820529}, + {-122.35919952392578,37.8065289741725}, + {-122.35679626464844,37.820632846207864}, + {-122.3712158203125,37.835276322922695}, + {-122.3818588256836,37.82958198283902}, + {-122.37190246582031,37.80788523279169}, + {-122.38735198974608,37.791337175930686}, + {-122.40966796874999,37.812767557570204}, + {-122.46425628662108,37.807071480609274}, + {-122.46803283691405,37.810326435534755}, + {-122.47901916503906,37.81168262440736}, + {-122.48966217041016,37.78916666399649}, + {-122.50579833984375,37.78781006166096}, + {-122.5143814086914,37.779127216982424} + } + }; + + EXPECT_EQ((std::vector{ + { 12, 654, 1582 }, { 12, 655, 1582 }, + { 12, 654, 1583 }, { 12, 655, 1583 }, + { 12, 654, 1584 }, { 12, 655, 1584 } + }), util::tileCover(sanFranciscoGeom, 12)); +} + +TEST(TileCover, GeomInvalid) { + auto point = Point{ -122.5744, 97.6609 }; + EXPECT_THROW(util::tileCover(point, 2), std::domain_error); + + auto badPoly = Polygon { { {1.0, 35.0} } }; + EXPECT_EQ((std::vector{ }), util::tileCover(badPoly, 16)); + + //Should handle open polygons. + badPoly = Polygon { { {1.0, 34.2}, {1.0, 34.4}, {0.5, 34.3} } }; + EXPECT_EQ((std::vector{ + { 10, 513, 407 }, { 10, 514, 407}, + { 10, 513, 408 }, { 10, 514, 408} + }), util::tileCover(badPoly, 10)); +} + + +TEST(TileCount, World) { + EXPECT_EQ(1u, util::tileCount(LatLngBounds::world(), 0)); + EXPECT_EQ(4u, util::tileCount(LatLngBounds::world(), 1)); +} + TEST(TileCount, SanFranciscoZ10) { - EXPECT_EQ(4u, util::tileCount(sanFrancisco, 10, util::tileSize)); + EXPECT_EQ(4u, util::tileCount(sanFrancisco, 10)); +} + +TEST(TileCount, SanFranciscoWrappedZ10) { + EXPECT_EQ(4u, util::tileCount(sanFranciscoWrapped, 10)); } TEST(TileCount, SanFranciscoZ22) { - EXPECT_EQ(7254450u, util::tileCount(sanFrancisco, 22, util::tileSize)); + EXPECT_EQ(7254450u, util::tileCount(sanFrancisco, 22)); } +TEST(TileCount, BoundsCrossingAntimeridian) { + auto crossingBounds = LatLngBounds::hull({-20.9615, -214.309}, {19.477, -155.830}); + + EXPECT_EQ(1u, util::tileCount(crossingBounds, 0)); + EXPECT_EQ(4u, util::tileCount(crossingBounds, 3)); + EXPECT_EQ(8u, util::tileCount(crossingBounds, 4)); +} diff --git a/test/util/tile_range.test.cpp b/test/util/tile_range.test.cpp index c4c37c74d7..83ac5096a5 100644 --- a/test/util/tile_range.test.cpp +++ b/test/util/tile_range.test.cpp @@ -52,14 +52,14 @@ TEST(TileRange, ContainsWrappedBounds) { TEST(TileRange, ContainsBoundsCrossingAntimeridian) { { - auto cossingBounds = LatLngBounds::hull({-20.9615, -214.309}, {19.477, -155.830}); - auto range = util::TileRange::fromLatLngBounds(cossingBounds, 1); + auto crossingBounds = LatLngBounds::hull({-20.9615, -214.309}, {19.477, -155.830}); + auto range = util::TileRange::fromLatLngBounds(crossingBounds, 1); EXPECT_TRUE(range.contains(CanonicalTileID(1, 1, 1))); EXPECT_TRUE(range.contains(CanonicalTileID(1, 0, 0))); } { - auto cossingBounds = LatLngBounds::hull({-20.9615, -214.309}, {19.477, -155.830}); - auto range = util::TileRange::fromLatLngBounds(cossingBounds, 6); + auto crossingBounds = LatLngBounds::hull({-20.9615, -214.309}, {19.477, -155.830}); + auto range = util::TileRange::fromLatLngBounds(crossingBounds, 6); EXPECT_FALSE(range.contains(CanonicalTileID(6, 55, 34))); EXPECT_FALSE(range.contains(CanonicalTileID(6, 5, 28))); EXPECT_TRUE(range.contains(CanonicalTileID(6, 63, 28))); -- cgit v1.2.1