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 : * Permission is hereby granted, free of charge, to any person obtaining a
11 : * copy of this software and associated documentation files (the "Software"),
12 : * to deal in the Software without restriction, including without limitation
13 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
14 : * and/or sell copies of the Software, and to permit persons to whom the
15 : * Software is furnished to do so, subject to the following conditions:
16 : *
17 : * The above copyright notice and this permission notice shall be included
18 : * in all copies or substantial portions of the Software.
19 : *
20 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
21 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
23 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
24 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
25 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
26 : * DEALINGS IN THE SOFTWARE.
27 : ****************************************************************************/
28 : #ifndef MARCHING_SQUARES_SEGMENT_MERGER_H
29 : #define MARCHING_SQUARES_SEGMENT_MERGER_H
30 :
31 : #include "point.h"
32 :
33 : #include <list>
34 : #include <map>
35 :
36 : #include <iostream>
37 :
38 : namespace marching_squares
39 : {
40 :
41 : // SegmentMerger: join segments into linestrings and possibly into rings of
42 : // polygons
43 : template <typename LineWriter, typename LevelGenerator> struct SegmentMerger
44 : {
45 : struct LineStringEx
46 : {
47 : LineString ls = LineString();
48 : bool isMerged = false;
49 : };
50 :
51 : // a collection of unmerged linestrings
52 : typedef std::list<LineStringEx> Lines;
53 :
54 36 : SegmentMerger(LineWriter &lineWriter, const LevelGenerator &levelGenerator,
55 : bool polygonize_)
56 : : polygonize(polygonize_), lineWriter_(lineWriter), lines_(),
57 36 : levelGenerator_(levelGenerator)
58 : {
59 36 : }
60 :
61 36 : ~SegmentMerger()
62 : {
63 36 : if (polygonize)
64 : {
65 66 : for (auto it = lines_.begin(); it != lines_.end(); ++it)
66 : {
67 49 : if (!it->second.empty())
68 0 : debug("remaining unclosed contour");
69 : }
70 : }
71 : // write all remaining (non-closed) lines
72 14288 : for (auto it = lines_.begin(); it != lines_.end(); ++it)
73 : {
74 14252 : const int levelIdx = it->first;
75 28357 : while (it->second.begin() != it->second.end())
76 : {
77 14105 : lineWriter_.addLine(levelGenerator_.level(levelIdx),
78 14105 : it->second.begin()->ls, /* closed */ false);
79 14105 : it->second.pop_front();
80 : }
81 : }
82 36 : }
83 :
84 10418 : void addBorderSegment(int levelIdx, const Point &start, const Point &end)
85 : {
86 10418 : addSegment_(levelIdx, start, end);
87 10418 : }
88 :
89 90723 : void addSegment(int levelIdx, const Point &start, const Point &end)
90 : {
91 90723 : addSegment_(levelIdx, start, end);
92 90723 : }
93 :
94 2662 : void beginningOfLine()
95 : {
96 2662 : if (polygonize)
97 1316 : return;
98 :
99 : // mark lines as non merged
100 19624 : for (auto &l : lines_)
101 : {
102 42720 : for (auto &ls : l.second)
103 : {
104 24442 : ls.isMerged = false;
105 : }
106 : }
107 : }
108 :
109 2658 : void endOfLine()
110 : {
111 2658 : if (polygonize)
112 1316 : return;
113 :
114 : // At the end of the line, we know that if no segment has been merged to
115 : // an existing line, it means there won't be anything more in the
116 : // future, we can then emit the line (this both speeds up and saves
117 : // memory)
118 :
119 19959 : for (auto &l : lines_)
120 : {
121 18617 : const int levelIdx = l.first;
122 18617 : auto it = l.second.begin();
123 47204 : while (it != l.second.end())
124 : {
125 28587 : if (!it->isMerged)
126 : {
127 : // Note that emitLine_ erases `it` and returns an iterator
128 : // advanced to the next element.
129 3904 : it = emitLine_(levelIdx, it, /* closed */ false);
130 : }
131 : else
132 : {
133 24683 : ++it;
134 : }
135 : }
136 : }
137 : }
138 :
139 : // non copyable
140 : SegmentMerger(const SegmentMerger<LineWriter, LevelGenerator> &) = delete;
141 : SegmentMerger<LineWriter, LevelGenerator> &
142 : operator=(const SegmentMerger<LineWriter, LevelGenerator> &) = delete;
143 :
144 : const bool polygonize;
145 :
146 : private:
147 : LineWriter &lineWriter_;
148 : // lines of each level
149 : std::map<int, Lines> lines_;
150 : const LevelGenerator &levelGenerator_;
151 :
152 101141 : void addSegment_(int levelIdx, const Point &start, const Point &end)
153 : {
154 101141 : Lines &lines = lines_[levelIdx];
155 :
156 101141 : if (start == end)
157 : {
158 0 : debug("degenerate segment (%f %f)", start.x, start.y);
159 80 : return;
160 : }
161 : // attempt to merge segment with existing line
162 101141 : auto it = lines.begin();
163 258275 : for (; it != lines.end(); ++it)
164 : {
165 232236 : if (it->ls.back() == end)
166 : {
167 1107 : it->ls.push_back(start);
168 1107 : it->isMerged = true;
169 1107 : break;
170 : }
171 231129 : if (it->ls.front() == end)
172 : {
173 33578 : it->ls.push_front(start);
174 33578 : it->isMerged = true;
175 33578 : break;
176 : }
177 197551 : if (it->ls.back() == start)
178 : {
179 39325 : it->ls.push_back(end);
180 39325 : it->isMerged = true;
181 39325 : break;
182 : }
183 158226 : if (it->ls.front() == start)
184 : {
185 1092 : it->ls.push_front(end);
186 1092 : it->isMerged = true;
187 1092 : break;
188 : }
189 : }
190 :
191 101141 : if (it == lines.end())
192 : {
193 : // new line
194 26039 : lines.push_back(LineStringEx());
195 26039 : lines.back().ls.push_back(start);
196 26039 : lines.back().ls.push_back(end);
197 26039 : lines.back().isMerged = true;
198 : }
199 75102 : else if (polygonize && (it->ls.front() == it->ls.back()))
200 : {
201 : // ring closed
202 80 : emitLine_(levelIdx, it, /* closed */ true);
203 80 : return;
204 : }
205 : else
206 : {
207 : // try to perform linemerge with another line
208 : // since we got out of the previous loop on the first match
209 : // there is no need to test previous elements
210 : // also: a segment merges at most two lines, no need to stall here
211 : // ;)
212 75022 : auto other = it;
213 75022 : ++other;
214 148354 : for (; other != lines.end(); ++other)
215 : {
216 81282 : if (it->ls.back() == other->ls.front())
217 : {
218 6099 : it->ls.pop_back();
219 6099 : it->ls.splice(it->ls.end(), other->ls);
220 6099 : it->isMerged = true;
221 6099 : lines.erase(other);
222 : // if that makes a closed ring, returns it
223 6099 : if (it->ls.front() == it->ls.back())
224 0 : emitLine_(levelIdx, it, /* closed */ true);
225 6099 : break;
226 : }
227 75183 : else if (other->ls.back() == it->ls.front())
228 : {
229 1845 : it->ls.pop_front();
230 1845 : other->ls.splice(other->ls.end(), it->ls);
231 1845 : other->isMerged = true;
232 1845 : lines.erase(it);
233 : // if that makes a closed ring, returns it
234 1845 : if (other->ls.front() == other->ls.back())
235 0 : emitLine_(levelIdx, other, /* closed */ true);
236 1845 : break;
237 : }
238 : // two lists must be merged but one is in the opposite direction
239 73338 : else if (it->ls.back() == other->ls.back())
240 : {
241 4 : it->ls.pop_back();
242 12 : for (auto rit = other->ls.rbegin(); rit != other->ls.rend();
243 8 : ++rit)
244 : {
245 8 : it->ls.push_back(*rit);
246 : }
247 4 : it->isMerged = true;
248 4 : lines.erase(other);
249 : // if that makes a closed ring, returns it
250 4 : if (it->ls.front() == it->ls.back())
251 0 : emitLine_(levelIdx, it, /* closed */ true);
252 4 : break;
253 : }
254 73334 : else if (it->ls.front() == other->ls.front())
255 : {
256 2 : it->ls.pop_front();
257 6 : for (auto rit = other->ls.begin(); rit != other->ls.end();
258 4 : ++rit)
259 : {
260 4 : it->ls.push_front(*rit);
261 : }
262 2 : it->isMerged = true;
263 2 : lines.erase(other);
264 : // if that makes a closed ring, returns it
265 2 : if (it->ls.front() == it->ls.back())
266 0 : emitLine_(levelIdx, it, /* closed */ true);
267 2 : break;
268 : }
269 : }
270 : }
271 : }
272 :
273 3984 : typename Lines::iterator emitLine_(int levelIdx,
274 : typename Lines::iterator it, bool closed)
275 : {
276 3984 : Lines &lines = lines_[levelIdx];
277 3984 : if (lines.empty())
278 0 : lines_.erase(levelIdx);
279 :
280 : // consume "it" and remove it from the list
281 3984 : lineWriter_.addLine(levelGenerator_.level(levelIdx), it->ls, closed);
282 3984 : return lines.erase(it);
283 : }
284 : };
285 :
286 : } // namespace marching_squares
287 : #endif
|
