summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--include/mbgl/style/expression/within.hpp3
-rw-r--r--src/mbgl/style/expression/within.cpp233
-rw-r--r--src/mbgl/util/geometry_within.cpp92
-rw-r--r--src/mbgl/util/geometry_within.hpp20
4 files changed, 180 insertions, 168 deletions
diff --git a/include/mbgl/style/expression/within.hpp b/include/mbgl/style/expression/within.hpp
index eb23c7d0e0..a8e45f9bf0 100644
--- a/include/mbgl/style/expression/within.hpp
+++ b/include/mbgl/style/expression/within.hpp
@@ -11,7 +11,7 @@ namespace expression {
class Within final : public Expression {
public:
- explicit Within(GeoJSON geojson, Feature::geometry_type geometries_, const WithinBBox& polygonBBox_);
+ explicit Within(GeoJSON geojson, Feature::geometry_type geometries_);
~Within() override;
@@ -31,7 +31,6 @@ public:
private:
GeoJSON geoJSONSource;
Feature::geometry_type geometries;
- WithinBBox polygonBBox;
};
} // namespace expression
diff --git a/src/mbgl/style/expression/within.cpp b/src/mbgl/style/expression/within.cpp
index 49ae8b54a8..0f2f837420 100644
--- a/src/mbgl/style/expression/within.cpp
+++ b/src/mbgl/style/expression/within.cpp
@@ -9,78 +9,149 @@
#include <mbgl/util/string.hpp>
#include <rapidjson/document.h>
+#include <mbgl/math/clamp.hpp>
namespace mbgl {
namespace {
-bool pointsWithinPolygons(const mbgl::GeometryTileFeature& feature,
- const mbgl::CanonicalTileID& canonical,
- const Feature::geometry_type& polygonGeoSet,
- const WithinBBox& polyBBox) {
- return polygonGeoSet.match(
- [&feature, &canonical, &polyBBox](const mapbox::geometry::multi_polygon<double>& polygons) -> bool {
- return convertGeometry(feature, canonical)
- .match(
- [&polygons, &polyBBox](const mapbox::geometry::point<double>& point) -> bool {
- return boxWithinBox(calculateBBox(point), polyBBox) && pointWithinPolygons(point, polygons);
- },
- [&polygons, &polyBBox](const mapbox::geometry::multi_point<double>& points) -> bool {
- return boxWithinBox(calculateBBox(points), polyBBox) &&
- std::all_of(points.begin(), points.end(), [&polygons](const auto& p) {
- return pointWithinPolygons(p, polygons);
- });
- },
- [](const auto&) -> bool { return false; });
- },
- [&feature, &canonical, &polyBBox](const mapbox::geometry::polygon<double>& polygon) -> bool {
- return convertGeometry(feature, canonical)
- .match(
- [&polygon, &polyBBox](const mapbox::geometry::point<double>& point) -> bool {
- return boxWithinBox(calculateBBox(point), polyBBox) && pointWithinPolygon(point, polygon);
- },
- [&polygon, &polyBBox](const mapbox::geometry::multi_point<double>& points) -> bool {
- return boxWithinBox(calculateBBox(points), polyBBox) &&
- std::all_of(points.begin(), points.end(), [&polygon](const auto& p) {
- return pointWithinPolygon(p, polygon);
- });
- },
- [](const auto&) -> bool { return false; });
- },
- [](const auto&) -> bool { return false; });
+Point<int64_t> latLonToTileCoodinates(const Point<double>& c, const mbgl::CanonicalTileID& canonical) {
+ Point<int64_t> p;
+
+ const double size = util::EXTENT * std::pow(2, canonical.z);
+
+ auto x = (c.x + 180.0) * size / 360.0;
+ p.x = (util::clamp<int64_t>(x, std::numeric_limits<int64_t>::min(), std::numeric_limits<int64_t>::max()));
+
+ auto y = (180 - (std::log(std::tan((c.y + 90) * M_PI / 360.0)) * 180 / M_PI)) * size / 360;
+ p.y = (util::clamp<int64_t>(y, std::numeric_limits<int64_t>::min(), std::numeric_limits<int64_t>::max()));
+
+ return p;
+};
+
+Polygon<int64_t> getTilePolygon(const Polygon<double>& polygon,
+ const mbgl::CanonicalTileID& canonical,
+ WithinBBox& bbox) {
+ Polygon<int64_t> result;
+ result.reserve(polygon.size());
+ for (const auto& ring : polygon) {
+ LinearRing<int64_t> temp;
+ temp.reserve(ring.size());
+ for (const auto p : ring) {
+ const auto coord = latLonToTileCoodinates(p, canonical);
+ temp.push_back(coord);
+ updateBBox(bbox, coord);
+ }
+ result.push_back(std::move(temp));
+ }
+ return result;
+}
+
+MultiPolygon<int64_t> getTilePolygons(const MultiPolygon<double>& polygons,
+ const mbgl::CanonicalTileID& canonical,
+ WithinBBox& bbox) {
+ MultiPolygon<int64_t> result;
+ result.reserve(polygons.size());
+ for (const auto& pg : polygons) {
+ result.push_back(getTilePolygon(pg, canonical, bbox));
+ }
+ return result;
+}
+
+MultiPoint<int64_t> getTilePoints(const GeometryCoordinates& points,
+ const mbgl::CanonicalTileID& canonical,
+ WithinBBox& bbox) {
+ const int64_t x0 = util::EXTENT * canonical.x;
+ const int64_t y0 = util::EXTENT * canonical.y;
+ MultiPoint<int64_t> results;
+ results.reserve(points.size());
+ for (const auto& p : points) {
+ auto point = Point<int64_t>(p.x + x0, p.y + y0);
+ updateBBox(bbox, point);
+ results.push_back(point);
+ }
+ return results;
}
-bool linesWithinPolygons(const mbgl::GeometryTileFeature& feature,
- const mbgl::CanonicalTileID& canonical,
- const Feature::geometry_type& polygonGeoSet,
- const WithinBBox& polyBBox) {
+MultiLineString<int64_t> getTileLines(const GeometryCollection& lines,
+ const mbgl::CanonicalTileID& canonical,
+ WithinBBox& bbox) {
+ const int64_t x0 = util::EXTENT * canonical.x;
+ const int64_t y0 = util::EXTENT * canonical.y;
+ MultiLineString<int64_t> results;
+ results.reserve(bbox.size());
+ for (const auto& line : lines) {
+ LineString<int64_t> lineString;
+ lineString.reserve(line.size());
+ for (const auto& p : line) {
+ auto point = Point<int64_t>(p.x + x0, p.y + y0);
+ updateBBox(bbox, point);
+ lineString.push_back(point);
+ }
+ results.push_back(std::move(lineString));
+ }
+ return results;
+}
+
+bool featureWithinPolygons(const GeometryTileFeature& feature,
+ const CanonicalTileID& canonical,
+ const Feature::geometry_type& polygonGeoSet) {
return polygonGeoSet.match(
- [&feature, &canonical, &polyBBox](const MultiPolygon<double>& polygons) -> bool {
- return convertGeometry(feature, canonical)
- .match(
- [&polygons, &polyBBox](const LineString<double>& line) -> bool {
- return boxWithinBox(calculateBBox(line), polyBBox) && lineStringWithinPolygons(line, polygons);
- },
- [&polygons, &polyBBox](const MultiLineString<double>& lines) -> bool {
- return boxWithinBox(calculateBBox(lines), polyBBox) &&
- std::all_of(lines.begin(), lines.end(), [&polygons](const auto& line) {
- return lineStringWithinPolygons(line, polygons);
- });
- },
- [](const auto&) -> bool { return false; });
+ [&feature, &canonical](const mapbox::geometry::multi_polygon<double>& polys) -> bool {
+ WithinBBox polyBBox = DefaultBBox;
+ auto polygons = getTilePolygons(polys, canonical, polyBBox);
+
+ const GeometryCollection& geometries = feature.getGeometries();
+ switch (feature.getType()) {
+ case FeatureType::Point: {
+ WithinBBox pointBBox = DefaultBBox;
+ MultiPoint<int64_t> points = getTilePoints(geometries.at(0), canonical, pointBBox);
+ if (!boxWithinBox(pointBBox, polyBBox)) return false;
+
+ return std::all_of(points.begin(), points.end(), [&polygons](const auto& p) {
+ return pointWithinPolygons(p, polygons);
+ });
+ }
+ case FeatureType::LineString: {
+ WithinBBox lineBBox = DefaultBBox;
+ MultiLineString<int64_t> multiLineString = getTileLines(geometries, canonical, lineBBox);
+
+ if (!boxWithinBox(lineBBox, polyBBox)) return false;
+
+ return std::all_of(multiLineString.begin(), multiLineString.end(), [&polygons](const auto& line) {
+ return lineStringWithinPolygons(line, polygons);
+ });
+ }
+ default:
+ return false;
+ };
},
- [&feature, &canonical, &polyBBox](const Polygon<double>& polygon) -> bool {
- return convertGeometry(feature, canonical)
- .match(
- [&polygon, &polyBBox](const LineString<double>& line) -> bool {
- return boxWithinBox(calculateBBox(line), polyBBox) && lineStringWithinPolygon(line, polygon);
- },
- [&polygon, &polyBBox](const MultiLineString<double>& lines) -> bool {
- return boxWithinBox(calculateBBox(lines), polyBBox) &&
- std::all_of(lines.begin(), lines.end(), [&polygon](const auto& line) {
- return lineStringWithinPolygon(line, polygon);
- });
- },
- [](const auto&) -> bool { return false; });
+ [&feature, &canonical](const mapbox::geometry::polygon<double>& poly) -> bool {
+ WithinBBox polyBBox = DefaultBBox;
+ const auto polygon = getTilePolygon(poly, canonical, polyBBox);
+
+ const GeometryCollection& geometries = feature.getGeometries();
+ switch (feature.getType()) {
+ case FeatureType::Point: {
+ WithinBBox pointBBox = DefaultBBox;
+ MultiPoint<int64_t> points = getTilePoints(geometries.at(0), canonical, pointBBox);
+ if (!boxWithinBox(pointBBox, polyBBox)) return false;
+
+ return std::all_of(points.begin(), points.end(), [&polygon](const auto& p) {
+ return pointWithinPolygon(p, polygon);
+ });
+ }
+ case FeatureType::LineString: {
+ WithinBBox lineBBox = DefaultBBox;
+ MultiLineString<int64_t> multiLineString = getTileLines(geometries, canonical, lineBBox);
+ if (!boxWithinBox(lineBBox, polyBBox)) return false;
+
+ return std::all_of(multiLineString.begin(), multiLineString.end(), [&polygon](const auto& line) {
+ return lineStringWithinPolygon(line, polygon);
+ });
+ }
+ default:
+ return false;
+ };
},
[](const auto&) -> bool { return false; });
}
@@ -100,16 +171,11 @@ mbgl::optional<mbgl::GeoJSON> parseValue(const mbgl::style::conversion::Converti
return nullopt;
}
-struct PolygonInfo {
- PolygonInfo(const Feature::geometry_type& geometry_) : geometry(geometry_), bbox(calculateBBox(geometry)){};
- Feature::geometry_type geometry;
- WithinBBox bbox;
-};
-
-mbgl::optional<PolygonInfo> getPolygonInfo(const Feature& polyFeature, mbgl::style::expression::ParsingContext& ctx) {
+mbgl::optional<Feature::geometry_type> getPolygonInfo(const Feature& polyFeature,
+ mbgl::style::expression::ParsingContext& ctx) {
const auto type = apply_visitor(ToFeatureType(), polyFeature.geometry);
if (type == FeatureType::Polygon) {
- return PolygonInfo(polyFeature.geometry);
+ return polyFeature.geometry;
}
ctx.error("'within' expression requires valid geojson source that contains polygon geometry type.");
return nullopt;
@@ -119,11 +185,8 @@ mbgl::optional<PolygonInfo> getPolygonInfo(const Feature& polyFeature, mbgl::sty
namespace style {
namespace expression {
-Within::Within(GeoJSON geojson, Feature::geometry_type geometries_, const WithinBBox& polygonBBox_)
- : Expression(Kind::Within, type::Boolean),
- geoJSONSource(std::move(geojson)),
- geometries(std::move(geometries_)),
- polygonBBox(polygonBBox_) {}
+Within::Within(GeoJSON geojson, Feature::geometry_type geometries_)
+ : Expression(Kind::Within, type::Boolean), geoJSONSource(std::move(geojson)), geometries(std::move(geometries_)) {}
Within::~Within() = default;
@@ -134,11 +197,9 @@ EvaluationResult Within::evaluate(const EvaluationContext& params) const {
return false;
}
auto geometryType = params.feature->getType();
- // Currently only support Point/Points in Polygon/Polygons
- if (geometryType == FeatureType::Point) {
- return pointsWithinPolygons(*params.feature, *params.canonical, geometries, polygonBBox);
- } else if (geometryType == FeatureType::LineString) {
- return linesWithinPolygons(*params.feature, *params.canonical, geometries, polygonBBox);
+ // Currently only support Point and LineString types in Polygon/Polygons
+ if (geometryType == FeatureType::Point || geometryType == FeatureType::LineString) {
+ return featureWithinPolygons(*params.feature, *params.canonical, geometries);
}
mbgl::Log::Warning(mbgl::Event::General,
"within expression currently only support Point/LineString geometry type.");
@@ -163,20 +224,20 @@ ParseResult Within::parse(const Convertible& value, ParsingContext& ctx) {
return parsedValue->match(
[&parsedValue, &ctx](const mapbox::geometry::geometry<double>& geometrySet) {
if (auto ret = getPolygonInfo(mbgl::Feature(geometrySet), ctx)) {
- return ParseResult(std::make_unique<Within>(*parsedValue, std::move(ret->geometry), ret->bbox));
+ return ParseResult(std::make_unique<Within>(*parsedValue, std::move(*ret)));
}
return ParseResult();
},
[&parsedValue, &ctx](const mapbox::feature::feature<double>& feature) {
if (auto ret = getPolygonInfo(mbgl::Feature(feature), ctx)) {
- return ParseResult(std::make_unique<Within>(*parsedValue, std::move(ret->geometry), ret->bbox));
+ return ParseResult(std::make_unique<Within>(*parsedValue, std::move(*ret)));
}
return ParseResult();
},
[&parsedValue, &ctx](const mapbox::feature::feature_collection<double>& features) {
for (const auto& feature : features) {
if (auto ret = getPolygonInfo(mbgl::Feature(feature), ctx)) {
- return ParseResult(std::make_unique<Within>(*parsedValue, std::move(ret->geometry), ret->bbox));
+ return ParseResult(std::make_unique<Within>(*parsedValue, std::move(*ret)));
}
}
return ParseResult();
@@ -234,7 +295,7 @@ mbgl::Value Within::serialize() const {
bool Within::operator==(const Expression& e) const {
if (e.getKind() == Kind::Within) {
auto rhs = static_cast<const Within*>(&e);
- return geoJSONSource == rhs->geoJSONSource && geometries == rhs->geometries && polygonBBox == rhs->polygonBBox;
+ return geoJSONSource == rhs->geoJSONSource && geometries == rhs->geometries;
}
return false;
}
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