From b4b27627d6da053574485ca2b80b395d37ebaffd Mon Sep 17 00:00:00 2001 From: zmiao Date: Mon, 20 Apr 2020 16:03:06 +0300 Subject: [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 --- src/mbgl/geometry/feature_index.cpp | 6 +- src/mbgl/style/expression/distance.cpp | 104 ++++++++++++++++----------------- src/mbgl/style/expression/within.cpp | 36 +++--------- src/mbgl/util/geometry_util.cpp | 62 +++++++++++++++----- src/mbgl/util/geometry_util.hpp | 59 ++++++++++++++----- 5 files changed, 153 insertions(+), 114 deletions(-) (limited to 'src') diff --git a/src/mbgl/geometry/feature_index.cpp b/src/mbgl/geometry/feature_index.cpp index 85a116bc2f..afe8bb0f23 100644 --- a/src/mbgl/geometry/feature_index.cpp +++ b/src/mbgl/geometry/feature_index.cpp @@ -8,7 +8,7 @@ #include #include #include -#include +#include #include #include @@ -216,7 +216,7 @@ void DynamicFeatureIndex::query(std::unordered_map queryBox = DefaultWithinBBox; for (const auto& p : queryGeometry) { const LatLng c = screenCoordinateToLatLng(p, state); const Point pm = project(c, state); @@ -225,7 +225,7 @@ void DynamicFeatureIndex::query(std::unordered_map featureBox = DefaultWithinBBox; for (const auto& p : f.envelope->front()) mbgl::updateBBox(featureBox, p); const bool hit = mbgl::boxWithinBox(featureBox, queryBox) || mbgl::boxWithinBox(queryBox, featureBox); diff --git a/src/mbgl/style/expression/distance.cpp b/src/mbgl/style/expression/distance.cpp index c4d0c7b56d..d42cfa39ea 100644 --- a/src/mbgl/style/expression/distance.cpp +++ b/src/mbgl/style/expression/distance.cpp @@ -24,20 +24,6 @@ namespace { const std::size_t MinPointsSize = 100; const std::size_t MinLinePointsSize = 50; -using BBox = std::array; -const BBox DefaultBBox = BBox{std::numeric_limits::infinity(), - std::numeric_limits::infinity(), - -std::numeric_limits::infinity(), - -std::numeric_limits::infinity()}; - -// bbox[minX, minY, maxX, maxY] -void updateBBox(BBox& bbox, const mapbox::geometry::point& 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]); -} - // Inclusive index range for multipoint or linestring container using IndexRange = std::pair; @@ -45,16 +31,20 @@ std::size_t getRangeSize(const IndexRange& range) { return range.second - range.first + 1; } -BBox getBBox(const mapbox::geometry::multi_point& points, const IndexRange& range) { - BBox bbox = DefaultBBox; +using DistanceBBox = GeometryBBox; + +DistanceBBox getBBox(const mapbox::geometry::multi_point& points, const IndexRange& range) { + assert(range.second >= range.first && range.second < points.size()); + DistanceBBox bbox = DefaultDistanceBBox; for (std::size_t i = range.first; i <= range.second; ++i) { updateBBox(bbox, points[i]); } return bbox; } -BBox getBBox(const mapbox::geometry::line_string& line, const IndexRange& range) { - BBox bbox = DefaultBBox; +DistanceBBox getBBox(const mapbox::geometry::line_string& line, const IndexRange& range) { + assert(range.second >= range.first && range.second < line.size()); + DistanceBBox bbox = DefaultDistanceBBox; for (std::size_t i = range.first; i <= range.second; ++i) { updateBBox(bbox, line[i]); } @@ -62,11 +52,13 @@ BBox getBBox(const mapbox::geometry::line_string& line, const IndexRange } // Calculate the distance between two bounding boxes. -// Calculate the delta in x and y direction, and use two fake points {0, 0} and {dx, dy} to calculate the distance. -// Distance will be 0 if bounding box are overlapping. -double bboxToBBoxDistance(const BBox& bbox1, const BBox& bbox2, mapbox::cheap_ruler::CheapRuler& ruler) { - double dx = 0.; - double dy = 0.; +// Calculate the delta in x and y direction, and use two fake points {0.0, 0.0} and {dx, dy} to calculate the distance. +// Distance will be 0.0 if bounding box are overlapping. +double bboxToBBoxDistance(const DistanceBBox& bbox1, + const DistanceBBox& bbox2, + mapbox::cheap_ruler::CheapRuler& ruler) { + double dx = 0.0; + double dy = 0.0; // bbox1 in left side if (bbox1[2] < bbox2[0]) { dx = bbox2[0] - bbox1[2]; @@ -83,7 +75,7 @@ double bboxToBBoxDistance(const BBox& bbox1, const BBox& bbox2, mapbox::cheap_ru if (bbox1[3] < bbox2[1]) { dy = bbox2[1] - bbox1[3]; } - return ruler.distance(mapbox::geometry::point{0., 0.}, mapbox::geometry::point{dx, dy}); + return ruler.distance(mapbox::geometry::point{0.0, 0.0}, mapbox::geometry::point{dx, dy}); } double pointToLineDistance(const mapbox::geometry::point& point, @@ -98,6 +90,8 @@ double lineToLineDistance(const mapbox::geometry::line_string& line1, const mapbox::geometry::line_string& line2, IndexRange& range2, mapbox::cheap_ruler::CheapRuler& ruler) { + assert(range1.second >= range1.first && range1.second < line1.size()); + assert(range2.second >= range2.first && range2.second < line2.size()); double dist = std::numeric_limits::infinity(); for (std::size_t i = range1.first; i < range1.second; ++i) { const auto& p1 = line1[i]; @@ -105,7 +99,7 @@ double lineToLineDistance(const mapbox::geometry::line_string& line1, for (std::size_t j = range2.first; j < range2.second; ++j) { const auto& q1 = line2[j]; const auto& q2 = line2[j + 1]; - if (GeometryUtil::segmentIntersectSegment(p1, p2, q1, q2)) return 0.; + if (segmentIntersectSegment(p1, p2, q1, q2)) return 0.0; auto dist1 = std::min(pointToLineDistance(p1, mapbox::geometry::line_string{q1, q2}, ruler), pointToLineDistance(p2, mapbox::geometry::line_string{q1, q2}, ruler)); auto dist2 = std::min(pointToLineDistance(q1, mapbox::geometry::line_string{p1, p2}, ruler), @@ -121,11 +115,13 @@ double pointsToPointsDistance(const mapbox::geometry::multi_point& point const mapbox::geometry::multi_point& points2, IndexRange& range2, mapbox::cheap_ruler::CheapRuler& ruler) { + assert(range1.second >= range1.first && range1.second < points1.size()); + assert(range2.second >= range2.first && range2.second < points2.size()); double dist = std::numeric_limits::infinity(); for (std::size_t i = range1.first; i <= range1.second; ++i) { for (std::size_t j = range2.first; j <= range2.second; ++j) { dist = std::min(dist, ruler.distance(points1[i], points2[j])); - if (dist == 0.) return dist; + if (dist == 0.0) return dist; } } return dist; @@ -154,8 +150,7 @@ std::pair, mbgl::optional> splitRange(con // using DistPair = std::tuple; -class Comparator { -public: +struct Comparator { bool operator()(DistPair& left, DistPair& right) { return std::get<0>(left) < std::get<0>(right); } }; // The priority queue will ensure the top element would always be the pair that has the biggest distance @@ -180,7 +175,7 @@ double lineToLineDistance(const mapbox::geometry::line_string& line1, // In case the set size are relatively small, we could use brute-force directly if (getRangeSize(rangeA) <= MinLinePointsSize && getRangeSize(rangeB) <= MinLinePointsSize) { miniDist = std::min(miniDist, lineToLineDistance(line1, rangeA, line2, rangeB, ruler)); - if (miniDist == 0.) return 0.; + if (miniDist == 0.0) return 0.0; } else { auto newRangesA = splitRange(rangeA, true /*isLine*/); auto newRangesB = splitRange(rangeB, true /*isLine*/); @@ -223,7 +218,7 @@ double pointsToPointsDistance(const mapbox::geometry::multi_point& point // In case the set size are relatively small, we could use brute-force directly if (getRangeSize(rangeA) <= MinPointsSize && getRangeSize(rangeB) <= MinPointsSize) { miniDist = std::min(miniDist, pointsToPointsDistance(pointSet1, rangeA, pointSet2, rangeB, ruler)); - if (miniDist == 0.) return 0.; + if (miniDist == 0.0) return 0.0; } else { auto newRangesA = splitRange(rangeA, false /*isLine*/); auto newRangesB = splitRange(rangeB, false /*isLine*/); @@ -263,11 +258,13 @@ double pointsToLineDistance(const mapbox::geometry::multi_point& points, // In case the set size are relatively small, we could use brute-force directly if (getRangeSize(rangeA) <= MinPointsSize && getRangeSize(rangeB) <= MinLinePointsSize) { + assert(rangeA.second >= rangeA.first && rangeA.second < points.size()); + assert(rangeB.second >= rangeB.first && rangeB.second < line.size()); auto subLine = mapbox::geometry::multi_point(line.begin() + rangeB.first, line.begin() + rangeB.second + 1); for (std::size_t i = rangeA.first; i <= rangeA.second; ++i) { miniDist = std::min(miniDist, pointToLineDistance(points[i], subLine, ruler)); - if (miniDist == 0.) return 0.; + if (miniDist == 0.0) return 0.0; } } else { auto newRangesA = splitRange(rangeA, false /*isLine*/); @@ -296,7 +293,7 @@ double pointsToLinesDistance(const mapbox::geometry::multi_point& points double dist = std::numeric_limits::infinity(); for (const auto& line : lines) { dist = std::min(dist, pointsToLineDistance(points, line, ruler)); - if (dist == 0.) return dist; + if (dist == 0.0) return 0.0; } return dist; } @@ -307,7 +304,7 @@ double lineToLinesDistance(const mapbox::geometry::line_string& line, double dist = std::numeric_limits::infinity(); for (const auto& l : lines) { dist = std::min(dist, lineToLineDistance(line, l, ruler)); - if (dist == 0.) return dist; + if (dist == 0.0) return 0.0; } return dist; } @@ -372,7 +369,7 @@ double calculateDistance(const GeometryTileFeature& feature, double dist = std::numeric_limits::infinity(); for (const auto& line : lines) { dist = std::min(dist, lineToGeometryDistance(line, geoSet, unit)); - if (dist == 0.) return dist; + if (dist == 0.0) return dist; } return dist; }, @@ -405,24 +402,24 @@ optional parseValue(const style::conversion::Convertible& value, styl ctx.error("Failed to parse unit argument from 'distance' expression"); return nullopt; } - if (*input == "Meters" || *input == "Metres") { + if (*input == "meters" || *input == "metres") { unit = mapbox::cheap_ruler::CheapRuler::Unit::Meters; - } else if (*input == "Kilometers") { + } else if (*input == "kilometers") { unit = mapbox::cheap_ruler::CheapRuler::Unit::Kilometers; - } else if (*input == "Miles") { + } else if (*input == "miles") { unit = mapbox::cheap_ruler::CheapRuler::Unit::Miles; - } else if (*input == "NauticalMiles") { + } else if (*input == "nauticalmiles") { unit = mapbox::cheap_ruler::CheapRuler::Unit::NauticalMiles; - } else if (*input == "Yards") { + } else if (*input == "yards") { unit = mapbox::cheap_ruler::CheapRuler::Unit::Yards; - } else if (*input == "Feet") { + } else if (*input == "feet") { unit = mapbox::cheap_ruler::CheapRuler::Unit::Feet; - } else if (*input == "Inches") { + } else if (*input == "inches") { unit = mapbox::cheap_ruler::CheapRuler::Unit::Inches; } else { ctx.error( - "'distance' expression only accepts following Units: 'Kilometers', 'Miles', 'NauticalMiles', " - "'Meters', 'Metres', 'Yards', 'Feet', 'Inches'."); + "'distance' expression only accepts following units: kilometers, miles, nauticalmiles, " + "meters, metres, yards, feet, inches."); return nullopt; } } @@ -438,8 +435,8 @@ optional parseValue(const style::conversion::Convertible& value, styl } } ctx.error( - "'distance' expression needs to be an array with format [\"Distance\", GeoJSONObj, \"unit(optional, Meters by " - "default)\"]."); + "'distance' expression needs to be an array with format [\"Distance\", GeoJSONObj, \"units\"(\"units\" is an " + "optional argument, 'meters' will be used by default)]."); return nullopt; } @@ -474,6 +471,7 @@ EvaluationResult Distance::evaluate(const EvaluationContext& params) const { if (geometryType == FeatureType::Point || geometryType == FeatureType::LineString) { auto distance = calculateDistance(*params.feature, *params.canonical, geometries, unit); if (!std::isnan(distance)) { + assert(distance >= 0.0); return distance; } } @@ -547,21 +545,21 @@ Value convertValue(const mapbox::geojson::rapidjson_value& v) { std::string getUnits(const mapbox::cheap_ruler::CheapRuler::Unit& unit) { switch (unit) { case mapbox::cheap_ruler::CheapRuler::Kilometers: - return "Kilometers"; + return "kilometers"; case mapbox::cheap_ruler::CheapRuler::Miles: - return "Miles"; + return "miles"; case mapbox::cheap_ruler::CheapRuler::NauticalMiles: - return "NauticalMiles"; + return "nauticalmiles"; case mapbox::cheap_ruler::CheapRuler::Meters: - return "Meters"; + return "meters"; case mapbox::cheap_ruler::CheapRuler::Yards: - return "Yards"; + return "yards"; case mapbox::cheap_ruler::CheapRuler::Feet: - return "Feet"; + return "feet"; case mapbox::cheap_ruler::CheapRuler::Inches: - return "Inches"; + return "inches"; default: - return "Error"; + return "error"; } } diff --git a/src/mbgl/style/expression/within.cpp b/src/mbgl/style/expression/within.cpp index a3e2500319..3fd2bf8f92 100644 --- a/src/mbgl/style/expression/within.cpp +++ b/src/mbgl/style/expression/within.cpp @@ -15,29 +15,6 @@ namespace mbgl { namespace { -// contains minX, minY, maxX, maxY -using WithinBBox = std::array; -const WithinBBox DefaultBBox = WithinBBox{std::numeric_limits::max(), - std::numeric_limits::max(), - std::numeric_limits::min(), - std::numeric_limits::min()}; - -// check if bbox1 is within bbox2 -void updateBBox(WithinBBox& bbox, const Point& 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 boxWithinBox(const WithinBBox& bbox1, const WithinBBox& 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; -} - Point latLonToTileCoodinates(const Point& point, const mbgl::CanonicalTileID& canonical) { const double size = util::EXTENT * std::pow(2, canonical.z); @@ -53,6 +30,7 @@ Point latLonToTileCoodinates(const Point& point, const mbgl::Ca return p; }; +using WithinBBox = GeometryBBox; Polygon getTilePolygon(const Polygon& polygon, const mbgl::CanonicalTileID& canonical, WithinBBox& bbox) { @@ -149,7 +127,7 @@ MultiLineString getTileLines(const GeometryCollection& lines, const auto worldSize = util::EXTENT * std::pow(2, canonical.z); if (bbox[2] - bbox[0] <= worldSize / 2) { - bbox = DefaultBBox; + bbox = DefaultWithinBBox; for (auto& line : results) { for (auto& p : line) { updatePoint(p, bbox, polyBBox, worldSize); @@ -162,28 +140,28 @@ MultiLineString getTileLines(const GeometryCollection& lines, bool featureWithinPolygons(const GeometryTileFeature& feature, const CanonicalTileID& canonical, const Feature::geometry_type& polygonGeoSet) { - WithinBBox polyBBox = DefaultBBox; + WithinBBox polyBBox = DefaultWithinBBox; const auto polygons = getTilePolygons(polygonGeoSet, canonical, polyBBox); assert(!polygons.empty()); const GeometryCollection& geometries = feature.getGeometries(); switch (feature.getType()) { case FeatureType::Point: { assert(!geometries.empty()); - WithinBBox pointBBox = DefaultBBox; + WithinBBox pointBBox = DefaultWithinBBox; MultiPoint points = getTilePoints(geometries.at(0), canonical, pointBBox, polyBBox); if (!boxWithinBox(pointBBox, polyBBox)) return false; return std::all_of(points.begin(), points.end(), [&polygons](const auto& p) { - return GeometryUtil::pointWithinPolygons(p, polygons); + return pointWithinPolygons(p, polygons); }); } case FeatureType::LineString: { - WithinBBox lineBBox = DefaultBBox; + WithinBBox lineBBox = DefaultWithinBBox; MultiLineString multiLineString = getTileLines(geometries, canonical, lineBBox, polyBBox); if (!boxWithinBox(lineBBox, polyBBox)) return false; return std::all_of(multiLineString.begin(), multiLineString.end(), [&polygons](const auto& line) { - return GeometryUtil::lineStringWithinPolygons(line, polygons); + return lineStringWithinPolygons(line, polygons); }); } default: 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 -bool GeometryUtil::rayIntersect(const Point& p, const Point& p1, const Point& p2) { +void updateBBox(GeometryBBox& bbox, const Point& 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 +bool boxWithinBox(const GeometryBBox& bbox1, const GeometryBBox& 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 +bool rayIntersect(const Point& p, const Point& p1, const Point& 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 -bool GeometryUtil::pointOnBoundary(const Point& p, const Point& p1, const Point& p2) { +bool pointOnBoundary(const Point& p, const Point& p1, const Point& 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::pointOnBoundary(const Point& p, const Point& p1, con } template -bool GeometryUtil::segmentIntersectSegment(const Point& a, - const Point& b, - const Point& c, - const Point& d) { +bool segmentIntersectSegment(const Point& a, const Point& b, const Point& c, const Point& d) { // a, b are end points for line segment1, c and d are end points for line segment2 const auto perp = [](const Point& v1, const Point& v2) { return (v1.x * v2.y - v1.y * v2.x); }; @@ -58,7 +73,7 @@ bool GeometryUtil::segmentIntersectSegment(const Point& a, } template -bool GeometryUtil::lineIntersectPolygon(const Point& p1, const Point& p2, const Polygon& polygon) { +bool lineIntersectPolygon(const Point& p1, const Point& p2, const Polygon& polygon) { for (auto ring : polygon) { auto length = ring.size(); // loop through every edge of the ring @@ -73,7 +88,7 @@ bool GeometryUtil::lineIntersectPolygon(const Point& p1, const Point& p // ray casting algorithm for detecting if point is in polygon template -bool GeometryUtil::pointWithinPolygon(const Point& point, const Polygon& polygon, bool trueOnBoundary) { +bool pointWithinPolygon(const Point& point, const Polygon& polygon, bool trueOnBoundary) { bool within = false; for (const auto& ring : polygon) { const auto length = ring.size(); @@ -89,7 +104,7 @@ bool GeometryUtil::pointWithinPolygon(const Point& point, const Polygon } template -bool GeometryUtil::pointWithinPolygons(const Point& point, const MultiPolygon& polygons, bool trueOnBoundary) { +bool pointWithinPolygons(const Point& point, const MultiPolygon& polygons, bool trueOnBoundary) { for (const auto& polygon : polygons) { if (pointWithinPolygon(point, polygon, trueOnBoundary)) return true; } @@ -97,7 +112,7 @@ bool GeometryUtil::pointWithinPolygons(const Point& point, const MultiPoly } template -bool GeometryUtil::lineStringWithinPolygon(const LineString& line, const Polygon& polygon) { +bool lineStringWithinPolygon(const LineString& line, const Polygon& 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::lineStringWithinPolygon(const LineString& line, const P } template -bool GeometryUtil::lineStringWithinPolygons(const LineString& line, const MultiPolygon& polygons) { +bool lineStringWithinPolygons(const LineString& line, const MultiPolygon& polygons) { for (const auto& polygon : polygons) { if (lineStringWithinPolygon(line, polygon)) return true; } return false; } -template struct GeometryUtil; -template struct GeometryUtil; +template void updateBBox(GeometryBBox& bbox, const Point& p); +template bool boxWithinBox(const GeometryBBox& bbox1, const GeometryBBox& bbox2); +template bool segmentIntersectSegment(const Point& a, + const Point& b, + const Point& c, + const Point& d); +template bool rayIntersect(const Point& p, const Point& p1, const Point& p2); +template bool pointOnBoundary(const Point& p, const Point& p1, const Point& p2); +template bool lineIntersectPolygon(const Point& p1, const Point& p2, const Polygon& polygon); +template bool pointWithinPolygon(const Point& point, + const Polygon& polygon, + bool trueOnBoundary = false); +template bool pointWithinPolygons(const Point& point, + const MultiPolygon& polygons, + bool trueOnBoundary = false); +template bool lineStringWithinPolygon(const LineString& line, const Polygon& polygon); +template bool lineStringWithinPolygons(const LineString& line, const MultiPolygon& polygons); + +template void updateBBox(GeometryBBox& bbox, const Point& p); +template bool segmentIntersectSegment(const Point& a, + const Point& b, + const Point& c, + const Point& 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 #include namespace mbgl { +// contains minX, minY, maxX, maxY template -struct GeometryUtil { - using type = T; - static bool segmentIntersectSegment(const Point& a, - const Point& b, - const Point& c, - const Point& d); - static bool rayIntersect(const Point& p, const Point& p1, const Point& p2); - static bool pointOnBoundary(const Point& p, const Point& p1, const Point& p2); - static bool lineIntersectPolygon(const Point& p1, const Point& p2, const Polygon& polygon); - static bool pointWithinPolygon(const Point& point, const Polygon& polygon, bool trueOnBoundary = false); - static bool pointWithinPolygons(const Point& point, - const MultiPolygon& polygons, - bool trueOnBoundary = false); - static bool lineStringWithinPolygon(const LineString& line, const Polygon& polygon); - static bool lineStringWithinPolygons(const LineString& line, const MultiPolygon& polygons); -}; +using GeometryBBox = std::array; +const GeometryBBox DefaultWithinBBox = std::array{std::numeric_limits::max(), + std::numeric_limits::max(), + std::numeric_limits::min(), + std::numeric_limits::min()}; + +const GeometryBBox DefaultDistanceBBox = std::array{std::numeric_limits::infinity(), + std::numeric_limits::infinity(), + -std::numeric_limits::infinity(), + -std::numeric_limits::infinity()}; + +template +void updateBBox(GeometryBBox& bbox, const Point& p); + +// check if bbox1 is within bbox2 +template +bool boxWithinBox(const GeometryBBox& bbox1, const GeometryBBox& bbox2); + +template +bool segmentIntersectSegment(const Point& a, const Point& b, const Point& c, const Point& d); + +template +bool rayIntersect(const Point& p, const Point& p1, const Point& p2); + +template +bool pointOnBoundary(const Point& p, const Point& p1, const Point& p2); + +template +bool lineIntersectPolygon(const Point& p1, const Point& p2, const Polygon& polygon); + +template +bool pointWithinPolygon(const Point& point, const Polygon& polygon, bool trueOnBoundary = false); + +template +bool pointWithinPolygons(const Point& point, const MultiPolygon& polygons, bool trueOnBoundary = false); + +template +bool lineStringWithinPolygon(const LineString& line, const Polygon& polygon); + +template +bool lineStringWithinPolygons(const LineString& line, const MultiPolygon& polygons); } // namespace mbgl -- cgit v1.2.1