Line data Source code
1 : /******************************************************************************
2 : *
3 : * Project: Marching square algorithm
4 : * Purpose: Core algorithm implementation for contour line generation.
5 : * Author: Oslandia <infos at oslandia dot com>
6 : *
7 : ******************************************************************************
8 : * Copyright (c) 2018, Oslandia <infos at oslandia dot com>
9 : *
10 : * SPDX-License-Identifier: MIT
11 : ****************************************************************************/
12 : #ifndef MARCHING_SQUARES_SEGMENT_MERGER_H
13 : #define MARCHING_SQUARES_SEGMENT_MERGER_H
14 :
15 : #include "point.h"
16 :
17 : #include <list>
18 : #include <map>
19 :
20 : #include <iostream>
21 :
22 : namespace marching_squares
23 : {
24 :
25 : // SegmentMerger: join segments into linestrings and possibly into rings of
26 : // polygons
27 : template <typename LineWriter, typename LevelGenerator> struct SegmentMerger
28 : {
29 : struct LineStringEx
30 : {
31 : LineString ls = LineString();
32 : bool isMerged = false;
33 : };
34 :
35 : // a collection of unmerged linestrings
36 : typedef std::list<LineStringEx> Lines;
37 :
38 41 : SegmentMerger(LineWriter &lineWriter, const LevelGenerator &levelGenerator,
39 : bool polygonize_)
40 : : polygonize(polygonize_), lineWriter_(lineWriter), lines_(),
41 41 : levelGenerator_(levelGenerator)
42 : {
43 41 : }
44 :
45 41 : ~SegmentMerger()
46 : {
47 41 : if (polygonize)
48 : {
49 110 : for (auto it = lines_.begin(); it != lines_.end(); ++it)
50 : {
51 87 : if (!it->second.empty())
52 0 : debug("remaining unclosed contour");
53 : }
54 : }
55 : // write all remaining (non-closed) lines
56 310 : for (auto it = lines_.begin(); it != lines_.end(); ++it)
57 : {
58 269 : const int levelIdx = it->first;
59 357 : while (it->second.begin() != it->second.end())
60 : {
61 88 : lineWriter_.addLine(levelGenerator_.level(levelIdx),
62 88 : it->second.begin()->ls, /* closed */ false);
63 88 : it->second.pop_front();
64 : }
65 : }
66 41 : }
67 :
68 87501 : void addSegment(int levelIdx, const Point &start, const Point &end)
69 : {
70 87501 : addSegment_(levelIdx, start, end);
71 87501 : }
72 :
73 16922 : void addBorderSegment(int levelIdx, const Point &start, const Point &end)
74 : {
75 16922 : addSegment_(levelIdx, start, end);
76 16922 : }
77 :
78 4052 : void beginningOfLine()
79 : {
80 4052 : if (polygonize)
81 2126 : return;
82 :
83 : // mark lines as non merged
84 20382 : for (auto &l : lines_)
85 : {
86 38110 : for (auto &ls : l.second)
87 : {
88 19654 : ls.isMerged = false;
89 : }
90 : }
91 : }
92 :
93 4052 : void endOfLine()
94 : {
95 4052 : if (polygonize)
96 2126 : return;
97 :
98 : // At the end of the line, we know that if no segment has been merged to
99 : // an existing line, it means there won't be anything more in the
100 : // future, we can then emit the line (this both speeds up and saves
101 : // memory)
102 :
103 20564 : for (auto &l : lines_)
104 : {
105 18638 : const int levelIdx = l.first;
106 18638 : auto it = l.second.begin();
107 40404 : while (it != l.second.end())
108 : {
109 21766 : if (!it->isMerged)
110 : {
111 : // Note that emitLine_ erases `it` and returns an iterator
112 : // advanced to the next element.
113 2024 : it = emitLine_(levelIdx, it, /* closed */ false);
114 : }
115 : else
116 : {
117 19742 : ++it;
118 : }
119 : }
120 : }
121 : }
122 :
123 : // non copyable
124 : SegmentMerger(const SegmentMerger<LineWriter, LevelGenerator> &) = delete;
125 : SegmentMerger<LineWriter, LevelGenerator> &
126 : operator=(const SegmentMerger<LineWriter, LevelGenerator> &) = delete;
127 :
128 : const bool polygonize;
129 :
130 : private:
131 : LineWriter &lineWriter_;
132 : // lines of each level
133 : std::map<int, Lines> lines_;
134 : const LevelGenerator &levelGenerator_;
135 :
136 104423 : void addSegment_(int levelIdx, const Point &start, const Point &end)
137 : {
138 104423 : Lines &lines = lines_[levelIdx];
139 :
140 104423 : if (start == end)
141 : {
142 0 : debug("degenerate segment (%f %f)", start.x, start.y);
143 618 : return;
144 : }
145 : // attempt to merge segment with existing line
146 104423 : auto it = lines.begin();
147 239657 : for (; it != lines.end(); ++it)
148 : {
149 227120 : if (it->ls.back() == end)
150 : {
151 1309 : it->ls.push_back(start);
152 1309 : it->isMerged = true;
153 1309 : break;
154 : }
155 225811 : if (it->ls.front() == end)
156 : {
157 40221 : it->ls.push_front(start);
158 40221 : it->isMerged = true;
159 40221 : break;
160 : }
161 185590 : if (it->ls.back() == start)
162 : {
163 47198 : it->ls.push_back(end);
164 47198 : it->isMerged = true;
165 47198 : break;
166 : }
167 138392 : if (it->ls.front() == start)
168 : {
169 3158 : it->ls.push_front(end);
170 3158 : it->isMerged = true;
171 3158 : break;
172 : }
173 : }
174 :
175 104423 : if (it == lines.end())
176 : {
177 : // new line
178 12537 : lines.push_back(LineStringEx());
179 12537 : lines.back().ls.push_back(start);
180 12537 : lines.back().ls.push_back(end);
181 12537 : lines.back().isMerged = true;
182 : }
183 91886 : else if (polygonize && (it->ls.front() == it->ls.back()))
184 : {
185 : // ring closed
186 618 : emitLine_(levelIdx, it, /* closed */ true);
187 618 : return;
188 : }
189 : else
190 : {
191 : // try to perform linemerge with another line
192 : // since we got out of the previous loop on the first match
193 : // there is no need to test previous elements
194 : // also: a segment merges at most two lines, no need to stall here
195 : // ;)
196 91268 : auto other = it;
197 91268 : ++other;
198 156896 : for (; other != lines.end(); ++other)
199 : {
200 75435 : if (it->ls.back() == other->ls.front())
201 : {
202 6894 : it->ls.pop_back();
203 6894 : it->ls.splice(it->ls.end(), other->ls);
204 6894 : it->isMerged = true;
205 6894 : lines.erase(other);
206 : // if that makes a closed ring, returns it
207 6894 : if (it->ls.front() == it->ls.back())
208 0 : emitLine_(levelIdx, it, /* closed */ true);
209 6894 : break;
210 : }
211 68541 : else if (other->ls.back() == it->ls.front())
212 : {
213 1927 : it->ls.pop_front();
214 1927 : other->ls.splice(other->ls.end(), it->ls);
215 1927 : other->isMerged = true;
216 1927 : lines.erase(it);
217 : // if that makes a closed ring, returns it
218 1927 : if (other->ls.front() == other->ls.back())
219 0 : emitLine_(levelIdx, other, /* closed */ true);
220 1927 : break;
221 : }
222 : // two lists must be merged but one is in the opposite direction
223 66614 : else if (it->ls.back() == other->ls.back())
224 : {
225 60 : it->ls.pop_back();
226 904 : for (auto rit = other->ls.rbegin(); rit != other->ls.rend();
227 844 : ++rit)
228 : {
229 844 : it->ls.push_back(*rit);
230 : }
231 60 : it->isMerged = true;
232 60 : lines.erase(other);
233 : // if that makes a closed ring, returns it
234 60 : if (it->ls.front() == it->ls.back())
235 0 : emitLine_(levelIdx, it, /* closed */ true);
236 60 : break;
237 : }
238 66554 : else if (it->ls.front() == other->ls.front())
239 : {
240 926 : it->ls.pop_front();
241 5386 : for (auto rit = other->ls.begin(); rit != other->ls.end();
242 4460 : ++rit)
243 : {
244 4460 : it->ls.push_front(*rit);
245 : }
246 926 : it->isMerged = true;
247 926 : lines.erase(other);
248 : // if that makes a closed ring, returns it
249 926 : if (it->ls.front() == it->ls.back())
250 0 : emitLine_(levelIdx, it, /* closed */ true);
251 926 : break;
252 : }
253 : }
254 : }
255 : }
256 :
257 2642 : typename Lines::iterator emitLine_(int levelIdx,
258 : typename Lines::iterator it, bool closed)
259 : {
260 2642 : Lines &lines = lines_[levelIdx];
261 2642 : if (lines.empty())
262 0 : lines_.erase(levelIdx);
263 :
264 : // consume "it" and remove it from the list
265 2642 : lineWriter_.addLine(levelGenerator_.level(levelIdx), it->ls, closed);
266 2642 : return lines.erase(it);
267 : }
268 : };
269 :
270 : } // namespace marching_squares
271 : #endif
|
