[core][tile mode] Placement algorithm improvements

Now, the intersecting symbols are placed across all layers according to the following rules:
1) First we look, which of the tile border(s) the symbol intersects and prioritize the the symbol accordingly (high priority -> low priority):
vertical & horizontal -> vertical -> horizontal

2) For the symbols that intersect the same tile border(s), assuming the tile border split symbol into several sections, we look at the minimal section length.
The symbol with a larger minimal section length is placed first.

3) Finally, for the symbols that intersect the same tile border(s), and have equal minimal section length, we look at the anchor Y cordinate.

3 files changed, 81 insertions, 29 deletions

diff --git a/src/mbgl/text/collision_index.cpp b/src/mbgl/text/collision_index.cpp
index a0b8a8ab77..4cd7b58c74 100644
--- a/src/mbgl/text/collision_index.cpp
+++ b/src/mbgl/text/collision_index.cpp
@@ -104,13 +104,42 @@ inline bool CollisionIndex::overlapsTile(const CollisionBoundaries& boundaries,
            boundaries[1] < tileBoundaries[3] && boundaries[3] > tileBoundaries[1];
 }
 
-bool CollisionIndex::intersectsTileEdges(const CollisionBox& box,
-                                         Point<float> shift,
-                                         const mat4& posMatrix,
-                                         const float textPixelRatio,
-                                         const CollisionBoundaries& tileEdges) const {
-    auto collisionBoundaries = getProjectedCollisionBoundaries(posMatrix, shift, textPixelRatio, box);
-    return overlapsTile(collisionBoundaries, tileEdges) && !isInsideTile(collisionBoundaries, tileEdges);
+IntersectStatus CollisionIndex::intersectsTileEdges(const CollisionBox& box,
+                                                    Point<float> shift,
+                                                    const mat4& posMatrix,
+                                                    const float textPixelRatio,
+                                                    const CollisionBoundaries& tileEdges) const {
+    auto boundaries = getProjectedCollisionBoundaries(posMatrix, shift, textPixelRatio, box);
+    IntersectStatus result;
+    const float x1 = boundaries[0];
+    const float y1 = boundaries[1];
+    const float x2 = boundaries[2];
+    const float y2 = boundaries[3];
+
+    const float tileX1 = tileEdges[0];
+    const float tileY1 = tileEdges[1];
+    const float tileX2 = tileEdges[2];
+    const float tileY2 = tileEdges[3];
+
+    // Check left border
+    int minSectionLength = std::min(tileX1 - x1, x2 - tileX1);
+    if (minSectionLength <= 0) { // Check right border
+        minSectionLength = std::min(tileX2 - x1, x2 - tileX2);
+    }
+    if (minSectionLength > 0) {
+        result.flags |= IntersectStatus::VerticalBorders;
+        result.minSectionLength = minSectionLength;
+    }
+    // Check top border
+    minSectionLength = std::min(tileY1 - y1, y2 - tileY1);
+    if (minSectionLength <= 0) { // Check bottom border
+        minSectionLength = std::min(tileY2 - y1, y2 - tileY2);
+    }
+    if (minSectionLength > 0) {
+        result.flags |= IntersectStatus::HorizontalBorders;
+        result.minSectionLength = std::min(result.minSectionLength, minSectionLength);
+    }
+    return result;
 }
 
 std::pair<bool, bool> CollisionIndex::placeFeature(
diff --git a/src/mbgl/text/collision_index.hpp b/src/mbgl/text/collision_index.hpp
index c6f689bc7e..d22d962069 100644
--- a/src/mbgl/text/collision_index.hpp
+++ b/src/mbgl/text/collision_index.hpp
@@ -15,17 +15,22 @@ class PlacedSymbol;
 struct TileDistance;
 
 using CollisionBoundaries = std::array<float, 4>; // [x1, y1, x2, y2]
-
+struct IntersectStatus {
+    enum Flags : uint8_t { None = 0, HorizontalBorders = 1 << 0, VerticalBorders = 1 << 1 };
+    Flags flags = None;
+    // Assuming tile border divides box in two sections
+    int minSectionLength = 0;
+};
 class CollisionIndex {
 public:
     using CollisionGrid = GridIndex<IndexedSubfeature>;
 
     explicit CollisionIndex(const TransformState&, MapMode);
-    bool intersectsTileEdges(const CollisionBox&,
-                             Point<float> shift,
-                             const mat4& posMatrix,
-                             const float textPixelRatio,
-                             const CollisionBoundaries& tileEdges) const;
+    IntersectStatus intersectsTileEdges(const CollisionBox&,
+                                        Point<float> shift,
+                                        const mat4& posMatrix,
+                                        const float textPixelRatio,
+                                        const CollisionBoundaries& tileEdges) const;
     std::pair<bool, bool> placeFeature(
         const CollisionFeature& feature,
         Point<float> shift,
diff --git a/src/mbgl/text/placement.cpp b/src/mbgl/text/placement.cpp
index 58ad44962b..e825fc3305 100644
--- a/src/mbgl/text/placement.cpp
+++ b/src/mbgl/text/placement.cpp
@@ -72,7 +72,7 @@ public:
                      const RenderTile& renderTile_,
                      const TransformState& state_,
                      float placementZoom,
-                     const CollisionGroups::CollisionGroup& collisionGroup_,
+                     CollisionGroups::CollisionGroup collisionGroup_,
                      optional<CollisionBoundaries> avoidEdges_ = nullopt)
         : bucket(bucket_),
           renderTile(renderTile_),
@@ -80,7 +80,7 @@ public:
           pixelsToTileUnits(renderTile_.id.pixelsToTileUnits(1, placementZoom)),
           scale(std::pow(2, placementZoom - getOverscaledID().overscaledZ)),
           pixelRatio(util::tileSize * getOverscaledID().overscaleFactor() / util::EXTENT),
-          collisionGroup(collisionGroup_),
+          collisionGroup(std::move(collisionGroup_)),
           partiallyEvaluatedTextSize(bucket_.textSizeBinder->evaluateForZoom(placementZoom)),
           partiallyEvaluatedIconSize(bucket_.iconSizeBinder->evaluateForZoom(placementZoom)),
           avoidEdges(std::move(avoidEdges_)) {}
@@ -230,7 +230,7 @@ Point<float> calculateVariableLayoutOffset(style::SymbolAnchorType anchor,
 
 void Placement::placeSymbolBucket(const BucketPlacementData& params, std::set<uint32_t>& seenCrossTileIDs) {
     assert(updateParameters);
-    const SymbolBucket& symbolBucket = static_cast<const SymbolBucket&>(params.bucket.get());
+    const auto& symbolBucket = static_cast<const SymbolBucket&>(params.bucket.get());
     const RenderTile& renderTile = params.tile;
     PlacementContext ctx{symbolBucket,
                          params.tile,
@@ -1244,10 +1244,13 @@ void StaticPlacement::commit() {
 /// Placement for Tile map mode.
 
 struct Intersection {
-    Intersection(const SymbolInstance& symbol_, const PlacementContext& ctx_) : symbol(symbol_), ctx(ctx_) {}
+    Intersection(const SymbolInstance& symbol_, PlacementContext ctx_, IntersectStatus status_)
+        : symbol(symbol_), ctx(std::move(ctx_)), status(status_) {}
     std::reference_wrapper<const SymbolInstance> symbol;
     PlacementContext ctx;
+    IntersectStatus status;
 };
+
 class TilePlacement : public StaticPlacement {
 public:
     explicit TilePlacement(std::shared_ptr<const UpdateParameters> updateParameters_)
@@ -1290,8 +1293,17 @@ void TilePlacement::placeLayers(const RenderLayerReferences& layers) {
         placeLayer(*it, seenCrossTileIDs);
     }
 
-    // Add more stability, sorting intersections by their Y position.
     std::stable_sort(intersections.begin(), intersections.end(), [](const Intersection& a, const Intersection& b) {
+        uint8_t flagsA = a.status.flags;
+        uint8_t flagsB = b.status.flags;
+        // Items arranged as: VerticalBorders & HorizontalBorders (3) ->
+        // VerticalBorders (2) -> HorizontalBorders (1)
+        if (flagsA != flagsB) return flagsA > flagsB;
+        // If both intersects the same border(s), look for a more noticable cut-off.
+        if (a.status.minSectionLength != b.status.minSectionLength) {
+            return a.status.minSectionLength > b.status.minSectionLength;
+        }
+        // Finally, look at Y position.
         return a.symbol.get().anchor.point.y < b.symbol.get().anchor.point.y;
     });
     // Place intersections.
@@ -1369,12 +1381,13 @@ void TilePlacement::placeSymbolBucket(const BucketPlacementData& params, std::se
         {collisionIndex, UnwrappedTileID(z, x + 1, y), {-util::EXTENT, 0.0f}}  // right
     }};
 
-    auto collisionBoxIntersectsTileEdges = [&](const CollisionBox& collisionBox, Point<float> shift) noexcept->bool {
-        bool intersects =
+    auto collisionBoxIntersectsTileEdges = [&](const CollisionBox& collisionBox,
+                                               Point<float> shift) noexcept->IntersectStatus {
+        IntersectStatus intersects =
             collisionIndex.intersectsTileEdges(collisionBox, shift, renderTile.matrix, ctx.pixelRatio, *tileBorders);
         // Check if this symbol intersects the neighbor tile borders. If so, it also shall be placed with priority.
         for (const auto& neighbor : neighbours) {
-            if (intersects) break;
+            if (intersects.flags != IntersectStatus::None) break;
             intersects = collisionIndex.intersectsTileEdges(
                 collisionBox, shift + neighbor.shift, neighbor.matrix, ctx.pixelRatio, neighbor.borders);
         }
@@ -1387,8 +1400,8 @@ void TilePlacement::placeSymbolBucket(const BucketPlacementData& params, std::se
         pitchTextWithMap = ctx.pitchTextWithMap,
         rotateTextWithMap = ctx.rotateTextWithMap,
         bearing = ctx.getTransformState().getBearing()
-    ](const SymbolInstance& symbol) noexcept->bool {
-        bool intersects = false;
+    ](const SymbolInstance& symbol) noexcept->IntersectStatus {
+        IntersectStatus result;
         if (!symbol.textCollisionFeature.boxes.empty()) {
             const auto& textCollisionBox = symbol.textCollisionFeature.boxes.front();
 
@@ -1405,19 +1418,23 @@ void TilePlacement::placeSymbolBucket(const BucketPlacementData& params, std::se
                                                        pitchTextWithMap,
                                                        bearing);
             }
-            intersects = collisionBoxIntersectsTileEdges(textCollisionBox, offset);
+            result = collisionBoxIntersectsTileEdges(textCollisionBox, offset);
         }
 
-        if (!symbol.iconCollisionFeature.boxes.empty() && !intersects) {
+        if (!symbol.iconCollisionFeature.boxes.empty()) {
             const auto& iconCollisionBox = symbol.iconCollisionFeature.boxes.front();
-            intersects = collisionBoxIntersectsTileEdges(iconCollisionBox, {});
+            auto iconIntersects = collisionBoxIntersectsTileEdges(iconCollisionBox, {});
+            result.flags |= iconIntersects.flags;
+            result.minSectionLength = std::max(result.minSectionLength, iconIntersects.minSectionLength);
         }
 
-        return intersects;
+        return result;
     };
 
     for (const SymbolInstance& symbol : symbolInstances) {
-        if (symbolIntersectsTileEdges(symbol)) intersections.emplace_back(symbol, ctx);
+        auto intersectStatus = symbolIntersectsTileEdges(symbol);
+        if (intersectStatus.flags == IntersectStatus::None) continue;
+        intersections.emplace_back(symbol, ctx, intersectStatus);
     }
 }
 
@@ -1426,7 +1443,8 @@ bool TilePlacement::stickToFirstVariableAnchor(const CollisionBox& box,
                                                const mat4& posMatrix,
                                                float textPixelRatio) {
     assert(tileBorders);
-    return collisionIndex.intersectsTileEdges(box, shift, posMatrix, textPixelRatio, *tileBorders);
+    auto status = collisionIndex.intersectsTileEdges(box, shift, posMatrix, textPixelRatio, *tileBorders);
+    return status.flags != IntersectStatus::None;
 }
 
 void TilePlacement::newSymbolPlaced(const SymbolInstance& symbol,