From 5fb9fb1a3cf939ad265a6f63ce901d312e0a2534 Mon Sep 17 00:00:00 2001 From: Asheem Mamoowala Date: Mon, 4 Dec 2017 16:30:17 -0800 Subject: [core] Support wrapped bounds in LatLngBounds::contains and LatLngBounds::intersect. --- include/mbgl/util/geo.hpp | 89 +++++++++++++++++++++++++++------ test/util/geo.test.cpp | 125 ++++++++++++++++++++++++++++++++++++++++++++-- 2 files changed, 196 insertions(+), 18 deletions(-) diff --git a/include/mbgl/util/geo.hpp b/include/mbgl/util/geo.hpp index 54a8c99fab..60043ee156 100644 --- a/include/mbgl/util/geo.hpp +++ b/include/mbgl/util/geo.hpp @@ -154,25 +154,84 @@ public: sw.longitude() > ne.longitude(); } - bool contains(const LatLng& point) const { - return (point.latitude() >= sw.latitude() && - point.latitude() <= ne.latitude() && - point.longitude() >= sw.longitude() && - point.longitude() <= ne.longitude()); + bool crossesAntimeridian() const { + return (sw.wrapped().longitude() > ne.wrapped().longitude()); } - bool contains(const LatLngBounds& area) const { - return (area.ne.latitude() <= ne.latitude() && - area.sw.latitude() >= sw.latitude() && - area.ne.longitude() <= ne.longitude() && - area.sw.longitude() >= sw.longitude()); + bool contains(const LatLng& point, LatLng::WrapMode wrap = LatLng::Unwrapped) const { + bool containsLatitude = point.latitude() >= sw.latitude() && + point.latitude() <= ne.latitude(); + if (!containsLatitude) { + return false; + } + + bool containsUnwrappedLongitude = point.longitude() >= sw.longitude() && + point.longitude() <= ne.longitude(); + if (containsUnwrappedLongitude) { + return true; + } else if (wrap == LatLng::Wrapped) { + LatLngBounds wrapped(sw.wrapped(), ne.wrapped()); + auto ptLon = point.wrapped().longitude(); + if (crossesAntimeridian()) { + return (ptLon >= wrapped.sw.longitude() && + ptLon <= util::LONGITUDE_MAX) || + (ptLon <= wrapped.ne.longitude() && + ptLon >= -util::LONGITUDE_MAX); + } else { + return (ptLon >= wrapped.sw.longitude() && + ptLon <= wrapped.ne.longitude()); + } + } + return false; } - bool intersects(const LatLngBounds area) const { - return (area.ne.latitude() > sw.latitude() && - area.sw.latitude() < ne.latitude() && - area.ne.longitude() > sw.longitude() && - area.sw.longitude() < ne.longitude()); + bool contains(const LatLngBounds& area, LatLng::WrapMode wrap = LatLng::Unwrapped) const { + bool containsLatitude = area.north() <= north() && area.south() >= south(); + if (!containsLatitude) { + return false; + } + + bool containsUnwrapped = area.east() <= east() && area.west() >= west(); + if(containsUnwrapped) { + return true; + } else if (wrap == LatLng::Wrapped) { + LatLngBounds wrapped(sw.wrapped(), ne.wrapped()); + LatLngBounds other(area.sw.wrapped(), area.ne.wrapped()); + if (crossesAntimeridian() & !area.crossesAntimeridian()) { + return (other.east() <= util::LONGITUDE_MAX && other.west() >= wrapped.west()) || + (other.east() <= wrapped.east() && other.west() >= -util::LONGITUDE_MAX); + } else { + return other.east() <= wrapped.east() && other.west() >= wrapped.west(); + } + } + return false; + } + + bool intersects(const LatLngBounds area, LatLng::WrapMode wrap = LatLng::Unwrapped) const { + bool latitudeIntersects = area.north() > south() && area.south() < north(); + if (!latitudeIntersects) { + return false; + } + + bool longitudeIntersects = area.east() > west() && area.west() < east(); + if (longitudeIntersects) { + return true; + } else if (wrap == LatLng::Wrapped) { + LatLngBounds wrapped(sw.wrapped(), ne.wrapped()); + LatLngBounds other(area.sw.wrapped(), area.ne.wrapped()); + if (crossesAntimeridian()) { + return area.crossesAntimeridian() || + other.east() > wrapped.west() || + other.west() < wrapped.east(); + } else if (other.crossesAntimeridian()){ + return other.east() > wrapped.west() || + other.west() < wrapped.east(); + } else { + return other.east() > wrapped.west() && + other.west() < wrapped.east(); + } + } + return false; } private: diff --git a/test/util/geo.test.cpp b/test/util/geo.test.cpp index 38f29d1dd4..6832ba3486 100644 --- a/test/util/geo.test.cpp +++ b/test/util/geo.test.cpp @@ -221,8 +221,127 @@ TEST(LatLngBounds, FromTileID) { } } -TEST(LatLngBounds, Contains) { - const LatLngBounds bounds( CanonicalTileID(4,2,6)); - const LatLngBounds innerBounds( CanonicalTileID(9,82,197)); +TEST(LatLngBounds, ContainsPoint) { + auto bounds = LatLngBounds::hull({50.0, -100.0},{-50.0, 100.0}); + + EXPECT_FALSE(bounds.contains(LatLng{0.0, 170.0})); + EXPECT_FALSE(bounds.contains(LatLng{0.0, -170.0})); + EXPECT_TRUE(bounds.contains(LatLng{0.0, -100.0})); + EXPECT_TRUE(bounds.contains(LatLng{-50.0, 100.0})); + EXPECT_FALSE(bounds.contains(LatLng{0.0, 365.0})); +} + +TEST(LatLngBounds, ContainsPoint_Wrapped) { + auto bounds = LatLngBounds::hull({50.0, -160.0}, {-50.0, 160.0}); + EXPECT_FALSE(bounds.contains(LatLng{0.0, 170.0})); + EXPECT_FALSE(bounds.contains(LatLng{0.0, -170.0})); + + bounds = LatLngBounds::hull({50.0, -200}, {-50.0, -160.0}); + EXPECT_FALSE(bounds.contains(LatLng{0.0, 170.0})); + EXPECT_TRUE(bounds.contains(LatLng{0.0, 170.0}, LatLng::Wrapped)); + EXPECT_TRUE(bounds.contains(LatLng{0.0, -170.0})); + EXPECT_TRUE(bounds.contains(LatLng{0.0, -170.0}, LatLng::Wrapped)); + EXPECT_FALSE(bounds.contains(LatLng{0.0, 190.0})); + EXPECT_TRUE(bounds.contains(LatLng{0.0, 190.0}, LatLng::Wrapped)); + EXPECT_FALSE(bounds.contains(LatLng{0.0, 541.0})); + EXPECT_TRUE(bounds.contains(LatLng{0.0, 541.0}, LatLng::Wrapped)); +} + +TEST(LatLngBounds, ContainsBounds) { + auto bounds = LatLngBounds::hull({ 50.0, -160.0 }, {-50.0, 160.0}); + EXPECT_TRUE(bounds.contains(bounds)); + + auto innerBounds = LatLngBounds::hull({10.0, -180.0}, {-10.0, -170.0}); + EXPECT_FALSE(bounds.contains(innerBounds)); + EXPECT_FALSE(innerBounds.contains(bounds)); + + innerBounds = LatLngBounds::hull({10, 120.0}, {-60, 125.0}); + EXPECT_FALSE(bounds.contains(innerBounds)); + EXPECT_FALSE(innerBounds.contains(bounds)); + + innerBounds = LatLngBounds::hull({10, 120.0}, {-10, 125.0}); + EXPECT_TRUE(bounds.contains(innerBounds)); + EXPECT_FALSE(innerBounds.contains(bounds)); + +} + +TEST(LatLngBounds, ContainsBounds_Wrapped) { + auto bounds = LatLngBounds::hull({50.0, -200}, {-50.0, -160.0}); + + auto inner = LatLngBounds::hull({10.0, -180.0}, {-10.0, -170.0}); + EXPECT_TRUE(bounds.contains(inner)); + EXPECT_TRUE(bounds.contains(inner, LatLng::Wrapped)); + + inner = LatLngBounds::hull({10.0, 180.0}, {-10.0, 190.0}); + EXPECT_FALSE(bounds.contains(inner)); + EXPECT_TRUE(bounds.contains(inner, LatLng::Wrapped)); + + inner = LatLngBounds::hull({10.0, 190.0}, {-10.0, 220.0}); + EXPECT_FALSE(bounds.contains(inner)); + EXPECT_FALSE(bounds.contains(inner, LatLng::Wrapped)); + + auto unwrapped = LatLngBounds::hull({10.0, 170.0}, { -10.0, -175.0}); + EXPECT_FALSE(bounds.contains(unwrapped)); + EXPECT_FALSE(bounds.contains(unwrapped, LatLng::Wrapped)); + + unwrapped = LatLngBounds::hull({10.0, 0.0} , {-10.0, -10.0}); + EXPECT_FALSE(bounds.contains(unwrapped)); + EXPECT_FALSE(bounds.contains(unwrapped, LatLng::Wrapped)); + + unwrapped = LatLngBounds::hull({10.0, -165.0}, {-10.0, -180.0}); + EXPECT_TRUE(bounds.contains(unwrapped)); + EXPECT_TRUE(bounds.contains(unwrapped, LatLng::Wrapped)); + + unwrapped = LatLngBounds::hull({10.0, 180.0}, {-10.0, 160.0}); + EXPECT_FALSE(bounds.contains(unwrapped)); + EXPECT_TRUE(bounds.contains(unwrapped, LatLng::Wrapped)); + + unwrapped = LatLngBounds::hull({10.0, 540.0}, {-10.0, 560.0}); + EXPECT_FALSE(bounds.contains(unwrapped)); + EXPECT_TRUE(bounds.contains(unwrapped, LatLng::Wrapped)); +} + +TEST(LatLngBounds, ContainsTileIDs) { + LatLngBounds bounds(CanonicalTileID(4,2,6)); + LatLngBounds innerBounds(CanonicalTileID(9,82,197)); EXPECT_TRUE(bounds.contains(innerBounds)); + EXPECT_FALSE(bounds.contains(LatLngBounds{ CanonicalTileID(3, 1, 0) })); +} + +TEST(LatLngBounds, Intersects) { + auto bounds = LatLngBounds::hull({ 50.0, -160.0 }, { -50.0, 160.0 }); + EXPECT_TRUE(bounds.intersects(bounds)); + + auto other = LatLngBounds::hull({50.0, -160.0}, {10, 160.0}); + EXPECT_TRUE(bounds.intersects(other)); + EXPECT_TRUE(other.intersects(bounds)); +} + +TEST(LatLngBounds, Intersects_Wrapped) { + auto bounds = LatLngBounds::hull({50.0, -200.0}, {-50.0, -160.0}); + EXPECT_TRUE(bounds.intersects(bounds)); + + auto other = LatLngBounds::hull({50.0, -150.0}, {10, 160.0}); + EXPECT_FALSE(bounds.intersects(other)); + EXPECT_FALSE(other.intersects(bounds)); + EXPECT_FALSE(bounds.intersects(other, LatLng::Wrapped)); + EXPECT_FALSE(other.intersects(bounds, LatLng::Wrapped)); + + other = LatLngBounds::hull({10.0, -150.0}, {-10.0, -210.0}); + EXPECT_TRUE(bounds.intersects(other)); + EXPECT_TRUE(bounds.intersects(other, LatLng::Wrapped)); + EXPECT_TRUE(other.intersects(bounds)); + EXPECT_TRUE(other.intersects(bounds, LatLng::Wrapped)); + + other = LatLngBounds::hull({10.0, 150.0}, {-10.0, 210.0}); + EXPECT_FALSE(bounds.intersects(other)); + EXPECT_FALSE(other.intersects(bounds)); + EXPECT_TRUE(bounds.intersects(other, LatLng::Wrapped)); + EXPECT_TRUE(other.intersects(bounds, LatLng::Wrapped)); + + other = LatLngBounds::hull({10.0, 195.0}, {-10.0, 300.0}); + EXPECT_FALSE(bounds.intersects(other)); + EXPECT_FALSE(other.intersects(bounds)); + EXPECT_TRUE(bounds.intersects(other, LatLng::Wrapped)); + EXPECT_TRUE(other.intersects(bounds, LatLng::Wrapped)); } -- cgit v1.2.1