First implementation of queryRenderedSymbols

25 files changed, 121 insertions, 144 deletions

diff --git a/src/mbgl/annotation/render_annotation_source.cpp b/src/mbgl/annotation/render_annotation_source.cpp
index ba80be0da0..a0b69af8d5 100644
--- a/src/mbgl/annotation/render_annotation_source.cpp
+++ b/src/mbgl/annotation/render_annotation_source.cpp
@@ -63,8 +63,9 @@ std::unordered_map<std::string, std::vector<Feature>>
 RenderAnnotationSource::queryRenderedFeatures(const ScreenLineString& geometry,
                                               const TransformState& transformState,
                                               const std::vector<const RenderLayer*>& layers,
-                                              const RenderedQueryOptions& options) const {
-    return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options);
+                                              const RenderedQueryOptions& options,
+                                              const CollisionIndex& collisionIndex) const {
+    return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options, collisionIndex);
 }
 
 std::vector<Feature> RenderAnnotationSource::querySourceFeatures(const SourceQueryOptions&) const {
diff --git a/src/mbgl/annotation/render_annotation_source.hpp b/src/mbgl/annotation/render_annotation_source.hpp
index 6209c943f1..aa2578d4e3 100644
--- a/src/mbgl/annotation/render_annotation_source.hpp
+++ b/src/mbgl/annotation/render_annotation_source.hpp
@@ -27,7 +27,8 @@ public:
     queryRenderedFeatures(const ScreenLineString& geometry,
                           const TransformState& transformState,
                           const std::vector<const RenderLayer*>& layers,
-                          const RenderedQueryOptions& options) const final;
+                          const RenderedQueryOptions& options,
+                          const CollisionIndex& collisionIndex) const final;
 
     std::vector<Feature>
     querySourceFeatures(const SourceQueryOptions&) const final;
