diff options
51 files changed, 1295 insertions, 179 deletions
diff --git a/include/mbgl/map/map.hpp b/include/mbgl/map/map.hpp index 0b1720e65b..41f34c102b 100644 --- a/include/mbgl/map/map.hpp +++ b/include/mbgl/map/map.hpp @@ -158,6 +158,10 @@ public: const char* before = nullptr); void removeCustomLayer(const std::string& id); + // Feature queries + std::vector<std::string> queryRenderedFeatures(const ScreenCoordinate&, const optional<std::vector<std::string>>& layerIDs = {}); + std::vector<std::string> queryRenderedFeatures(const std::array<ScreenCoordinate, 2>&, const optional<std::vector<std::string>>& layerIDs = {}); + // Memory void setSourceTileCacheSize(size_t); void onLowMemory(); diff --git a/include/mbgl/util/math.hpp b/include/mbgl/util/math.hpp index 1e5073ab3b..c0fdea47fb 100644 --- a/include/mbgl/util/math.hpp +++ b/include/mbgl/util/math.hpp @@ -88,6 +88,14 @@ inline T dist(const S1& a, const S2& b) { return c; } +template <typename T, typename S1, typename S2> +inline T distSqr(const S1& a, const S2& b) { + T dx = b.x - a.x; + T dy = b.y - a.y; + T c = dx * dx + dy * dy; + return c; +} + template <typename T> inline T round(const T& a) { return T(::round(a.x), ::round(a.y)); @@ -113,6 +121,15 @@ inline S unit(const S& a) { return a * (1 / magnitude); } +template <typename T, typename S = double> +inline T rotate(const T& a, S angle) { + S cos = std::cos(angle); + S sin = std::sin(angle); + S x = cos * a.x - sin * a.y; + S y = sin * a.x + cos * a.y; + return T(x, y); +} + template <typename T> T clamp(T value, T min_, T max_) { return max(min_, min(max_, value)); diff --git a/package.json b/package.json index 62c1a7940a..7fb9631643 100644 --- a/package.json +++ b/package.json @@ -18,7 +18,7 @@ }, "devDependencies": { "aws-sdk": "^2.3.5", - "mapbox-gl-test-suite": "mapbox/mapbox-gl-test-suite#d974ec6b3748a258f8ddd7528e049493390177b4", + "mapbox-gl-test-suite": "mapbox/mapbox-gl-test-suite#e211ead52b9268c53f998096d5f6ba15977cf4ea", "node-gyp": "^3.3.1", "request": "^2.72.0", "tape": "^4.5.1" @@ -30,7 +30,7 @@ "preinstall": "npm install node-pre-gyp", "install": "node-pre-gyp install --fallback-to-build=false || make node", "test": "tape platform/node/test/js/**/*.test.js", - "test-suite": "node platform/node/test/render.test.js" + "test-suite": "node platform/node/test/render.test.js && node platform/node/test/query.test.js" }, "gypfile": true, "binary": { diff --git a/platform/node/src/node_map.cpp b/platform/node/src/node_map.cpp index 7968e83554..cf828782f5 100644 --- a/platform/node/src/node_map.cpp +++ b/platform/node/src/node_map.cpp @@ -50,6 +50,7 @@ NAN_MODULE_INIT(NodeMap::Init) { Nan::SetPrototypeMethod(tpl, "render", Render); Nan::SetPrototypeMethod(tpl, "release", Release); Nan::SetPrototypeMethod(tpl, "dumpDebugLogs", DumpDebugLogs); + Nan::SetPrototypeMethod(tpl, "queryRenderedFeatures", QueryRenderedFeatures); constructor.Reset(tpl->GetFunction()); Nan::Set(target, Nan::New("Map").ToLocalChecked(), tpl->GetFunction()); @@ -448,6 +449,55 @@ NAN_METHOD(NodeMap::DumpDebugLogs) { info.GetReturnValue().SetUndefined(); } +NAN_METHOD(NodeMap::QueryRenderedFeatures) { + auto nodeMap = Nan::ObjectWrap::Unwrap<NodeMap>(info.Holder()); + Nan::HandleScope scope; + + if (!nodeMap->isValid()) return Nan::ThrowError(releasedMessage()); + + if (info.Length() <= 0 || !info[0]->IsArray()) { + return Nan::ThrowTypeError("First argument must be an array"); + } + + auto posOrBox = info[0].As<v8::Array>(); + if (posOrBox->Length() != 2) { + return Nan::ThrowTypeError("First argument must have two components"); + } + + try { + std::vector<std::string> result; + + if (Nan::Get(posOrBox, 0).ToLocalChecked()->IsArray()) { + + auto pos0 = Nan::Get(posOrBox, 0).ToLocalChecked().As<v8::Array>(); + auto pos1 = Nan::Get(posOrBox, 1).ToLocalChecked().As<v8::Array>(); + + std::array<mbgl::ScreenCoordinate, 2> queryBox = {{{ + Nan::Get(pos0, 0).ToLocalChecked()->NumberValue(), + Nan::Get(pos0, 1).ToLocalChecked()->NumberValue() + }, { + Nan::Get(pos1, 0).ToLocalChecked()->NumberValue(), + Nan::Get(pos1, 1).ToLocalChecked()->NumberValue() + }}}; + result = nodeMap->map->queryRenderedFeatures(queryBox); + + } else { + mbgl::ScreenCoordinate queryPoint( + Nan::Get(posOrBox, 0).ToLocalChecked()->NumberValue(), + Nan::Get(posOrBox, 1).ToLocalChecked()->NumberValue()); + result = nodeMap->map->queryRenderedFeatures(queryPoint); + } + + auto array = Nan::New<v8::Array>(); + for (unsigned int i = 0; i < result.size(); i++) { + array->Set(i, Nan::New<v8::String>(result[i]).ToLocalChecked()); + } + info.GetReturnValue().Set(array); + } catch (const std::exception &ex) { + return Nan::ThrowError(ex.what()); + } +} + //////////////////////////////////////////////////////////////////////////////////////////////// // Instance diff --git a/platform/node/src/node_map.hpp b/platform/node/src/node_map.hpp index ac01c9b3a7..6e28eb541e 100644 --- a/platform/node/src/node_map.hpp +++ b/platform/node/src/node_map.hpp @@ -27,6 +27,7 @@ public: static NAN_METHOD(Render); static NAN_METHOD(Release); static NAN_METHOD(DumpDebugLogs); + static NAN_METHOD(QueryRenderedFeatures); void startRender(RenderOptions options); void renderFinished(); diff --git a/platform/node/test/query.test.js b/platform/node/test/query.test.js new file mode 100644 index 0000000000..1309c03467 --- /dev/null +++ b/platform/node/test/query.test.js @@ -0,0 +1,12 @@ +'use strict'; + +var suite = require('mapbox-gl-test-suite').query; +var suiteImplementation = require('./suite_implementation'); + +var tests; + +if (process.argv[1] === __filename && process.argv.length > 2) { + tests = process.argv.slice(2); +} + +suite.run('native', {tests: tests}, suiteImplementation); diff --git a/platform/node/test/render.test.js b/platform/node/test/render.test.js index 05a6b2ba68..0527a19070 100644 --- a/platform/node/test/render.test.js +++ b/platform/node/test/render.test.js @@ -1,8 +1,7 @@ 'use strict'; -var mbgl = require('../../../lib/mapbox-gl-native'); var suite = require('mapbox-gl-test-suite').render; -var request = require('request'); +var suiteImplementation = require('./suite_implementation'); var tests; @@ -10,47 +9,4 @@ if (process.argv[1] === __filename && process.argv.length > 2) { tests = process.argv.slice(2); } -mbgl.on('message', function(msg) { - console.log('%s (%s): %s', msg.severity, msg.class, msg.text); -}); - -suite.run('native', {tests: tests}, function (style, options, callback) { - var map = new mbgl.Map({ - ratio: options.pixelRatio, - request: function(req, callback) { - request(req.url, {encoding: null}, function (err, response, body) { - if (err) { - callback(err); - } else if (response.statusCode != 200) { - callback(new Error(response.statusMessage)); - } else { - callback(null, {data: body}); - } - }); - } - }); - - var timedOut = false; - var watchdog = setTimeout(function () { - timedOut = true; - map.dumpDebugLogs(); - callback(new Error('timed out after 20 seconds')); - }, 20000); - - options.center = style.center; - options.zoom = style.zoom; - options.bearing = style.bearing; - options.pitch = style.pitch; - options.debug = { - tileBorders: options.debug, - collision: options.collisionDebug - }; - - map.load(style); - map.render(options, function (err, pixels) { - map.release(); - if (timedOut) return; - clearTimeout(watchdog); - callback(err, pixels); - }); -}); +suite.run('native', {tests: tests}, suiteImplementation); diff --git a/platform/node/test/suite_implementation.js b/platform/node/test/suite_implementation.js new file mode 100644 index 0000000000..a5c70ab802 --- /dev/null +++ b/platform/node/test/suite_implementation.js @@ -0,0 +1,60 @@ +'use strict'; + +var mbgl = require('../../../lib/mapbox-gl-native'); +var request = require('request'); + +mbgl.on('message', function(msg) { + console.log('%s (%s): %s', msg.severity, msg.class, msg.text); +}); + +module.exports = function (style, options, callback) { + var map = new mbgl.Map({ + ratio: options.pixelRatio, + request: function(req, callback) { + request(req.url, {encoding: null}, function (err, response, body) { + if (err) { + callback(err); + } else if (response.statusCode != 200) { + callback(new Error(response.statusMessage)); + } else { + callback(null, {data: body}); + } + }); + } + }); + + var timedOut = false; + var watchdog = setTimeout(function () { + timedOut = true; + map.dumpDebugLogs(); + callback(new Error('timed out after 20 seconds')); + }, 20000); + + options.center = style.center; + options.zoom = style.zoom; + options.bearing = style.bearing; + options.pitch = style.pitch; + options.debug = { + tileBorders: options.debug, + collision: options.collisionDebug + }; + + map.load(style); + + map.render(options, function (err, pixels) { + var results = options.queryGeometry ? + map.queryRenderedFeatures(options.queryGeometry) : + []; + map.release(); + if (timedOut) return; + clearTimeout(watchdog); + callback(err, pixels, results.map(prepareFeatures)); + }); + + function prepareFeatures(json) { + var r = JSON.parse(json); + delete r.layer; + r.geometry = null; + return r; + } +}; diff --git a/src/mbgl/annotation/annotation_tile.hpp b/src/mbgl/annotation/annotation_tile.hpp index bd233e8057..14c4f63d5f 100644 --- a/src/mbgl/annotation/annotation_tile.hpp +++ b/src/mbgl/annotation/annotation_tile.hpp @@ -27,6 +27,7 @@ class AnnotationTileLayer : public GeometryTileLayer { public: std::size_t featureCount() const override { return features.size(); } util::ptr<const GeometryTileFeature> getFeature(std::size_t i) const override { return features[i]; } + std::string getName() const override { return ""; }; std::vector<util::ptr<const AnnotationTileFeature>> features; }; diff --git a/src/mbgl/geometry/feature_index.cpp b/src/mbgl/geometry/feature_index.cpp new file mode 100644 index 0000000000..99bda537de --- /dev/null +++ b/src/mbgl/geometry/feature_index.cpp @@ -0,0 +1,236 @@ +#include <mbgl/geometry/feature_index.hpp> +#include <mbgl/util/math.hpp> +#include <mbgl/style/style.hpp> +#include <mbgl/style/style_layer.hpp> +#include <mbgl/layer/symbol_layer.hpp> +#include <mbgl/util/get_geometries.hpp> +#include <mbgl/text/collision_tile.hpp> +#include <mbgl/util/rapidjson.hpp> +#include <rapidjson/writer.h> + +#include <cassert> +#include <string> + +using namespace mbgl; + +FeatureIndex::FeatureIndex() {} + +void FeatureIndex::insert(const GeometryCollection& geometries, std::size_t index, + const std::string& sourceLayerName, const std::string& bucketName) { + + auto sortIndex = treeBoxes.size(); + + for (auto& ring : geometries) { + + float minX = std::numeric_limits<float>::infinity(); + float minY = std::numeric_limits<float>::infinity(); + float maxX = -std::numeric_limits<float>::infinity(); + float maxY = -std::numeric_limits<float>::infinity(); + for (auto& p : ring) { + const float x = p.x; + const float y = p.y; + minX = util::min(minX, x); + minY = util::min(minY, y); + maxX = util::max(maxX, x); + maxY = util::max(maxY, y); + } + + treeBoxes.emplace_back( + TreeBox { + TreePoint { minX, minY }, + TreePoint { maxX, maxY } + }, + IndexedSubfeature { index, sourceLayerName, bucketName, sortIndex } + ); + } +} + +void FeatureIndex::loadTree() { + tree.insert(treeBoxes.begin(), treeBoxes.end()); +} + +bool vectorContains(const std::vector<std::string>& vector, const std::string& s) { + return std::find(vector.begin(), vector.end(), s) != vector.end(); +} + +bool vectorsIntersect(const std::vector<std::string>& vectorA, const std::vector<std::string>& vectorB) { + for (auto& a : vectorA) { + if (vectorContains(vectorB, a)) return true;; + } + return false; +} + + +bool topDown(const FeatureTreeBox& a, const FeatureTreeBox& b) { + return std::get<1>(a).sortIndex > std::get<1>(b).sortIndex; +} + +bool topDownSymbols(const IndexedSubfeature& a, const IndexedSubfeature& b) { + return a.sortIndex < b.sortIndex; +} + +void FeatureIndex::query( + std::unordered_map<std::string, std::vector<std::string>>& result, + const GeometryCollection& queryGeometry, + const float bearing, + const double tileSize, + const double scale, + const optional<std::vector<std::string>>& filterLayerIDs, + const GeometryTile& geometryTile, + const Style& style) const { + + const float pixelsToTileUnits = util::EXTENT / tileSize / scale; + + float additionalRadius = style.getQueryRadius() * pixelsToTileUnits; + + float minX = std::numeric_limits<float>::infinity(); + float minY = std::numeric_limits<float>::infinity(); + float maxX = -std::numeric_limits<float>::infinity(); + float maxY = -std::numeric_limits<float>::infinity(); + + for (auto& ring : queryGeometry) { + for (auto& p : ring) { + minX = util::min<float>(minX, p.x); + minY = util::min<float>(minY, p.y); + maxX = util::max<float>(maxX, p.x); + maxY = util::max<float>(maxY, p.y); + } + } + + TreeBox queryBox = { + TreePoint { minX - additionalRadius, minY - additionalRadius }, + TreePoint { maxX + additionalRadius, maxY + additionalRadius } + }; + + // query circle, line, fill features + std::vector<FeatureTreeBox> matchingBoxes; + tree.query(bgi::intersects(queryBox), std::back_inserter(matchingBoxes)); + std::sort(matchingBoxes.begin(), matchingBoxes.end(), topDown); + + size_t previousSortIndex = std::numeric_limits<size_t>::max(); + for (auto& matchingBox : matchingBoxes) { + auto& indexedFeature = std::get<1>(matchingBox); + + // If this feature is the same as the previous feature, skip it. + if (indexedFeature.sortIndex == previousSortIndex) continue; + previousSortIndex = indexedFeature.sortIndex; + + addFeature(result, indexedFeature, queryGeometry, filterLayerIDs, geometryTile, style, bearing, pixelsToTileUnits); + } + + // query symbol features + assert(collisionTile); + std::vector<IndexedSubfeature> symbolFeatures = collisionTile->queryRenderedSymbols(minX, minY, maxX, maxY, scale); + std::sort(symbolFeatures.begin(), symbolFeatures.end(), topDownSymbols); + for (auto& symbolFeature : symbolFeatures) { + addFeature(result, symbolFeature, queryGeometry, filterLayerIDs, geometryTile, style, bearing, pixelsToTileUnits); + } +} + +void FeatureIndex::addFeature( + std::unordered_map<std::string, std::vector<std::string>>& result, + const IndexedSubfeature& indexedFeature, + const GeometryCollection& queryGeometry, + const optional<std::vector<std::string>>& filterLayerIDs, + const GeometryTile& geometryTile, + const Style& style, + const float bearing, + const float pixelsToTileUnits) const { + + auto& layerIDs = bucketLayerIDs.at(indexedFeature.bucketName); + + if (filterLayerIDs && !vectorsIntersect(layerIDs, *filterLayerIDs)) return; + + auto sourceLayer = geometryTile.getLayer(indexedFeature.sourceLayerName); + assert(sourceLayer); + auto feature = sourceLayer->getFeature(indexedFeature.index); + assert(feature); + + for (auto& layerID : layerIDs) { + + if (filterLayerIDs && !vectorContains(*filterLayerIDs, layerID)) continue; + + auto styleLayer = style.getLayer(layerID); + if (!styleLayer) continue; + + if (!styleLayer->is<SymbolLayer>()) { + auto geometries = getGeometries(*feature); + if (!styleLayer->queryIntersectsGeometry(queryGeometry, geometries, bearing, pixelsToTileUnits)) continue; + } + + auto& layerResult = result[layerID]; + + auto properties = feature->getProperties(); + rapidjson::StringBuffer buffer; + buffer.Clear(); + rapidjson::Writer<rapidjson::StringBuffer> writer(buffer); + + writer.StartObject(); + writer.Key("type"); + writer.String("Feature"); + auto id = feature->getID(); + if (id) { + writer.Key("id"); + writer.Double(feature->getID()); + } + writer.Key("properties"); + writer.StartObject(); + for (auto& prop : properties) { + std::string key = prop.first; + Value& value = prop.second; + + writer.Key(key.c_str()); + + if (value.is<std::string>()) { + writer.String(value.get<std::string>().c_str()); + } else if (value.is<bool>()) { + writer.Bool(value.get<bool>()); + } else if (value.is<int64_t>()) { + writer.Int64(value.get<int64_t>()); + } else if (value.is<uint64_t>()) { + writer.Uint64(value.get<uint64_t>()); + } else if (value.is<double>()) { + writer.Double(value.get<double>()); + } + } + writer.EndObject(); + writer.EndObject(); + + layerResult.push_back(buffer.GetString()); + } +} + +optional<GeometryCollection> FeatureIndex::translateQueryGeometry( + const GeometryCollection& queryGeometry, + const std::array<float, 2>& translate, + const TranslateAnchorType anchorType, + const float bearing, + const float pixelsToTileUnits) { + + if (translate[0] == 0 && translate[1] == 0) return {}; + + GeometryCoordinate translateVec(translate[0] * pixelsToTileUnits, translate[1] * pixelsToTileUnits); + + if (anchorType == TranslateAnchorType::Viewport) { + translateVec = util::rotate(translateVec, -bearing); + } + + GeometryCollection translated; + for (auto& ring : queryGeometry) { + translated.emplace_back(); + auto& translatedRing = translated.back(); + for (auto& p : ring) { + translatedRing.push_back(p - translateVec); + } + } + return translated; +} + +void FeatureIndex::addBucketLayerName(const std::string& bucketName, const std::string& layerID) { + auto& layerIDs = bucketLayerIDs[bucketName]; + layerIDs.push_back(layerID); +} + +void FeatureIndex::setCollisionTile(std::unique_ptr<CollisionTile> collisionTile_) { + collisionTile = std::move(collisionTile_); +} diff --git a/src/mbgl/geometry/feature_index.hpp b/src/mbgl/geometry/feature_index.hpp new file mode 100644 index 0000000000..dc64ea9cee --- /dev/null +++ b/src/mbgl/geometry/feature_index.hpp @@ -0,0 +1,100 @@ +#ifndef MBGL_GEOMETRY_FEATURE_INDEX +#define MBGL_GEOMETRY_FEATURE_INDEX + +#include <mbgl/tile/geometry_tile.hpp> + +#include <vector> +#include <string> +#include <unordered_map> + +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wunused-function" +#pragma GCC diagnostic ignored "-Wunused-parameter" +#pragma GCC diagnostic ignored "-Wunused-variable" +#pragma GCC diagnostic ignored "-Wshadow" +#ifdef __clang__ +#pragma GCC diagnostic ignored "-Wunknown-pragmas" +#endif +#pragma GCC diagnostic ignored "-Wpragmas" +#pragma GCC diagnostic ignored "-Wdeprecated-register" +#pragma GCC diagnostic ignored "-Wshorten-64-to-32" +#pragma GCC diagnostic ignored "-Wunused-local-typedefs" +#pragma GCC diagnostic ignored "-Wmaybe-uninitialized" +#include <boost/geometry.hpp> +#include <boost/geometry/geometries/point.hpp> +#include <boost/geometry/geometries/box.hpp> +#include <boost/geometry/index/rtree.hpp> +#pragma GCC diagnostic pop + +namespace mbgl { + +class Style; +class CollisionTile; +enum class TranslateAnchorType : bool; + +class IndexedSubfeature { + public: + std::size_t index; + std::string sourceLayerName; + std::string bucketName; + size_t sortIndex; +}; + +namespace bg = boost::geometry; +namespace bgm = bg::model; +namespace bgi = bg::index; +typedef bgm::point<float, 2, bg::cs::cartesian> TreePoint; +typedef bgm::box<TreePoint> TreeBox; +typedef std::pair<TreeBox, IndexedSubfeature> FeatureTreeBox; +typedef bgi::rtree<FeatureTreeBox, bgi::linear<16, 4>> FeatureTree; + +class FeatureIndex { + public: + FeatureIndex(); + + void insert(const GeometryCollection&, std::size_t index, const std::string& sourceLayerName, const std::string& bucketName); + void loadTree(); + + void query( + std::unordered_map<std::string, std::vector<std::string>>& result, + const GeometryCollection& queryGeometry, + const float bearing, + const double tileSize, + const double scale, + const optional<std::vector<std::string>>& layerIDs, + const GeometryTile& geometryTile, + const Style&) const; + + static optional<GeometryCollection> translateQueryGeometry( + const GeometryCollection& queryGeometry, + const std::array<float, 2>& translate, + const TranslateAnchorType, + const float bearing, + const float pixelsToTileUnits); + + void addBucketLayerName(const std::string &bucketName, const std::string &layerName); + + void setCollisionTile(std::unique_ptr<CollisionTile>); + + private: + + void addFeature( + std::unordered_map<std::string, std::vector<std::string>>& result, + const IndexedSubfeature &indexedFeature, + const GeometryCollection& queryGeometry, + const optional<std::vector<std::string>>& filterLayerIDs, + const GeometryTile& geometryTile, + const Style& style, + const float bearing, + const float pixelsToTileUnits) const; + + std::unique_ptr<CollisionTile> collisionTile; + std::vector<FeatureTreeBox> treeBoxes; + FeatureTree tree; + + std::unordered_map<std::string,std::vector<std::string>> bucketLayerIDs; + +}; +} + +#endif diff --git a/src/mbgl/layer/circle_layer.cpp b/src/mbgl/layer/circle_layer.cpp index a305d8763a..1cdc3fa057 100644 --- a/src/mbgl/layer/circle_layer.cpp +++ b/src/mbgl/layer/circle_layer.cpp @@ -2,6 +2,9 @@ #include <mbgl/style/style_bucket_parameters.hpp> #include <mbgl/renderer/circle_bucket.hpp> #include <mbgl/util/get_geometries.hpp> +#include <mbgl/geometry/feature_index.hpp> +#include <mbgl/util/math.hpp> +#include <mbgl/util/intersection_tests.hpp> namespace mbgl { @@ -46,11 +49,34 @@ bool CircleLayer::recalculate(const StyleCalculationParameters& parameters) { std::unique_ptr<Bucket> CircleLayer::createBucket(StyleBucketParameters& parameters) const { auto bucket = std::make_unique<CircleBucket>(parameters.mode); - parameters.eachFilteredFeature(filter, [&] (const auto& feature) { - bucket->addGeometry(getGeometries(feature)); + auto& name = bucketName(); + parameters.eachFilteredFeature(filter, [&] (const auto& feature, std::size_t index, const std::string& layerName) { + auto geometries = getGeometries(feature); + bucket->addGeometry(geometries); + parameters.featureIndex.insert(geometries, index, layerName, name); }); return std::move(bucket); } +float CircleLayer::getQueryRadius() const { + const std::array<float, 2>& translate = paint.circleTranslate; + return paint.circleRadius + util::length(translate[0], translate[1]); +} + +bool CircleLayer::queryIntersectsGeometry( + const GeometryCollection& queryGeometry, + const GeometryCollection& geometry, + const float bearing, + const float pixelsToTileUnits) const { + + auto translatedQueryGeometry = FeatureIndex::translateQueryGeometry( + queryGeometry, paint.circleTranslate, paint.circleTranslateAnchor, bearing, pixelsToTileUnits); + + auto circleRadius = paint.circleRadius * pixelsToTileUnits; + + return util::multiPolygonIntersectsBufferedMultiPoint( + translatedQueryGeometry.value_or(queryGeometry), geometry, circleRadius); +} + } // namespace mbgl diff --git a/src/mbgl/layer/circle_layer.hpp b/src/mbgl/layer/circle_layer.hpp index 25cbc34083..6a6f4ed526 100644 --- a/src/mbgl/layer/circle_layer.hpp +++ b/src/mbgl/layer/circle_layer.hpp @@ -29,6 +29,13 @@ public: std::unique_ptr<Bucket> createBucket(StyleBucketParameters&) const override; + float getQueryRadius() const override; + bool queryIntersectsGeometry( + const GeometryCollection& queryGeometry, + const GeometryCollection& geometry, + const float bearing, + const float pixelsToTileUnits) const override; + CirclePaintProperties paint; }; diff --git a/src/mbgl/layer/fill_layer.cpp b/src/mbgl/layer/fill_layer.cpp index 0ba83e7fe4..eff80fb6d5 100644 --- a/src/mbgl/layer/fill_layer.cpp +++ b/src/mbgl/layer/fill_layer.cpp @@ -2,6 +2,9 @@ #include <mbgl/style/style_bucket_parameters.hpp> #include <mbgl/renderer/fill_bucket.hpp> #include <mbgl/util/get_geometries.hpp> +#include <mbgl/geometry/feature_index.hpp> +#include <mbgl/util/math.hpp> +#include <mbgl/util/intersection_tests.hpp> namespace mbgl { @@ -58,11 +61,31 @@ bool FillLayer::recalculate(const StyleCalculationParameters& parameters) { std::unique_ptr<Bucket> FillLayer::createBucket(StyleBucketParameters& parameters) const { auto bucket = std::make_unique<FillBucket>(); - parameters.eachFilteredFeature(filter, [&] (const auto& feature) { - bucket->addGeometry(getGeometries(feature)); + auto& name = bucketName(); + parameters.eachFilteredFeature(filter, [&] (const auto& feature, std::size_t index, const std::string& layerName) { + auto geometries = getGeometries(feature); + bucket->addGeometry(geometries); + parameters.featureIndex.insert(geometries, index, layerName, name); }); return std::move(bucket); } +float FillLayer::getQueryRadius() const { + const std::array<float, 2>& translate = paint.fillTranslate; + return util::length(translate[0], translate[1]); +} + +bool FillLayer::queryIntersectsGeometry( + const GeometryCollection& queryGeometry, + const GeometryCollection& geometry, + const float bearing, + const float pixelsToTileUnits) const { + + auto translatedQueryGeometry = FeatureIndex::translateQueryGeometry( + queryGeometry, paint.fillTranslate, paint.fillTranslateAnchor, bearing, pixelsToTileUnits); + + return util::multiPolygonIntersectsMultiPolygon(translatedQueryGeometry.value_or(queryGeometry), geometry); +} + } // namespace mbgl diff --git a/src/mbgl/layer/fill_layer.hpp b/src/mbgl/layer/fill_layer.hpp index b0740a810f..880cbe14ae 100644 --- a/src/mbgl/layer/fill_layer.hpp +++ b/src/mbgl/layer/fill_layer.hpp @@ -30,6 +30,13 @@ public: std::unique_ptr<Bucket> createBucket(StyleBucketParameters&) const override; + float getQueryRadius() const override; + bool queryIntersectsGeometry( + const GeometryCollection& queryGeometry, + const GeometryCollection& geometry, + const float bearing, + const float pixelsToTileUnits) const override; + FillPaintProperties paint; }; diff --git a/src/mbgl/layer/line_layer.cpp b/src/mbgl/layer/line_layer.cpp index 0ba49d3f97..e99a0d69f1 100644 --- a/src/mbgl/layer/line_layer.cpp +++ b/src/mbgl/layer/line_layer.cpp @@ -3,6 +3,9 @@ #include <mbgl/renderer/line_bucket.hpp> #include <mbgl/map/tile_id.hpp> #include <mbgl/util/get_geometries.hpp> +#include <mbgl/geometry/feature_index.hpp> +#include <mbgl/util/math.hpp> +#include <mbgl/util/intersection_tests.hpp> namespace mbgl { @@ -80,11 +83,76 @@ std::unique_ptr<Bucket> LineLayer::createBucket(StyleBucketParameters& parameter bucket->layout.lineMiterLimit.calculate(p); bucket->layout.lineRoundLimit.calculate(p); - parameters.eachFilteredFeature(filter, [&] (const auto& feature) { - bucket->addGeometry(getGeometries(feature)); + auto& name = bucketName(); + parameters.eachFilteredFeature(filter, [&] (const auto& feature, std::size_t index, const std::string& layerName) { + auto geometries = getGeometries(feature); + bucket->addGeometry(geometries); + parameters.featureIndex.insert(geometries, index, layerName, name); }); return std::move(bucket); } + +float LineLayer::getLineWidth() const { + if (paint.lineGapWidth > 0) { + return paint.lineGapWidth + 2 * paint.lineWidth; + } else { + return paint.lineWidth; + } +} + +optional<GeometryCollection> offsetLine(const GeometryCollection& rings, const float offset) { + if (offset == 0) return {}; + + GeometryCollection newRings; + vec2<double> zero(0, 0); + for (auto& ring : rings) { + newRings.emplace_back(); + auto& newRing = newRings.back(); + + for (auto i = ring.begin(); i != ring.end(); i++) { + auto& p = *i; + + auto aToB = i == ring.begin() ? + zero : + util::perp(util::unit(vec2<double>(p - *(i - 1)))); + auto bToC = i + 1 == ring.end() ? + zero : + util::perp(util::unit(vec2<double>(*(i + 1) - p))); + auto extrude = util::unit(aToB + bToC); + + const double cosHalfAngle = extrude.x * bToC.x + extrude.y * bToC.y; + extrude *= (1.0 / cosHalfAngle); + + newRing.push_back((extrude * offset) + p); + } + } + + return newRings; +} + +float LineLayer::getQueryRadius() const { + const std::array<float, 2>& translate = paint.lineTranslate; + return getLineWidth() / 2.0 + std::abs(paint.lineOffset) + util::length(translate[0], translate[1]); +} + +bool LineLayer::queryIntersectsGeometry( + const GeometryCollection& queryGeometry, + const GeometryCollection& geometry, + const float bearing, + const float pixelsToTileUnits) const { + + const float halfWidth = getLineWidth() / 2.0 * pixelsToTileUnits; + + auto translatedQueryGeometry = FeatureIndex::translateQueryGeometry( + queryGeometry, paint.lineTranslate, paint.lineTranslateAnchor, bearing, pixelsToTileUnits); + auto offsetGeometry = offsetLine(geometry, paint.lineOffset * pixelsToTileUnits); + + return util::multiPolygonIntersectsBufferedMultiLine( + translatedQueryGeometry.value_or(queryGeometry), + offsetGeometry.value_or(geometry), + halfWidth); +} + } // namespace mbgl diff --git a/src/mbgl/layer/line_layer.hpp b/src/mbgl/layer/line_layer.hpp index 324573d6df..00c8805e5f 100644 --- a/src/mbgl/layer/line_layer.hpp +++ b/src/mbgl/layer/line_layer.hpp @@ -42,10 +42,19 @@ public: std::unique_ptr<Bucket> createBucket(StyleBucketParameters&) const override; + float getQueryRadius() const override; + bool queryIntersectsGeometry( + const GeometryCollection& queryGeometry, + const GeometryCollection& geometry, + const float bearing, + const float pixelsToTileUnits) const override; + LineLayoutProperties layout; LinePaintProperties paint; float dashLineWidth = 1; +private: + float getLineWidth() const; }; template <> diff --git a/src/mbgl/layer/symbol_layer.cpp b/src/mbgl/layer/symbol_layer.cpp index a72e3e18ee..0a4d585d7a 100644 --- a/src/mbgl/layer/symbol_layer.cpp +++ b/src/mbgl/layer/symbol_layer.cpp @@ -116,7 +116,9 @@ bool SymbolLayer::recalculate(const StyleCalculationParameters& parameters) { std::unique_ptr<Bucket> SymbolLayer::createBucket(StyleBucketParameters& parameters) const { auto bucket = std::make_unique<SymbolBucket>(parameters.tileID.overscaleFactor(), parameters.tileID.z, - parameters.mode); + parameters.mode, + id, + parameters.layer.getName()); bucket->layout = layout; diff --git a/src/mbgl/map/map.cpp b/src/mbgl/map/map.cpp index 46eaa5049b..38198d42ec 100644 --- a/src/mbgl/map/map.cpp +++ b/src/mbgl/map/map.cpp @@ -22,6 +22,7 @@ #include <mbgl/util/exception.hpp> #include <mbgl/util/async_task.hpp> #include <mbgl/util/mapbox.hpp> +#include <mbgl/util/tile_coordinate.hpp> namespace mbgl { @@ -711,6 +712,39 @@ AnnotationIDs Map::getPointAnnotationsInBounds(const LatLngBounds& bounds) { return impl->annotationManager->getPointAnnotationsInBounds(bounds); } +#pragma mark - Feature query api + +std::vector<TileCoordinate> pointsToCoordinates(const std::vector<ScreenCoordinate>& queryPoints, const TransformState& transformState) { + std::vector<TileCoordinate> queryGeometry; + for (auto& p : queryPoints) { + queryGeometry.push_back(TileCoordinate::fromScreenCoordinate(transformState, 0, { p.x, transformState.getHeight() - p.y })); + } + return queryGeometry; +} + +std::vector<std::string> Map::queryRenderedFeatures(const ScreenCoordinate& point, const optional<std::vector<std::string>>& layerIDs) { + if (!impl->style) return {}; + + auto queryGeometry = pointsToCoordinates({ point }, impl->transform.getState()); + return impl->style->queryRenderedFeatures(queryGeometry, impl->transform.getZoom(), impl->transform.getAngle(), layerIDs); +} + +std::vector<std::string> Map::queryRenderedFeatures(const std::array<ScreenCoordinate, 2>& box, const optional<std::vector<std::string>>& layerIDs) { + if (!impl->style) return {}; + + std::vector<ScreenCoordinate> queryPoints { + { box[0].x, box[0].y }, + { box[1].x, box[0].y }, + { box[1].x, box[1].y }, + { box[0].x, box[1].y }, + { box[0].x, box[0].y } + }; + auto queryGeometry = pointsToCoordinates(queryPoints, impl->transform.getState()); + + return impl->style->queryRenderedFeatures(queryGeometry, impl->transform.getZoom(), impl->transform.getAngle(), layerIDs); +} + + #pragma mark - Style API void Map::addCustomLayer(const std::string& id, diff --git a/src/mbgl/renderer/symbol_bucket.cpp b/src/mbgl/renderer/symbol_bucket.cpp index c6d49101fc..65539e491a 100644 --- a/src/mbgl/renderer/symbol_bucket.cpp +++ b/src/mbgl/renderer/symbol_bucket.cpp @@ -36,7 +36,7 @@ SymbolInstance::SymbolInstance(Anchor& anchor, const GeometryCoordinates& line, const SymbolLayoutProperties& layout, const bool addToBuffers, const uint32_t index_, const float textBoxScale, const float textPadding, const float textAlongLine, const float iconBoxScale, const float iconPadding, const float iconAlongLine, - const GlyphPositions& face) : + const GlyphPositions& face, const IndexedSubfeature& indexedFeature) : x(anchor.x), y(anchor.y), index(index_), @@ -54,16 +54,19 @@ SymbolInstance::SymbolInstance(Anchor& anchor, const GeometryCoordinates& line, SymbolQuads()), // Create the collision features that will be used to check whether this symbol instance can be placed - textCollisionFeature(line, anchor, shapedText, textBoxScale, textPadding, textAlongLine), - iconCollisionFeature(line, anchor, shapedIcon, iconBoxScale, iconPadding, iconAlongLine) {}; + textCollisionFeature(line, anchor, shapedText, textBoxScale, textPadding, textAlongLine, indexedFeature), + iconCollisionFeature(line, anchor, shapedIcon, iconBoxScale, iconPadding, iconAlongLine, indexedFeature) + {}; -SymbolBucket::SymbolBucket(uint32_t overscaling_, float zoom_, const MapMode mode_) +SymbolBucket::SymbolBucket(uint32_t overscaling_, float zoom_, const MapMode mode_, const std::string& bucketName_, const std::string& sourceLayerName_) : overscaling(overscaling_), zoom(zoom_), tileSize(util::tileSize * overscaling_), tilePixelRatio(float(util::EXTENT) / tileSize), - mode(mode_) {} + mode(mode_), + bucketName(bucketName_), + sourceLayerName(sourceLayerName_) {} SymbolBucket::~SymbolBucket() { // Do not remove. header file only contains forward definitions to unique pointers. @@ -109,6 +112,8 @@ void SymbolBucket::parseFeatures(const GeometryTileLayer& layer, const Filter& f return; } + auto layerName = layer.getName(); + // Determine and load glyph ranges const GLsizei featureCount = static_cast<GLsizei>(layer.featureCount()); for (GLsizei i = 0; i < featureCount; i++) { @@ -119,6 +124,7 @@ void SymbolBucket::parseFeatures(const GeometryTileLayer& layer, const Filter& f continue; SymbolFeature ft; + ft.index = i; auto getValue = [&feature](const std::string& key) -> std::string { auto value = feature->getValue(key); @@ -283,7 +289,7 @@ void SymbolBucket::addFeatures(uintptr_t tileUID, // if either shapedText or icon position is present, add the feature if (shapedText || shapedIcon) { - addFeature(feature.geometry, shapedText, shapedIcon, face); + addFeature(feature.geometry, shapedText, shapedIcon, face, feature.index); } } @@ -292,7 +298,7 @@ void SymbolBucket::addFeatures(uintptr_t tileUID, void SymbolBucket::addFeature(const GeometryCollection &lines, - const Shaping &shapedText, const PositionedIcon &shapedIcon, const GlyphPositions &face) { + const Shaping &shapedText, const PositionedIcon &shapedIcon, const GlyphPositions &face, const size_t index) { const float minScale = 0.5f; const float glyphSize = 24.0f; @@ -321,6 +327,8 @@ void SymbolBucket::addFeature(const GeometryCollection &lines, util::clipLines(lines, 0, 0, util::EXTENT, util::EXTENT) : lines; + IndexedSubfeature indexedFeature = {index, sourceLayerName, bucketName, symbolInstances.size()}; + for (const auto& line : clippedLines) { if (line.empty()) continue; @@ -357,7 +365,7 @@ void SymbolBucket::addFeature(const GeometryCollection &lines, symbolInstances.emplace_back(anchor, line, shapedText, shapedIcon, layout, addToBuffers, symbolInstances.size(), textBoxScale, textPadding, textAlongLine, iconBoxScale, iconPadding, iconAlongLine, - face); + face, indexedFeature); } } } @@ -445,9 +453,7 @@ void SymbolBucket::placeFeatures(CollisionTile& collisionTile) { // Insert final placement into collision tree and add glyphs/icons to buffers if (hasText) { - if (!layout.textIgnorePlacement) { - collisionTile.insertFeature(symbolInstance.textCollisionFeature, glyphScale); - } + collisionTile.insertFeature(symbolInstance.textCollisionFeature, glyphScale, layout.textIgnorePlacement); if (glyphScale < collisionTile.maxScale) { addSymbols<SymbolRenderData::TextBuffer, TextElementGroup>( renderDataInProgress->text, symbolInstance.glyphQuads, glyphScale, @@ -456,9 +462,7 @@ void SymbolBucket::placeFeatures(CollisionTile& collisionTile) { } if (hasIcon) { - if (!layout.iconIgnorePlacement) { - collisionTile.insertFeature(symbolInstance.iconCollisionFeature, iconScale); - } + collisionTile.insertFeature(symbolInstance.iconCollisionFeature, iconScale, layout.iconIgnorePlacement); if (iconScale < collisionTile.maxScale) { addSymbols<SymbolRenderData::IconBuffer, IconElementGroup>( renderDataInProgress->icon, symbolInstance.iconQuads, iconScale, diff --git a/src/mbgl/renderer/symbol_bucket.hpp b/src/mbgl/renderer/symbol_bucket.hpp index 1b37a1e005..709f9fc65a 100644 --- a/src/mbgl/renderer/symbol_bucket.hpp +++ b/src/mbgl/renderer/symbol_bucket.hpp @@ -32,12 +32,14 @@ class SpriteAtlas; class SpriteStore; class GlyphAtlas; class GlyphStore; +class IndexedSubfeature; class SymbolFeature { public: GeometryCollection geometry; std::u32string label; std::string sprite; + std::size_t index; }; struct Anchor; @@ -49,7 +51,7 @@ class SymbolInstance { const SymbolLayoutProperties& layout, const bool inside, const uint32_t index, const float textBoxScale, const float textPadding, const float textAlongLine, const float iconBoxScale, const float iconPadding, const float iconAlongLine, - const GlyphPositions& face); + const GlyphPositions& face, const IndexedSubfeature& indexedfeature); float x; float y; uint32_t index; @@ -67,7 +69,7 @@ class SymbolBucket : public Bucket { typedef ElementGroup<1> CollisionBoxElementGroup; public: - SymbolBucket(uint32_t overscaling, float zoom, const MapMode); + SymbolBucket(uint32_t overscaling, float zoom, const MapMode, const std::string& bucketName_, const std::string& sourceLayerName_); ~SymbolBucket() override; void upload(gl::GLObjectStore&) override; @@ -95,7 +97,8 @@ public: private: void addFeature(const GeometryCollection &lines, const Shaping &shapedText, const PositionedIcon &shapedIcon, - const GlyphPositions &face); + const GlyphPositions &face, + const size_t index); bool anchorIsTooClose(const std::u32string &text, const float repeatDistance, Anchor &anchor); std::map<std::u32string, std::vector<Anchor>> compareText; @@ -124,6 +127,8 @@ private: const uint32_t tileSize; const float tilePixelRatio; const MapMode mode; + const std::string bucketName; + const std::string sourceLayerName; std::set<GlyphRange> ranges; std::vector<SymbolInstance> symbolInstances; diff --git a/src/mbgl/source/source.cpp b/src/mbgl/source/source.cpp index 47efbe9088..18de7bc093 100644 --- a/src/mbgl/source/source.cpp +++ b/src/mbgl/source/source.cpp @@ -14,6 +14,7 @@ #include <mbgl/style/style_layer.hpp> #include <mbgl/style/style_update_parameters.hpp> #include <mbgl/platform/log.hpp> +#include <mbgl/util/math.hpp> #include <mbgl/util/std.hpp> #include <mbgl/util/token.hpp> #include <mbgl/util/string.hpp> @@ -478,6 +479,86 @@ void Source::updateTilePtrs() { } } +vec2<int16_t> coordinateToTilePoint(const TileID& tileID, const TileCoordinate& coord) { + auto zoomedCoord = coord.zoomTo(tileID.sourceZ); + return { + int16_t(util::clamp<int64_t>((zoomedCoord.x - (tileID.x + tileID.w * std::pow(2, tileID.sourceZ))) * util::EXTENT, + std::numeric_limits<int16_t>::min(), + std::numeric_limits<int16_t>::max())), + int16_t(util::clamp<int64_t>((zoomedCoord.y - tileID.y) * util::EXTENT, + std::numeric_limits<int16_t>::min(), + std::numeric_limits<int16_t>::max())) + }; +} + +struct TileQuery { + Tile* tile; + GeometryCollection queryGeometry; + double tileSize; + double scale; +}; + +std::unordered_map<std::string, std::vector<std::string>> Source::queryRenderedFeatures( + const std::vector<TileCoordinate>& queryGeometry, + const double zoom, + const double bearing, + const optional<std::vector<std::string>>& layerIDs) { + + std::unordered_map<std::string, std::vector<std::string>> result; + + double minX = std::numeric_limits<double>::infinity(); + double minY = std::numeric_limits<double>::infinity(); + double maxX = -std::numeric_limits<double>::infinity(); + double maxY = -std::numeric_limits<double>::infinity(); + double z = queryGeometry[0].z; + + for (auto& c : queryGeometry) { + minX = util::min(minX, c.x); + minY = util::min(minY, c.y); + maxX = util::max(maxX, c.x); + maxY = util::max(maxY, c.y); + } + + std::unordered_map<uint64_t, TileQuery> tileQueries; + + for (auto& tilePtr : tilePtrs) { + auto& tile = *tilePtr; + uint64_t integerID = tile.id.to_uint64(); + + auto tileSpaceBoundsMin = coordinateToTilePoint(tile.id, { minX, minY, z }); + auto tileSpaceBoundsMax = coordinateToTilePoint(tile.id, { maxX, maxY, z }); + + if (tileSpaceBoundsMin.x >= util::EXTENT || tileSpaceBoundsMin.y >= util::EXTENT || + tileSpaceBoundsMax.x < 0 || tileSpaceBoundsMax.y < 0) continue; + + GeometryCoordinates tileSpaceQueryGeometry; + + for (auto& c : queryGeometry) { + tileSpaceQueryGeometry.push_back(coordinateToTilePoint(tile.id, c)); + } + + auto it = tileQueries.find(integerID); + if (it != tileQueries.end()) { + it->second.queryGeometry.push_back(std::move(tileSpaceQueryGeometry)); + } else { + tileQueries.emplace(integerID, TileQuery{ + tilePtr, + { tileSpaceQueryGeometry }, + util::tileSize * std::pow(2, tile.id.z - tile.id.sourceZ), + std::pow(2, zoom - tile.id.z) + }); + } + } + + + for (auto& it : tileQueries) { + auto& tileQuery = std::get<1>(it); + tileQuery.tile->data->queryRenderedFeatures(result, tileQuery.queryGeometry, bearing, tileQuery.tileSize, tileQuery.scale, layerIDs); + } + + return result; +} + void Source::setCacheSize(size_t size) { cache.setSize(size); } diff --git a/src/mbgl/source/source.hpp b/src/mbgl/source/source.hpp index 1aad191a5c..a4b6961245 100644 --- a/src/mbgl/source/source.hpp +++ b/src/mbgl/source/source.hpp @@ -20,12 +20,14 @@ class GeoJSONVT; namespace mbgl { +class Style; class StyleUpdateParameters; class Painter; class FileSource; class AsyncRequest; class TransformState; class Tile; +class TileCoordinate; struct ClipID; struct box; @@ -70,6 +72,12 @@ public: std::forward_list<Tile *> getLoadedTiles() const; const std::vector<Tile*>& getTiles() const; + std::unordered_map<std::string, std::vector<std::string>> queryRenderedFeatures( + const std::vector<TileCoordinate>& queryGeometry, + const double zoom, + const double bearing, + const optional<std::vector<std::string>>& layerIDs); + void setCacheSize(size_t); void onLowMemory(); diff --git a/src/mbgl/style/style.cpp b/src/mbgl/style/style.cpp index 553be89dd4..4d515b4e60 100644 --- a/src/mbgl/style/style.cpp +++ b/src/mbgl/style/style.cpp @@ -314,6 +314,44 @@ RenderData Style::getRenderData() const { return result; } +std::vector<std::string> Style::queryRenderedFeatures( + const std::vector<TileCoordinate>& queryGeometry, + const double zoom, + const double bearing, + const optional<std::vector<std::string>>& layerIDs) { + std::vector<std::unordered_map<std::string, std::vector<std::string>>> sourceResults; + for (const auto& source : sources) { + sourceResults.emplace_back(source->queryRenderedFeatures(queryGeometry, zoom, bearing, layerIDs)); + } + + + std::vector<std::string> features; + auto featuresInserter = std::back_inserter(features); + + // Combine all results based on the style layer order. + for (auto& layerPtr : layers) { + auto& layerID = layerPtr->id; + for (auto& sourceResult : sourceResults) { + auto it = sourceResult.find(layerID); + if (it != sourceResult.end()) { + auto& layerFeatures = it->second; + std::move(layerFeatures.begin(), layerFeatures.end(), featuresInserter); + } + } + } + + return features; +} + +float Style::getQueryRadius() const { + float additionalRadius = 0; + for (auto& layer : layers) { + additionalRadius = util::max(additionalRadius, layer->getQueryRadius()); + } + return additionalRadius; +} + + void Style::setSourceTileCacheSize(size_t size) { for (const auto& source : sources) { source->setCacheSize(size); diff --git a/src/mbgl/style/style.hpp b/src/mbgl/style/style.hpp index 790518d08e..5dac4d4790 100644 --- a/src/mbgl/style/style.hpp +++ b/src/mbgl/style/style.hpp @@ -30,6 +30,7 @@ class StyleLayer; class Tile; class Bucket; class StyleUpdateParameters; +class TileCoordinate; struct RenderItem { inline RenderItem(const StyleLayer& layer_, @@ -107,6 +108,14 @@ public: RenderData getRenderData() const; + std::vector<std::string> queryRenderedFeatures( + const std::vector<TileCoordinate>& queryGeometry, + const double zoom, + const double bearing, + const optional<std::vector<std::string>>& layerIDs); + + float getQueryRadius() const; + void setSourceTileCacheSize(size_t); void onLowMemory(); diff --git a/src/mbgl/style/style_bucket_parameters.cpp b/src/mbgl/style/style_bucket_parameters.cpp index 8591dd430c..cf5184bd8b 100644 --- a/src/mbgl/style/style_bucket_parameters.cpp +++ b/src/mbgl/style/style_bucket_parameters.cpp @@ -5,7 +5,8 @@ namespace mbgl { void StyleBucketParameters::eachFilteredFeature(const Filter& filter, - std::function<void (const GeometryTileFeature&)> function) { + std::function<void (const GeometryTileFeature&, std::size_t index, const std::string& layerName)> function) { + auto name = layer.getName(); for (std::size_t i = 0; !cancelled() && i < layer.featureCount(); i++) { auto feature = layer.getFeature(i); @@ -13,7 +14,7 @@ void StyleBucketParameters::eachFilteredFeature(const Filter& filter, if (!Filter::visit(filter, evaluator)) continue; - function(*feature); + function(*feature, i, name); } } diff --git a/src/mbgl/style/style_bucket_parameters.hpp b/src/mbgl/style/style_bucket_parameters.hpp index c77980f37c..402e5810d3 100644 --- a/src/mbgl/style/style_bucket_parameters.hpp +++ b/src/mbgl/style/style_bucket_parameters.hpp @@ -16,6 +16,7 @@ class SpriteStore; class GlyphAtlas; class GlyphStore; class CollisionTile; +class FeatureIndex; class StyleBucketParameters { public: @@ -27,6 +28,7 @@ public: SpriteStore& spriteStore_, GlyphAtlas& glyphAtlas_, GlyphStore& glyphStore_, + FeatureIndex& featureIndex_, const MapMode mode_) : tileID(tileID_), layer(layer_), @@ -36,13 +38,14 @@ public: spriteStore(spriteStore_), glyphAtlas(glyphAtlas_), glyphStore(glyphStore_), + featureIndex(featureIndex_), mode(mode_) {} bool cancelled() const { return state == TileData::State::obsolete; } - void eachFilteredFeature(const Filter&, std::function<void (const GeometryTileFeature&)>); + void eachFilteredFeature(const Filter&, std::function<void (const GeometryTileFeature&, std::size_t index, const std::string& layerName)>); const TileID& tileID; const GeometryTileLayer& layer; @@ -52,6 +55,7 @@ public: SpriteStore& spriteStore; GlyphAtlas& glyphAtlas; GlyphStore& glyphStore; + FeatureIndex& featureIndex; const MapMode mode; }; diff --git a/src/mbgl/style/style_layer.hpp b/src/mbgl/style/style_layer.hpp index 9313138587..a568126e51 100644 --- a/src/mbgl/style/style_layer.hpp +++ b/src/mbgl/style/style_layer.hpp @@ -6,6 +6,7 @@ #include <mbgl/renderer/render_pass.hpp> #include <mbgl/util/noncopyable.hpp> #include <mbgl/util/rapidjson.hpp> +#include <mbgl/tile/geometry_tile.hpp> #include <memory> #include <string> @@ -60,6 +61,13 @@ public: // Checks whether this layer can be rendered. bool needsRendering() const; + virtual float getQueryRadius() const { return 0; } + virtual bool queryIntersectsGeometry( + const GeometryCollection&, + const GeometryCollection&, + const float, + const float) const { return false; }; + public: std::string id; std::string ref; diff --git a/src/mbgl/text/collision_feature.cpp b/src/mbgl/text/collision_feature.cpp index 42f1119b33..09c04ede78 100644 --- a/src/mbgl/text/collision_feature.cpp +++ b/src/mbgl/text/collision_feature.cpp @@ -5,7 +5,8 @@ namespace mbgl { CollisionFeature::CollisionFeature(const GeometryCoordinates &line, const Anchor &anchor, const float top, const float bottom, const float left, const float right, - const float boxScale, const float padding, const bool alongLine, const bool straight) { + const float boxScale, const float padding, const bool alongLine, const IndexedSubfeature& indexedFeature, + const bool straight) { if (top == 0 && bottom == 0 && left == 0 && right == 0) return; @@ -28,18 +29,19 @@ CollisionFeature::CollisionFeature(const GeometryCoordinates &line, const Anchor // used for icon labels that are aligned with the line, but don't curve along it const vec2<double> vector = util::unit(vec2<double>(line[anchor.segment + 1] - line[anchor.segment])) * length; const GeometryCoordinates newLine({ anchorPoint - vector, anchorPoint + vector }); - bboxifyLabel(newLine, anchorPoint, 0, length, height); + bboxifyLabel(newLine, anchorPoint, 0, length, height, indexedFeature); } else { // used for text labels that curve along a line - bboxifyLabel(line, anchorPoint, anchor.segment, length, height); + bboxifyLabel(line, anchorPoint, anchor.segment, length, height, indexedFeature); } } else { - boxes.emplace_back(anchor, x1, y1, x2, y2, std::numeric_limits<float>::infinity()); + boxes.emplace_back(anchor, x1, y1, x2, y2, std::numeric_limits<float>::infinity(), indexedFeature); } } void CollisionFeature::bboxifyLabel(const GeometryCoordinates &line, - GeometryCoordinate &anchorPoint, const int segment, const float labelLength, const float boxSize) { + GeometryCoordinate &anchorPoint, const int segment, const float labelLength, const float boxSize, + const IndexedSubfeature& indexedFeature) { const float step = boxSize / 2; const unsigned int nBoxes = std::floor(labelLength / step); @@ -95,7 +97,7 @@ void CollisionFeature::bboxifyLabel(const GeometryCoordinates &line, const float distanceToInnerEdge = std::max(std::fabs(boxDistanceToAnchor - firstBoxOffset) - step / 2, 0.0f); const float maxScale = labelLength / 2 / distanceToInnerEdge; - boxes.emplace_back(boxAnchor, -boxSize / 2, -boxSize / 2, boxSize / 2, boxSize / 2, maxScale); + boxes.emplace_back(boxAnchor, -boxSize / 2, -boxSize / 2, boxSize / 2, boxSize / 2, maxScale, indexedFeature); } } diff --git a/src/mbgl/text/collision_feature.hpp b/src/mbgl/text/collision_feature.hpp index fcfb8e9ae9..0cd0b5554c 100644 --- a/src/mbgl/text/collision_feature.hpp +++ b/src/mbgl/text/collision_feature.hpp @@ -5,14 +5,16 @@ #include <mbgl/geometry/anchor.hpp> #include <mbgl/text/shaping.hpp> #include <mbgl/tile/geometry_tile.hpp> +#include <mbgl/geometry/feature_index.hpp> #include <vector> namespace mbgl { class CollisionBox { public: - explicit CollisionBox(const vec2<float> &_anchor, float _x1, float _y1, float _x2, float _y2, float _maxScale) : - anchor(_anchor), x1(_x1), y1(_y1), x2(_x2), y2(_y2), maxScale(_maxScale) {} + explicit CollisionBox(const vec2<float> &_anchor, float _x1, float _y1, float _x2, float _y2, float _maxScale, + const IndexedSubfeature& indexedFeature_ = { 0, "", "", 0 }) : + anchor(_anchor), x1(_x1), y1(_y1), x2(_x2), y2(_y2), maxScale(_maxScale), indexedFeature(indexedFeature_) {} // the box is centered around the anchor point vec2<float> anchor; @@ -29,6 +31,8 @@ namespace mbgl { // the scale at which the label can first be shown float placementScale = 0.0f; + + IndexedSubfeature indexedFeature; }; class CollisionFeature { @@ -36,28 +40,31 @@ namespace mbgl { // for text inline explicit CollisionFeature(const GeometryCoordinates &line, const Anchor &anchor, const Shaping &shapedText, - const float boxScale, const float padding, const bool alongLine) + const float boxScale, const float padding, const bool alongLine, const IndexedSubfeature& indexedFeature) : CollisionFeature(line, anchor, shapedText.top, shapedText.bottom, shapedText.left, shapedText.right, - boxScale, padding, alongLine, false) {} + boxScale, padding, alongLine, indexedFeature, false) {} // for icons inline explicit CollisionFeature(const GeometryCoordinates &line, const Anchor &anchor, const PositionedIcon &shapedIcon, - const float boxScale, const float padding, const bool alongLine) + const float boxScale, const float padding, const bool alongLine, const IndexedSubfeature& indexedFeature) : CollisionFeature(line, anchor, shapedIcon.top, shapedIcon.bottom, shapedIcon.left, shapedIcon.right, - boxScale, padding, alongLine, true) {} + boxScale, padding, alongLine, indexedFeature, true) {} explicit CollisionFeature(const GeometryCoordinates &line, const Anchor &anchor, const float top, const float bottom, const float left, const float right, - const float boxScale, const float padding, const bool alongLine, const bool straight); + const float boxScale, const float padding, const bool alongLine, + const IndexedSubfeature&, const bool straight); std::vector<CollisionBox> boxes; private: - void bboxifyLabel(const GeometryCoordinates &line, GeometryCoordinate &anchorPoint, const int segment, const float length, const float height); + void bboxifyLabel(const GeometryCoordinates &line, GeometryCoordinate &anchorPoint, + const int segment, const float length, const float height, + const IndexedSubfeature&); }; } // namespace mbgl diff --git a/src/mbgl/text/collision_tile.cpp b/src/mbgl/text/collision_tile.cpp index d02307d2ed..6b9240df1f 100644 --- a/src/mbgl/text/collision_tile.cpp +++ b/src/mbgl/text/collision_tile.cpp @@ -1,4 +1,5 @@ #include <mbgl/text/collision_tile.hpp> +#include <mbgl/geometry/feature_index.hpp> #include <mbgl/util/constants.hpp> #include <cmath> @@ -121,7 +122,7 @@ float CollisionTile::placeFeature(const CollisionFeature &feature, const bool al return minPlacementScale; } -void CollisionTile::insertFeature(CollisionFeature &feature, const float minPlacementScale) { +void CollisionTile::insertFeature(CollisionFeature &feature, const float minPlacementScale, const bool ignorePlacement) { for (auto& box : feature.boxes) { box.placementScale = minPlacementScale; } @@ -131,22 +132,58 @@ void CollisionTile::insertFeature(CollisionFeature &feature, const float minPlac for (auto& box : feature.boxes) { treeBoxes.emplace_back(getTreeBox(box.anchor.matMul(rotationMatrix), box), box); } - tree.insert(treeBoxes.begin(), treeBoxes.end()); + if (ignorePlacement) { + ignoredTree.insert(treeBoxes.begin(), treeBoxes.end()); + } else { + tree.insert(treeBoxes.begin(), treeBoxes.end()); + } } } -Box CollisionTile::getTreeBox(const vec2<float> &anchor, const CollisionBox &box) { +Box CollisionTile::getTreeBox(const vec2<float> &anchor, const CollisionBox &box, const float scale) { return Box{ CollisionPoint{ - anchor.x + box.x1, - anchor.y + box.y1 * yStretch + anchor.x + box.x1 / scale, + anchor.y + box.y1 / scale * yStretch }, CollisionPoint{ - anchor.x + box.x2, - anchor.y + box.y2 * yStretch + anchor.x + box.x2 / scale, + anchor.y + box.y2 / scale * yStretch } }; } +std::vector<IndexedSubfeature> CollisionTile::queryRenderedSymbols(const float minX, const float minY, const float maxX, const float maxY, const float scale) { + + std::vector<IndexedSubfeature> result; + + auto anchor = vec2<float>(minX, minY).matMul(rotationMatrix); + CollisionBox queryBox(anchor, 0, 0, maxX - minX, maxY - minY, scale); + + std::vector<CollisionTreeBox> blockingBoxes; + tree.query(bgi::intersects(getTreeBox(anchor, queryBox)), std::back_inserter(blockingBoxes)); + ignoredTree.query(bgi::intersects(getTreeBox(anchor, queryBox)), std::back_inserter(blockingBoxes)); + + std::unordered_map<std::string, std::set<std::size_t>> sourceLayerFeatures; + + for (auto& blockingTreeBox : blockingBoxes) { + const auto& blocking = std::get<1>(blockingTreeBox); + + auto& indexedFeature = blocking.indexedFeature; + + auto& seenFeatures = sourceLayerFeatures[indexedFeature.sourceLayerName]; + if (seenFeatures.find(indexedFeature.index) == seenFeatures.end()) { + auto blockingAnchor = blocking.anchor.matMul(rotationMatrix); + float minPlacementScale = findPlacementScale(minScale, anchor, queryBox, blockingAnchor, blocking); + if (minPlacementScale >= scale) { + seenFeatures.insert(indexedFeature.index); + result.push_back(indexedFeature); + } + } + } + + return result; +} + } // namespace mbgl diff --git a/src/mbgl/text/collision_tile.hpp b/src/mbgl/text/collision_tile.hpp index eb5d4bc64c..4bc25ddcb7 100644 --- a/src/mbgl/text/collision_tile.hpp +++ b/src/mbgl/text/collision_tile.hpp @@ -33,12 +33,16 @@ typedef bgm::box<CollisionPoint> Box; typedef std::pair<Box, CollisionBox> CollisionTreeBox; typedef bgi::rtree<CollisionTreeBox, bgi::linear<16, 4>> Tree; +class IndexedSubfeature; + class CollisionTile { public: explicit CollisionTile(PlacementConfig); float placeFeature(const CollisionFeature& feature, const bool allowOverlap, const bool avoidEdges); - void insertFeature(CollisionFeature& feature, const float minPlacementScale); + void insertFeature(CollisionFeature& feature, const float minPlacementScale, const bool ignorePlacement); + + std::vector<IndexedSubfeature> queryRenderedSymbols(const float minX, const float minY, const float maxX, const float maxY, const float scale); const PlacementConfig config; @@ -50,9 +54,10 @@ private: float findPlacementScale(float minPlacementScale, const vec2<float>& anchor, const CollisionBox& box, const vec2<float>& blockingAnchor, const CollisionBox& blocking); - Box getTreeBox(const vec2<float>& anchor, const CollisionBox& box); + Box getTreeBox(const vec2<float>& anchor, const CollisionBox& box, const float scale = 1.0); Tree tree; + Tree ignoredTree; std::array<float, 4> rotationMatrix; std::array<float, 4> reverseRotationMatrix; std::array<CollisionBox, 4> edges; diff --git a/src/mbgl/tile/geojson_tile.hpp b/src/mbgl/tile/geojson_tile.hpp index 340d1053c6..f6d9d9cce7 100644 --- a/src/mbgl/tile/geojson_tile.hpp +++ b/src/mbgl/tile/geojson_tile.hpp @@ -39,6 +39,7 @@ public: GeoJSONTileLayer(Features&&); std::size_t featureCount() const override; util::ptr<const GeometryTileFeature> getFeature(std::size_t) const override; + std::string getName() const override { return ""; }; private: const Features features; diff --git a/src/mbgl/tile/geometry_tile.hpp b/src/mbgl/tile/geometry_tile.hpp index 71077d03ac..57d8eab1cc 100644 --- a/src/mbgl/tile/geometry_tile.hpp +++ b/src/mbgl/tile/geometry_tile.hpp @@ -13,6 +13,7 @@ #include <cstdint> #include <string> #include <vector> +#include <unordered_map> #include <functional> namespace mbgl { @@ -38,6 +39,8 @@ public: virtual ~GeometryTileFeature() = default; virtual FeatureType getType() const = 0; virtual optional<Value> getValue(const std::string& key) const = 0; + virtual std::unordered_map<std::string,Value> getProperties() const { return std::unordered_map<std::string,Value>{}; }; + virtual uint64_t getID() const { return 0; } virtual GeometryCollection getGeometries() const = 0; virtual uint32_t getExtent() const { return defaultExtent; } }; @@ -47,6 +50,7 @@ public: virtual ~GeometryTileLayer() = default; virtual std::size_t featureCount() const = 0; virtual util::ptr<const GeometryTileFeature> getFeature(std::size_t) const = 0; + virtual std::string getName() const = 0; }; class GeometryTile : private util::noncopyable { diff --git a/src/mbgl/tile/tile_data.cpp b/src/mbgl/tile/tile_data.cpp index 46ce64771c..cb12e301f2 100644 --- a/src/mbgl/tile/tile_data.cpp +++ b/src/mbgl/tile/tile_data.cpp @@ -29,4 +29,12 @@ void TileData::dumpDebugLogs() const { Log::Info(Event::General, "TileData::state: %s", TileData::StateToString(state)); } +void TileData::queryRenderedFeatures( + std::unordered_map<std::string, std::vector<std::string>>&, + const GeometryCollection&, + const double, + const double, + const double, + const optional<std::vector<std::string>>&) {} + } // namespace mbgl diff --git a/src/mbgl/tile/tile_data.hpp b/src/mbgl/tile/tile_data.hpp index 201507f799..26c0032e35 100644 --- a/src/mbgl/tile/tile_data.hpp +++ b/src/mbgl/tile/tile_data.hpp @@ -7,11 +7,13 @@ #include <mbgl/map/tile_id.hpp> #include <mbgl/renderer/bucket.hpp> #include <mbgl/text/placement_config.hpp> +#include <mbgl/tile/geometry_tile.hpp> #include <atomic> #include <string> #include <memory> #include <functional> +#include <unordered_map> namespace mbgl { @@ -82,6 +84,14 @@ public: virtual void redoPlacement(PlacementConfig, const std::function<void()>&) {} virtual void redoPlacement(const std::function<void()>&) {} + virtual void queryRenderedFeatures( + std::unordered_map<std::string, std::vector<std::string>>& result, + const GeometryCollection& queryGeometry, + const double bearing, + const double tileSize, + const double scale, + const optional<std::vector<std::string>>& layerIDs); + bool isReady() const { return isReadyState(state); } diff --git a/src/mbgl/tile/tile_worker.cpp b/src/mbgl/tile/tile_worker.cpp index 917b61fde9..2a631de7bd 100644 --- a/src/mbgl/tile/tile_worker.cpp +++ b/src/mbgl/tile/tile_worker.cpp @@ -37,12 +37,14 @@ TileWorker::~TileWorker() { } TileParseResult TileWorker::parseAllLayers(std::vector<std::unique_ptr<StyleLayer>> layers_, - std::unique_ptr<const GeometryTile> geometryTile, + std::unique_ptr<const GeometryTile> geometryTile_, PlacementConfig config) { // We're doing a fresh parse of the tile, because the underlying data has changed. pending.clear(); placementPending.clear(); partialParse = false; + featureIndex = std::make_unique<FeatureIndex>(); + geometryTile = std::move(geometryTile_); // Store the layers for use in redoPlacement. layers = std::move(layers_); @@ -55,17 +57,12 @@ TileParseResult TileWorker::parseAllLayers(std::vector<std::unique_ptr<StyleLaye const StyleLayer* layer = i->get(); if (parsed.find(layer->bucketName()) == parsed.end()) { parsed.emplace(layer->bucketName()); - parseLayer(layer, *geometryTile); + parseLayer(layer); } + featureIndex->addBucketLayerName(layer->bucketName(), layer->id); } - result.state = pending.empty() ? TileData::State::parsed : TileData::State::partial; - - if (result.state == TileData::State::parsed) { - placeLayers(config); - } - - return std::move(result); + return prepareResult(config); } TileParseResult TileWorker::parsePendingLayers(const PlacementConfig config) { @@ -90,39 +87,49 @@ TileParseResult TileWorker::parsePendingLayers(const PlacementConfig config) { ++it; } + return prepareResult(config); +} + +TileParseResult TileWorker::prepareResult(const PlacementConfig& config) { result.state = pending.empty() ? TileData::State::parsed : TileData::State::partial; if (result.state == TileData::State::parsed) { - placeLayers(config); + featureIndex->setCollisionTile(placeLayers(config)); + featureIndex->loadTree(); + result.featureIndex = std::move(featureIndex); + result.geometryTile = std::move(geometryTile); } return std::move(result); } -void TileWorker::placeLayers(const PlacementConfig config) { - redoPlacement(&placementPending, config); +std::unique_ptr<CollisionTile> TileWorker::placeLayers(const PlacementConfig config) { + auto collisionTile = redoPlacement(&placementPending, config); for (auto &p : placementPending) { p.second->swapRenderData(); insertBucket(p.first, std::move(p.second)); } placementPending.clear(); + return collisionTile; } -void TileWorker::redoPlacement( +std::unique_ptr<CollisionTile> TileWorker::redoPlacement( const std::unordered_map<std::string, std::unique_ptr<Bucket>>* buckets, PlacementConfig config) { - CollisionTile collisionTile(config); + auto collisionTile = std::make_unique<CollisionTile>(config); for (auto i = layers.rbegin(); i != layers.rend(); i++) { const auto it = buckets->find((*i)->id); if (it != buckets->end()) { - it->second->placeFeatures(collisionTile); + it->second->placeFeatures(*collisionTile); } } + + return collisionTile; } -void TileWorker::parseLayer(const StyleLayer* layer, const GeometryTile& geometryTile) { +void TileWorker::parseLayer(const StyleLayer* layer) { // Cancel early when parsing. if (state == TileData::State::obsolete) return; @@ -139,7 +146,7 @@ void TileWorker::parseLayer(const StyleLayer* layer, const GeometryTile& geometr return; } - auto geometryLayer = geometryTile.getLayer(layer->sourceLayer); + auto geometryLayer = geometryTile->getLayer(layer->sourceLayer); if (!geometryLayer) { // The layer specified in the bucket does not exist. Do nothing. if (debug::tileParseWarnings) { @@ -157,6 +164,7 @@ void TileWorker::parseLayer(const StyleLayer* layer, const GeometryTile& geometr spriteStore, glyphAtlas, glyphStore, + *featureIndex, mode); std::unique_ptr<Bucket> bucket = layer->createBucket(parameters); diff --git a/src/mbgl/tile/tile_worker.hpp b/src/mbgl/tile/tile_worker.hpp index 2943b100ab..7c4b147d08 100644 --- a/src/mbgl/tile/tile_worker.hpp +++ b/src/mbgl/tile/tile_worker.hpp @@ -7,6 +7,7 @@ #include <mbgl/util/variant.hpp> #include <mbgl/util/ptr.hpp> #include <mbgl/text/placement_config.hpp> +#include <mbgl/geometry/feature_index.hpp> #include <string> #include <memory> @@ -27,14 +28,16 @@ class SymbolLayer; // We're using this class to shuttle the resulting buckets from the worker thread to the MapContext // thread. This class is movable-only because the vector contains movable-only value elements. -class TileParseResultBuckets { +class TileParseResultData { public: TileData::State state = TileData::State::invalid; std::unordered_map<std::string, std::unique_ptr<Bucket>> buckets; + std::unique_ptr<FeatureIndex> featureIndex; + std::unique_ptr<const GeometryTile> geometryTile; }; using TileParseResult = variant< - TileParseResultBuckets, // success + TileParseResultData, // success std::exception_ptr>; // error class TileWorker : public util::noncopyable { @@ -54,13 +57,14 @@ public: TileParseResult parsePendingLayers(PlacementConfig); - void redoPlacement(const std::unordered_map<std::string, std::unique_ptr<Bucket>>*, + std::unique_ptr<CollisionTile> redoPlacement(const std::unordered_map<std::string, std::unique_ptr<Bucket>>*, PlacementConfig); private: - void parseLayer(const StyleLayer*, const GeometryTile&); + TileParseResult prepareResult(const PlacementConfig& config); + void parseLayer(const StyleLayer*); void insertBucket(const std::string& name, std::unique_ptr<Bucket>); - void placeLayers(PlacementConfig); + std::unique_ptr<CollisionTile> placeLayers(PlacementConfig); const TileID id; const std::string sourceID; @@ -75,6 +79,9 @@ private: std::vector<std::unique_ptr<StyleLayer>> layers; + std::unique_ptr<FeatureIndex> featureIndex; + std::unique_ptr<const GeometryTile> geometryTile; + // Contains buckets that we couldn't parse so far due to missing resources. // They will be attempted on subsequent parses. std::list<std::pair<const SymbolLayer*, std::unique_ptr<Bucket>>> pending; @@ -84,7 +91,7 @@ private: std::unordered_map<std::string, std::unique_ptr<Bucket>> placementPending; // Temporary holder - TileParseResultBuckets result; + TileParseResultData result; }; } // namespace mbgl diff --git a/src/mbgl/tile/vector_tile.cpp b/src/mbgl/tile/vector_tile.cpp index 4c6027d36c..f3a02c5d76 100644 --- a/src/mbgl/tile/vector_tile.cpp +++ b/src/mbgl/tile/vector_tile.cpp @@ -54,8 +54,8 @@ VectorTileFeature::VectorTileFeature(pbf feature_pbf, const VectorTileLayer& lay } optional<Value> VectorTileFeature::getValue(const std::string& key) const { - auto keyIter = layer.keys.find(key); - if (keyIter == layer.keys.end()) { + auto keyIter = layer.keysMap.find(key); + if (keyIter == layer.keysMap.end()) { return optional<Value>(); } @@ -63,7 +63,7 @@ optional<Value> VectorTileFeature::getValue(const std::string& key) const { while (tags) { uint32_t tag_key = tags.varint(); - if (layer.keys.size() <= tag_key) { + if (layer.keysMap.size() <= tag_key) { throw std::runtime_error("feature referenced out of range key"); } @@ -84,6 +84,21 @@ optional<Value> VectorTileFeature::getValue(const std::string& key) const { return optional<Value>(); } +std::unordered_map<std::string,Value> VectorTileFeature::getProperties() const { + std::unordered_map<std::string,Value> properties; + pbf tags = tags_pbf; + while (tags) { + uint32_t tag_key = tags.varint(); + uint32_t tag_val = tags.varint(); + properties[layer.keys.at(tag_key)] = layer.values.at(tag_val); + } + return properties; +} + +uint64_t VectorTileFeature::getID() const { + return id; +} + GeometryCollection VectorTileFeature::getGeometries() const { pbf data(geometry_pbf); uint8_t cmd = 1; @@ -166,7 +181,7 @@ VectorTileLayer::VectorTileLayer(pbf layer_pbf) { } else if (layer_pbf.tag == 2) { // feature features.push_back(layer_pbf.message()); } else if (layer_pbf.tag == 3) { // keys - keys.emplace(layer_pbf.string(), keys.size()); + keysMap.emplace(layer_pbf.string(), keysMap.size()); } else if (layer_pbf.tag == 4) { // values values.emplace_back(parseValue(layer_pbf.message())); } else if (layer_pbf.tag == 5) { // extent @@ -175,12 +190,20 @@ VectorTileLayer::VectorTileLayer(pbf layer_pbf) { layer_pbf.skip(); } } + + for (auto &pair : keysMap) { + keys.emplace_back(std::reference_wrapper<const std::string>(pair.first)); + } } util::ptr<const GeometryTileFeature> VectorTileLayer::getFeature(std::size_t i) const { return std::make_shared<VectorTileFeature>(features.at(i), *this); } +std::string VectorTileLayer::getName() const { + return name; +} + VectorTileMonitor::VectorTileMonitor(const TileID& tileID_, float pixelRatio_, const std::string& urlTemplate_, FileSource& fileSource_) : tileID(tileID_), pixelRatio(pixelRatio_), diff --git a/src/mbgl/tile/vector_tile.hpp b/src/mbgl/tile/vector_tile.hpp index 4d330f17f2..0e583ab33a 100644 --- a/src/mbgl/tile/vector_tile.hpp +++ b/src/mbgl/tile/vector_tile.hpp @@ -6,6 +6,8 @@ #include <mbgl/util/pbf.hpp> #include <map> +#include <unordered_map> +#include <functional> namespace mbgl { @@ -17,6 +19,8 @@ public: FeatureType getType() const override { return type; } optional<Value> getValue(const std::string&) const override; + std::unordered_map<std::string,Value> getProperties() const override; + uint64_t getID() const override; GeometryCollection getGeometries() const override; uint32_t getExtent() const override; @@ -34,6 +38,7 @@ public: std::size_t featureCount() const override { return features.size(); } util::ptr<const GeometryTileFeature> getFeature(std::size_t) const override; + std::string getName() const override; private: friend class VectorTile; @@ -41,7 +46,8 @@ private: std::string name; uint32_t extent = 4096; - std::map<std::string, uint32_t> keys; + std::map<std::string, uint32_t> keysMap; + std::vector<std::reference_wrapper<const std::string>> keys; std::vector<Value> values; std::vector<pbf> features; }; diff --git a/src/mbgl/tile/vector_tile_data.cpp b/src/mbgl/tile/vector_tile_data.cpp index 9727b4cb0b..c71b2b733d 100644 --- a/src/mbgl/tile/vector_tile_data.cpp +++ b/src/mbgl/tile/vector_tile_data.cpp @@ -5,6 +5,8 @@ #include <mbgl/util/work_request.hpp> #include <mbgl/style/style.hpp> #include <mbgl/storage/file_source.hpp> +#include <mbgl/geometry/feature_index.hpp> +#include <mbgl/text/collision_tile.hpp> namespace mbgl { @@ -65,8 +67,8 @@ VectorTileData::VectorTileData(const TileID& id_, } std::exception_ptr error; - if (result.is<TileParseResultBuckets>()) { - auto& resultBuckets = result.get<TileParseResultBuckets>(); + if (result.is<TileParseResultData>()) { + auto& resultBuckets = result.get<TileParseResultData>(); state = resultBuckets.state; // Persist the configuration we just placed so that we can later check whether we need to @@ -77,6 +79,11 @@ VectorTileData::VectorTileData(const TileID& id_, // existing buckets in case we got a refresh parse. buckets = std::move(resultBuckets.buckets); + if (state == State::parsed) { + featureIndex = std::move(resultBuckets.featureIndex); + geometryTile = std::move(resultBuckets.geometryTile); + } + } else { error = result.get<std::exception_ptr>(); state = State::obsolete; @@ -105,8 +112,8 @@ bool VectorTileData::parsePending(std::function<void(std::exception_ptr)> callba } std::exception_ptr error; - if (result.is<TileParseResultBuckets>()) { - auto& resultBuckets = result.get<TileParseResultBuckets>(); + if (result.is<TileParseResultData>()) { + auto& resultBuckets = result.get<TileParseResultData>(); state = resultBuckets.state; // Move over all buckets we received in this parse request, potentially overwriting @@ -119,6 +126,11 @@ bool VectorTileData::parsePending(std::function<void(std::exception_ptr)> callba // place again in case the configuration has changed. placedConfig = config; + if (state == State::parsed) { + featureIndex = std::move(resultBuckets.featureIndex); + geometryTile = std::move(resultBuckets.geometryTile); + } + } else { error = result.get<std::exception_ptr>(); state = State::obsolete; @@ -153,7 +165,7 @@ void VectorTileData::redoPlacement(const std::function<void()>& callback) { // we are parsing buckets. if (workRequest) return; - workRequest = worker.redoPlacement(tileWorker, buckets, targetConfig, [this, callback, config = targetConfig] { + workRequest = worker.redoPlacement(tileWorker, buckets, targetConfig, [this, callback, config = targetConfig](std::unique_ptr<CollisionTile> collisionTile) { workRequest.reset(); // Persist the configuration we just placed so that we can later check whether we need to @@ -164,6 +176,10 @@ void VectorTileData::redoPlacement(const std::function<void()>& callback) { bucket.second->swapRenderData(); } + if (featureIndex) { + featureIndex->setCollisionTile(std::move(collisionTile)); + } + // The target configuration could have changed since we started placement. In this case, // we're starting another placement run. if (placedConfig != targetConfig) { @@ -174,6 +190,19 @@ void VectorTileData::redoPlacement(const std::function<void()>& callback) { }); } +void VectorTileData::queryRenderedFeatures( + std::unordered_map<std::string, std::vector<std::string>>& result, + const GeometryCollection& queryGeometry, + const double bearing, + const double tileSize, + const double scale, + const optional<std::vector<std::string>>& layerIDs) { + + if (!featureIndex || !geometryTile) return; + + featureIndex->query(result, queryGeometry, bearing, tileSize, scale, layerIDs, *geometryTile, style); +} + void VectorTileData::cancel() { state = State::obsolete; tileRequest.reset(); diff --git a/src/mbgl/tile/vector_tile_data.hpp b/src/mbgl/tile/vector_tile_data.hpp index ef405e34b4..303fe343fe 100644 --- a/src/mbgl/tile/vector_tile_data.hpp +++ b/src/mbgl/tile/vector_tile_data.hpp @@ -14,6 +14,7 @@ namespace mbgl { class Style; class AsyncRequest; class GeometryTileMonitor; +class FeatureIndex; class VectorTileData : public TileData { public: @@ -35,6 +36,14 @@ public: bool hasData() const override; + void queryRenderedFeatures( + std::unordered_map<std::string, std::vector<std::string>>& result, + const GeometryCollection& queryGeometry, + const double bearing, + const double tileSize, + const double scale, + const optional<std::vector<std::string>>& layerIDs) override; + void cancel() override; private: @@ -50,6 +59,9 @@ private: // objects and they get added by tile parsing operations. std::unordered_map<std::string, std::unique_ptr<Bucket>> buckets; + std::unique_ptr<FeatureIndex> featureIndex; + std::unique_ptr<const GeometryTile> geometryTile; + // Stores the placement configuration of the text that is currently placed on the screen. PlacementConfig placedConfig; diff --git a/src/mbgl/util/intersection_tests.cpp b/src/mbgl/util/intersection_tests.cpp new file mode 100644 index 0000000000..44ec24db12 --- /dev/null +++ b/src/mbgl/util/intersection_tests.cpp @@ -0,0 +1,147 @@ +#include <mbgl/util/intersection_tests.hpp> +#include <mbgl/util/math.hpp> + +namespace mbgl { +namespace util { + +bool polygonContainsPoint(const GeometryCoordinates& ring, const GeometryCoordinate& p) { + bool c = false; + for (auto i = ring.begin(), j = ring.end() - 1; i != ring.end(); j = i++) { + auto& p1 = *i; + auto& p2 = *j; + if (((p1.y > p.y) != (p2.y > p.y)) && (p.x < float(p2.x - p1.x) * float(p.y - p1.y) / float(p2.y - p1.y) + p1.x)) { + c = !c; + } + } + return c; +} + +bool multiPolygonContainsPoint(const GeometryCollection& rings, const GeometryCoordinate& p) { + bool c = false; + for (auto& ring : rings) { + c = (c != polygonContainsPoint(ring, p)); + } + return c; +} + +// Code from http://stackoverflow.com/a/1501725/331379. +float distToSegmentSquared(const GeometryCoordinate& p, const GeometryCoordinate& v, const GeometryCoordinate& w) { + if (v == w) return util::distSqr<float>(p, v); + const float l2 = util::distSqr<float>(v, w); + const float t = float((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2; + if (t < 0) return util::distSqr<float>(p, v); + if (t > 1) return util::distSqr<float>(p, w); + return util::distSqr<float>(p, vec2<float>(w - v) * t + v); +} + +bool pointIntersectsBufferedLine(const GeometryCoordinate& p, const GeometryCoordinates& line, const float radius) { + const float radiusSquared = radius * radius; + + if (line.size() == 1) return util::distSqr<float>(p, line.at(0)) < radiusSquared; + if (line.size() == 0) return false; + + for (auto i = line.begin() + 1; i != line.end(); i++) { + // Find line segments that have a distance <= radius^2 to p + // In that case, we treat the line as "containing point p". + auto& v = *(i - 1); + auto& w = *i; + if (distToSegmentSquared(p, v, w) < radiusSquared) return true; + } + return false; +} + +// http://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/ +bool isCounterClockwise(const GeometryCoordinate& a, const GeometryCoordinate& b, const GeometryCoordinate& c) { + return (c.y - a.y) * (b.x - a.x) > (b.y - a.y) * (c.x - a.x); +} + +bool lineSegmentIntersectsLineSegment(const GeometryCoordinate& a0, const GeometryCoordinate& a1, const GeometryCoordinate& b0, const GeometryCoordinate& b1) { + return isCounterClockwise(a0, b0, b1) != isCounterClockwise(a1, b0, b1) && + isCounterClockwise(a0, a1, b0) != isCounterClockwise(a0, a1, b1); +} +bool lineIntersectsLine(const GeometryCoordinates& lineA, const GeometryCoordinates& lineB) { + if (lineA.size() == 0 || lineB.size() == 0) return false; + for (auto i = lineA.begin(); i != lineA.end() - 1; i++) { + auto& a0 = *i; + auto& a1 = *(i + 1); + for (auto j = lineB.begin(); j != lineB.end() - 1; j++) { + auto& b0 = *j; + auto& b1 = *(j + 1); + if (lineSegmentIntersectsLineSegment(a0, a1, b0, b1)) return true; + } + } + return false; +} + +bool lineIntersectsBufferedLine(const GeometryCoordinates& lineA, const GeometryCoordinates& lineB, float radius) { + if (lineA.size() > 1) { + if (lineIntersectsLine(lineA, lineB)) return true; + + // Check whether any point in either line is within radius of the other line + for (auto& p : lineB) { + if (pointIntersectsBufferedLine(p, lineA, radius)) return true; + } + } + + for (auto& p : lineA) { + if (pointIntersectsBufferedLine(p, lineB, radius)) return true; + } + + return false; +} + +bool multiPolygonIntersectsBufferedMultiPoint(const GeometryCollection& multiPolygon, const GeometryCollection& rings, float radius) { + for (auto& polygon : multiPolygon) { + for (auto& ring : rings) { + for (auto& point : ring) { + if (polygonContainsPoint(polygon, point)) return true; + if (pointIntersectsBufferedLine(point, polygon, radius)) return true; + } + } + } + return false; +} + +bool multiPolygonIntersectsBufferedMultiLine(const GeometryCollection& multiPolygon, const GeometryCollection& multiLine, float radius) { + for (auto& line : multiLine) { + for (auto& polygon : multiPolygon) { + + if (polygon.size() >= 3) { + for (auto& p : line) { + if (polygonContainsPoint(polygon, p)) return true; + } + } + + if (lineIntersectsBufferedLine(polygon, line, radius)) return true; + } + } + + return false; +} + +bool multiPolygonIntersectsMultiPolygon(const GeometryCollection& multiPolygonA, const GeometryCollection& multiPolygonB) { + if (multiPolygonA.size() == 1 && multiPolygonA.at(0).size() == 1) { + return multiPolygonContainsPoint(multiPolygonB, multiPolygonA.at(0).at(0)); + } + + for (auto& ring : multiPolygonB) { + for (auto& p : ring) { + if (multiPolygonContainsPoint(multiPolygonA, p)) return true; + } + } + + for (auto& polygon : multiPolygonA) { + for (auto& p : polygon) { + if (multiPolygonContainsPoint(multiPolygonB, p)) return true; + } + + for (auto& polygonB : multiPolygonB) { + if (lineIntersectsLine(polygon, polygonB)) return true; + } + } + + return false; +} + +} +} diff --git a/src/mbgl/util/intersection_tests.hpp b/src/mbgl/util/intersection_tests.hpp new file mode 100644 index 0000000000..a6e4308039 --- /dev/null +++ b/src/mbgl/util/intersection_tests.hpp @@ -0,0 +1,16 @@ +#ifndef MBGL_UTIL_INTERSECTION_TESTS +#define MBGL_UTIL_INTERSECTION_TESTS + +#include <mbgl/tile/geometry_tile.hpp> + +namespace mbgl { +namespace util { + +bool multiPolygonIntersectsBufferedMultiPoint(const GeometryCollection&, const GeometryCollection&, float radius); +bool multiPolygonIntersectsBufferedMultiLine(const GeometryCollection&, const GeometryCollection&, float radius); +bool multiPolygonIntersectsMultiPolygon(const GeometryCollection&, const GeometryCollection&); + +} +} // namespace mbgl + +#endif diff --git a/src/mbgl/util/tile_coordinate.cpp b/src/mbgl/util/tile_coordinate.cpp new file mode 100644 index 0000000000..d9a0ea352c --- /dev/null +++ b/src/mbgl/util/tile_coordinate.cpp @@ -0,0 +1 @@ +#include <mbgl/util/tile_coordinate.hpp> diff --git a/src/mbgl/util/tile_coordinate.hpp b/src/mbgl/util/tile_coordinate.hpp new file mode 100644 index 0000000000..9962c35b18 --- /dev/null +++ b/src/mbgl/util/tile_coordinate.hpp @@ -0,0 +1,39 @@ +#ifndef MBGL_UTIL_TILE_COORDINATE +#define MBGL_UTIL_TILE_COORDINATE + +#include <mbgl/style/types.hpp> +#include <mbgl/map/transform_state.hpp> + + +namespace mbgl { + +class TransformState; + +// Has floating point x/y coordinates. +// Used for computing the tiles that need to be visible in the viewport. +class TileCoordinate { +public: + double x, y, z; + + static TileCoordinate fromLatLng(const TransformState& state, double zoom, const LatLng& latLng) { + const double scale = std::pow(2, zoom - state.getZoom()); + return { + state.lngX(latLng.longitude) * scale / util::tileSize, + state.latY(latLng.latitude) * scale / util::tileSize, + zoom + }; + } + + static TileCoordinate fromScreenCoordinate(const TransformState& state, double zoom, const ScreenCoordinate& point) { + return fromLatLng(state, zoom, state.screenCoordinateToLatLng(point)); + } + + TileCoordinate zoomTo(double zoom) const { + double scale = std::pow(2, zoom - z); + return { x * scale, y * scale, zoom }; + } +}; + +} // namespace mbgl + +#endif diff --git a/src/mbgl/util/tile_cover.cpp b/src/mbgl/util/tile_cover.cpp index 6efff4bb57..f2bda3f45b 100644 --- a/src/mbgl/util/tile_cover.cpp +++ b/src/mbgl/util/tile_cover.cpp @@ -8,25 +8,6 @@ namespace mbgl { namespace { -// Has floating point x/y coordinates. -// Used for computing the tiles that need to be visible in the viewport. -class TileCoordinate { -public: - double x, y; - - static TileCoordinate fromLatLng(const TransformState& state, double zoom, const LatLng& latLng) { - const double scale = std::pow(2, zoom - state.getZoom()); - return { - state.lngX(latLng.longitude) * scale / util::tileSize, - state.latY(latLng.latitude) * scale / util::tileSize, - }; - } - - static TileCoordinate fromScreenCoordinate(const TransformState& state, double zoom, const ScreenCoordinate& point) { - return fromLatLng(state, zoom, state.screenCoordinateToLatLng(point)); - } -}; - // Taken from polymaps src/Layer.js // https://github.com/simplegeo/polymaps/blob/master/src/Layer.js#L333-L383 struct edge { diff --git a/src/mbgl/util/tile_cover.hpp b/src/mbgl/util/tile_cover.hpp index a489964abf..7323df520c 100644 --- a/src/mbgl/util/tile_cover.hpp +++ b/src/mbgl/util/tile_cover.hpp @@ -3,6 +3,7 @@ #include <mbgl/map/tile_id.hpp> #include <mbgl/style/types.hpp> +#include <mbgl/util/tile_coordinate.hpp> #include <vector> diff --git a/src/mbgl/util/worker.cpp b/src/mbgl/util/worker.cpp index b84b0c43ef..e116d3f6c6 100644 --- a/src/mbgl/util/worker.cpp +++ b/src/mbgl/util/worker.cpp @@ -5,6 +5,7 @@ #include <mbgl/renderer/raster_bucket.hpp> #include <mbgl/tile/geometry_tile.hpp> #include <mbgl/style/style_layer.hpp> +#include <mbgl/text/collision_tile.hpp> #include <cassert> #include <future> @@ -53,9 +54,8 @@ public: void redoPlacement(TileWorker* worker, const std::unordered_map<std::string, std::unique_ptr<Bucket>>* buckets, PlacementConfig config, - std::function<void()> callback) { - worker->redoPlacement(buckets, config); - callback(); + std::function<void(std::unique_ptr<CollisionTile>)> callback) { + callback(worker->redoPlacement(buckets, config)); } }; @@ -101,7 +101,7 @@ std::unique_ptr<AsyncRequest> Worker::redoPlacement(TileWorker& worker, const std::unordered_map<std::string, std::unique_ptr<Bucket>>& buckets, PlacementConfig config, - std::function<void()> callback) { + std::function<void(std::unique_ptr<CollisionTile>)> callback) { current = (current + 1) % threads.size(); return threads[current]->invokeWithCallback(&Worker::Impl::redoPlacement, callback, &worker, &buckets, config); diff --git a/src/mbgl/util/worker.hpp b/src/mbgl/util/worker.hpp index 0e1a3222c7..ee237b6aeb 100644 --- a/src/mbgl/util/worker.hpp +++ b/src/mbgl/util/worker.hpp @@ -13,6 +13,7 @@ namespace mbgl { class AsyncRequest; class RasterBucket; class GeometryTileLoader; +class CollisionTile; using RasterTileParseResult = variant< std::unique_ptr<Bucket>, // success @@ -52,7 +53,7 @@ public: Request redoPlacement(TileWorker&, const std::unordered_map<std::string, std::unique_ptr<Bucket>>&, PlacementConfig config, - std::function<void()> callback); + std::function<void(std::unique_ptr<CollisionTile>)> callback); private: class Impl; diff --git a/test/util/merge_lines.cpp b/test/util/merge_lines.cpp index 6e7273d48c..4b6bad15f6 100644 --- a/test/util/merge_lines.cpp +++ b/test/util/merge_lines.cpp @@ -8,21 +8,21 @@ const std::u32string bbb = U"b"; TEST(MergeLines, SameText) { // merges lines with the same text std::vector<mbgl::SymbolFeature> input1 = { - { {{{0, 0}, {1, 0}, {2, 0}}}, aaa, "" }, - { {{{4, 0}, {5, 0}, {6, 0}}}, bbb, "" }, - { {{{8, 0}, {9, 0}}}, aaa, "" }, - { {{{2, 0}, {3, 0}, {4, 0}}}, aaa, "" }, - { {{{6, 0}, {7, 0}, {8, 0}}}, aaa, "" }, - { {{{5, 0}, {6, 0}}}, aaa, "" } + { {{{0, 0}, {1, 0}, {2, 0}}}, aaa, "", 0 }, + { {{{4, 0}, {5, 0}, {6, 0}}}, bbb, "", 0 }, + { {{{8, 0}, {9, 0}}}, aaa, "", 0 }, + { {{{2, 0}, {3, 0}, {4, 0}}}, aaa, "", 0 }, + { {{{6, 0}, {7, 0}, {8, 0}}}, aaa, "", 0 }, + { {{{5, 0}, {6, 0}}}, aaa, "", 0 } }; const std::vector<mbgl::SymbolFeature> expected1 = { - { {{{0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0}}}, aaa, "" }, - { {{{4, 0}, {5, 0}, {6, 0}}}, bbb, "" }, - { {{{5, 0}, {6, 0}, {7, 0}, {8, 0}, {9, 0}}}, aaa, "" }, - { {{}}, aaa, "" }, - { {{}}, aaa, "" }, - { {{}}, aaa, "" } + { {{{0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0}}}, aaa, "", 0 }, + { {{{4, 0}, {5, 0}, {6, 0}}}, bbb, "", 0 }, + { {{{5, 0}, {6, 0}, {7, 0}, {8, 0}, {9, 0}}}, aaa, "", 0 }, + { {{}}, aaa, "", 0 }, + { {{}}, aaa, "", 0 }, + { {{}}, aaa, "", 0 } }; mbgl::util::mergeLines(input1); @@ -35,15 +35,15 @@ TEST(MergeLines, SameText) { TEST(MergeLines, BothEnds) { // mergeLines handles merge from both ends std::vector<mbgl::SymbolFeature> input2 = { - { {{{0, 0}, {1, 0}, {2, 0}}}, aaa, "" }, - { {{{4, 0}, {5, 0}, {6, 0}}}, aaa, "" }, - { {{{2, 0}, {3, 0}, {4, 0}}}, aaa, "" } + { {{{0, 0}, {1, 0}, {2, 0}}}, aaa, "", 0 }, + { {{{4, 0}, {5, 0}, {6, 0}}}, aaa, "", 0 }, + { {{{2, 0}, {3, 0}, {4, 0}}}, aaa, "", 0 } }; const std::vector<mbgl::SymbolFeature> expected2 = { - { {{{0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {6, 0}}}, aaa, "" }, - { {{}}, aaa, "" }, - { {{}}, aaa, "" } + { {{{0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {6, 0}}}, aaa, "", 0 }, + { {{}}, aaa, "", 0 }, + { {{}}, aaa, "", 0 } }; mbgl::util::mergeLines(input2); @@ -56,15 +56,15 @@ TEST(MergeLines, BothEnds) { TEST(MergeLines, CircularLines) { // mergeLines handles circular lines std::vector<mbgl::SymbolFeature> input3 = { - { {{{0, 0}, {1, 0}, {2, 0}}}, aaa, "" }, - { {{{2, 0}, {3, 0}, {4, 0}}}, aaa, "" }, - { {{{4, 0}, {0, 0}}}, aaa, "" } + { {{{0, 0}, {1, 0}, {2, 0}}}, aaa, "", 0 }, + { {{{2, 0}, {3, 0}, {4, 0}}}, aaa, "", 0 }, + { {{{4, 0}, {0, 0}}}, aaa, "", 0 } }; const std::vector<mbgl::SymbolFeature> expected3 = { - { {{{0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0}, {0, 0}}}, aaa, "" }, - { {{}}, aaa, "" }, - { {{}}, aaa, "" } + { {{{0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0}, {0, 0}}}, aaa, "", 0 }, + { {{}}, aaa, "", 0 }, + { {{}}, aaa, "", 0 } }; mbgl::util::mergeLines(input3); |