[core] Move {clip,merge}_lines to layout directory

5 files changed, 218 insertions, 2 deletions

diff --git a/src/mbgl/layout/clip_lines.cpp b/src/mbgl/layout/clip_lines.cpp
new file mode 100644
index 0000000000..05b9103f69
--- /dev/null
+++ b/src/mbgl/layout/clip_lines.cpp
@@ -0,0 +1,68 @@
+#include <mbgl/layout/clip_lines.hpp>
+
+#include <cmath>
+
+namespace mbgl {
+namespace util {
+
+GeometryCollection clipLines(const GeometryCollection &lines,
+        const int16_t x1, const int16_t y1, const int16_t x2, const int16_t y2) {
+
+    GeometryCollection clippedLines;
+
+    for (auto& line : lines) {
+
+        if (line.empty())
+            continue;
+
+        auto end = line.end() - 1;
+        for (auto it = line.begin(); it != end; it++) {
+            GeometryCoordinate p0 = *(it);
+            GeometryCoordinate p1 = *(it + 1);
+
+            if (p0.x < x1 && p1.x < x1) {
+                continue;
+            } else if (p0.x < x1) {
+                p0 = { x1, static_cast<int16_t>(::round(p0.y + (p1.y - p0.y) * ((float)(x1 - p0.x) / (p1.x - p0.x)))) };
+            } else if (p1.x < x1) {
+                p1 = { x1, static_cast<int16_t>(::round(p0.y + (p1.y - p0.y) * ((float)(x1 - p0.x) / (p1.x - p0.x)))) };
+            }
+
+            if (p0.y < y1 && p1.y < y1) {
+                continue;
+            } else if (p0.y < y1) {
+                p0 = { static_cast<int16_t>(::round(p0.x + (p1.x - p0.x) * ((float)(y1 - p0.y) / (p1.y - p0.y)))), y1 };
+            } else if (p1.y < y1) {
+                p1 = { static_cast<int16_t>(::round(p0.x + (p1.x - p0.x) * ((float)(y1 - p0.y) / (p1.y - p0.y)))), y1 };
+            }
+
+            if (p0.x >= x2 && p1.x >= x2) {
+                continue;
+            } else if (p0.x >= x2) {
+                p0 = { x2, static_cast<int16_t>(::round(p0.y + (p1.y - p0.y) * ((float)(x2 - p0.x) / (p1.x - p0.x)))) };
+            } else if (p1.x >= x2) {
+                p1 = { x2, static_cast<int16_t>(::round(p0.y + (p1.y - p0.y) * ((float)(x2 - p0.x) / (p1.x - p0.x)))) };
+            }
+
+            if (p0.y >= y2 && p1.y >= y2) {
+                continue;
+            } else if (p0.y >= y2) {
+                p0 = { static_cast<int16_t>(::round(p0.x + (p1.x - p0.x) * ((float)(y2 - p0.y) / (p1.y - p0.y)))), y2 };
+            } else if (p1.y >= y2) {
+                p1 = { static_cast<int16_t>(::round(p0.x + (p1.x - p0.x) * ((float)(y2 - p0.y) / (p1.y - p0.y)))), y2 };
+            }
+
+            if (clippedLines.empty() || (!clippedLines.back().empty() && !(p0 == clippedLines.back().back()))) {
+                clippedLines.emplace_back();
+                clippedLines.back().push_back(p0);
+            }
+
+            clippedLines.back().push_back(p1);
+        }
+    }
+
+    return clippedLines;
+}
+
+} // end namespace util
+} // end namespace mbgl
diff --git a/src/mbgl/layout/clip_lines.hpp b/src/mbgl/layout/clip_lines.hpp
new file mode 100644
index 0000000000..c1cfd4bbb9
--- /dev/null
+++ b/src/mbgl/layout/clip_lines.hpp
@@ -0,0 +1,16 @@
+#pragma once
+
+#include <map>
+#include <string>
+#include <vector>
+#include <mbgl/tile/geometry_tile_data.hpp>
+
+namespace mbgl {
+namespace util {
+
+
+GeometryCollection clipLines(const GeometryCollection &lines,
+        const int16_t x1, const int16_t y1, const int16_t x2, const int16_t y2);
+
+} // end namespace util
+} // end namespace mbgl
diff --git a/src/mbgl/layout/merge_lines.cpp b/src/mbgl/layout/merge_lines.cpp
new file mode 100644
index 0000000000..1e33a655e7
--- /dev/null
+++ b/src/mbgl/layout/merge_lines.cpp
@@ -0,0 +1,106 @@
+#include <mbgl/layout/merge_lines.hpp>
+
+#include <boost/functional/hash.hpp>
+
+namespace mbgl {
+namespace util {
+
+using Index = std::unordered_map<size_t, unsigned int>;
+
+unsigned int mergeFromRight(std::vector<SymbolFeature> &features,
+                            Index &rightIndex,
+                            Index::iterator left,
+                            size_t rightKey,
+                            GeometryCollection &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,
+                           Index &leftIndex,
+                           size_t leftKey,
+                           Index::iterator right,
+                           GeometryCollection &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;
+}
+
+enum class Side {
+    Left = false,
+    Right = true,
+};
+
+size_t
+getKey(const std::u32string& text, const GeometryCollection& geom, Side side) {
+    const GeometryCoordinate& coord = side == Side::Right ? geom[0].back() : geom[0].front();
+
+    auto hash = std::hash<std::u32string>()(text);
+    boost::hash_combine(hash, coord.x);
+    boost::hash_combine(hash, coord.y);
+    return hash;
+}
+
+void mergeLines(std::vector<SymbolFeature> &features) {
+
+    Index leftIndex;
+    Index rightIndex;
+
+    for (unsigned int k = 0; k < features.size(); k++) {
+        SymbolFeature &feature = features[k];
+        GeometryCollection &geometry = feature.geometry;
+
+        if (!feature.label.length()) {
+            continue;
+        }
+
+        const auto leftKey = getKey(feature.label, geometry, Side::Left);
+        const auto rightKey = getKey(feature.label, geometry, Side::Right);
+
+        const auto left = rightIndex.find(leftKey);
+        const 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, Side::Right)] = 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
diff --git a/src/mbgl/layout/merge_lines.hpp b/src/mbgl/layout/merge_lines.hpp
new file mode 100644
index 0000000000..bb4c01f6a2
--- /dev/null
+++ b/src/mbgl/layout/merge_lines.hpp
@@ -0,0 +1,26 @@
+#pragma once
+
+#include <unordered_map>
+#include <string>
+#include <vector>
+#include <mbgl/layout/symbol_layout.hpp>
+
+namespace mbgl {
+namespace util {
+
+unsigned int mergeFromRight(std::vector<SymbolFeature> &features,
+                            std::unordered_map<std::string, unsigned int> &rightIndex,
+                            std::unordered_map<std::string, unsigned int>::iterator left,
+                            std::string &rightKey,
+                            GeometryCollection &geom);
+
+unsigned int mergeFromLeft(std::vector<SymbolFeature> &features,
+                           std::unordered_map<std::string, unsigned int> &leftIndex,
+                           std::string &leftKey,
+                           std::unordered_map<std::string, unsigned int>::iterator right,
+                           GeometryCollection &geom);
+
+void mergeLines(std::vector<SymbolFeature> &features);
+
+} // end namespace util
+} // end namespace mbgl
diff --git a/src/mbgl/layout/symbol_layout.cpp b/src/mbgl/layout/symbol_layout.cpp
index aa22eb428d..2a85ead32b 100644
--- a/src/mbgl/layout/symbol_layout.cpp
+++ b/src/mbgl/layout/symbol_layout.cpp
@@ -1,4 +1,6 @@
 #include <mbgl/layout/symbol_layout.hpp>
+#include <mbgl/layout/merge_lines.hpp>
+#include <mbgl/layout/clip_lines.hpp>
 #include <mbgl/renderer/symbol_bucket.hpp>
 #include <mbgl/style/filter_evaluator.hpp>
 #include <mbgl/sprite/sprite_store.hpp>
@@ -10,8 +12,6 @@
 #include <mbgl/util/utf.hpp>
 #include <mbgl/util/token.hpp>
 #include <mbgl/util/math.hpp>
-#include <mbgl/util/merge_lines.hpp>
-#include <mbgl/util/clip_lines.hpp>
 #include <mbgl/util/std.hpp>
 #include <mbgl/util/constants.hpp>
 #include <mbgl/util/string.hpp>