diff --git a/src/mbgl/geometry/feature_index.cpp b/src/mbgl/geometry/feature_index.cpp
index 648a6d16ba..77335bce36 100644
--- a/src/mbgl/geometry/feature_index.cpp
+++ b/src/mbgl/geometry/feature_index.cpp
@@ -51,7 +51,7 @@ void FeatureIndex::query(
         const GeometryTileData& geometryTileData,
         const CanonicalTileID& tileID,
         const std::vector<const RenderLayer*>& layers,
-        const CollisionIndex* collisionIndex,
+        const CollisionIndex& collisionIndex,
         const float additionalQueryRadius) const {
 
     // Determine query radius
@@ -60,9 +60,15 @@ void FeatureIndex::query(
 
     // Query the grid index
     mapbox::geometry::box<int16_t> box = mapbox::geometry::envelope(queryGeometry);
-    std::vector<IndexedSubfeature> features = grid.query({ convertPoint<float>(box.min - additionalRadius),
+    typedef std::pair<IndexedSubfeature, GridIndex<IndexedSubfeature>::BBox> QueryResult;
+    std::vector<QueryResult> queryResults = grid.query({ convertPoint<float>(box.min - additionalRadius),
                                                            convertPoint<float>(box.max + additionalRadius) });
 
+    // TODO: clumsy way to discard this data
+    std::vector<IndexedSubfeature> features;
+    for (auto& queryResult : queryResults) {
+        features.push_back(queryResult.first);
+    }
 
     std::sort(features.begin(), features.end(), topDown);
     size_t previousSortIndex = std::numeric_limits<size_t>::max();
@@ -75,12 +81,7 @@ void FeatureIndex::query(
         addFeature(result, indexedFeature, queryGeometry, queryOptions, geometryTileData, tileID, layers, bearing, pixelsToTileUnits);
     }
 
-    // Query symbol features, if they've been placed.
-    if (!collisionIndex) {
-        return;
-    }
-
-    std::vector<IndexedSubfeature> symbolFeatures;// = collisionIndex->queryRenderedSymbols(queryGeometry, UnwrappedTileID(), scale); // TODO: hook up
+    std::vector<IndexedSubfeature> symbolFeatures = collisionIndex.queryRenderedSymbols(queryGeometry, UnwrappedTileID(0, tileID)); // TODO: hook up
     std::sort(symbolFeatures.begin(), symbolFeatures.end(), topDownSymbols);
     for (const auto& symbolFeature : symbolFeatures) {
         addFeature(result, symbolFeature, queryGeometry, queryOptions, geometryTileData, tileID, layers, bearing, pixelsToTileUnits);
diff --git a/src/mbgl/geometry/feature_index.hpp b/src/mbgl/geometry/feature_index.hpp
index a067165fa8..38b84071ac 100644
--- a/src/mbgl/geometry/feature_index.hpp
+++ b/src/mbgl/geometry/feature_index.hpp
@@ -47,7 +47,7 @@ public:
             const GeometryTileData&,
             const CanonicalTileID&,
             const std::vector<const RenderLayer*>&,
-            const CollisionIndex*,
+            const CollisionIndex&,
             const float additionalQueryRadius) const;
 
     static optional<GeometryCoordinates> translateQueryGeometry(
diff --git a/src/mbgl/renderer/render_source.hpp b/src/mbgl/renderer/render_source.hpp
index 8293923ff6..8c84af4f1e 100644
--- a/src/mbgl/renderer/render_source.hpp
+++ b/src/mbgl/renderer/render_source.hpp
@@ -24,6 +24,7 @@ class SourceQueryOptions;
 class Tile;
 class RenderSourceObserver;
 class TileParameters;
+class CollisionIndex;
 
 class RenderSource : protected TileObserver {
 public:
@@ -63,7 +64,8 @@ public:
     queryRenderedFeatures(const ScreenLineString& geometry,
                           const TransformState& transformState,
                           const std::vector<const RenderLayer*>& layers,
-                          const RenderedQueryOptions& options) const = 0;
+                          const RenderedQueryOptions& options,
+                          const CollisionIndex& collisionIndex) const = 0;
 
     virtual std::vector<Feature>
     querySourceFeatures(const SourceQueryOptions&) const = 0;
diff --git a/src/mbgl/renderer/renderer_impl.cpp b/src/mbgl/renderer/renderer_impl.cpp
index ea8ddbee28..71f42c3ef6 100644
--- a/src/mbgl/renderer/renderer_impl.cpp
+++ b/src/mbgl/renderer/renderer_impl.cpp
@@ -631,7 +631,7 @@ std::vector<Feature> Renderer::Impl::queryRenderedFeatures(const ScreenLineStrin
     std::unordered_map<std::string, std::vector<Feature>> resultsByLayer;
     for (const auto& sourceID : sourceIDs) {
         if (RenderSource* renderSource = getRenderSource(sourceID)) {
-            auto sourceResults = renderSource->queryRenderedFeatures(geometry, transformState, layers, options);
+            auto sourceResults = renderSource->queryRenderedFeatures(geometry, transformState, layers, options, placement->collisionIndex);
             std::move(sourceResults.begin(), sourceResults.end(), std::inserter(resultsByLayer, resultsByLayer.begin()));
         }
     }
diff --git a/src/mbgl/renderer/sources/render_geojson_source.cpp b/src/mbgl/renderer/sources/render_geojson_source.cpp
index 504db78ea3..d07cfcdc41 100644
--- a/src/mbgl/renderer/sources/render_geojson_source.cpp
+++ b/src/mbgl/renderer/sources/render_geojson_source.cpp
@@ -84,8 +84,9 @@ std::unordered_map<std::string, std::vector<Feature>>
 RenderGeoJSONSource::queryRenderedFeatures(const ScreenLineString& geometry,
                                            const TransformState& transformState,
                                            const std::vector<const RenderLayer*>& layers,
-                                           const RenderedQueryOptions& options) const {
-    return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options);
+                                           const RenderedQueryOptions& options,
+                                           const CollisionIndex& collisionIndex) const {
+    return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options, collisionIndex);
 }
 
 std::vector<Feature> RenderGeoJSONSource::querySourceFeatures(const SourceQueryOptions& options) const {
diff --git a/src/mbgl/renderer/sources/render_geojson_source.hpp b/src/mbgl/renderer/sources/render_geojson_source.hpp
index b2e06c68d4..55166ea901 100644
--- a/src/mbgl/renderer/sources/render_geojson_source.hpp
+++ b/src/mbgl/renderer/sources/render_geojson_source.hpp
@@ -31,7 +31,8 @@ public:
     queryRenderedFeatures(const ScreenLineString& geometry,
                           const TransformState& transformState,
                           const std::vector<const RenderLayer*>& layers,
-                          const RenderedQueryOptions& options) const final;
+                          const RenderedQueryOptions& options,
+                          const CollisionIndex&) const final;
 
     std::vector<Feature>
     querySourceFeatures(const SourceQueryOptions&) const final;
diff --git a/src/mbgl/renderer/sources/render_image_source.cpp b/src/mbgl/renderer/sources/render_image_source.cpp
index 9140e01711..b5c42584e0 100644
--- a/src/mbgl/renderer/sources/render_image_source.cpp
+++ b/src/mbgl/renderer/sources/render_image_source.cpp
@@ -84,7 +84,8 @@ std::unordered_map<std::string, std::vector<Feature>>
 RenderImageSource::queryRenderedFeatures(const ScreenLineString&,
                                          const TransformState&,
                                          const std::vector<const RenderLayer*>&,
-                                         const RenderedQueryOptions&) const {
+                                         const RenderedQueryOptions&,
+                                         const CollisionIndex&) const {
     return std::unordered_map<std::string, std::vector<Feature>> {};
 }
 
diff --git a/src/mbgl/renderer/sources/render_image_source.hpp b/src/mbgl/renderer/sources/render_image_source.hpp
index 8d80838c3b..72cf4cea61 100644
--- a/src/mbgl/renderer/sources/render_image_source.hpp
+++ b/src/mbgl/renderer/sources/render_image_source.hpp
@@ -32,7 +32,8 @@ public:
     queryRenderedFeatures(const ScreenLineString& geometry,
                           const TransformState& transformState,
                           const std::vector<const RenderLayer*>& layers,
-                          const RenderedQueryOptions& options) const final;
+                          const RenderedQueryOptions& options,
+                          const CollisionIndex& collisionIndex) const final;
 
     std::vector<Feature> querySourceFeatures(const SourceQueryOptions&) const final;
 
diff --git a/src/mbgl/renderer/sources/render_raster_source.cpp b/src/mbgl/renderer/sources/render_raster_source.cpp
index bcd719365d..f11f9b7aed 100644
--- a/src/mbgl/renderer/sources/render_raster_source.cpp
+++ b/src/mbgl/renderer/sources/render_raster_source.cpp
@@ -74,7 +74,8 @@ std::unordered_map<std::string, std::vector<Feature>>
 RenderRasterSource::queryRenderedFeatures(const ScreenLineString&,
                                           const TransformState&,
                                           const std::vector<const RenderLayer*>&,
-                                          const RenderedQueryOptions&) const {
+                                          const RenderedQueryOptions&,
+                                          const CollisionIndex& ) const {
     return std::unordered_map<std::string, std::vector<Feature>> {};
 }
 
diff --git a/src/mbgl/renderer/sources/render_raster_source.hpp b/src/mbgl/renderer/sources/render_raster_source.hpp
index e1bf5798ff..25041fde43 100644
--- a/src/mbgl/renderer/sources/render_raster_source.hpp
+++ b/src/mbgl/renderer/sources/render_raster_source.hpp
@@ -27,7 +27,8 @@ public:
     queryRenderedFeatures(const ScreenLineString& geometry,
                           const TransformState& transformState,
                           const std::vector<const RenderLayer*>& layers,
-                          const RenderedQueryOptions& options) const final;
+                          const RenderedQueryOptions& options,
+                          const CollisionIndex& collisionIndex) const final;
 
     std::vector<Feature>
     querySourceFeatures(const SourceQueryOptions&) const final;
diff --git a/src/mbgl/renderer/sources/render_vector_source.cpp b/src/mbgl/renderer/sources/render_vector_source.cpp
index ca3071c6b0..49f8fdff2c 100644
--- a/src/mbgl/renderer/sources/render_vector_source.cpp
+++ b/src/mbgl/renderer/sources/render_vector_source.cpp
@@ -77,8 +77,9 @@ std::unordered_map<std::string, std::vector<Feature>>
 RenderVectorSource::queryRenderedFeatures(const ScreenLineString& geometry,
                                           const TransformState& transformState,
                                           const std::vector<const RenderLayer*>& layers,
-                                          const RenderedQueryOptions& options) const {
-    return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options);
+                                          const RenderedQueryOptions& options,
+                                          const CollisionIndex& collisionIndex) const {
+    return tilePyramid.queryRenderedFeatures(geometry, transformState, layers, options, collisionIndex);
 }
 
 std::vector<Feature> RenderVectorSource::querySourceFeatures(const SourceQueryOptions& options) const {
diff --git a/src/mbgl/renderer/sources/render_vector_source.hpp b/src/mbgl/renderer/sources/render_vector_source.hpp
index ac319a167e..4a992e854f 100644
--- a/src/mbgl/renderer/sources/render_vector_source.hpp
+++ b/src/mbgl/renderer/sources/render_vector_source.hpp
@@ -27,7 +27,8 @@ public:
     queryRenderedFeatures(const ScreenLineString& geometry,
                           const TransformState& transformState,
                           const std::vector<const RenderLayer*>& layers,
-                          const RenderedQueryOptions& options) const final;
+                          const RenderedQueryOptions& options,
+                          const CollisionIndex& collisionIndex) const final;
 
     std::vector<Feature>
     querySourceFeatures(const SourceQueryOptions&) const final;
diff --git a/src/mbgl/renderer/tile_pyramid.cpp b/src/mbgl/renderer/tile_pyramid.cpp
index a2c675a889..4acc67daa8 100644
--- a/src/mbgl/renderer/tile_pyramid.cpp
+++ b/src/mbgl/renderer/tile_pyramid.cpp
@@ -199,7 +199,8 @@ void TilePyramid::update(const std::vector<Immutable<style::Layer::Impl>>& layer
 std::unordered_map<std::string, std::vector<Feature>> TilePyramid::queryRenderedFeatures(const ScreenLineString& geometry,
                                            const TransformState& transformState,
                                            const std::vector<const RenderLayer*>& layers,
-                                           const RenderedQueryOptions& options) const {
+                                           const RenderedQueryOptions& options,
+                                           const CollisionIndex& collisionIndex) const {
     std::unordered_map<std::string, std::vector<Feature>> result;
     if (renderTiles.empty() || geometry.empty()) {
         return result;
@@ -242,7 +243,8 @@ std::unordered_map<std::string, std::vector<Feature>> TilePyramid::queryRendered
                                               tileSpaceQueryGeometry,
                                               transformState,
                                               layers,
-                                              options);
+                                              options,
+                                              collisionIndex);
     }
 
     return result;
diff --git a/src/mbgl/renderer/tile_pyramid.hpp b/src/mbgl/renderer/tile_pyramid.hpp
index ac4572b103..feab8a838c 100644
--- a/src/mbgl/renderer/tile_pyramid.hpp
+++ b/src/mbgl/renderer/tile_pyramid.hpp
@@ -51,7 +51,8 @@ public:
     queryRenderedFeatures(const ScreenLineString& geometry,
                           const TransformState& transformState,
                           const std::vector<const RenderLayer*>&,
-                          const RenderedQueryOptions& options) const;
+                          const RenderedQueryOptions& options,
+                          const CollisionIndex& collisionIndex) const;
 
     std::vector<Feature> querySourceFeatures(const SourceQueryOptions&) const;
 
