Merge pull request #744 from mapbox/merge-roads

merge adjacent roads with the same text for labeling

5 files changed, 229 insertions, 27 deletions

diff --git a/src/mbgl/renderer/symbol_bucket.cpp b/src/mbgl/renderer/symbol_bucket.cpp
index 0eadacec5a..c6a7c8c4e1 100644
--- a/src/mbgl/renderer/symbol_bucket.cpp
+++ b/src/mbgl/renderer/symbol_bucket.cpp
@@ -16,6 +16,7 @@
 #include <mbgl/util/utf.hpp>
 #include <mbgl/util/token.hpp>
 #include <mbgl/util/math.hpp>
+#include <mbgl/util/merge_lines.hpp>
 
 namespace mbgl {
 
@@ -85,11 +86,31 @@ std::vector<SymbolFeature> SymbolBucket::processFeatures(const VectorTileLayer &
         }
 
         if (ft.label.length() || ft.sprite.length()) {
-            ft.geometry = feature.geometry;
+
+            auto &multiline = ft.geometry;
+
+            // Decode line
+            Geometry::command cmd;
+            pbf geom(feature.geometry);
+            Geometry geometry(geom);
+            bool first = true;
+            int32_t x, y;
+            while ((cmd = geometry.next(x, y)) != Geometry::end) {
+                if (first || cmd == Geometry::move_to) {
+                    multiline.emplace_back();
+                    first = false;
+                }
+                multiline.back().emplace_back(x, y);
+            }
+
             features.push_back(std::move(ft));
         }
     }
 
+    if (properties.placement == PlacementType::Line) {
+        util::mergeLines(features);
+    }
+
     glyphStore.waitForGlyphRanges(properties.text.font, ranges);
     sprite.waitUntilLoaded();
 
