Updates to labels along lines

Added a filter to remove anchors with the same text that are too close to each other.

Updates to spacing and offset of anchor placement along lines:

Takes into account icon size for calculating label length.

Recalculates spacing for long labels.

Adjusts offsets to first anchors if line is continued from outside the tile boundary.

6 files changed, 65 insertions, 23 deletions

diff --git a/src/mbgl/renderer/symbol_bucket.cpp b/src/mbgl/renderer/symbol_bucket.cpp
index 47087422ec..cfa56c9922 100644
--- a/src/mbgl/renderer/symbol_bucket.cpp
+++ b/src/mbgl/renderer/symbol_bucket.cpp
@@ -290,8 +290,10 @@ void SymbolBucket::addFeature(const std::vector<std::vector<Coordinate>> &lines,
         layout.placement == PlacementType::Line;
     const bool mayOverlap = layout.text.allow_overlap || layout.icon.allow_overlap ||
         layout.text.ignore_placement || layout.icon.ignore_placement;
+    const bool isLine = layout.placement == PlacementType::Line;
+    const float textRepeatDistance = symbolSpacing / 2;
 
-    auto& clippedLines = layout.placement == PlacementType::Line ?
+    auto& clippedLines = isLine ?
         util::clipLines(lines, 0, 0, 4096, 4096) :
         lines;
 
@@ -299,13 +301,17 @@ void SymbolBucket::addFeature(const std::vector<std::vector<Coordinate>> &lines,
         if (!line.size()) continue;
 
         // Calculate the anchor points around which you want to place labels
-        Anchors anchors = layout.placement == PlacementType::Line ?
-            getAnchors(line, symbolSpacing, textMaxAngle, shapedText.left, shapedText.right, glyphSize, textBoxScale, overscaling) :
+        Anchors anchors = isLine ?
+            getAnchors(line, symbolSpacing, textMaxAngle, shapedText.left, shapedText.right, shapedIcon.left, shapedIcon.right, glyphSize, textBoxScale, overscaling) :
             Anchors({ Anchor(float(line[0].x), float(line[0].y), 0, minScale) });
 
-
         // For each potential label, create the placement features used to check for collisions, and the quads use for rendering.
         for (Anchor &anchor : anchors) {
+            if (shapedText && isLine) {
+                if (anchorIsTooClose(shapedText.text, textRepeatDistance, anchor)) {
+                    continue;
+                }
+            }
 
             const bool inside = !(anchor.x < 0 || anchor.x > 4096 || anchor.y < 0 || anchor.y > 4096);
 
@@ -331,6 +337,21 @@ void SymbolBucket::addFeature(const std::vector<std::vector<Coordinate>> &lines,
         }
     }
 }
+    
+bool SymbolBucket::anchorIsTooClose(const std::u32string &text, const float repeatDistance, Anchor &anchor) {
+    if (compareText.find(text) == compareText.end()) {
+        compareText.emplace(text, Anchors());
+    } else {
+        auto otherAnchors = compareText.find(text)->second;
+        for (Anchor &otherAnchor : otherAnchors) {
+            if (util::dist<float>(anchor, otherAnchor) < repeatDistance) {
+                return true;
+            }
+        }
+    }
+    compareText[text].push_back(anchor);
+    return false;
+}
 
 void SymbolBucket::placeFeatures() {
     placeFeatures(false);
diff --git a/src/mbgl/renderer/symbol_bucket.hpp b/src/mbgl/renderer/symbol_bucket.hpp
index a5c98fbf32..3a181be55d 100644
--- a/src/mbgl/renderer/symbol_bucket.hpp
+++ b/src/mbgl/renderer/symbol_bucket.hpp
@@ -94,7 +94,9 @@ private:
     void addFeature(const std::vector<std::vector<Coordinate>> &lines,
             const Shaping &shapedText, const PositionedIcon &shapedIcon,
             const GlyphPositions &face);
-
+    bool anchorIsTooClose(const std::u32string &text, const float repeatDistance, Anchor &anchor);
+    std::map<std::u32string, std::vector<Anchor>> compareText;
+    
     void addToDebugBuffers();
 
     void placeFeatures(bool swapImmediately);
diff --git a/src/mbgl/text/font_stack.cpp b/src/mbgl/text/font_stack.cpp
index 88a739b804..7785a14238 100644
--- a/src/mbgl/text/font_stack.cpp
+++ b/src/mbgl/text/font_stack.cpp
@@ -22,7 +22,7 @@ const Shaping FontStack::getShaping(const std::u32string &string, const float ma
                                     const float lineHeight, const float horizontalAlign,
                                     const float verticalAlign, const float justify,
                                     const float spacing, const vec2<float> &translate) const {
-    Shaping shaping(translate.x * 24, translate.y * 24);
+    Shaping shaping(translate.x * 24, translate.y * 24, string);
 
     // the y offset *should* be part of the font metadata
     const int32_t yOffset = -17;
diff --git a/src/mbgl/text/get_anchors.cpp b/src/mbgl/text/get_anchors.cpp
index 88c09983a6..e86dba4017 100644
--- a/src/mbgl/text/get_anchors.cpp
+++ b/src/mbgl/text/get_anchors.cpp
@@ -8,10 +8,10 @@
 namespace mbgl {
 
 Anchors resample(const std::vector<Coordinate> &line, const float offset, const float spacing,
-        const float angleWindowSize, const float maxAngle, const float labelLength, const bool placeAtMiddle) {
+        const float angleWindowSize, const float maxAngle, const float labelLength, const bool continuedLine, const bool placeAtMiddle) {
 
     float distance = 0;
-    float markedDistance = offset != 0.0f ? offset - spacing : 0;
+    float markedDistance = offset - spacing;
 
     Anchors anchors;
 
@@ -43,37 +43,54 @@ Anchors resample(const std::vector<Coordinate> &line, const float offset, const
         distance += segmentDist;
     }
 
-    if (!placeAtMiddle && !anchors.size()) {
+    if (!placeAtMiddle && !anchors.size() && !continuedLine) {
         // The first attempt at finding anchors at which labels can be placed failed.
         // Try again, but this time just try placing one anchor at the middle of the line.
         // This has the most effect for short lines in overscaled tiles, since the
         // initial offset used in overscaled tiles is calculated to align labels with positions in
         // parent tiles instead of placing the label as close to the beginning as possible.
-        anchors = std::move(resample(line, distance / 2, spacing, angleWindowSize, maxAngle, labelLength, true));
+        anchors = std::move(resample(line, distance / 2, spacing, angleWindowSize, maxAngle, labelLength, continuedLine, true));
     }
 
     return anchors;
 }
 
 Anchors getAnchors(const std::vector<Coordinate> &line, float spacing,
-        const bool maxAngle, const float left, const float right,
+        const float maxAngle, const float textLeft, const float textRight,
+        const float iconLeft, const float iconRight,
         const float glyphSize, const float boxScale, const float overscaling) {
 
     // Resample a line to get anchor points for labels and check that each
     // potential label passes text-max-angle check and has enough froom to fit
     // on the line.
 
-    const float angleWindowSize = (left - right) != 0.0f ?
+    const float angleWindowSize = (textLeft - textRight) != 0.0f ?
         3.0f / 5.0f * glyphSize * boxScale :
         0;
-
-    // Offset the first anchor by half the label length (or half the spacing distance for icons).
-    // Add a bit of extra offset to avoid collisions at T intersections.
-    const float labelLength = right - left ? right - left : spacing;
-    const float extraOffset = glyphSize * 2;
-    const float offset = std::fmod((labelLength / 2 + extraOffset) * boxScale * overscaling, spacing);
-
-    return resample(line, offset, spacing, angleWindowSize, maxAngle, labelLength * boxScale, false);
+    
+    const float labelLength = fmax(textRight - textLeft, iconRight - iconLeft);
+    
+    // Is the line continued from outside the tile boundary?
+    const bool continuedLine = (line[0].x == 0 || line[0].x == 4096 || line[0].y == 0 || line[0].y == 4096);
+    
+    // Is the label long, relative to the spacing?
+    // If so, adjust the spacing so there is always a minimum space of `spacing / 4` between label edges.
+    if (spacing - labelLength * boxScale  < spacing / 4) {
+        spacing = labelLength * boxScale + spacing / 4;
+    }
+    
+    // Offset the first anchor by:
+    // Either half the label length plus a fixed extra offset if the line is not continued
+    // Or half the spacing if the line is continued.
+
+    // For non-continued lines, add a bit of fixed extra offset to avoid collisions at T intersections.
+    const float fixedExtraOffset = glyphSize * 2;
+    
+    const float offset = !continuedLine ?
+    std::fmod((labelLength / 2 + fixedExtraOffset) * boxScale * overscaling, spacing) :
+    std::fmod(spacing / 2 * overscaling, spacing);
+
+    return resample(line, offset, spacing, angleWindowSize, maxAngle, labelLength * boxScale, continuedLine, false);
 }
 
 }
diff --git a/src/mbgl/text/get_anchors.hpp b/src/mbgl/text/get_anchors.hpp
index ca879d2243..3f737ee6c7 100644
--- a/src/mbgl/text/get_anchors.hpp
+++ b/src/mbgl/text/get_anchors.hpp
@@ -7,7 +7,8 @@
 namespace mbgl {
 
 Anchors getAnchors(const std::vector<Coordinate> &line, float spacing,
-        const bool maxAngle, const float left, const float right,
+        const float maxAngle, const float textLeft, const float textRight,
+        const float iconLeft, const float iconRight,
         const float glyphSize, const float boxScale, const float overscaling);
 }
 
diff --git a/src/mbgl/text/glyph.hpp b/src/mbgl/text/glyph.hpp
index be7c9befd5..334e1428c3 100644
--- a/src/mbgl/text/glyph.hpp
+++ b/src/mbgl/text/glyph.hpp
@@ -58,9 +58,10 @@ public:
 class Shaping {
     public:
     inline explicit Shaping() : top(0), bottom(0), left(0), right(0) {}
-    inline explicit Shaping(float x, float y)
-        : top(y), bottom(y), left(x), right(x) {}
+    inline explicit Shaping(float x, float y, std::u32string text_)
+        : text(text_), top(y), bottom(y), left(x), right(x) {}
     std::vector<PositionedGlyph> positionedGlyphs;
+    std::u32string text;
     int32_t top;
     int32_t bottom;
     int32_t left;