[core] Support wrapped bounds in LatLngBounds::contains and LatLngBounds::intersect.

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));
 }