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 52 : SegmentMerger(LineWriter &lineWriter, const LevelGenerator &levelGenerator,
40 : bool polygonize_)
41 : : polygonize(polygonize_), lineWriter_(lineWriter), lines_(),
42 52 : levelGenerator_(levelGenerator), m_anSkipLevels()
43 : {
44 52 : }
45 :
46 52 : ~SegmentMerger()
47 : {
48 52 : if (polygonize)
49 : {
50 154 : for (auto it = lines_.begin(); it != lines_.end(); ++it)
51 : {
52 121 : if (!it->second.empty())
53 0 : debug("remaining unclosed contour");
54 : }
55 : }
56 : // write all remaining (non-closed) lines
57 537 : for (auto it = lines_.begin(); it != lines_.end(); ++it)
58 : {
59 485 : const int levelIdx = it->first;
60 :
61 : // Skip levels that should be skipped
62 485 : if (std::find(m_anSkipLevels.begin(), m_anSkipLevels.end(),
63 970 : levelIdx) != m_anSkipLevels.end())
64 : {
65 22 : continue;
66 : }
67 707 : while (it->second.begin() != it->second.end())
68 : {
69 244 : lineWriter_.addLine(levelGenerator_.level(levelIdx),
70 244 : it->second.begin()->ls, /* closed */ false);
71 244 : it->second.pop_front();
72 : }
73 : }
74 52 : }
75 :
76 105903 : void addSegment(int levelIdx, const Point &start, const Point &end)
77 : {
78 105903 : addSegment_(levelIdx, start, end);
79 105903 : }
80 :
81 25958 : void addBorderSegment(int levelIdx, const Point &start, const Point &end)
82 : {
83 25958 : addSegment_(levelIdx, start, end);
84 25958 : }
85 :
86 5209 : void beginningOfLine()
87 : {
88 5209 : if (polygonize)
89 3262 : return;
90 :
91 : // mark lines as non merged
92 22551 : for (auto &l : lines_)
93 : {
94 46689 : for (auto &ls : l.second)
95 : {
96 26085 : ls.isMerged = false;
97 : }
98 : }
99 : }
100 :
101 5209 : void endOfLine()
102 : {
103 5209 : if (polygonize)
104 3262 : 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 22915 : for (auto &l : lines_)
112 : {
113 20968 : const int levelIdx = l.first;
114 20968 : auto it = l.second.begin();
115 51285 : while (it != l.second.end())
116 : {
117 30317 : if (!it->isMerged)
118 : {
119 : // Note that emitLine_ erases `it` and returns an iterator
120 : // advanced to the next element.
121 3988 : it = emitLine_(levelIdx, it, /* closed */ false);
122 : }
123 : else
124 : {
125 26329 : ++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 24 : void setSkipLevels(const std::vector<int> &anSkipLevels)
142 : {
143 : // Warn if polygonize is not set
144 24 : if (!polygonize)
145 : {
146 0 : CPLError(
147 : CE_Warning, CPLE_NotSupported,
148 : "setSkipLevels is ignored when polygonize option is not set");
149 : }
150 24 : m_anSkipLevels = anSkipLevels;
151 24 : }
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 131861 : void addSegment_(int levelIdx, const Point &start, const Point &end)
165 : {
166 :
167 131861 : Lines &lines = lines_[levelIdx];
168 :
169 131861 : if (start == end)
170 : {
171 4 : debug("degenerate segment (%f %f)", start.x, start.y);
172 666 : return;
173 : }
174 : // attempt to merge segment with existing line
175 131857 : auto it = lines.begin();
176 318889 : for (; it != lines.end(); ++it)
177 : {
178 303170 : if (it->ls.back() == end)
179 : {
180 1878 : it->ls.push_back(start);
181 1878 : it->isMerged = true;
182 1878 : break;
183 : }
184 301292 : if (it->ls.front() == end)
185 : {
186 52059 : it->ls.push_front(start);
187 52059 : it->isMerged = true;
188 52059 : break;
189 : }
190 249233 : if (it->ls.back() == start)
191 : {
192 58476 : it->ls.push_back(end);
193 58476 : it->isMerged = true;
194 58476 : break;
195 : }
196 190757 : if (it->ls.front() == start)
197 : {
198 3725 : it->ls.push_front(end);
199 3725 : it->isMerged = true;
200 3725 : break;
201 : }
202 : }
203 :
204 131857 : if (it == lines.end())
205 : {
206 : // new line
207 15719 : lines.push_back(LineStringEx());
208 15719 : lines.back().ls.push_back(start);
209 15719 : lines.back().ls.push_back(end);
210 15719 : lines.back().isMerged = true;
211 : }
212 116138 : else if (polygonize && (it->ls.front() == it->ls.back()))
213 : {
214 : // ring closed
215 662 : emitLine_(levelIdx, it, /* closed */ true);
216 662 : 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 115476 : auto other = it;
226 115476 : ++other;
227 205089 : for (; other != lines.end(); ++other)
228 : {
229 100438 : if (it->ls.back() == other->ls.front())
230 : {
231 7527 : it->ls.pop_back();
232 7527 : it->ls.splice(it->ls.end(), other->ls);
233 7527 : it->isMerged = true;
234 7527 : lines.erase(other);
235 : // if that makes a closed ring, returns it
236 7527 : if (it->ls.front() == it->ls.back())
237 0 : emitLine_(levelIdx, it, /* closed */ true);
238 7527 : break;
239 : }
240 92911 : else if (other->ls.back() == it->ls.front())
241 : {
242 2304 : it->ls.pop_front();
243 2304 : other->ls.splice(other->ls.end(), it->ls);
244 2304 : other->isMerged = true;
245 2304 : lines.erase(it);
246 : // if that makes a closed ring, returns it
247 2304 : if (other->ls.front() == other->ls.back())
248 0 : emitLine_(levelIdx, other, /* closed */ true);
249 2304 : break;
250 : }
251 : // two lists must be merged but one is in the opposite direction
252 90607 : else if (it->ls.back() == other->ls.back())
253 : {
254 62 : it->ls.pop_back();
255 910 : for (auto rit = other->ls.rbegin(); rit != other->ls.rend();
256 848 : ++rit)
257 : {
258 848 : it->ls.push_back(*rit);
259 : }
260 62 : it->isMerged = true;
261 62 : lines.erase(other);
262 : // if that makes a closed ring, returns it
263 62 : if (it->ls.front() == it->ls.back())
264 0 : emitLine_(levelIdx, it, /* closed */ true);
265 62 : break;
266 : }
267 90545 : else if (it->ls.front() == other->ls.front())
268 : {
269 932 : it->ls.pop_front();
270 5404 : for (auto rit = other->ls.begin(); rit != other->ls.end();
271 4472 : ++rit)
272 : {
273 4472 : it->ls.push_front(*rit);
274 : }
275 932 : it->isMerged = true;
276 932 : lines.erase(other);
277 : // if that makes a closed ring, returns it
278 932 : if (it->ls.front() == it->ls.back())
279 0 : emitLine_(levelIdx, it, /* closed */ true);
280 932 : break;
281 : }
282 : }
283 : }
284 : }
285 :
286 4650 : typename Lines::iterator emitLine_(int levelIdx,
287 : typename Lines::iterator it, bool closed)
288 : {
289 :
290 4650 : Lines &lines = lines_[levelIdx];
291 4650 : 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 4650 : if (std::find(m_anSkipLevels.begin(), m_anSkipLevels.end(), levelIdx) !=
297 9300 : m_anSkipLevels.end())
298 : {
299 25 : it->ls.clear();
300 : }
301 4650 : lineWriter_.addLine(levelGenerator_.level(levelIdx), it->ls, closed);
302 4650 : return lines.erase(it);
303 : }
304 : };
305 :
306 : } // namespace marching_squares
307 : #endif
|
