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 "cpl_error.h"
16 : #include "point.h"
17 :
18 : #include <list>
19 : #include <map>
20 :
21 : #include <iostream>
22 :
23 : namespace marching_squares
24 : {
25 :
26 : // SegmentMerger: join segments into linestrings and possibly into rings of
27 : // polygons
28 : template <typename LineWriter, typename LevelGenerator> struct SegmentMerger
29 : {
30 : struct LineStringEx
31 : {
32 : LineString ls = LineString();
33 : bool isMerged = false;
34 : };
35 :
36 : // a collection of unmerged linestrings
37 : typedef std::list<LineStringEx> Lines;
38 :
39 77 : SegmentMerger(LineWriter &lineWriter, const LevelGenerator &levelGenerator,
40 : bool polygonize_)
41 : : polygonize(polygonize_), lineWriter_(lineWriter), lines_(),
42 77 : levelGenerator_(levelGenerator), m_anSkipLevels()
43 : {
44 77 : }
45 :
46 77 : ~SegmentMerger()
47 : {
48 77 : if (polygonize)
49 : {
50 183 : for (auto it = lines_.begin(); it != lines_.end(); ++it)
51 : {
52 144 : if (!it->second.empty())
53 0 : debug("remaining unclosed contour");
54 : }
55 : }
56 : // write all remaining (non-closed) lines
57 670 : for (auto it = lines_.begin(); it != lines_.end(); ++it)
58 : {
59 593 : const int levelIdx = it->first;
60 :
61 : // Skip levels that should be skipped
62 593 : if (std::find(m_anSkipLevels.begin(), m_anSkipLevels.end(),
63 1186 : levelIdx) != m_anSkipLevels.end())
64 : {
65 29 : continue;
66 : }
67 855 : while (it->second.begin() != it->second.end())
68 : {
69 291 : lineWriter_.addLine(levelGenerator_.level(levelIdx),
70 291 : it->second.begin()->ls, /* closed */ false);
71 291 : it->second.pop_front();
72 : }
73 : }
74 77 : }
75 :
76 109460 : void addSegment(int levelIdx, const Point &start, const Point &end)
77 : {
78 109460 : addSegment_(levelIdx, start, end);
79 109460 : }
80 :
81 26088 : void addBorderSegment(int levelIdx, const Point &start, const Point &end)
82 : {
83 26088 : addSegment_(levelIdx, start, end);
84 26088 : }
85 :
86 5320 : void beginningOfLine()
87 : {
88 5320 : if (polygonize)
89 3280 : return;
90 :
91 : // mark lines as non merged
92 23140 : for (auto &l : lines_)
93 : {
94 48621 : for (auto &ls : l.second)
95 : {
96 27521 : ls.isMerged = false;
97 : }
98 : }
99 : }
100 :
101 5320 : void endOfLine()
102 : {
103 5320 : if (polygonize)
104 3280 : return;
105 :
106 : // At the end of the line, we know that if no segment has been merged to
107 : // an existing line, it means there won't be anything more in the
108 : // future, we can then emit the line (this both speeds up and saves
109 : // memory)
110 :
111 23589 : for (auto &l : lines_)
112 : {
113 21549 : const int levelIdx = l.first;
114 21549 : auto it = l.second.begin();
115 53787 : while (it != l.second.end())
116 : {
117 32238 : if (!it->isMerged)
118 : {
119 : // Note that emitLine_ erases `it` and returns an iterator
120 : // advanced to the next element.
121 4426 : it = emitLine_(levelIdx, it, /* closed */ false);
122 : }
123 : else
124 : {
125 27812 : ++it;
126 : }
127 : }
128 : }
129 : }
130 :
131 : // non copyable
132 : SegmentMerger(const SegmentMerger<LineWriter, LevelGenerator> &) = delete;
133 : SegmentMerger<LineWriter, LevelGenerator> &
134 : operator=(const SegmentMerger<LineWriter, LevelGenerator> &) = delete;
135 :
136 : /**
137 : * @brief setSkipLevels sets the levels that should be skipped
138 : * when polygonize option is set.
139 : * @param anSkipLevels integer 0-based levels to skip.
140 : */
141 30 : void setSkipLevels(const std::vector<int> &anSkipLevels)
142 : {
143 : // Warn if polygonize is not set
144 30 : if (!polygonize)
145 : {
146 0 : CPLError(
147 : CE_Warning, CPLE_NotSupported,
148 : "setSkipLevels is ignored when polygonize option is not set");
149 : }
150 30 : m_anSkipLevels = anSkipLevels;
151 30 : }
152 :
153 : const bool polygonize;
154 :
155 : private:
156 : LineWriter &lineWriter_;
157 : // lines of each level
158 : std::map<int, Lines> lines_;
159 : const LevelGenerator &levelGenerator_;
160 :
161 : // Store 0-indexed levels to skip when polygonize option is set
162 : std::vector<int> m_anSkipLevels;
163 :
164 135548 : void addSegment_(int levelIdx, const Point &start, const Point &end)
165 : {
166 :
167 135548 : Lines &lines = lines_[levelIdx];
168 :
169 135548 : if (start == end)
170 : {
171 4 : debug("degenerate segment (%f %f)", start.x, start.y);
172 689 : return;
173 : }
174 : // attempt to merge segment with existing line
175 135544 : auto it = lines.begin();
176 333870 : for (; it != lines.end(); ++it)
177 : {
178 317371 : if (it->ls.back() == end)
179 : {
180 2032 : it->ls.push_back(start);
181 2032 : it->isMerged = true;
182 2032 : break;
183 : }
184 315339 : if (it->ls.front() == end)
185 : {
186 53410 : it->ls.push_front(start);
187 53410 : it->isMerged = true;
188 53410 : break;
189 : }
190 261929 : if (it->ls.back() == start)
191 : {
192 59722 : it->ls.push_back(end);
193 59722 : it->isMerged = true;
194 59722 : break;
195 : }
196 202207 : if (it->ls.front() == start)
197 : {
198 3881 : it->ls.push_front(end);
199 3881 : it->isMerged = true;
200 3881 : break;
201 : }
202 : }
203 :
204 135544 : if (it == lines.end())
205 : {
206 : // new line
207 16499 : lines.push_back(LineStringEx());
208 16499 : lines.back().ls.push_back(start);
209 16499 : lines.back().ls.push_back(end);
210 16499 : lines.back().isMerged = true;
211 : }
212 119045 : else if (polygonize && (it->ls.front() == it->ls.back()))
213 : {
214 : // ring closed
215 685 : emitLine_(levelIdx, it, /* closed */ true);
216 685 : return;
217 : }
218 : else
219 : {
220 : // try to perform linemerge with another line
221 : // since we got out of the previous loop on the first match
222 : // there is no need to test previous elements
223 : // also: a segment merges at most two lines, no need to stall here
224 : // ;)
225 118360 : auto other = it;
226 118360 : ++other;
227 213088 : for (; other != lines.end(); ++other)
228 : {
229 105825 : if (it->ls.back() == other->ls.front())
230 : {
231 7673 : it->ls.pop_back();
232 7673 : it->ls.splice(it->ls.end(), other->ls);
233 7673 : it->isMerged = true;
234 7673 : lines.erase(other);
235 : // if that makes a closed ring, returns it
236 7673 : if (it->ls.front() == it->ls.back())
237 0 : emitLine_(levelIdx, it, /* closed */ true);
238 7673 : break;
239 : }
240 98152 : else if (other->ls.back() == it->ls.front())
241 : {
242 2416 : it->ls.pop_front();
243 2416 : other->ls.splice(other->ls.end(), it->ls);
244 2416 : other->isMerged = true;
245 2416 : lines.erase(it);
246 : // if that makes a closed ring, returns it
247 2416 : if (other->ls.front() == other->ls.back())
248 0 : emitLine_(levelIdx, other, /* closed */ true);
249 2416 : break;
250 : }
251 : // two lists must be merged but one is in the opposite direction
252 95736 : else if (it->ls.back() == other->ls.back())
253 : {
254 65 : it->ls.pop_back();
255 919 : for (auto rit = other->ls.rbegin(); rit != other->ls.rend();
256 854 : ++rit)
257 : {
258 854 : it->ls.push_back(*rit);
259 : }
260 65 : it->isMerged = true;
261 65 : lines.erase(other);
262 : // if that makes a closed ring, returns it
263 65 : if (it->ls.front() == it->ls.back())
264 0 : emitLine_(levelIdx, it, /* closed */ true);
265 65 : break;
266 : }
267 95671 : else if (it->ls.front() == other->ls.front())
268 : {
269 943 : it->ls.pop_front();
270 5437 : for (auto rit = other->ls.begin(); rit != other->ls.end();
271 4494 : ++rit)
272 : {
273 4494 : it->ls.push_front(*rit);
274 : }
275 943 : it->isMerged = true;
276 943 : lines.erase(other);
277 : // if that makes a closed ring, returns it
278 943 : if (it->ls.front() == it->ls.back())
279 0 : emitLine_(levelIdx, it, /* closed */ true);
280 943 : break;
281 : }
282 : }
283 : }
284 : }
285 :
286 5111 : typename Lines::iterator emitLine_(int levelIdx,
287 : typename Lines::iterator it, bool closed)
288 : {
289 :
290 5111 : Lines &lines = lines_[levelIdx];
291 5111 : if (lines.empty())
292 0 : lines_.erase(levelIdx);
293 :
294 : // consume "it" and remove it from the list
295 : // but clear the line if the level should be skipped
296 5111 : if (std::find(m_anSkipLevels.begin(), m_anSkipLevels.end(), levelIdx) !=
297 10222 : m_anSkipLevels.end())
298 : {
299 32 : it->ls.clear();
300 : }
301 5111 : lineWriter_.addLine(levelGenerator_.level(levelIdx), it->ls, closed);
302 5111 : return lines.erase(it);
303 : }
304 : };
305 :
306 : } // namespace marching_squares
307 : #endif
|
