[core] Update unit tests for viewport collision.

Add 'GridIndex' unit test.

9 files changed, 71 insertions, 110 deletions

diff --git a/cmake/test-files.cmake b/cmake/test-files.cmake
index 319790f05a..f291650238 100644
--- a/cmake/test-files.cmake
+++ b/cmake/test-files.cmake
@@ -116,7 +116,6 @@ set(MBGL_TEST_FILES
     test/text/quads.test.cpp
 
     # tile
-    test/tile/annotation_tile.test.cpp
     test/tile/geojson_tile.test.cpp
     test/tile/geometry_tile_data.test.cpp
     test/tile/raster_tile.test.cpp
@@ -128,6 +127,7 @@ set(MBGL_TEST_FILES
     test/util/async_task.test.cpp
     test/util/dtoa.test.cpp
     test/util/geo.test.cpp
+    test/util/grid_index.test.cpp
     test/util/http_timeout.test.cpp
     test/util/image.test.cpp
     test/util/mapbox.test.cpp
diff --git a/test/api/annotations.test.cpp b/test/api/annotations.test.cpp
index 9e622f780a..f3d270c459 100644
--- a/test/api/annotations.test.cpp
+++ b/test/api/annotations.test.cpp
@@ -366,8 +366,8 @@ TEST(Annotations, QueryFractionalZoomLevels) {
     test.map.addAnnotationImage(namedMarker("default_marker"));
 
     std::vector<mbgl::AnnotationID> ids;
-    for (int longitude = 0; longitude < 10; ++longitude) {
-        for (int latitude = 0; latitude < 10; ++latitude) {
+    for (int longitude = 0; longitude < 10; longitude += 2) {
+        for (int latitude = 0; latitude < 10; latitude += 2) {
             ids.push_back(test.map.addAnnotation(SymbolAnnotation { { double(latitude), double(longitude) }, "default_marker" }));
         }
     }
@@ -399,8 +399,8 @@ TEST(Annotations, VisibleFeatures) {
     test.map.setLatLngZoom({ 5, 5 }, 3);
 
     std::vector<mbgl::AnnotationID> ids;
-    for (int longitude = 0; longitude < 10; ++longitude) {
-        for (int latitude = 0; latitude <= 10; ++latitude) {
+    for (int longitude = 0; longitude < 10; longitude += 2) {
+        for (int latitude = 0; latitude <= 10; latitude += 2) {
             ids.push_back(test.map.addAnnotation(SymbolAnnotation { { double(latitude), double(longitude) }, "default_marker" }));
         }
     }
diff --git a/test/fixtures/api/query_style.json b/test/fixtures/api/query_style.json
index 2e499c383d..fd147f7899 100644
--- a/test/fixtures/api/query_style.json
+++ b/test/fixtures/api/query_style.json
@@ -67,7 +67,8 @@
       "type": "symbol",
       "source": "source1",
       "layout": {
-        "icon-image": "test-icon"
+        "icon-image": "test-icon",
+        "icon-allow-overlap": true
       }
     },
     {
@@ -75,7 +76,8 @@
       "type": "symbol",
       "source": "source2",
       "layout": {
-        "icon-image": "test-icon"
+        "icon-image": "test-icon",
+        "icon-allow-overlap": true
       }
     },
     {
@@ -83,7 +85,8 @@
       "type": "symbol",
       "source": "source3",
       "layout": {
-        "icon-image": "test-icon"
+        "icon-image": "test-icon",
+        "icon-allow-overlap": true
       }
     },
     {
@@ -91,7 +94,8 @@
       "type": "symbol",
       "source": "source4",
       "layout": {
-        "icon-image": "test-icon"
+        "icon-image": "test-icon",
+        "icon-allow-overlap": true
       }
     }
   ]
diff --git a/test/fixtures/map/offline/expected.png b/test/fixtures/map/offline/expected.png
index 973c4102da..0005137ae3 100644
--- a/test/fixtures/map/offline/expected.png
+++ b/test/fixtures/map/offline/expected.png
diff --git a/test/gl/bucket.test.cpp b/test/gl/bucket.test.cpp
index 0e73dfb28f..f4f153a831 100644
--- a/test/gl/bucket.test.cpp
+++ b/test/gl/bucket.test.cpp
@@ -109,9 +109,11 @@ TEST(Buckets, SymbolBucket) {
     style::SymbolLayoutProperties::PossiblyEvaluated layout;
     bool sdfIcons = false;
     bool iconsNeedLinear = false;
+    bool sortFeaturesByY = false;
+    std::vector<SymbolInstance> symbolInstances;
 
     gl::Context context;
-    SymbolBucket bucket { layout, {}, 16.0f, 1.0f, 0, sdfIcons, iconsNeedLinear };
+    SymbolBucket bucket { layout, {}, 16.0f, 1.0f, 0, sdfIcons, iconsNeedLinear, sortFeaturesByY, std::move(symbolInstances) };
     ASSERT_FALSE(bucket.hasIconData());
     ASSERT_FALSE(bucket.hasTextData());
     ASSERT_FALSE(bucket.hasCollisionBoxData());
diff --git a/test/tile/annotation_tile.test.cpp b/test/tile/annotation_tile.test.cpp
deleted file mode 100644
index 8f3f903925..0000000000
--- a/test/tile/annotation_tile.test.cpp
+++ /dev/null
@@ -1,95 +0,0 @@
-#include <mbgl/test/util.hpp>
-#include <mbgl/test/fake_file_source.hpp>
-
-#include <mbgl/util/default_thread_pool.hpp>
-#include <mbgl/util/run_loop.hpp>
-#include <mbgl/map/transform.hpp>
-#include <mbgl/renderer/tile_parameters.hpp>
-#include <mbgl/renderer/query.hpp>
-#include <mbgl/text/collision_tile.hpp>
-#include <mbgl/geometry/feature_index.hpp>
-#include <mbgl/annotation/annotation_manager.hpp>
-#include <mbgl/annotation/annotation_tile.hpp>
-#include <mbgl/renderer/image_manager.hpp>
-#include <mbgl/text/glyph_manager.hpp>
-#include <mbgl/renderer/backend_scope.hpp>
-#include <mbgl/gl/headless_backend.hpp>
-#include <mbgl/style/style.hpp>
-
-#include <memory>
-
-using namespace mbgl;
-
-class AnnotationTileTest {
-public:
-    FakeFileSource fileSource;
-    TransformState transformState;
-    util::RunLoop loop;
-    ThreadPool threadPool { 1 };
-    style::Style style { loop, fileSource, 1 };
-    AnnotationManager annotationManager { style };
-    HeadlessBackend backend;
-    BackendScope scope { backend };
-    ImageManager imageManager;
-    GlyphManager glyphManager { fileSource };
-
-    TileParameters tileParameters {
-        1.0,
-        MapDebugOptions(),
-        transformState,
-        threadPool,
-        fileSource,
-        MapMode::Continuous,
-        annotationManager,
-        imageManager,
-        glyphManager,
-        0
-    };
-};
-
-// Don't query stale collision tile
-TEST(AnnotationTile, Issue8289) {
-    AnnotationTileTest test;
-    AnnotationTile tile(OverscaledTileID(0, 0, 0), test.tileParameters);
-
-    auto data = std::make_unique<AnnotationTileData>();
-    data->addLayer("test")->addFeature(0, FeatureType::Point, GeometryCollection());
-
-    // Simulate layout and placement of a symbol layer.
-    tile.onLayout(GeometryTile::LayoutResult {
-        std::unordered_map<std::string, std::shared_ptr<Bucket>>(),
-        std::make_unique<FeatureIndex>(),
-        std::move(data),
-    }, 0);
-
-    auto collisionTile = std::make_unique<CollisionTile>(PlacementConfig());
-
-    IndexedSubfeature subfeature { 0, "", "", 0 };
-    CollisionFeature feature(GeometryCoordinates(), Anchor(0, 0, 0, 0), -5, 5, -5, 5, 1, 0, style::SymbolPlacementType::Point, subfeature, CollisionFeature::AlignmentType::Curved);
-    collisionTile->insertFeature(feature, 0, true);
-    collisionTile->placeFeature(feature, false, false);
-
-    tile.onPlacement(GeometryTile::PlacementResult {
-        std::unordered_map<std::string, std::shared_ptr<Bucket>>(),
-        std::move(collisionTile),
-        {},
-        {},
-    }, 0);
-
-    // Simulate a second layout with empty data.
-    tile.onLayout(GeometryTile::LayoutResult {
-        std::unordered_map<std::string, std::shared_ptr<Bucket>>(),
-        std::make_unique<FeatureIndex>(),
-        std::make_unique<AnnotationTileData>(),
-    }, 0);
-
-    std::unordered_map<std::string, std::vector<Feature>> result;
-    GeometryCoordinates queryGeometry {{ Point<int16_t>(0, 0) }};
-    TransformState transformState;
-    RenderedQueryOptions options;
-
-    tile.queryRenderedFeatures(result, queryGeometry, transformState, {}, options);
-
-    EXPECT_TRUE(result.empty());
-}
-
diff --git a/test/tile/geojson_tile.test.cpp b/test/tile/geojson_tile.test.cpp
index 953c3b8a5f..c05e04bc8d 100644
--- a/test/tile/geojson_tile.test.cpp
+++ b/test/tile/geojson_tile.test.cpp
@@ -66,7 +66,6 @@ TEST(GeoJSONTile, Issue7648) {
 
     tile.setLayers({{ layer.baseImpl }});
     tile.setObserver(&observer);
-    tile.setPlacementConfig({});
 
     while (!tile.isComplete()) {
         test.loop.runOnce();
@@ -93,7 +92,6 @@ TEST(GeoJSONTile, Issue9927) {
     GeoJSONTile tile(OverscaledTileID(0, 0, 0), "source", test.tileParameters, features);
 
     tile.setLayers({{ layer.baseImpl }});
-    tile.setPlacementConfig({});
 
     while (!tile.isComplete()) {
         test.loop.runOnce();
diff --git a/test/tile/vector_tile.test.cpp b/test/tile/vector_tile.test.cpp
index 7e8b659b7a..9d42f7ae74 100644
--- a/test/tile/vector_tile.test.cpp
+++ b/test/tile/vector_tile.test.cpp
@@ -11,7 +11,6 @@
 #include <mbgl/renderer/tile_parameters.hpp>
 #include <mbgl/renderer/buckets/symbol_bucket.hpp>
 #include <mbgl/renderer/query.hpp>
-#include <mbgl/text/collision_tile.hpp>
 #include <mbgl/geometry/feature_index.hpp>
 #include <mbgl/annotation/annotation_manager.hpp>
 #include <mbgl/renderer/image_manager.hpp>
@@ -71,12 +70,13 @@ TEST(VectorTile, Issue7615) {
     VectorTile tile(OverscaledTileID(0, 0, 0), "source", test.tileParameters, test.tileset);
 
     style::SymbolLayer symbolLayer("symbol", "source");
+    std::vector<SymbolInstance> symbolInstances;
     auto symbolBucket = std::make_shared<SymbolBucket>(
         style::SymbolLayoutProperties::PossiblyEvaluated(),
         std::map<
             std::string,
             std::pair<style::IconPaintProperties::PossiblyEvaluated, style::TextPaintProperties::PossiblyEvaluated>>(),
-        16.0f, 1.0f, 0.0f, false, false);
+        16.0f, 1.0f, 0.0f, false, false, false, std::move(symbolInstances));
     
     // Simulate placement of a symbol layer.
     tile.onPlacement(GeometryTile::PlacementResult {
@@ -84,7 +84,6 @@ TEST(VectorTile, Issue7615) {
             symbolLayer.getID(),
             symbolBucket
         }},
-        nullptr,
         {},
         {},
     }, 0);
diff --git a/test/util/grid_index.test.cpp b/test/util/grid_index.test.cpp
new file mode 100644
index 0000000000..b0a4e581a3
--- /dev/null
+++ b/test/util/grid_index.test.cpp
@@ -0,0 +1,53 @@
+#include <mbgl/util/grid_index.hpp>
+#include <mbgl/util/grid_index.cpp>
+
+#include <mbgl/test/util.hpp>
+
+using namespace mbgl;
+
+TEST(GridIndex, IndexesFeatures) {
+    GridIndex<int16_t> grid(100, 100, 10);
+    grid.insert(0, {{4, 10}, {6, 30}});
+    grid.insert(1, {{4, 10}, {30, 12}});
+    grid.insert(2, {{-10, 30}, {5, 35}});
+    
+    EXPECT_EQ(grid.query({{4, 10}, {5, 11}}), (std::vector<int16_t>{0, 1}));
+    EXPECT_EQ(grid.query({{24, 10}, {25, 11}}), (std::vector<int16_t>{1}));
+    EXPECT_EQ(grid.query({{40, 40}, {100, 100}}), (std::vector<int16_t>{}));
+    EXPECT_EQ(grid.query({{-6, 0}, {3, 100}}), (std::vector<int16_t>{2}));
+    EXPECT_EQ(grid.query({{-1000, -1000}, {1000, 1000}}), (std::vector<int16_t>{0, 1, 2}));
+}
+
+TEST(GridIndex, DuplicateKeys) {
+    GridIndex<int16_t> grid(100, 100, 10);
+    #define KEY 123
+    grid.insert(KEY, {{3, 4}, {4, 4}});
+    grid.insert(KEY, {{13, 13}, {14, 14}});
+    grid.insert(KEY, {{23, 23}, {24, 24}});
+    
+    EXPECT_EQ(grid.query({{0, 0}, {30, 30}}), (std::vector<int16_t>{KEY, KEY, KEY}));
+}
+
+TEST(GridIndex, CircleCircle) {
+    GridIndex<int16_t> grid(100, 100, 10);
+    grid.insert(0, {{50, 50}, 10});
+    grid.insert(1, {{60, 60}, 15});
+    grid.insert(2, {{-10, 110}, 20});
+    
+    EXPECT_TRUE(grid.hitTest({{55, 55}, 2}));
+    EXPECT_FALSE(grid.hitTest({{10, 10}, 10}));
+    EXPECT_TRUE(grid.hitTest({{0, 100}, 10}));
+    EXPECT_TRUE(grid.hitTest({{80, 60}, 10}));
+}
+
+TEST(GridIndex, CircleBox) {
+    GridIndex<int16_t> grid(100, 100, 10);
+    grid.insert(0, {{50, 50}, 10});
+    grid.insert(1, {{60, 60}, 15});
+    grid.insert(2, {{-10, 110}, 20});
+    
+    EXPECT_EQ(grid.query({{45, 45}, {55, 55}}), (std::vector<int16_t>{0, 1}));
+    EXPECT_EQ(grid.query({{0, 0}, {30, 30}}), (std::vector<int16_t>{}));
+    EXPECT_EQ(grid.query({{0, 80}, {20, 100}}), (std::vector<int16_t>{2}));
+}
+