[core, android, ios, macos] Replaced getPointAnnotationsInBounds() w/ queryPointAnnotations() (#5165)

queryPointAnnotations() accepts a screen rectangle instead of a geographic bounding box, so marker hit testing works at the edges of a rotated, tilted map view.

Fixes #5151.

16 files changed, 75 insertions, 63 deletions

diff --git a/include/mbgl/map/map.hpp b/include/mbgl/map/map.hpp
index 0e0c04ff0f..fac110e2a8 100644
--- a/include/mbgl/map/map.hpp
+++ b/include/mbgl/map/map.hpp
@@ -148,8 +148,6 @@ public:
     void updateAnnotation(AnnotationID, const Annotation&);
     void removeAnnotation(AnnotationID);
 
-    AnnotationIDs getPointAnnotationsInBounds(const LatLngBounds&);
-
     // Sources
     style::Source* getSource(const std::string& sourceID);
     void addSource(std::unique_ptr<style::Source>);
@@ -163,6 +161,7 @@ public:
     // Feature queries
     std::vector<Feature> queryRenderedFeatures(const ScreenCoordinate&, const optional<std::vector<std::string>>& layerIDs = {});
     std::vector<Feature> queryRenderedFeatures(const ScreenBox&,        const optional<std::vector<std::string>>& layerIDs = {});
+    AnnotationIDs queryPointAnnotations(const ScreenBox&);
 
     // Memory
     void setSourceTileCacheSize(size_t);
diff --git a/platform/android/MapboxGLAndroidSDK/src/main/java/com/mapbox/mapboxsdk/annotations/MarkerViewManager.java b/platform/android/MapboxGLAndroidSDK/src/main/java/com/mapbox/mapboxsdk/annotations/MarkerViewManager.java
index 682ba140c4..9631bc4ca8 100644
--- a/platform/android/MapboxGLAndroidSDK/src/main/java/com/mapbox/mapboxsdk/annotations/MarkerViewManager.java
+++ b/platform/android/MapboxGLAndroidSDK/src/main/java/com/mapbox/mapboxsdk/annotations/MarkerViewManager.java
@@ -2,6 +2,7 @@ package com.mapbox.mapboxsdk.annotations;
 
 import android.content.Context;
 import android.graphics.PointF;
+import android.graphics.RectF;
 import android.os.SystemClock;
 import android.support.annotation.NonNull;
 import android.support.annotation.Nullable;
@@ -321,7 +322,7 @@ public class MarkerViewManager {
 
         if (!markerViewAdapters.contains(markerViewAdapter)) {
             markerViewAdapters.add(markerViewAdapter);
-            invalidateViewMarkersInBounds();
+            invalidateViewMarkersInVisibleRegion();
         }
     }
 
@@ -346,7 +347,7 @@ public class MarkerViewManager {
     /**
      * Schedule that ViewMarkers found in the viewport are invalidated.
      * <p>
-     * This method is rate limited, and {@link #invalidateViewMarkersInBounds} will only be called
+     * This method is rate limited, and {@link #invalidateViewMarkersInVisibleRegion} will only be called
      * once each 250 ms.
      * </p>
      */
@@ -356,7 +357,7 @@ public class MarkerViewManager {
             if (currentTime < viewMarkerBoundsUpdateTime) {
                 return;
             }
-            invalidateViewMarkersInBounds();
+            invalidateViewMarkersInVisibleRegion();
             viewMarkerBoundsUpdateTime = currentTime + 250;
         }
     }
@@ -368,9 +369,9 @@ public class MarkerViewManager {
      * ones for each found Marker in the changed viewport.
      * </p>
      */
-    public void invalidateViewMarkersInBounds() {
-        Projection projection = mapboxMap.getProjection();
-        List<MarkerView> markers = mapView.getMarkerViewsInBounds(projection.getVisibleRegion().latLngBounds);
+    public void invalidateViewMarkersInVisibleRegion() {
+        RectF mapViewRect = new RectF(0, 0, mapView.getWidth(), mapView.getHeight());
+        List<MarkerView> markers = mapView.getMarkerViewsInRect(mapViewRect);
         View convertView;
 
         // remove old markers
diff --git a/platform/android/MapboxGLAndroidSDK/src/main/java/com/mapbox/mapboxsdk/maps/MapView.java b/platform/android/MapboxGLAndroidSDK/src/main/java/com/mapbox/mapboxsdk/maps/MapView.java
index 54f165ac86..b17350f4f4 100644
--- a/platform/android/MapboxGLAndroidSDK/src/main/java/com/mapbox/mapboxsdk/maps/MapView.java
+++ b/platform/android/MapboxGLAndroidSDK/src/main/java/com/mapbox/mapboxsdk/maps/MapView.java
@@ -1153,13 +1153,13 @@ public class MapView extends FrameLayout {
         mNativeMapView.removeAnnotations(ids);
     }
 
-    List<Marker> getMarkersInBounds(@NonNull LatLngBounds bbox) {
-        if (mDestroyed || bbox == null) {
+    List<Marker> getMarkersInRect(@NonNull RectF rect) {
+        if (mDestroyed || rect == null) {
             return new ArrayList<>();
         }
 
-        // TODO: filter in JNI using C++ parameter to getAnnotationsInBounds
-        long[] ids = mNativeMapView.getAnnotationsInBounds(bbox);
+        // TODO: filter in JNI using C++ parameter to queryPointAnnotations
+        long[] ids = mNativeMapView.queryPointAnnotations(rect);
 
         List<Long> idsList = new ArrayList<>(ids.length);
         for (int i = 0; i < ids.length; i++) {
@@ -1179,13 +1179,13 @@ public class MapView extends FrameLayout {
         return new ArrayList<>(annotations);
     }
 
-    public List<MarkerView> getMarkerViewsInBounds(@NonNull LatLngBounds bbox) {
-        if (mDestroyed || bbox == null) {
+    public List<MarkerView> getMarkerViewsInRect(@NonNull RectF rect) {
+        if (mDestroyed || rect == null) {
             return new ArrayList<>();
         }
 
-        // TODO: filter in JNI using C++ parameter to getAnnotationsInBounds
-        long[] ids = mNativeMapView.getAnnotationsInBounds(bbox);
+        // TODO: filter in JNI using C++ parameter to queryPointAnnotations
+        long[] ids = mNativeMapView.queryPointAnnotations(rect);
 
         List<Long> idsList = new ArrayList<>(ids.length);
         for (int i = 0; i < ids.length; i++) {
@@ -1730,13 +1730,7 @@ public class MapView extends FrameLayout {
                     tapPoint.x + mAverageIconWidth / 2 + toleranceSides,
                     tapPoint.y + mAverageIconHeight / 2 + toleranceTopBottom);
 
-            LatLngBounds.Builder builder = new LatLngBounds.Builder();
-            builder.include(fromScreenLocation(new PointF(tapRect.left, tapRect.bottom)));
-            builder.include(fromScreenLocation(new PointF(tapRect.left, tapRect.top)));
-            builder.include(fromScreenLocation(new PointF(tapRect.right, tapRect.top)));
-            builder.include(fromScreenLocation(new PointF(tapRect.right, tapRect.bottom)));
-
-            List<Marker> nearbyMarkers = getMarkersInBounds(builder.build());
+            List<Marker> nearbyMarkers = getMarkersInRect(tapRect);
             long newSelectedMarkerId = -1;
 
             if (nearbyMarkers != null && nearbyMarkers.size() > 0) {
diff --git a/platform/android/MapboxGLAndroidSDK/src/main/java/com/mapbox/mapboxsdk/maps/MapboxMap.java b/platform/android/MapboxGLAndroidSDK/src/main/java/com/mapbox/mapboxsdk/maps/MapboxMap.java
index 288c6feb4f..b2c48be69c 100644
--- a/platform/android/MapboxGLAndroidSDK/src/main/java/com/mapbox/mapboxsdk/maps/MapboxMap.java
+++ b/platform/android/MapboxGLAndroidSDK/src/main/java/com/mapbox/mapboxsdk/maps/MapboxMap.java
@@ -765,7 +765,7 @@ public class MapboxMap {
         long id = mMapView.addMarker(marker);
         marker.setId(id);
         mAnnotations.put(id, marker);
-        mMarkerViewManager.invalidateViewMarkersInBounds();
+        mMarkerViewManager.invalidateViewMarkersInVisibleRegion();
         return marker;
     }
 
diff --git a/platform/android/MapboxGLAndroidSDK/src/main/java/com/mapbox/mapboxsdk/maps/NativeMapView.java b/platform/android/MapboxGLAndroidSDK/src/main/java/com/mapbox/mapboxsdk/maps/NativeMapView.java
index 929f515d8d..c93ac9c145 100755
--- a/platform/android/MapboxGLAndroidSDK/src/main/java/com/mapbox/mapboxsdk/maps/NativeMapView.java
+++ b/platform/android/MapboxGLAndroidSDK/src/main/java/com/mapbox/mapboxsdk/maps/NativeMapView.java
@@ -402,8 +402,8 @@ final class NativeMapView {
         nativeRemoveAnnotations(mNativeMapViewPtr, ids);
     }
 
-    public long[] getAnnotationsInBounds(LatLngBounds bbox) {
-        return nativeGetAnnotationsInBounds(mNativeMapViewPtr, bbox);
+    public long[] queryPointAnnotations(RectF rect) {
+        return nativeQueryPointAnnotations(mNativeMapViewPtr, rect);
     }
 
     public void addAnnotationIcon(String symbol, int width, int height, float scale, byte[] pixels) {
@@ -641,7 +641,7 @@ final class NativeMapView {
 
     private native void nativeRemoveAnnotations(long nativeMapViewPtr, long[] id);
 
-    private native long[] nativeGetAnnotationsInBounds(long mNativeMapViewPtr, LatLngBounds bbox);
+    private native long[] nativeQueryPointAnnotations(long mNativeMapViewPtr, RectF rect);
 
     private native void nativeAddAnnotationIcon(long nativeMapViewPtr, String symbol,
                                                 int width, int height, float scale, byte[] pixels);
diff --git a/platform/android/src/jni.cpp b/platform/android/src/jni.cpp
index 5907a0ff9d..89dbfe1cc2 100755
--- a/platform/android/src/jni.cpp
+++ b/platform/android/src/jni.cpp
@@ -842,20 +842,24 @@ void nativeRemoveAnnotations(JNIEnv *env, jni::jobject* obj, jlong nativeMapView
     }
 }
 
-jni::jarray<jlong>* nativeGetAnnotationsInBounds(JNIEnv *env, jni::jobject* obj, jlong nativeMapViewPtr, jni::jobject* latLngBounds_) {
-    mbgl::Log::Debug(mbgl::Event::JNI, "nativeGetAnnotationsInBounds");
+jni::jarray<jlong>* nativeQueryPointAnnotations(JNIEnv *env, jni::jobject* obj, jlong nativeMapViewPtr, jni::jobject* rect) {
+    mbgl::Log::Debug(mbgl::Event::JNI, "nativeQueryPointAnnotations");
     assert(nativeMapViewPtr != 0);
     NativeMapView *nativeMapView = reinterpret_cast<NativeMapView *>(nativeMapViewPtr);
 
     // Conversion
-    mbgl::LatLngBounds latLngBounds = latlngbounds_from_java(env, latLngBounds_);
-    if (latLngBounds.isEmpty()) {
-        return nullptr;
-    }
+    jfloat left = jni::GetField<jfloat>(*env, rect, *rectFLeftId);
+    jfloat right = jni::GetField<jfloat>(*env, rect, *rectFRightId);
+    jfloat top = jni::GetField<jfloat>(*env, rect, *rectFTopId);
+    jfloat bottom = jni::GetField<jfloat>(*env, rect, *rectFBottomId);
+    mbgl::ScreenBox box = {
+        { left, top },
+        { right, bottom },
+    };
 
     // Assume only points for now
-    std::vector<uint32_t> annotations = nativeMapView->getMap().getPointAnnotationsInBounds(
-        latLngBounds);
+    std::vector<uint32_t> annotations = nativeMapView->getMap().queryPointAnnotations(
+        box);
 
     return std_vector_uint_to_jobject(env, annotations);
 }
@@ -1772,7 +1776,7 @@ extern "C" JNIEXPORT jint JNI_OnLoad(JavaVM *vm, void *reserved) {
         MAKE_NATIVE_METHOD(nativeUpdatePolygon, "(JJLcom/mapbox/mapboxsdk/annotations/Polygon;)J"),
         MAKE_NATIVE_METHOD(nativeUpdatePolyline, "(JJLcom/mapbox/mapboxsdk/annotations/Polyline;)J"),
         MAKE_NATIVE_METHOD(nativeRemoveAnnotations, "(J[J)V"),
-        MAKE_NATIVE_METHOD(nativeGetAnnotationsInBounds, "(JLcom/mapbox/mapboxsdk/geometry/LatLngBounds;)[J"),
+        MAKE_NATIVE_METHOD(nativeQueryPointAnnotations, "(JLandroid/graphics/RectF;)[J"),
         MAKE_NATIVE_METHOD(nativeAddAnnotationIcon, "(JLjava/lang/String;IIF[B)V"),
         MAKE_NATIVE_METHOD(nativeSetVisibleCoordinateBounds, "(J[Lcom/mapbox/mapboxsdk/geometry/LatLng;Landroid/graphics/RectF;DJ)V"),
         MAKE_NATIVE_METHOD(nativeOnLowMemory, "(J)V"),
diff --git a/platform/ios/src/MGLMapView.mm b/platform/ios/src/MGLMapView.mm
index fa885d020d..113bd2cef6 100644
--- a/platform/ios/src/MGLMapView.mm
+++ b/platform/ios/src/MGLMapView.mm
@@ -3371,8 +3371,10 @@ mbgl::Duration MGLDurationInSeconds(NSTimeInterval duration)
 /// Returns the tags of the annotations coincident with the given rectangle.
 - (std::vector<MGLAnnotationTag>)annotationTagsInRect:(CGRect)rect
 {
-    mbgl::LatLngBounds queryBounds = [self convertRect:rect toLatLngBoundsFromView:self];
-    return _mbglMap->getPointAnnotationsInBounds(queryBounds);
+    return _mbglMap->queryPointAnnotations({
+        { CGRectGetMinX(rect), CGRectGetMinY(rect) },
+        { CGRectGetMaxX(rect), CGRectGetMaxY(rect) },
+    });
 }
 
 - (id <MGLAnnotation>)selectedAnnotation
diff --git a/platform/macos/src/MGLMapView.mm b/platform/macos/src/MGLMapView.mm
index c9f295d7e7..de127a7481 100644
--- a/platform/macos/src/MGLMapView.mm
+++ b/platform/macos/src/MGLMapView.mm
@@ -1897,8 +1897,11 @@ public:
 
 /// Returns the tags of the annotations coincident with the given rectangle.
 - (std::vector<MGLAnnotationTag>)annotationTagsInRect:(NSRect)rect {
-    mbgl::LatLngBounds queryBounds = [self convertRect:rect toLatLngBoundsFromView:self];
-    return _mbglMap->getPointAnnotationsInBounds(queryBounds);
+    // Cocoa origin is at the lower-left corner.
+    return _mbglMap->queryPointAnnotations({
+        { NSMinX(rect), NSHeight(self.bounds) - NSMaxY(rect) },
+        { NSMaxX(rect), NSHeight(self.bounds) - NSMinY(rect) },
+    });
 }
 
 - (id <MGLAnnotation>)selectedAnnotation {
diff --git a/src/mbgl/annotation/annotation_manager.cpp b/src/mbgl/annotation/annotation_manager.cpp
index 0cd6bdf231..4e837d370d 100644
--- a/src/mbgl/annotation/annotation_manager.cpp
+++ b/src/mbgl/annotation/annotation_manager.cpp
@@ -115,17 +115,6 @@ void AnnotationManager::removeAndAdd(const AnnotationID& id, const Annotation& a
     });
 }
 
-AnnotationIDs AnnotationManager::getPointAnnotationsInBounds(const LatLngBounds& bounds) const {
-    AnnotationIDs result;
-
-    symbolTree.query(boost::geometry::index::intersects(bounds),
-        boost::make_function_output_iterator([&](const auto& val){
-            result.push_back(val->id);
-        }));
-
-    return result;
-}
-
 std::unique_ptr<AnnotationTileData> AnnotationManager::getTileData(const CanonicalTileID& tileID) {
     if (symbolAnnotations.empty() && shapeAnnotations.empty())
         return nullptr;
diff --git a/src/mbgl/annotation/annotation_manager.hpp b/src/mbgl/annotation/annotation_manager.hpp
index ffe6cd163a..a0f25fdf57 100644
--- a/src/mbgl/annotation/annotation_manager.hpp
+++ b/src/mbgl/annotation/annotation_manager.hpp
@@ -33,8 +33,6 @@ public:
     Update updateAnnotation(const AnnotationID&, const Annotation&, const uint8_t maxZoom);
     void removeAnnotation(const AnnotationID&);
 
-    AnnotationIDs getPointAnnotationsInBounds(const LatLngBounds&) const;
-
     void addIcon(const std::string& name, std::shared_ptr<const SpriteImage>);
     void removeIcon(const std::string& name);
     double getTopOffsetPixelsForIcon(const std::string& name);
diff --git a/src/mbgl/annotation/annotation_tile.cpp b/src/mbgl/annotation/annotation_tile.cpp
index 91b7f7ddc1..06ae82adb3 100644
--- a/src/mbgl/annotation/annotation_tile.cpp
+++ b/src/mbgl/annotation/annotation_tile.cpp
@@ -21,9 +21,11 @@ AnnotationTile::~AnnotationTile() {
 
 void AnnotationTile::setNecessity(Necessity) {}
 
-AnnotationTileFeature::AnnotationTileFeature(FeatureType type_, GeometryCollection geometries_,
-                                 std::unordered_map<std::string, std::string> properties_)
-    : type(type_),
+AnnotationTileFeature::AnnotationTileFeature(const AnnotationID id_,
+                                             FeatureType type_, GeometryCollection geometries_,
+                                             std::unordered_map<std::string, std::string> properties_)
+    : id(id_),
+      type(type_),
       properties(std::move(properties_)),
       geometries(std::move(geometries_)) {}
 
diff --git a/src/mbgl/annotation/annotation_tile.hpp b/src/mbgl/annotation/annotation_tile.hpp
index 3e7c2c447f..4e0b1551d7 100644
--- a/src/mbgl/annotation/annotation_tile.hpp
+++ b/src/mbgl/annotation/annotation_tile.hpp
@@ -1,5 +1,6 @@
 #pragma once
 
+#include <mbgl/annotation/annotation.hpp>
 #include <mbgl/tile/geometry_tile.hpp>
 #include <mbgl/tile/geometry_tile_data.hpp>
 
@@ -25,13 +26,15 @@ private:
 
 class AnnotationTileFeature : public GeometryTileFeature {
 public:
-    AnnotationTileFeature(FeatureType, GeometryCollection,
+    AnnotationTileFeature(AnnotationID, FeatureType, GeometryCollection,
                           std::unordered_map<std::string, std::string> properties = {{}});
 
     FeatureType getType() const override { return type; }
     optional<Value> getValue(const std::string&) const override;
+    optional<FeatureIdentifier> getID() const override { return { id }; }
     GeometryCollection getGeometries() const override { return geometries; }
 
+    const AnnotationID id;
     const FeatureType type;
     const std::unordered_map<std::string, std::string> properties;
     const GeometryCollection geometries;
diff --git a/src/mbgl/annotation/shape_annotation_impl.cpp b/src/mbgl/annotation/shape_annotation_impl.cpp
index 445ee76511..345fe3acda 100644
--- a/src/mbgl/annotation/shape_annotation_impl.cpp
+++ b/src/mbgl/annotation/shape_annotation_impl.cpp
@@ -55,7 +55,7 @@ void ShapeAnnotationImpl::updateTileData(const CanonicalTileID& tileID, Annotati
         }
 
         layer.features.emplace_back(
-            std::make_shared<AnnotationTileFeature>(featureType, renderGeometry));
+            std::make_shared<AnnotationTileFeature>(id, featureType, renderGeometry));
     }
 }
 
diff --git a/src/mbgl/annotation/symbol_annotation_impl.cpp b/src/mbgl/annotation/symbol_annotation_impl.cpp
index 5ac2581949..20454e05c1 100644
--- a/src/mbgl/annotation/symbol_annotation_impl.cpp
+++ b/src/mbgl/annotation/symbol_annotation_impl.cpp
@@ -31,7 +31,8 @@ void SymbolAnnotationImpl::updateLayer(const CanonicalTileID& tileID, Annotation
     projected *= double(util::EXTENT);
 
     layer.features.emplace_back(
-        std::make_shared<const AnnotationTileFeature>(FeatureType::Point,
+        std::make_shared<const AnnotationTileFeature>(id,
+                                                      FeatureType::Point,
                                                       GeometryCollection {{ {{ convertPoint<int16_t>(projected) }} }},
                                                       featureProperties));
 }
diff --git a/src/mbgl/map/map.cpp b/src/mbgl/map/map.cpp
index 659832dc77..7570a8d303 100644
--- a/src/mbgl/map/map.cpp
+++ b/src/mbgl/map/map.cpp
@@ -703,10 +703,6 @@ void Map::removeAnnotation(AnnotationID annotation) {
     update(Update::AnnotationStyle | Update::AnnotationData);
 }
 
-AnnotationIDs Map::getPointAnnotationsInBounds(const LatLngBounds& bounds) {
-    return impl->annotationManager->getPointAnnotationsInBounds(bounds);
-}
-
 #pragma mark - Feature query api
 
 std::vector<Feature> Map::queryRenderedFeatures(const ScreenCoordinate& point, const optional<std::vector<std::string>>& layerIDs) {
@@ -735,6 +731,18 @@ std::vector<Feature> Map::queryRenderedFeatures(const ScreenBox& box, const opti
     });
 }
 
+AnnotationIDs Map::queryPointAnnotations(const ScreenBox& box) {
+    auto features = queryRenderedFeatures(box, {{ AnnotationManager::PointLayerID }});
+    AnnotationIDs ids;
+    ids.reserve(features.size());
+    for (auto &feature : features) {
+        assert(feature.id);
+        assert(*feature.id <= std::numeric_limits<AnnotationID>::max());
+        ids.push_back(static_cast<AnnotationID>(feature.id->get<uint64_t>()));
+    }
+    return ids;
+}
+
 #pragma mark - Style API
 
 style::Source* Map::getSource(const std::string& sourceID) {
diff --git a/test/api/annotations.cpp b/test/api/annotations.cpp
index a1e67b29c4..336e36ab99 100644
--- a/test/api/annotations.cpp
+++ b/test/api/annotations.cpp
@@ -217,9 +217,17 @@ TEST(Annotations, QueryRenderedFeatures) {
     test.map.setStyleJSON(util::read_file("test/fixtures/api/empty.json"));
     test.map.addAnnotationIcon("default_marker", namedMarker("default_marker.png"));
     test.map.addAnnotation(SymbolAnnotation { Point<double> { 0, 0 }, "default_marker" });
+    test.map.addAnnotation(SymbolAnnotation { Point<double> { 0, 50 }, "default_marker" });
 
     test::render(test.map);
 
     auto features = test.map.queryRenderedFeatures(test.map.pixelForLatLng({ 0, 0 }));
     EXPECT_EQ(features.size(), 1u);
+    EXPECT_TRUE(!!features[0].id);
+    EXPECT_EQ(*features[0].id, 0);
+
+    auto features2 = test.map.queryRenderedFeatures(test.map.pixelForLatLng({ 50, 0 }));
+    EXPECT_EQ(features2.size(), 1);
+    EXPECT_TRUE(!!features2[0].id);
+    EXPECT_EQ(*features2[0].id, 1);
 }