@@ -146,6 +167,8 @@ void SymbolBucket::addFeatures(const VectorTileLayer &layer, const FilterExpress
     const FontStack &fontStack = glyphStore.getFontStack(properties.text.font);
 
     for (const SymbolFeature &feature : features) {
+        if (!feature.geometry.size()) continue;
+
         Shaping shaping;
         Rect<uint16_t> image;
         GlyphPositions face;
@@ -181,32 +204,12 @@ void SymbolBucket::addFeatures(const VectorTileLayer &layer, const FilterExpress
 
         // if either shaping or icon position is present, add the feature
         if (shaping.size() || image) {
-            addFeature(feature.geometry, shaping, face, image);
-        }
-    }
-}
-
-void SymbolBucket::addFeature(const pbf &geom_pbf, const Shaping &shaping,
-                              const GlyphPositions &face, const Rect<uint16_t> &image) {
-    // Decode all lines.
-    std::vector<Coordinate> line;
-    Geometry::command cmd;
-
-    Coordinate coord;
-    pbf geom(geom_pbf);
-    Geometry geometry(geom);
-    int32_t x, y;
-    while ((cmd = geometry.next(x, y)) != Geometry::end) {
-        if (cmd == Geometry::move_to) {
-            if (!line.empty()) {
-                addFeature(line, shaping, face, image);
-                line.clear();
+            for (const std::vector<Coordinate> &line : feature.geometry) {
+                if (line.size()) {
+                    addFeature(line, shaping, face, image);
+                }
             }
         }
-        line.emplace_back(x, y);
-    }
-    if (line.size()) {
-        addFeature(line, shaping, face, image);
     }
 }
 
diff --git a/src/mbgl/renderer/symbol_bucket.hpp b/src/mbgl/renderer/symbol_bucket.hpp
index dd596b1a00..bc148579fa 100644
--- a/src/mbgl/renderer/symbol_bucket.hpp
+++ b/src/mbgl/renderer/symbol_bucket.hpp
@@ -30,7 +30,7 @@ class FontStack;
 
 class SymbolFeature {
 public:
-    pbf geometry;
+    std::vector<std::vector<Coordinate>> geometry;
     std::u32string label;
     std::string sprite;
 };
@@ -77,7 +77,6 @@ private:
     std::vector<SymbolFeature> processFeatures(const VectorTileLayer &layer, const FilterExpression &filter, GlyphStore &glyphStore, const Sprite &sprite);
 
 
-    void addFeature(const pbf &geom_pbf, const Shaping &shaping, const GlyphPositions &face, const Rect<uint16_t> &image);
     void addFeature(const std::vector<Coordinate> &line, const Shaping &shaping, const GlyphPositions &face, const Rect<uint16_t> &image);
 
 
diff --git a/src/mbgl/util/merge_lines.hpp b/src/mbgl/util/merge_lines.hpp
new file mode 100644
index 0000000000..e0dd4c6415
--- /dev/null
+++ b/src/mbgl/util/merge_lines.hpp
@@ -0,0 +1,107 @@
+#ifndef MBGL_UTIL_MERGELINES
+#define MBGL_UTIL_MERGELINES
+
+#include <map>
+#include <string>
+#include <vector>
+#include <sstream>
+#include <mbgl/renderer/symbol_bucket.hpp>
+
+
+namespace mbgl {
+namespace util {
+
+unsigned int mergeFromRight(
+        std::vector<SymbolFeature> &features,
+        std::map<std::string,unsigned int> &rightIndex,
+        std::map<std::string,unsigned int>::iterator left,
+        std::string &rightKey,
+        std::vector<std::vector<Coordinate>> &geom) {
+
+    unsigned int index = left->second;
+    rightIndex.erase(left);
+    rightIndex[rightKey] = index;
+    features[index].geometry[0].pop_back();
+    features[index].geometry[0].insert(features[index].geometry[0].end(), geom[0].begin(), geom[0].end());
+    geom[0].clear();
+    return index;
+}
+
+unsigned int mergeFromLeft(
+        std::vector<SymbolFeature> &features,
+        std::map<std::string,unsigned int> &leftIndex,
+        std::string &leftKey,
+        std::map<std::string,unsigned int>::iterator right,
+        std::vector<std::vector<Coordinate>> &geom) {
+
+    unsigned int index = right->second;
+    leftIndex.erase(right);
+    leftIndex[leftKey] = index;
+    geom[0].pop_back();
+    geom[0].insert(geom[0].end(), features[index].geometry[0].begin(), features[index].geometry[0].end());
+    features[index].geometry[0].clear();
+    std::swap(features[index].geometry[0], geom[0]);
+    return index;
+}
+
+std::string getKey(const std::u32string &text, const std::vector<std::vector<Coordinate>> &geom, bool onRight) {
+    const Coordinate &coord = onRight ? geom[0].back() : geom[0].front();
+    std::ostringstream key;
+    for (const char32_t &c : text) {
+        key << (char)c;
+    }
+    key << ":" << coord.x << ":" << coord.y;
+    return key.str();
+}
+
+
+void mergeLines(std::vector<SymbolFeature> &features) {
+
+    std::map<std::string,unsigned int> leftIndex;
+    std::map<std::string,unsigned int> rightIndex;
+
+    for (unsigned int k = 0; k < features.size(); k++) {
+        SymbolFeature &feature = features[k];
+        std::vector<std::vector<Coordinate>> &geometry = feature.geometry;
+
+        if (!feature.label.length()) {
+            continue;
+        }
+
+        std::string leftKey = getKey(feature.label, geometry, false);
+        std::string rightKey = getKey(feature.label, geometry, true);
+
+        auto left = rightIndex.find(leftKey);
+        auto right = leftIndex.find(rightKey);
+
+        if ((left != rightIndex.end()) && (right != leftIndex.end()) && (left->second != right->second)) {
+            // found lines with the same text adjacent to both ends of the current line, merge all three
+            unsigned int j = mergeFromLeft(features, leftIndex, leftKey, right, geometry);
+            unsigned int i = mergeFromRight(features, rightIndex, left, rightKey, features[j].geometry);
+
+            leftIndex.erase(leftKey);
+            rightIndex.erase(rightKey);
+            rightIndex[getKey(feature.label, features[i].geometry, true)] = i;
+
+        } else if (left != rightIndex.end()) {
+            // found mergeable line adjacent to the start of the current line, merge
+            mergeFromRight(features, rightIndex, left, rightKey, geometry);
+
+        } else if (right != leftIndex.end()) {
+            // found mergeable line adjacent to the end of the current line, merge
+            mergeFromLeft(features, leftIndex, leftKey, right, geometry);
+
+        } else {
+            // no adjacent lines, add as a new item
+            leftIndex[leftKey] = k;
+            rightIndex[rightKey] = k;
+        }
+
+    }
+
+}
+
+} // end namespace util
+} // end namespace mbgl
+
+#endif
diff --git a/test/merge_lines.cpp b/test/merge_lines.cpp
new file mode 100644
index 0000000000..3c887105fa
--- /dev/null
+++ b/test/merge_lines.cpp
@@ -0,0 +1,73 @@
+#include "gtest/gtest.h"
+
+#include <mbgl/util/merge_lines.hpp>
+
+
+TEST(mergeLines, mergeLines) {
+
+    std::u32string a = U"a";
+    std::u32string b = U"b";
+
+    // merges lines with the same text
+    std::vector<mbgl::SymbolFeature> input1 = {
+        { {{{0, 0}, {1, 0}, {2, 0}}}, a, "" },
+        { {{{4, 0}, {5, 0}, {6, 0}}}, b, "" },
+        { {{{8, 0}, {9, 0}}}, a, "" },
+        { {{{2, 0}, {3, 0}, {4, 0}}}, a, "" },
+        { {{{6, 0}, {7, 0}, {8, 0}}}, a, "" },
+        { {{{5, 0}, {6, 0}}}, a, "" }
+    };
+
+    std::vector<mbgl::SymbolFeature> expected1 = {
+        { {{{0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0}}}, a, "" },
+        { {{{4, 0}, {5, 0}, {6, 0}}}, b, "" },
+        { {{{5, 0}, {6, 0}, {7, 0}, {8, 0}, {9, 0}}}, a, "" },
+        { {{}}, a, "" },
+        { {{}}, a, "" },
+        { {{}}, a, "" }
+    };
+
+    mbgl::util::mergeLines(input1);
+
+    for (int i = 0; i < 6; i++) {
+        EXPECT_EQ(input1[i].geometry, expected1[i].geometry);
+    }
+
+    // mergeLines handles merge from both ends
+    std::vector<mbgl::SymbolFeature> input2 = {
+        { {{{0, 0}, {1, 0}, {2, 0}}}, a, "" },
+        { {{{4, 0}, {5, 0}, {6, 0}}}, a, "" },
+        { {{{2, 0}, {3, 0}, {4, 0}}}, a, "" }
+    };
+
+    std::vector<mbgl::SymbolFeature> expected2 = {
+        { {{{0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {6, 0}}}, a, "" },
+        { {{}}, a, "" },
+        { {{}}, a, "" }
+    };
+
+    mbgl::util::mergeLines(input2);
+
+    for (int i = 0; i < 3; i++) {
+        EXPECT_EQ(input2[i].geometry, expected2[i].geometry);
+    }
+
+    // mergeLines handles circular lines
+    std::vector<mbgl::SymbolFeature> input3 = {
+        { {{{0, 0}, {1, 0}, {2, 0}}}, a, "" },
+        { {{{2, 0}, {3, 0}, {4, 0}}}, a, "" },
+        { {{{4, 0}, {0, 0}}}, a, "" }
+    };
+
+    std::vector<mbgl::SymbolFeature> expected3 = {
+        { {{{0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0}, {0, 0}}}, a, "" },
+        { {{}}, a, "" },
+        { {{}}, a, "" }
+    };
+
+    mbgl::util::mergeLines(input3);
+
+    for (int i = 0; i < 3; i++) {
+        EXPECT_EQ(input3[i].geometry, expected3[i].geometry);
+    }
+}
diff --git a/test/test.gyp b/test/test.gyp
index 5cb84dbd4e..406e0b23a7 100644
--- a/test/test.gyp
+++ b/test/test.gyp
@@ -168,6 +168,25 @@
         }]
       ]
     },
+    { 'target_name': 'merge_lines',
+      'product_name': 'test_merge_lines',
+      'type': 'executable',
+      'sources': [
+        './main.cpp',
+        './merge_lines.cpp',
+      ],
+      'dependencies': [
+        '../deps/gtest/gtest.gyp:gtest',
+        '../mapboxgl.gyp:mbgl-standalone',
+      ],
+      'include_dirs': [ '../src' ],
+      'conditions': [
+        ['OS == "mac"', { 'xcode_settings': { 'OTHER_LDFLAGS': [ '<@(ldflags)' ] }
+        }, {
+          'libraries': [ '<@(ldflags)' ],
+        }]
+      ]
+    },
     { 'target_name': 'headless',
       'product_name': 'test_headless',
       'type': 'executable',
@@ -237,6 +256,7 @@
         'variant',
         'tile',
         'functions',
+        'merge_lines',
         'headless',
         'style_parser',
         'comparisons',