diff --git a/src/mbgl/text/collision_index.cpp b/src/mbgl/text/collision_index.cpp
index 0112e1de1a..cf68c796bf 100644
--- a/src/mbgl/text/collision_index.cpp
+++ b/src/mbgl/text/collision_index.cpp
@@ -235,18 +235,20 @@ void CollisionIndex::insertFeature(CollisionFeature& feature, bool ignorePlaceme
     }
 }
 
-std::vector<IndexedSubfeature> CollisionIndex::queryRenderedSymbols(const GeometryCoordinates& queryGeometry, const UnwrappedTileID&, const float) const {
+std::vector<IndexedSubfeature> CollisionIndex::queryRenderedSymbols(const GeometryCoordinates& queryGeometry, const UnwrappedTileID& tileID) const {
     std::vector<IndexedSubfeature> result;
-    if (true || queryGeometry.empty() || (collisionGrid.empty() && ignoredGrid.empty())) {
+    if (queryGeometry.empty() || (collisionGrid.empty() && ignoredGrid.empty())) {
         return result;
     }
     
-    // TODO: reimplement queryRenderedSymbols
-/*
     mat4 posMatrix;
+    mat4 projMatrix;
+    transformState.getProjMatrix(projMatrix);
     transformState.matrixFor(posMatrix, tileID);
+    matrix::multiply(posMatrix, projMatrix, posMatrix);
 
     GeometryCoordinates polygon;
+    // todo: use envelope?
     auto minX = std::numeric_limits<GridUnit>::max();
     auto minY = std::numeric_limits<GridUnit>::max();
     auto maxX = std::numeric_limits<GridUnit>::min();
@@ -263,92 +265,57 @@ std::vector<IndexedSubfeature> CollisionIndex::queryRenderedSymbols(const Geomet
         polygon.push_back(convertPoint<int16_t>(projected));
     }
     
-    std::vector<IndexedSubfeature> thisTileFeatures;
-    std::vector<IndexedSubfeature> features = collisionGrid.query({{minX, minY}, {maxX, maxY}});
-    // TODO: reimplement "thisTileFeatures" filter
-    // onst tileID = tileCoord.id;
-    for (auto& feature : features) {
-        //if (features[i].tileID === tileID) {
-            thisTileFeatures.push_back(feature);
-        //}
+    typedef std::pair<IndexedSubfeature, GridIndex<IndexedSubfeature>::BBox> QueryResult;
+    
+    std::vector<QueryResult> thisTileFeatures;
+    std::vector<QueryResult> features = collisionGrid.query({{minX, minY}, {maxX, maxY}});
+
+    for (auto& queryResult : features) {
+    auto& feature = queryResult.first;
+        UnwrappedTileID featureTileID(feature.z, feature.x, feature.y); // TODO: Think about overscaling/wrapping
+        if (featureTileID == tileID) {
+            thisTileFeatures.push_back(queryResult);
+        }
     }
     
-    std::vector<IndexedSubfeature> ignoredFeatures = ignoredGrid.query({{minX, minY}, {maxX, maxY}});
-    // TODO: reimplement "thisTileFeatures" filter
-    // onst tileID = tileCoord.id;
-    for (auto& feature : ignoredFeatures) {
-        //if (features[i].tileID === tileID) {
-            thisTileFeatures.push_back(feature);
-        //}
+    std::vector<QueryResult> ignoredFeatures = ignoredGrid.query({{minX, minY}, {maxX, maxY}});
+    for (auto& queryResult : ignoredFeatures) {
+        auto& feature = queryResult.first;
+        UnwrappedTileID featureTileID(feature.z, feature.x, feature.y); // TODO: Think about overscaling/wrapping
+        if (featureTileID == tileID) {
+            thisTileFeatures.push_back(queryResult);
+        }
     }
 
-    for (auto& feature : thisTileFeatures) {
-        for (let i = 0; i < thisTileFeatures.length; i++) {
-            const blocking = collisionBoxArray.get(thisTileFeatures[i]);
-            const sourceLayer = blocking.sourceLayerIndex;
-            const featureIndex = blocking.featureIndex;
+    std::unordered_map<std::string, std::unordered_set<std::size_t>> sourceLayerFeatures;
+    for (auto& queryResult : thisTileFeatures) {
+        auto& feature = queryResult.first;
+        auto& bbox = queryResult.second;
 
-            // Skip already seen features.
-            if (sourceLayerFeatures[sourceLayer] === undefined) {
-                sourceLayerFeatures[sourceLayer] = {};
-            }
-            if (sourceLayerFeatures[sourceLayer][featureIndex]) continue;
-
-
-            // Check if query intersects with the feature box
-            // "Collision Circles" for line labels are treated as boxes here
-            // Since there's no actual collision taking place, the circle vs. square
-            // distinction doesn't matter as much, and box geometry is easier
-            // to work with.
-            const projectedPoint = this.projectAndGetPerspectiveRatio(posMatrix, blocking.anchorPointX, blocking.anchorPointY);
-            const tileToViewport = textPixelRatio * projectedPoint.perspectiveRatio;
-            const x1 = blocking.x1 / tileToViewport + projectedPoint.point.x;
-            const y1 = blocking.y1 / tileToViewport + projectedPoint.point.y;
-            const x2 = blocking.x2 / tileToViewport + projectedPoint.point.x;
-            const y2 = blocking.y2 / tileToViewport + projectedPoint.point.y;
-            const bbox = [
-                new Point(x1, y1),
-                new Point(x2, y1),
-                new Point(x2, y2),
-                new Point(x1, y2)
-            ];
-            if (!intersectionTests.polygonIntersectsPolygon(query, bbox)) continue;
-
-            sourceLayerFeatures[sourceLayer][featureIndex] = true;
-            result.push(thisTileFeatures[i]);
-        }
+        // Skip already seen features.
+        auto& seenFeatures = sourceLayerFeatures[feature.sourceLayerName];
+        if (seenFeatures.find(feature.index) != seenFeatures.end())
+            continue;
 
-        return result;
+        seenFeatures.insert(feature.index);
 
-    // Predicate for ruling out already seen features.
-    std::unordered_map<std::string, std::unordered_set<std::size_t>> sourceLayerFeatures;
-    auto seenFeature = [&] (const CollisionTreeBox& treeBox) -> bool {
-        const IndexedSubfeature& feature = std::get<2>(treeBox);
-        const auto& seenFeatures = sourceLayerFeatures[feature.sourceLayerName];
-        return seenFeatures.find(feature.index) == seenFeatures.end();
-    };
-
-
-    // Check if query polygon intersects with the feature box at current scale.
-    auto intersectsAtScale = [&] (const CollisionTreeBox& treeBox) -> bool {
-        const CollisionBox& collisionBox = std::get<1>(treeBox);
-        const auto projectedAnchor = projectAndGetPerspectiveRatio(posMatrix, collisionBox.anchor);
-        const float tileToViewport = textPixelRatio * projectedAnchor.second;
-
-        const int16_t x1 = projectedAnchor.first.x + (collisionBox.x1 / tileToViewport);
-        const int16_t y1 = projectedAnchor.first.y + (collisionBox.y1 / tileToViewport);
-        const int16_t x2 = projectedAnchor.first.x + (collisionBox.x2 / tileToViewport);
-        const int16_t y2 = projectedAnchor.first.y + (collisionBox.y2 / tileToViewport);
-        auto bbox = GeometryCoordinates {
-            { x1, y1 }, { x2, y1 }, { x2, y2 }, { x1, y2 }
+        int16_t minX1 = bbox.min.x;
+        int16_t maxX1 = bbox.max.y;
+        int16_t minY1 = bbox.min.y;
+        int16_t maxY1 = bbox.max.y;
+
+        auto bboxPoints = GeometryCoordinates {
+            { minX1, minY1 }, { maxX1, minY1 }, { maxX1, maxY1 }, { minX1, maxY1 }
         };
-        return util::polygonIntersectsPolygon(polygon, bbox);
-    };
+        
+        if (!util::polygonIntersectsPolygon(polygon, bboxPoints))
+            continue;
 
-    auto predicates = bgi::satisfies(seenFeature) && bgi::satisfies(intersectsAtScale);
+        result.push_back(feature);
+    }
 
     return result;
-    */
+
 }
 
 std::pair<float,float> CollisionIndex::projectAnchor(const mat4& posMatrix, const Point<float>& point) const {
diff --git a/src/mbgl/text/collision_index.hpp b/src/mbgl/text/collision_index.hpp
index 226a3be5ed..0d19d6f9cd 100644
--- a/src/mbgl/text/collision_index.hpp
+++ b/src/mbgl/text/collision_index.hpp
@@ -31,7 +31,7 @@ public:
 
     void insertFeature(CollisionFeature& feature, bool ignorePlacement);
 
-    std::vector<IndexedSubfeature> queryRenderedSymbols(const GeometryCoordinates&, const UnwrappedTileID& tileID, const float textPixelRatio) const;
+    std::vector<IndexedSubfeature> queryRenderedSymbols(const GeometryCoordinates&, const UnwrappedTileID& tileID) const;
 
     
 private:
diff --git a/src/mbgl/text/placement.hpp b/src/mbgl/text/placement.hpp
index 9802ad546b..7188d600d1 100644
--- a/src/mbgl/text/placement.hpp
+++ b/src/mbgl/text/placement.hpp
@@ -46,6 +46,9 @@ namespace mbgl {
             float symbolFadeChange(TimePoint now) const;
             bool hasTransitions(TimePoint now) const;
 
+            // TODO: public for queryRenderedFeatures
+            CollisionIndex collisionIndex;
+
         private:
 
             void placeLayerBucket(
@@ -59,7 +62,6 @@ namespace mbgl {
 
             void updateBucketOpacities(SymbolBucket&);
 
-            CollisionIndex collisionIndex;
             TransformState state;
             TimePoint commitTime;
 
diff --git a/src/mbgl/tile/geometry_tile.cpp b/src/mbgl/tile/geometry_tile.cpp
index f93b188ae0..ff5177aa0d 100644
--- a/src/mbgl/tile/geometry_tile.cpp
+++ b/src/mbgl/tile/geometry_tile.cpp
@@ -216,7 +216,8 @@ void GeometryTile::queryRenderedFeatures(
     const GeometryCoordinates& queryGeometry,
     const TransformState& transformState,
     const std::vector<const RenderLayer*>& layers,
-    const RenderedQueryOptions& options) {
+    const RenderedQueryOptions& options,
+    const CollisionIndex& collisionIndex) {
 
     if (!featureIndex || !data) return;
 
@@ -238,7 +239,7 @@ void GeometryTile::queryRenderedFeatures(
                         *data,
                         id.canonical,
                         layers,
-                        0, // TODO: hook up to global CollisionIndex
+                        collisionIndex, // TODO: hook up to global CollisionIndex
                         additionalRadius);
 }
 
diff --git a/src/mbgl/tile/geometry_tile.hpp b/src/mbgl/tile/geometry_tile.hpp
index 354188e0ea..80f2f8c6d7 100644
--- a/src/mbgl/tile/geometry_tile.hpp
+++ b/src/mbgl/tile/geometry_tile.hpp
@@ -55,7 +55,8 @@ public:
             const GeometryCoordinates& queryGeometry,
             const TransformState&,
             const std::vector<const RenderLayer*>& layers,
-            const RenderedQueryOptions& options) override;
+            const RenderedQueryOptions& options,
+            const CollisionIndex& collisionIndex) override;
 
     void querySourceFeatures(
         std::vector<Feature>& result,
diff --git a/src/mbgl/tile/tile.cpp b/src/mbgl/tile/tile.cpp
index f36a472e72..85899a98cb 100644
--- a/src/mbgl/tile/tile.cpp
+++ b/src/mbgl/tile/tile.cpp
@@ -34,7 +34,8 @@ void Tile::queryRenderedFeatures(
         const GeometryCoordinates&,
         const TransformState&,
         const std::vector<const RenderLayer*>&,
-        const RenderedQueryOptions&) {}
+        const RenderedQueryOptions&,
+        const CollisionIndex&) {}
 
 void Tile::querySourceFeatures(
         std::vector<Feature>&,
diff --git a/src/mbgl/tile/tile.hpp b/src/mbgl/tile/tile.hpp
index 93c896f2ef..06d2a93644 100644
--- a/src/mbgl/tile/tile.hpp
+++ b/src/mbgl/tile/tile.hpp
@@ -62,7 +62,8 @@ public:
             const GeometryCoordinates& queryGeometry,
             const TransformState&,
             const std::vector<const RenderLayer*>&,
-            const RenderedQueryOptions& options);
+            const RenderedQueryOptions& options,
+            const CollisionIndex&);
 
     virtual void querySourceFeatures(
             std::vector<Feature>& result,
diff --git a/src/mbgl/util/grid_index.cpp b/src/mbgl/util/grid_index.cpp
index 7f2ed78e5f..5a24d23e20 100644
--- a/src/mbgl/util/grid_index.cpp
+++ b/src/mbgl/util/grid_index.cpp
@@ -62,21 +62,10 @@ void GridIndex<T>::insert(T&& t, const BCircle& bcircle) {
 }
 
 template <class T>
-std::vector<T> GridIndex<T>::query(const BBox& queryBBox) const {
-    std::vector<T> result;
-    query(queryBBox, [&](const T& t) -> bool {
-        result.push_back(t);
-        return false;
-    });
-    return result;
-}
-
-// TODO: templatize this on geometry type
-template <class T>
-std::vector<T> GridIndex<T>::query(const BCircle& queryBCircle) const {
-    std::vector<T> result;
-    query(queryBCircle, [&](const T& t) -> bool {
-        result.push_back(t);
+std::vector<std::pair<T, typename GridIndex<T>::BBox>> GridIndex<T>::query(const BBox& queryBBox) const {
+    std::vector<std::pair<T, BBox>> result;
+    query(queryBBox, [&](const T& t, const BBox& bbox) -> bool {
+        result.push_back(std::make_pair(t, bbox));
         return false;
     });
     return result;
@@ -85,7 +74,7 @@ std::vector<T> GridIndex<T>::query(const BCircle& queryBCircle) const {
 template <class T>
 bool GridIndex<T>::hitTest(const BBox& queryBBox) const {
     bool hit = false;
-    query(queryBBox, [&](const T&) -> bool {
+    query(queryBBox, [&](const T&, const BBox&) -> bool {
         hit = true;
         return true;
     });
@@ -96,7 +85,7 @@ bool GridIndex<T>::hitTest(const BBox& queryBBox) const {
 template <class T>
 bool GridIndex<T>::hitTest(const BCircle& queryBCircle) const {
     bool hit = false;
-    query(queryBCircle, [&](const T&) -> bool {
+    query(queryBCircle, [&](const T&, const BBox&) -> bool {
         hit = true;
         return true;
     });
@@ -120,7 +109,7 @@ typename GridIndex<T>::BBox GridIndex<T>::convertToBox(const BCircle& circle) co
 }
 
 template <class T>
-void GridIndex<T>::query(const BBox& queryBBox, std::function<bool (const T&)> resultFn) const {
+void GridIndex<T>::query(const BBox& queryBBox, std::function<bool (const T&, const BBox&)> resultFn) const {
     std::unordered_set<size_t> seenBoxes;
     std::unordered_set<size_t> seenCircles;
     
@@ -129,12 +118,12 @@ void GridIndex<T>::query(const BBox& queryBBox, std::function<bool (const T&)> r
     } else if (completeIntersection(queryBBox)) {
         // TODO: std::for_each?
         for (auto& element : boxElements) {
-            if (resultFn(element.first)) {
+            if (resultFn(element.first, element.second)) {
                 return;
             };
         }
         for (auto& element : circleElements) {
-            if (resultFn(element.first)) {
+            if (resultFn(element.first, convertToBox(element.second))) {
                 return;
             };
         }
@@ -157,7 +146,7 @@ void GridIndex<T>::query(const BBox& queryBBox, std::function<bool (const T&)> r
                     auto& pair = boxElements.at(uid);
                     auto& bbox = pair.second;
                     if (boxesCollide(queryBBox, bbox)) {
-                        if (resultFn(pair.first)) {
+                        if (resultFn(pair.first, bbox)) {
                             return;
                         }
                     }
@@ -172,7 +161,7 @@ void GridIndex<T>::query(const BBox& queryBBox, std::function<bool (const T&)> r
                     auto& pair = circleElements.at(uid);
                     auto& bcircle = pair.second;
                     if (circleAndBoxCollide(bcircle, queryBBox)) {
-                        if (resultFn(pair.first)) {
+                        if (resultFn(pair.first, convertToBox(bcircle))) {
                             return;
                         }
                     }
@@ -183,7 +172,7 @@ void GridIndex<T>::query(const BBox& queryBBox, std::function<bool (const T&)> r
 }
 
 template <class T>
-void GridIndex<T>::query(const BCircle& queryBCircle, std::function<bool (const T&)> resultFn) const {
+void GridIndex<T>::query(const BCircle& queryBCircle, std::function<bool (const T&, const BBox&)> resultFn) const {
     std::unordered_set<size_t> seenBoxes;
     std::unordered_set<size_t> seenCircles;
 
@@ -193,12 +182,12 @@ void GridIndex<T>::query(const BCircle& queryBCircle, std::function<bool (const
     } else if (completeIntersection(queryBBox)) {
         // TODO: std::for_each?
         for (auto& element : boxElements) {
-            if (resultFn(element.first)) {
+            if (resultFn(element.first, element.second)) {
                 return;
             };
         }
         for (auto& element : circleElements) {
-            if (resultFn(element.first)) {
+            if (resultFn(element.first, convertToBox(element.second))) {
                 return;
             };
         }
@@ -221,7 +210,7 @@ void GridIndex<T>::query(const BCircle& queryBCircle, std::function<bool (const
                     auto& pair = boxElements.at(uid);
                     auto& bbox = pair.second;
                     if (circleAndBoxCollide(queryBCircle, bbox)) {
-                        if (resultFn(pair.first)) {
+                        if (resultFn(pair.first, bbox)) {
                             return;
                         }
                     }
@@ -236,7 +225,7 @@ void GridIndex<T>::query(const BCircle& queryBCircle, std::function<bool (const
                     auto& pair = circleElements.at(uid);
                     auto& bcircle = pair.second;
                     if (circlesCollide(queryBCircle, bcircle)) {
-                        if (resultFn(pair.first)) {
+                        if (resultFn(pair.first, convertToBox(bcircle))) {
                             return;
                         }
                     }
diff --git a/src/mbgl/util/grid_index.hpp b/src/mbgl/util/grid_index.hpp
index 20e3dfff68..30b033cedd 100644
--- a/src/mbgl/util/grid_index.hpp
+++ b/src/mbgl/util/grid_index.hpp
@@ -65,8 +65,7 @@ public:
     void insert(T&& t, const BBox&);
     void insert(T&& t, const BCircle&);
     
-    std::vector<T> query(const BBox&) const;
-    std::vector<T> query(const BCircle&) const;
+    std::vector<std::pair<T,BBox>> query(const BBox&) const;
     
     bool hitTest(const BBox&) const;
     bool hitTest(const BCircle&) const;
@@ -78,8 +77,8 @@ private:
     bool completeIntersection(const BBox& query) const;
     BBox convertToBox(const BCircle& circle) const;
 
-    void query(const BBox&, std::function<bool (const T&)>) const;
-    void query(const BCircle&, std::function<bool (const T&)>) const;
+    void query(const BBox&, std::function<bool (const T&, const BBox&)>) const;
+    void query(const BCircle&, std::function<bool (const T&, const BBox&)>) const;
 
     int16_t convertToXCellCoord(const float x) const;
     int16_t convertToYCellCoord(const float y) const;