[core] implement queryRenderedFeatures

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);