1 #include <mbgl/layout/merge_lines.hpp>
2 #include <mbgl/layout/symbol_feature.hpp>
3
4 #include <boost/functional/hash.hpp>
5
6 namespace mbgl {
7 namespace util {
8
9 // Map of key -> index into features
10 using Index = std::unordered_map<size_t, size_t>;
11
mergeFromRight(std::vector<SymbolFeature> & features,Index & rightIndex,Index::iterator left,size_t rightKey,GeometryCollection & geom)12 size_t mergeFromRight(std::vector<SymbolFeature>& features,
13 Index& rightIndex,
14 Index::iterator left,
15 size_t rightKey,
16 GeometryCollection& geom) {
17
18 const size_t index = left->second;
19 rightIndex.erase(left);
20 rightIndex[rightKey] = index;
21 features[index].geometry[0].pop_back();
22 features[index].geometry[0].insert(
23 features[index].geometry[0].end(), geom[0].begin(), geom[0].end());
24 geom[0].clear();
25 return index;
26 }
27
mergeFromLeft(std::vector<SymbolFeature> & features,Index & leftIndex,Index::iterator right,size_t leftKey,GeometryCollection & geom)28 size_t mergeFromLeft(std::vector<SymbolFeature>& features,
29 Index& leftIndex,
30 Index::iterator right,
31 size_t leftKey,
32 GeometryCollection& geom) {
33
34 const size_t index = right->second;
35 leftIndex.erase(right);
36 leftIndex[leftKey] = index;
37 geom[0].pop_back();
38 geom[0].insert(
39 geom[0].end(), features[index].geometry[0].begin(), features[index].geometry[0].end());
40 features[index].geometry[0].clear();
41 std::swap(features[index].geometry[0], geom[0]);
42 return index;
43 }
44
getKey(const std::u16string & text,const GeometryCoordinate & coord)45 size_t getKey(const std::u16string& text, const GeometryCoordinate& coord) {
46 auto hash = std::hash<std::u16string>()(text);
47 boost::hash_combine(hash, coord.x);
48 boost::hash_combine(hash, coord.y);
49 return hash;
50 }
51
mergeLines(std::vector<SymbolFeature> & features)52 void mergeLines(std::vector<SymbolFeature>& features) {
53 Index leftIndex;
54 Index rightIndex;
55
56 for (size_t k = 0; k < features.size(); k++) {
57 SymbolFeature& feature = features[k];
58 GeometryCollection& geometry = feature.geometry;
59
60 if (!feature.text || geometry.empty() || geometry[0].empty()) {
61 continue;
62 }
63
64 const size_t leftKey = getKey(*feature.text, geometry[0].front());
65 const size_t rightKey = getKey(*feature.text, geometry[0].back());
66
67 const auto left = rightIndex.find(leftKey);
68 const auto right = leftIndex.find(rightKey);
69
70 if (left != rightIndex.end() && right != leftIndex.end() && left->second != right->second) {
71 // found lines with the same text adjacent to both ends of the current line, merge all
72 // three
73 size_t j = mergeFromLeft(features, leftIndex, right, leftKey, geometry);
74 size_t i = mergeFromRight(features, rightIndex, left, rightKey, features[j].geometry);
75
76 leftIndex.erase(leftKey);
77 rightIndex.erase(rightKey);
78 rightIndex[getKey(*feature.text, features[i].geometry[0].back())] = i;
79
80 } else if (left != rightIndex.end()) {
81 // found mergeable line adjacent to the start of the current line, merge
82 mergeFromRight(features, rightIndex, left, rightKey, geometry);
83
84 } else if (right != leftIndex.end()) {
85 // found mergeable line adjacent to the end of the current line, merge
86 mergeFromLeft(features, leftIndex, right, leftKey, geometry);
87
88 } else {
89 // no adjacent lines, add as a new item
90 leftIndex[leftKey] = k;
91 rightIndex[rightKey] = k;
92 }
93 }
94 }
95
96 } // end namespace util
97 } // end namespace mbgl
98