[core] Distance expression: Change template class into template function in geometry_util, add range assertion for distance contaniner IndexRange

Change distance units to small letters, update tests accordingly

2 files changed, 92 insertions, 29 deletions

diff --git a/src/mbgl/util/geometry_util.cpp b/src/mbgl/util/geometry_util.cpp
index df4119ce6a..4a90c75582 100644
--- a/src/mbgl/util/geometry_util.cpp
+++ b/src/mbgl/util/geometry_util.cpp
@@ -5,13 +5,31 @@
 namespace mbgl {
 
 template <typename T>
-bool GeometryUtil<T>::rayIntersect(const Point<T>& p, const Point<T>& p1, const Point<T>& p2) {
+void updateBBox(GeometryBBox<T>& bbox, const Point<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]);
+}
+
+// check if bbox1 is within bbox2
+template <typename T>
+bool boxWithinBox(const GeometryBBox<T>& bbox1, const GeometryBBox<T>& bbox2) {
+    if (bbox1[0] <= bbox2[0]) return false;
+    if (bbox1[2] >= bbox2[2]) return false;
+    if (bbox1[1] <= bbox2[1]) return false;
+    if (bbox1[3] >= bbox2[3]) return false;
+    return true;
+}
+
+template <typename T>
+bool rayIntersect(const Point<T>& p, const Point<T>& p1, const Point<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 is on line segment with end points p1 and p2
 template <typename T>
-bool GeometryUtil<T>::pointOnBoundary(const Point<T>& p, const Point<T>& p1, const Point<T>& p2) {
+bool pointOnBoundary(const Point<T>& p, const Point<T>& p1, const Point<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
@@ -23,10 +41,7 @@ bool GeometryUtil<T>::pointOnBoundary(const Point<T>& p, const Point<T>& p1, con
 }
 
 template <typename T>
-bool GeometryUtil<T>::segmentIntersectSegment(const Point<T>& a,
-                                              const Point<T>& b,
-                                              const Point<T>& c,
-                                              const Point<T>& d) {
+bool segmentIntersectSegment(const Point<T>& a, const Point<T>& b, const Point<T>& c, const Point<T>& d) {
     // a, b are end points for line segment1, c and d are end points for line segment2
     const auto perp = [](const Point<T>& v1, const Point<T>& v2) { return (v1.x * v2.y - v1.y * v2.x); };
 
@@ -58,7 +73,7 @@ bool GeometryUtil<T>::segmentIntersectSegment(const Point<T>& a,
 }
 
 template <typename T>
-bool GeometryUtil<T>::lineIntersectPolygon(const Point<T>& p1, const Point<T>& p2, const Polygon<T>& polygon) {
+bool lineIntersectPolygon(const Point<T>& p1, const Point<T>& p2, const Polygon<T>& polygon) {
     for (auto ring : polygon) {
         auto length = ring.size();
         // loop through every edge of the ring
@@ -73,7 +88,7 @@ bool GeometryUtil<T>::lineIntersectPolygon(const Point<T>& p1, const Point<T>& p
 
 // ray casting algorithm for detecting if point is in polygon
 template <typename T>
-bool GeometryUtil<T>::pointWithinPolygon(const Point<T>& point, const Polygon<T>& polygon, bool trueOnBoundary) {
+bool pointWithinPolygon(const Point<T>& point, const Polygon<T>& polygon, bool trueOnBoundary) {
     bool within = false;
     for (const auto& ring : polygon) {
         const auto length = ring.size();
@@ -89,7 +104,7 @@ bool GeometryUtil<T>::pointWithinPolygon(const Point<T>& point, const Polygon<T>
 }
 
 template <typename T>
-bool GeometryUtil<T>::pointWithinPolygons(const Point<T>& point, const MultiPolygon<T>& polygons, bool trueOnBoundary) {
+bool pointWithinPolygons(const Point<T>& point, const MultiPolygon<T>& polygons, bool trueOnBoundary) {
     for (const auto& polygon : polygons) {
         if (pointWithinPolygon(point, polygon, trueOnBoundary)) return true;
     }
@@ -97,7 +112,7 @@ bool GeometryUtil<T>::pointWithinPolygons(const Point<T>& point, const MultiPoly
 }
 
 template <typename T>
-bool GeometryUtil<T>::lineStringWithinPolygon(const LineString<T>& line, const Polygon<T>& polygon) {
+bool lineStringWithinPolygon(const LineString<T>& line, const Polygon<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) {
@@ -116,14 +131,35 @@ bool GeometryUtil<T>::lineStringWithinPolygon(const LineString<T>& line, const P
 }
 
 template <typename T>
-bool GeometryUtil<T>::lineStringWithinPolygons(const LineString<T>& line, const MultiPolygon<T>& polygons) {
+bool lineStringWithinPolygons(const LineString<T>& line, const MultiPolygon<T>& polygons) {
     for (const auto& polygon : polygons) {
         if (lineStringWithinPolygon(line, polygon)) return true;
     }
     return false;
 }
 
-template struct GeometryUtil<double>;
-template struct GeometryUtil<int64_t>;
+template void updateBBox(GeometryBBox<int64_t>& bbox, const Point<int64_t>& p);
+template bool boxWithinBox(const GeometryBBox<int64_t>& bbox1, const GeometryBBox<int64_t>& bbox2);
+template bool segmentIntersectSegment(const Point<int64_t>& a,
+                                      const Point<int64_t>& b,
+                                      const Point<int64_t>& c,
+                                      const Point<int64_t>& d);
+template bool rayIntersect(const Point<int64_t>& p, const Point<int64_t>& p1, const Point<int64_t>& p2);
+template bool pointOnBoundary(const Point<int64_t>& p, const Point<int64_t>& p1, const Point<int64_t>& p2);
+template bool lineIntersectPolygon(const Point<int64_t>& p1, const Point<int64_t>& p2, const Polygon<int64_t>& polygon);
+template bool pointWithinPolygon(const Point<int64_t>& point,
+                                 const Polygon<int64_t>& polygon,
+                                 bool trueOnBoundary = false);
+template bool pointWithinPolygons(const Point<int64_t>& point,
+                                  const MultiPolygon<int64_t>& polygons,
+                                  bool trueOnBoundary = false);
+template bool lineStringWithinPolygon(const LineString<int64_t>& line, const Polygon<int64_t>& polygon);
+template bool lineStringWithinPolygons(const LineString<int64_t>& line, const MultiPolygon<int64_t>& polygons);
+
+template void updateBBox(GeometryBBox<double>& bbox, const Point<double>& p);
+template bool segmentIntersectSegment(const Point<double>& a,
+                                      const Point<double>& b,
+                                      const Point<double>& c,
+                                      const Point<double>& d);
 
 } // namespace mbgl
diff --git a/src/mbgl/util/geometry_util.hpp b/src/mbgl/util/geometry_util.hpp
index ccf7bfc504..3bdef9f357 100644
--- a/src/mbgl/util/geometry_util.hpp
+++ b/src/mbgl/util/geometry_util.hpp
@@ -1,25 +1,52 @@
 #pragma once
 
+#include <array>
 #include <mbgl/util/geometry.hpp>
 
 namespace mbgl {
 
+// contains minX, minY, maxX, maxY
 template <typename T>
-struct GeometryUtil {
-    using type = T;
-    static bool segmentIntersectSegment(const Point<type>& a,
-                                        const Point<type>& b,
-                                        const Point<type>& c,
-                                        const Point<type>& d);
-    static bool rayIntersect(const Point<type>& p, const Point<type>& p1, const Point<type>& p2);
-    static bool pointOnBoundary(const Point<type>& p, const Point<type>& p1, const Point<type>& p2);
-    static bool lineIntersectPolygon(const Point<type>& p1, const Point<type>& p2, const Polygon<type>& polygon);
-    static bool pointWithinPolygon(const Point<type>& point, const Polygon<type>& polygon, bool trueOnBoundary = false);
-    static bool pointWithinPolygons(const Point<type>& point,
-                                    const MultiPolygon<type>& polygons,
-                                    bool trueOnBoundary = false);
-    static bool lineStringWithinPolygon(const LineString<type>& line, const Polygon<type>& polygon);
-    static bool lineStringWithinPolygons(const LineString<type>& line, const MultiPolygon<type>& polygons);
-};
+using GeometryBBox = std::array<T, 4>;
+const GeometryBBox<int64_t> DefaultWithinBBox = std::array<int64_t, 4>{std::numeric_limits<int64_t>::max(),
+                                                                       std::numeric_limits<int64_t>::max(),
+                                                                       std::numeric_limits<int64_t>::min(),
+                                                                       std::numeric_limits<int64_t>::min()};
+
+const GeometryBBox<double> DefaultDistanceBBox = std::array<double, 4>{std::numeric_limits<double>::infinity(),
+                                                                       std::numeric_limits<double>::infinity(),
+                                                                       -std::numeric_limits<double>::infinity(),
+                                                                       -std::numeric_limits<double>::infinity()};
+
+template <typename T>
+void updateBBox(GeometryBBox<T>& bbox, const Point<T>& p);
+
+// check if bbox1 is within bbox2
+template <typename T>
+bool boxWithinBox(const GeometryBBox<T>& bbox1, const GeometryBBox<T>& bbox2);
+
+template <typename T>
+bool segmentIntersectSegment(const Point<T>& a, const Point<T>& b, const Point<T>& c, const Point<T>& d);
+
+template <typename T>
+bool rayIntersect(const Point<T>& p, const Point<T>& p1, const Point<T>& p2);
+
+template <typename T>
+bool pointOnBoundary(const Point<T>& p, const Point<T>& p1, const Point<T>& p2);
+
+template <typename T>
+bool lineIntersectPolygon(const Point<T>& p1, const Point<T>& p2, const Polygon<T>& polygon);
+
+template <typename T>
+bool pointWithinPolygon(const Point<T>& point, const Polygon<T>& polygon, bool trueOnBoundary = false);
+
+template <typename T>
+bool pointWithinPolygons(const Point<T>& point, const MultiPolygon<T>& polygons, bool trueOnBoundary = false);
+
+template <typename T>
+bool lineStringWithinPolygon(const LineString<T>& line, const Polygon<T>& polygon);
+
+template <typename T>
+bool lineStringWithinPolygons(const LineString<T>& line, const MultiPolygon<T>& polygons);
 
 } // namespace mbgl