[core] implement symbol-avoid-edges

ref #3582

if `symbol-avoid-edges` is true, this prevents symbols from colliding
with tile edges.

3 files changed, 98 insertions, 41 deletions

diff --git a/src/mbgl/renderer/symbol_bucket.cpp b/src/mbgl/renderer/symbol_bucket.cpp
index 45e718fd94..75cf496d15 100644
--- a/src/mbgl/renderer/symbol_bucket.cpp
+++ b/src/mbgl/renderer/symbol_bucket.cpp
@@ -396,10 +396,14 @@ void SymbolBucket::placeFeatures(CollisionTile& collisionTile) {
 
         // Calculate the scales at which the text and icon can be placed without collision.
 
-        float glyphScale = hasText && !layout.text.allowOverlap ?
-            collisionTile.placeFeature(symbolInstance.textCollisionFeature) : collisionTile.minScale;
-        float iconScale = hasIcon && !layout.icon.allowOverlap ?
-            collisionTile.placeFeature(symbolInstance.iconCollisionFeature) : collisionTile.minScale;
+        float glyphScale = hasText ?
+            collisionTile.placeFeature(symbolInstance.textCollisionFeature,
+                    layout.text.allowOverlap, layout.avoidEdges) :
+            collisionTile.minScale;
+        float iconScale = hasIcon ?
+            collisionTile.placeFeature(symbolInstance.iconCollisionFeature,
+                    layout.icon.allowOverlap, layout.avoidEdges) :
+            collisionTile.minScale;
 
 
         // Combine the scales for icons and text.
diff --git a/src/mbgl/text/collision_tile.cpp b/src/mbgl/text/collision_tile.cpp
index dbd9a6cb10..b24e2cfcdb 100644
--- a/src/mbgl/text/collision_tile.cpp
+++ b/src/mbgl/text/collision_tile.cpp
@@ -3,13 +3,26 @@
 
 namespace mbgl {
 
-CollisionTile::CollisionTile(PlacementConfig config_) : config(config_) {
+auto infinity = std::numeric_limits<float>::infinity();
+
+CollisionTile::CollisionTile(PlacementConfig config_) : config(config_),
+    edges({{
+        // left
+        CollisionBox(vec2<float>(0, 0), 0, -infinity, 0, infinity, infinity),
+        // right
+        CollisionBox(vec2<float>(extent, 0), 0, -infinity, 0, infinity, infinity),
+        // top
+        CollisionBox(vec2<float>(0, 0), -infinity, 0, infinity, 0, infinity),
+        // bottom
+        CollisionBox(vec2<float>(0, extent), -infinity, 0, infinity, 0, infinity),
+    }}) {
     tree.clear();
 
     // Compute the transformation matrix.
     const float angle_sin = std::sin(config.angle);
     const float angle_cos = std::cos(config.angle);
     rotationMatrix = { { angle_cos, -angle_sin, angle_sin, angle_cos } };
+    reverseRotationMatrix = { { angle_cos, angle_sin, -angle_sin, angle_cos } };
 
     // Stretch boxes in y direction to account for the map tilt.
     const float _yStretch = 1.0f / std::cos(config.pitch);
@@ -19,54 +32,88 @@ CollisionTile::CollisionTile(PlacementConfig config_) : config(config_) {
     yStretch = std::pow(_yStretch, 1.3);
 }
 
-float CollisionTile::placeFeature(const CollisionFeature &feature) {
 
-    float minPlacementScale = minScale;
+float CollisionTile::findPlacementScale(float minPlacementScale, const vec2<float>& anchor,
+        const CollisionBox& box, const vec2<float>& blockingAnchor, const CollisionBox& blocking) {
 
-    for (auto& box : feature.boxes) {
-        const auto anchor = box.anchor.matMul(rotationMatrix);
 
-        std::vector<CollisionTreeBox> blockingBoxes;
-        tree.query(bgi::intersects(getTreeBox(anchor, box)), std::back_inserter(blockingBoxes));
+    // Find the lowest scale at which the two boxes can fit side by side without overlapping.
+    // Original algorithm:
+    float s1 = (blocking.x1 - box.x2) / (anchor.x - blockingAnchor.x); // scale at which new box is to the left of old box
+    float s2 = (blocking.x2 - box.x1) / (anchor.x - blockingAnchor.x); // scale at which new box is to the right of old box
+    float s3 = (blocking.y1 - box.y2) * yStretch / (anchor.y - blockingAnchor.y); // scale at which new box is to the top of old box
+    float s4 = (blocking.y2 - box.y1) * yStretch / (anchor.y - blockingAnchor.y); // scale at which new box is to the bottom of old box
 
-        for (auto& blockingTreeBox : blockingBoxes) {
-            const auto& blocking = std::get<1>(blockingTreeBox);
-            auto blockingAnchor = blocking.anchor.matMul(rotationMatrix);
+    if (std::isnan(s1) || std::isnan(s2)) s1 = s2 = 1;
+    if (std::isnan(s3) || std::isnan(s4)) s3 = s4 = 1;
 
-            // Find the lowest scale at which the two boxes can fit side by side without overlapping.
-            // Original algorithm:
-            float s1 = (blocking.x1 - box.x2) / (anchor.x - blockingAnchor.x); // scale at which new box is to the left of old box
-            float s2 = (blocking.x2 - box.x1) / (anchor.x - blockingAnchor.x); // scale at which new box is to the right of old box
-            float s3 = (blocking.y1 - box.y2) * yStretch / (anchor.y - blockingAnchor.y); // scale at which new box is to the top of old box
-            float s4 = (blocking.y2 - box.y1) * yStretch / (anchor.y - blockingAnchor.y); // scale at which new box is to the bottom of old box
+    float collisionFreeScale = ::fmin(::fmax(s1, s2), ::fmax(s3, s4));
+
+    if (collisionFreeScale > blocking.maxScale) {
+        // After a box's maxScale the label has shrunk enough that the box is no longer needed to cover it,
+        // so unblock the new box at the scale that the old box disappears.
+        collisionFreeScale = blocking.maxScale;
+    }
 
-            if (std::isnan(s1) || std::isnan(s2)) s1 = s2 = 1;
-            if (std::isnan(s3) || std::isnan(s4)) s3 = s4 = 1;
+    if (collisionFreeScale > box.maxScale) {
+        // If the box can only be shown after it is visible, then the box can never be shown.
+        // But the label can be shown after this box is not visible.
+        collisionFreeScale = box.maxScale;
+    }
 
-            float collisionFreeScale = ::fmin(::fmax(s1, s2), ::fmax(s3, s4));
+    if (collisionFreeScale > minPlacementScale &&
+            collisionFreeScale >= blocking.placementScale) {
+        // If this collision occurs at a lower scale than previously found collisions
+        // and the collision occurs while the other label is visible
 
-            if (collisionFreeScale > blocking.maxScale) {
-                // After a box's maxScale the label has shrunk enough that the box is no longer needed to cover it,
-                // so unblock the new box at the scale that the old box disappears.
-                collisionFreeScale = blocking.maxScale;
-            }
+        // this this is the lowest scale at which the label won't collide with anything
+        minPlacementScale = collisionFreeScale;
+    }
 
-            if (collisionFreeScale > box.maxScale) {
-                // If the box can only be shown after it is visible, then the box can never be shown.
-                // But the label can be shown after this box is not visible.
-                collisionFreeScale = box.maxScale;
-            }
+    return minPlacementScale;
+}
+
+float CollisionTile::placeFeature(const CollisionFeature &feature, const bool allowOverlap, const bool avoidEdges) {
+
+    float minPlacementScale = minScale;
+
+    for (auto& box : feature.boxes) {
+        const auto anchor = box.anchor.matMul(rotationMatrix);
+
+        if (!allowOverlap) {
+            std::vector<CollisionTreeBox> blockingBoxes;
+            tree.query(bgi::intersects(getTreeBox(anchor, box)), std::back_inserter(blockingBoxes));
 
-            if (collisionFreeScale > minPlacementScale &&
-                    collisionFreeScale >= blocking.placementScale) {
-                // If this collision occurs at a lower scale than previously found collisions
-                // and the collision occurs while the other label is visible
+            for (auto& blockingTreeBox : blockingBoxes) {
+                const auto& blocking = std::get<1>(blockingTreeBox);
+                auto blockingAnchor = blocking.anchor.matMul(rotationMatrix);
 
-                // this this is the lowest scale at which the label won't collide with anything
-                minPlacementScale = collisionFreeScale;
+                minPlacementScale = findPlacementScale(minPlacementScale, anchor, box, blockingAnchor, blocking);
+                if (minPlacementScale >= maxScale) return minPlacementScale;
             }
+        }
 
-            if (minPlacementScale >= maxScale) return minPlacementScale;
+        if (avoidEdges) {
+            const vec2<float> tl = { box.x1, box.y1 };
+            const vec2<float> tr = { box.x2, box.y1 };
+            const vec2<float> bl = { box.x1, box.y2 };
+            const vec2<float> br = { box.x2, box.y2 };
+            const vec2<float> rtl = tl.matMul(reverseRotationMatrix);
+            const vec2<float> rtr = tr.matMul(reverseRotationMatrix);
+            const vec2<float> rbl = bl.matMul(reverseRotationMatrix);
+            const vec2<float> rbr = br.matMul(reverseRotationMatrix);
+            CollisionBox rotatedBox(box.anchor,
+                    ::fmin(::fmin(rtl.x, rtr.x), ::fmin(rbl.x, rbr.x)),
+                    ::fmin(::fmin(rtl.y, rtr.y), ::fmin(rbl.y, rbr.y)),
+                    ::fmax(::fmax(rtl.x, rtr.x), ::fmax(rbl.x, rbr.x)),
+                    ::fmax(::fmax(rtl.y, rtr.y), ::fmax(rbl.y, rbr.y)),
+                    box.maxScale);
+
+            for (auto& blocking : edges) {
+                minPlacementScale = findPlacementScale(minPlacementScale, box.anchor, rotatedBox, blocking.anchor, blocking);
+
+                if (minPlacementScale >= maxScale) return minPlacementScale;
+            }
         }
     }
 
diff --git a/src/mbgl/text/collision_tile.hpp b/src/mbgl/text/collision_tile.hpp
index edd5eb61a0..f535dfe4ff 100644
--- a/src/mbgl/text/collision_tile.hpp
+++ b/src/mbgl/text/collision_tile.hpp
@@ -37,7 +37,7 @@ class CollisionTile {
 public:
     explicit CollisionTile(PlacementConfig);
 
-    float placeFeature(const CollisionFeature& feature);
+    float placeFeature(const CollisionFeature& feature, const bool allowOverlap, const bool avoidEdges);
     void insertFeature(CollisionFeature& feature, const float minPlacementScale);
 
     const PlacementConfig config;
@@ -47,10 +47,16 @@ public:
     float yStretch;
 
 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);
 
     Tree tree;
     std::array<float, 4> rotationMatrix;
+    std::array<float, 4> reverseRotationMatrix;
+    const float extent = 4096;
+    std::array<CollisionBox, 4> edges;
 };
 
 } // namespace mbgl