[core] Using TileCoordinates for geometry comparison

2 files changed, 32 insertions, 80 deletions

diff --git a/src/mbgl/util/geometry_within.cpp b/src/mbgl/util/geometry_within.cpp
index 4a0a5cce11..3c5e26c940 100644
--- a/src/mbgl/util/geometry_within.cpp
+++ b/src/mbgl/util/geometry_within.cpp
@@ -5,12 +5,14 @@
 namespace mbgl {
 
 namespace {
-bool rayIntersect(const Point<double>& p, const Point<double>& p1, const Point<double>& p2) {
+
+bool rayIntersect(const Point<int64_t>& p, const Point<int64_t>& p1, const Point<int64_t>& p2) {
     return ((p1.y > p.y) != (p2.y > p.y)) && (p.x < (p2.x - p1.x) * (p.y - p1.y) / (p2.y - p1.y) + p1.x);
 }
 
 // check if point p in on line segment with end points p1 and p2
-bool onBoundary(const Point<double>& p, const Point<double>& p1, const Point<double>& p2) {
+
+bool onBoundary(const Point<int64_t>& p, const Point<int64_t>& p1, const Point<int64_t>& p2) {
     // requirements of point p on line segment:
     // 1. colinear: cross product of vector p->p1(x1, y1) and vector p->p2(x2, y2) equals to 0
     // 2. p is between p1 and p2
@@ -22,20 +24,24 @@ bool onBoundary(const Point<double>& p, const Point<double>& p1, const Point<dou
 }
 
 // a, b are end points for line segment1, c and d are end points for line segment2
-bool lineIntersectLine(const Point<double>& a, const Point<double>& b, const Point<double>& c, const Point<double>& d) {
-    const auto perp = [](const Point<double>& v1, const Point<double>& v2) { return (v1.x * v2.y - v1.y * v2.x); };
+
+bool lineIntersectLine(const Point<int64_t>& a,
+                       const Point<int64_t>& b,
+                       const Point<int64_t>& c,
+                       const Point<int64_t>& d) {
+    const auto perp = [](const Point<int64_t>& v1, const Point<int64_t>& v2) { return (v1.x * v2.y - v1.y * v2.x); };
 
     // check if two segments are parallel or not
     // precondition is end point a, b is inside polygon, if line a->b is
     // parallel to polygon edge c->d, then a->b won't intersect with c->d
-    auto vectorP = Point<double>(b.x - a.x, b.y - a.y);
-    auto vectorQ = Point<double>(d.x - c.x, d.y - c.y);
+    auto vectorP = Point<int64_t>(b.x - a.x, b.y - a.y);
+    auto vectorQ = Point<int64_t>(d.x - c.x, d.y - c.y);
     if (perp(vectorQ, vectorP) == 0) return false;
 
     // check if p1 and p2 are in different sides of line segment q1->q2
     const auto twoSided =
-        [](const Point<double>& p1, const Point<double>& p2, const Point<double>& q1, const Point<double>& q2) {
-            double x1, y1, x2, y2, x3, y3;
+        [](const Point<int64_t>& p1, const Point<int64_t>& p2, const Point<int64_t>& q1, const Point<int64_t>& q2) {
+            int64_t x1, y1, x2, y2, x3, y3;
 
             // q1->p1 (x1, y1), q1->p2 (x2, y2), q1->q2 (x3, y3)
             x1 = p1.x - q1.x;
@@ -55,7 +61,7 @@ bool lineIntersectLine(const Point<double>& a, const Point<double>& b, const Poi
     return false;
 }
 
-bool lineIntersectPolygon(const Point<double>& p1, const Point<double>& p2, const Polygon<double>& polygon) {
+bool lineIntersectPolygon(const Point<int64_t>& p1, const Point<int64_t>& p2, const Polygon<int64_t>& polygon) {
     for (auto ring : polygon) {
         auto length = ring.size();
         // loop through every edge of the ring
@@ -68,21 +74,16 @@ bool lineIntersectPolygon(const Point<double>& p1, const Point<double>& p2, cons
     return false;
 }
 
-void updateBBox(WithinBBox& bbox, const Point<double>& p) {
+} // namespace
+
+void updateBBox(WithinBBox& bbox, const Point<int64_t>& p) {
     bbox[0] = std::min(p.x, bbox[0]);
     bbox[1] = std::min(p.y, bbox[1]);
     bbox[2] = std::max(p.x, bbox[2]);
     bbox[3] = std::max(p.y, bbox[3]);
 }
 
-bool isBBoxValid(const WithinBBox& bbox) {
-    return bbox != DefaultBBox;
-}
-
-} // namespace
-
 bool boxWithinBox(const WithinBBox& bbox1, const WithinBBox& bbox2) {
-    if (!isBBoxValid(bbox1) || !isBBoxValid(bbox2)) return false;
     if (bbox1[0] <= bbox2[0]) return false;
     if (bbox1[2] >= bbox2[2]) return false;
     if (bbox1[1] <= bbox2[1]) return false;
@@ -90,57 +91,8 @@ bool boxWithinBox(const WithinBBox& bbox1, const WithinBBox& bbox2) {
     return true;
 }
 
-WithinBBox calculateBBox(const Geometry<double>& geometries) {
-    WithinBBox result = DefaultBBox;
-
-    return geometries.match(
-        [&result](const Point<double>& point) {
-            updateBBox(result, point);
-            return result;
-        },
-        [&result](const MultiPoint<double>& points) {
-            for (const auto point : points) {
-                updateBBox(result, point);
-            }
-            return result;
-        },
-        [&result](const LineString<double>& line) {
-            for (const auto point : line) {
-                updateBBox(result, point);
-            }
-            return result;
-        },
-        [&result](const MultiLineString<double>& lines) {
-            for (const auto& line : lines) {
-                for (const auto point : line) {
-                    updateBBox(result, point);
-                }
-            }
-            return result;
-        },
-        [&result](const Polygon<double>& polygon) {
-            for (const auto& ring : polygon) {
-                for (const auto point : ring) {
-                    updateBBox(result, point);
-                }
-            }
-            return result;
-        },
-        [&result](const MultiPolygon<double>& polygons) {
-            for (const auto& polygon : polygons) {
-                for (const auto& ring : polygon) {
-                    for (const auto point : ring) {
-                        updateBBox(result, point);
-                    }
-                }
-            }
-            return result;
-        },
-        [](const auto&) { return DefaultBBox; });
-}
-
 // ray casting algorithm for detecting if point is in polygon
-bool pointWithinPolygon(const Point<double>& point, const Polygon<double>& polygon) {
+bool pointWithinPolygon(const Point<int64_t>& point, const Polygon<int64_t>& polygon) {
     bool within = false;
     for (const auto& ring : polygon) {
         const auto length = ring.size();
@@ -155,14 +107,14 @@ bool pointWithinPolygon(const Point<double>& point, const Polygon<double>& polyg
     return within;
 }
 
-bool pointWithinPolygons(const Point<double>& point, const MultiPolygon<double>& polygons) {
+bool pointWithinPolygons(const Point<int64_t>& point, const MultiPolygon<int64_t>& polygons) {
     for (const auto& polygon : polygons) {
         if (pointWithinPolygon(point, polygon)) return true;
     }
     return false;
 }
 
-bool lineStringWithinPolygon(const LineString<double>& line, const Polygon<double>& polygon) {
+bool lineStringWithinPolygon(const LineString<int64_t>& line, const Polygon<int64_t>& polygon) {
     const auto length = line.size();
     // First, check if geometry points of line segments are all inside polygon
     for (std::size_t i = 0; i < length; ++i) {
@@ -180,7 +132,7 @@ bool lineStringWithinPolygon(const LineString<double>& line, const Polygon<doubl
     return true;
 }
 
-bool lineStringWithinPolygons(const LineString<double>& line, const MultiPolygon<double>& polygons) {
+bool lineStringWithinPolygons(const LineString<int64_t>& line, const MultiPolygon<int64_t>& polygons) {
     for (const auto& polygon : polygons) {
         if (lineStringWithinPolygon(line, polygon)) return true;
     }
diff --git a/src/mbgl/util/geometry_within.hpp b/src/mbgl/util/geometry_within.hpp
index 56f755c7d7..b078783501 100644
--- a/src/mbgl/util/geometry_within.hpp
+++ b/src/mbgl/util/geometry_within.hpp
@@ -7,23 +7,23 @@
 namespace mbgl {
 
 // contains minX, minY, maxX, maxY
-using WithinBBox = std::array<double, 4>;
-const WithinBBox DefaultBBox = WithinBBox{std::numeric_limits<double>::infinity(),
-                                          std::numeric_limits<double>::infinity(),
-                                          -std::numeric_limits<double>::infinity(),
-                                          -std::numeric_limits<double>::infinity()};
+using WithinBBox = std::array<int64_t, 4>;
+const WithinBBox DefaultBBox = WithinBBox{std::numeric_limits<int64_t>::max(),
+                                          std::numeric_limits<int64_t>::max(),
+                                          std::numeric_limits<int64_t>::min(),
+                                          std::numeric_limits<int64_t>::min()};
 
 // check if bbox1 is within bbox2
 bool boxWithinBox(const WithinBBox& bbox1, const WithinBBox& bbox2);
 
-WithinBBox calculateBBox(const Geometry<double>& geometries);
+void updateBBox(WithinBBox& bbox, const Point<int64_t>& p);
 
-bool pointWithinPolygon(const Point<double>& point, const Polygon<double>& polygon);
+bool pointWithinPolygon(const Point<int64_t>& point, const Polygon<int64_t>& polygon);
 
-bool pointWithinPolygons(const Point<double>& point, const MultiPolygon<double>& polygons);
+bool pointWithinPolygons(const Point<int64_t>& point, const MultiPolygon<int64_t>& polygons);
 
-bool lineStringWithinPolygon(const LineString<double>& lineString, const Polygon<double>& polygon);
+bool lineStringWithinPolygon(const LineString<int64_t>& lineString, const Polygon<int64_t>& polygon);
 
-bool lineStringWithinPolygons(const LineString<double>& line, const MultiPolygon<double>& polygons);
+bool lineStringWithinPolygons(const LineString<int64_t>& line, const MultiPolygon<int64_t>& polygons);
 
 } // namespace mbgl