Line data Source code
1 : /******************************************************************************
2 : *
3 : * Project: GDAL algorithms
4 : * Purpose: Tests for the marching squares algorithm
5 : * Author: Hugo Mercier, <hugo dot mercier at oslandia dot com>
6 : *
7 : ******************************************************************************
8 : * Copyright (c) 2018, Hugo Mercier, <hugo dot mercier at oslandia dot com>
9 : *
10 : * SPDX-License-Identifier: MIT
11 : ****************************************************************************/
12 :
13 : #include "gdal_unit_test.h"
14 :
15 : #include "gdal_alg.h"
16 :
17 : #include "marching_squares/level_generator.h"
18 : #include "marching_squares/polygon_ring_appender.h"
19 : #include "marching_squares/segment_merger.h"
20 : #include "marching_squares/contour_generator.h"
21 :
22 : #ifdef DEBUG
23 : #include <fstream>
24 : #endif
25 :
26 : #include <limits>
27 :
28 : #include "gtest_include.h"
29 :
30 : namespace marching_squares
31 : {
32 : class TestPolygonWriter
33 : {
34 : public:
35 13 : void startPolygon(double level)
36 : {
37 13 : currentPolygon_ = &polygons_[level];
38 13 : }
39 :
40 13 : void endPolygon()
41 : {
42 13 : }
43 :
44 16 : void addPart(const std::list<marching_squares::Point> &ring)
45 : {
46 16 : PolygonPart part;
47 16 : part.push_back(ring);
48 16 : currentPolygon_->emplace_back(part);
49 16 : currentPart_ = ¤tPolygon_->back();
50 16 : }
51 :
52 3 : void addInteriorRing(const std::list<marching_squares::Point> &ring)
53 : {
54 3 : currentPart_->push_back(ring);
55 3 : }
56 :
57 13 : void out(std::ostream &ostr, double level) const
58 : {
59 13 : auto pIt = polygons_.find(level);
60 13 : if (pIt == polygons_.end())
61 1 : return;
62 :
63 28 : for (const auto &part : pIt->second)
64 : {
65 16 : ostr << "{ ";
66 35 : for (const auto &ring : part)
67 : {
68 19 : ostr << "{ ";
69 247 : for (const auto &pt : ring)
70 : {
71 228 : ostr << "(" << pt.x << "," << pt.y << ") ";
72 : }
73 19 : ostr << "} ";
74 : }
75 16 : ostr << "} ";
76 : }
77 : }
78 :
79 : #ifdef DEBUG
80 : void toSvg(const std::string &filename)
81 : {
82 : std::ofstream ofs(filename);
83 : ofs << "<?xml version=\"1.0\" encoding=\"UTF-8\" "
84 : "standalone=\"no\"?><svg xmlns=\"http://www.w3.org/2000/svg\" "
85 : "version=\"1.1\">\n";
86 : ofs << "<defs><marker id=\"arrow\" refX=\"0\" refY=\"0\" "
87 : "orient=\"auto\">\n";
88 : ofs << "<path d=\"M 0,0 L-1.5,-1 L-1.5,1 L0,0\" "
89 : "style=\"fill:#000000;\" />\n";
90 : ofs << "</marker></defs>\n";
91 :
92 : const std::string colors[] = {"white", "#bbb", "#888",
93 : "#666", "#333", "black"};
94 :
95 : int level = 0;
96 : for (auto &p : polygons_)
97 : {
98 : for (const auto &part : p.second)
99 : {
100 : ofs << "<path style=\"fill:" << colors[level] << ";\" d=\"";
101 : for (const auto &ring : part)
102 : {
103 : ofs << "M ";
104 : for (const auto &point : ring)
105 : {
106 : ofs << point.x * 10 << "," << point.y * 10 << " ";
107 : }
108 : }
109 : ofs << "\"/>";
110 : }
111 : level++;
112 : }
113 : ofs << "</svg>";
114 : }
115 : #endif
116 :
117 : private:
118 : typedef std::vector<LineString> PolygonPart;
119 : typedef std::vector<PolygonPart> Polygon;
120 : Polygon *currentPolygon_ = nullptr;
121 : PolygonPart *currentPart_ = nullptr;
122 :
123 : public:
124 : std::map<double, Polygon> polygons_;
125 : };
126 :
127 2 : static bool equal_linestrings(const LineString &ls1, const LineString &ls2)
128 : {
129 2 : if (ls1.size() != ls2.size())
130 0 : return false;
131 2 : auto it1 = ls1.begin();
132 2 : auto it2 = ls2.begin();
133 20 : for (; it1 != ls1.end(); it1++, it2++)
134 : {
135 18 : if (!(*it1 == *it2))
136 0 : return false;
137 : }
138 2 : return true;
139 : }
140 : } // namespace marching_squares
141 :
142 : namespace
143 : {
144 : using namespace marching_squares;
145 :
146 : // Common fixture with test data
147 : struct test_ms_polygon : public ::testing::Test
148 : {
149 : };
150 :
151 : // Dummy test
152 4 : TEST_F(test_ms_polygon, dummy)
153 : {
154 : // one pixel
155 2 : std::vector<double> data = {2.0};
156 2 : TestPolygonWriter w;
157 : {
158 2 : PolygonRingAppender<TestPolygonWriter> appender(w);
159 : IntervalLevelRangeIterator levels(
160 1 : 0.0, 10.0, -std::numeric_limits<double>::infinity());
161 : SegmentMerger<PolygonRingAppender<TestPolygonWriter>,
162 : IntervalLevelRangeIterator>
163 2 : writer(appender, levels, /* polygonize */ true);
164 : ContourGenerator<decltype(writer), IntervalLevelRangeIterator> cg(
165 2 : 1, 1, false, NaN, writer, levels);
166 1 : cg.feedLine(&data[0]);
167 : }
168 :
169 : {
170 2 : std::ostringstream ostr;
171 1 : w.out(ostr, 10.0);
172 : // "Polygon #0",
173 2 : EXPECT_EQ(ostr.str(), "{ { (0.5,1) (1,1) (1,0.5) (1,0) (0.5,0) (0,0) "
174 : "(0,0.5) (0,1) (0.5,1) } } ");
175 : }
176 1 : }
177 :
178 4 : TEST_F(test_ms_polygon, four_pixels)
179 : {
180 : // four pixels
181 : // two rings
182 : // 5 10
183 : // 10 5
184 : // levels = 0, 10
185 : //
186 : // legend:
187 : // : contour
188 : // # border (level 0)
189 : // = border (level 10)
190 : //
191 : // NaN NaN NaN
192 : // +------------------+------------------+------------------+
193 : // | | | |
194 : // | (0,0) | (1,0) | (2,0) |
195 : // | 5 5| 7.5 10| 10 |
196 : // | +#########+########+########o+========++ |
197 : // | # | | : || |
198 : // | # | | : || |
199 : // | # | | : || |
200 : // +--------+---------+--------+---------o........o+--------+
201 : // |NaN 5 # 5| 10| 10# NaN|
202 : // | # | | # |
203 : // | # | | # |
204 : // | 7.5++---------+ 7.5 7.5+--------+ |
205 : // | # | | # |
206 : // | # | | # |
207 : // | # | 7.5 | # |
208 : // +-------++.........o--------+---------+--------+---------+
209 : // |NaN 10|| 10: | 5| 5 # NaN|
210 : // | || : | | # |
211 : // | || : | | # |
212 : // | ++=========o########+#########+########+ |
213 : // | 10 10| 7.5 5| 5 |
214 : // | (0,2) | (1,2) | (2,2) |
215 : // | | | |
216 : // +------------------+------------------+------------------+
217 : // NaN NaN NaN NaN
218 :
219 2 : std::vector<double> data = {5.0, 10.0, 10.0, 5.0};
220 2 : TestPolygonWriter w;
221 : {
222 2 : PolygonRingAppender<TestPolygonWriter> appender(w);
223 : IntervalLevelRangeIterator levels(
224 1 : 0.0, 10.0, -std::numeric_limits<double>::infinity());
225 : SegmentMerger<PolygonRingAppender<TestPolygonWriter>,
226 : IntervalLevelRangeIterator>
227 2 : writer(appender, levels, /* polygonize */ true);
228 : ContourGenerator<decltype(writer), IntervalLevelRangeIterator> cg(
229 2 : 2, 2, false, NaN, writer, levels);
230 1 : cg.feedLine(&data[0]);
231 1 : cg.feedLine(&data[2]);
232 : }
233 :
234 : {
235 2 : std::ostringstream ostr;
236 1 : w.out(ostr, 10.0);
237 : // "Polygon #1"
238 2 : EXPECT_EQ(ostr.str(),
239 : "{ { (1.5,2) (2,2) (2,1.5) (2,1) (2,0.5) (1.5,0.5) (1.5,0.5) "
240 : "(1.5,0) (1,0) (0.5,0) (0,0) (0,0.5) (0,1) (0,1.5) (0.5,1.5) "
241 : "(0.5,1.5) (0.5,2) (1,2) (1.5,2) } } ");
242 : }
243 : {
244 2 : std::ostringstream ostr;
245 1 : w.out(ostr, 20.0);
246 : // "Polygon #2"
247 2 : EXPECT_EQ(ostr.str(),
248 : "{ { (2,0.5) (2,0.5) (2,0) (1.5,0) (1.5,0) (1.5,0.5) "
249 : "(1.5,0.5) (2,0.5) } } { { (0.5,1.5) (0.5,1.5) (0,1.5) "
250 : "(0,1.5) (0,2) (0.5,2) (0.5,2) (0.5,1.5) } } ");
251 : }
252 1 : }
253 :
254 4 : TEST_F(test_ms_polygon, four_pixels_2)
255 : {
256 : // four pixels
257 : // 155 155.01
258 : // 154.99 155
259 : // levels = 155
260 :
261 : // NaN NaN NaN
262 : // +------------------+------------------+------------------+
263 : // | | | |
264 : // | (0,0) | (1,0) | (2,0) |
265 : // | 155 | 155.005 | 155.01 |
266 : // | +---------+--------+---------+---------+ |
267 : // | | 155 | 155.01 | |
268 : // | | | | | | |
269 : // | | | 155.005 | | |
270 : // +--------+---------+--------+---------+---------+--------+
271 : // |NaN 155 155 155.01 155.01 NaN|
272 : // | | | | | |
273 : // | 154.995 | | 155.005 |
274 : // | +-------154.995 155.005------+ |
275 : // | | | | | |
276 : // | | | | | |
277 : // | | | | | |
278 : // +--------+---------+--------+---------+---------+--------+
279 : // |NaN 154.99 154.99 154.995 155 155 NaN|
280 : // | | | | | | |
281 : // | | | | | | |
282 : // | +---------+--------+---------+---------+ |
283 : // | 154.99 154.99 154.995 155 155 |
284 : // | (0,2) | (1,2) | (2,2) |
285 : // | | | |
286 : // +------------------+------------------+------------------+
287 : // NaN NaN NaN NaN
288 :
289 2 : std::vector<double> data = {155.0, 155.01, 154.99, 155.0};
290 : {
291 2 : TestPolygonWriter w;
292 : {
293 2 : PolygonRingAppender<TestPolygonWriter> appender(w);
294 1 : const double levels[] = {155.0};
295 : FixedLevelRangeIterator levelGenerator(
296 1 : levels, 1, -std::numeric_limits<double>::infinity(),
297 2 : std::numeric_limits<double>::infinity());
298 : SegmentMerger<PolygonRingAppender<TestPolygonWriter>,
299 : FixedLevelRangeIterator>
300 2 : writer(appender, levelGenerator, /* polygonize */ true);
301 : ContourGenerator<decltype(writer), FixedLevelRangeIterator> cg(
302 2 : 2, 2, false, NaN, writer, levelGenerator);
303 1 : cg.feedLine(&data[0]);
304 1 : cg.feedLine(&data[2]);
305 : }
306 1 : EXPECT_EQ(w.polygons_.size(), 2);
307 : {
308 2 : std::ostringstream ostr;
309 1 : w.out(ostr, 155.0);
310 : // "Polygon #0"
311 2 : EXPECT_EQ(
312 : ostr.str(),
313 : "{ { (1.4999,2) (1.4999,1.5) (0.5,0.5001) (0,0.5001) (0,1) "
314 : "(0,1.5) (0,2) (0.5,2) (1,2) (1.4999,2) } } ");
315 : }
316 : {
317 2 : std::ostringstream ostr;
318 1 : w.out(ostr, Inf);
319 : // "Polygon #1"
320 2 : EXPECT_EQ(
321 : ostr.str(),
322 : "{ { (1.5,2) (2,2) (2,1.5) (2,1) (2,0.5) (2,0) (1.5,0) (1,0) "
323 : "(0.5,0) (0,0) (0,0.5) (0,0.5001) (0.5,0.5001) (1.4999,1.5) "
324 : "(1.4999,2) (1.5,2) } } ");
325 : }
326 : }
327 :
328 : {
329 2 : TestPolygonWriter w;
330 : {
331 2 : PolygonRingAppender<TestPolygonWriter> appender(w);
332 1 : const double levels[] = {155.0};
333 : FixedLevelRangeIterator levelGenerator(
334 1 : levels, 1, -std::numeric_limits<double>::infinity(),
335 2 : std::numeric_limits<double>::infinity());
336 : SegmentMerger<PolygonRingAppender<TestPolygonWriter>,
337 : FixedLevelRangeIterator>
338 2 : writer(appender, levelGenerator, /* polygonize */ true);
339 1 : writer.setSkipLevels({1});
340 : ContourGenerator<decltype(writer), FixedLevelRangeIterator> cg(
341 2 : 2, 2, false, NaN, writer, levelGenerator);
342 1 : cg.feedLine(&data[0]);
343 1 : cg.feedLine(&data[2]);
344 : }
345 : {
346 1 : EXPECT_EQ(w.polygons_.size(), 2);
347 1 : EXPECT_EQ(w.polygons_.find(Inf)->second.size(), 0);
348 : }
349 :
350 : {
351 2 : std::ostringstream ostr;
352 1 : w.out(ostr, 155.0);
353 : // "Polygon #0"
354 2 : EXPECT_EQ(
355 : ostr.str(),
356 : "{ { (1.4999,2) (1.4999,1.5) (0.5,0.5001) (0,0.5001) (0,1) "
357 : "(0,1.5) (0,2) (0.5,2) (1,2) (1.4999,2) } } ");
358 : }
359 : }
360 1 : }
361 :
362 4 : TEST_F(test_ms_polygon, nine_pixels)
363 : {
364 : // nine pixels
365 : // two nested rings
366 : // levels = 1, 11, 21
367 : // pixels
368 : // +-----+-----+-----+-----+-----+
369 : // | | | | | |
370 : // | NaN | NaN | NaN | NaN | NaN |
371 : // | | | | | |
372 : // +-----+-----+-----+-----+-----+
373 : // | | | | | |
374 : // | NaN | 0 | 4 | 0 | NaN |
375 : // | | | | | |
376 : // +-----+-----+-----+-----+-----+
377 : // | | | | | |
378 : // | NaN | 4 | 12 | 4 | NaN |
379 : // | | | | | |
380 : // +-----+-----+-----+-----+-----+
381 : // | | | | | |
382 : // | NaN | 0 | 4 | 0 | NaN |
383 : // | | | | | |
384 : // +-----+-----+-----+-----+-----+
385 : // | | | | | |
386 : // | NaN | NaN | NaN | NaN | NaN |
387 : // | | | | | |
388 : // +-----+-----+-----+-----+-----+
389 : //
390 : // NaN NaN NaN NaN NaN
391 : // +------------------+------------------+------------------+------------------+
392 : // | | | | | | (0,0)
393 : // | (1,0) | (2,0) | | | 0
394 : // 0| 2 4| 2 0| 0 | |
395 : // +---------+---o----+---------+---------+----o---+---------+ |
396 : // | | | : | | | : | | |
397 : // | | | : | | | : | | |
398 : // | | | : | | | : | | |
399 : // +--------+---------+---o----+---------+---------+----o---+---------+--------+
400 : // NaN |NaN 0| 0| _/ 2 4| 2 \_0| |0 | |
401 : // o.........o/ | \o.........o |
402 : // | | | | | | |
403 : // | 2+---------+ 2 | 2+---------+2
404 : // | | | | | | |
405 : // | | | | _o_ | |
406 : // | | | | / | \ | |
407 : // |
408 : // +--------+---------+---------------o--+--o---------------+---------+--------+
409 : // NaN |NaN 4| 4| \12 / 4| |4 | |
410 : // | | -o- | | |
411 : // | | | | | | |
412 : // | 2+---------+ 2 | 2+---------+2
413 : // | | | | | | |
414 : // | | o.........o_ | _o.........o
415 : // | | | | \_ 2 | 2 _/ | |
416 : // |
417 : // +--------+---------+---o----+---------+--------+----o/---+---------+--------+
418 : // NaN |NaN 0| 0| : | 4| | : 0| |0 | |
419 : // | | : | | | : | | |
420 : // | | | : | | | : | | |
421 : // | +---------+---o----+---------+--------+----o----+---------+ |
422 : // | 0 0| 2 4| 2 0| 0 |
423 : // | (0,3) | (1,3) | (2,3) | | | | | | |
424 : // +------------------+------------------+------------------+------------------+
425 : // NaN NaN NaN NaN NaN
426 2 : std::vector<double> data = {0.0, 4.0, 0.0, 4.0, 12.0, 4.0, 0.0, 4.0, 0.0};
427 2 : TestPolygonWriter w;
428 : {
429 2 : PolygonRingAppender<TestPolygonWriter> appender(w);
430 : IntervalLevelRangeIterator levels(
431 1 : 1.0, 10.0, -std::numeric_limits<double>::infinity());
432 : SegmentMerger<PolygonRingAppender<TestPolygonWriter>,
433 : IntervalLevelRangeIterator>
434 2 : writer(appender, levels, /* polygonize */ true);
435 : ContourGenerator<decltype(writer), IntervalLevelRangeIterator> cg(
436 2 : 3, 3, false, NaN, writer, levels);
437 1 : cg.feedLine(&data[0]);
438 1 : cg.feedLine(&data[3]);
439 1 : cg.feedLine(&data[6]);
440 : }
441 :
442 : {
443 2 : std::ostringstream ostr;
444 1 : w.out(ostr, 1.0);
445 : // "Polygon #0"
446 2 : EXPECT_EQ(ostr.str(),
447 : "{ { (0.5,0.75) (0.75,0.5) (0.75,0) (0.5,0) (0,0) (0,0.5) "
448 : "(0,0.75) (0.5,0.75) } } { { (2.5,0.75) (3,0.75) (3,0.5) "
449 : "(3,0) (2.5,0) (2.25,0) (2.25,0.5) (2.5,0.75) } } { { "
450 : "(0.75,3) (0.75,2.5) (0.5,2.25) (0,2.25) (0,2.5) (0,3) "
451 : "(0.5,3) (0.75,3) } } { { (2.5,3) (3,3) (3,2.5) (3,2.25) "
452 : "(2.5,2.25) (2.25,2.5) (2.25,3) (2.5,3) } } ");
453 : }
454 : {
455 2 : std::ostringstream ostr;
456 1 : w.out(ostr, 11.0);
457 : // "Polygon #1"
458 2 : EXPECT_EQ(ostr.str(),
459 : "{ { (2.25,2.5) (2.5,2.25) (3,2.25) (3,2) (3,1.5) (3,1) "
460 : "(3,0.75) (2.5,0.75) (2.25,0.5) (2.25,0) (2,0) (1.5,0) (1,0) "
461 : "(0.75,0) (0.75,0.5) (0.5,0.75) (0,0.75) (0,1) (0,1.5) (0,2) "
462 : "(0,2.25) (0.5,2.25) (0.75,2.5) (0.75,3) (1,3) (1.5,3) (2,3) "
463 : "(2.25,3) (2.25,2.5) } { (1.625,1.5) (1.5,1.625) (1.375,1.5) "
464 : "(1.5,1.375) (1.625,1.5) } } ");
465 : }
466 : {
467 2 : std::ostringstream ostr;
468 1 : w.out(ostr, 21.0);
469 : // "Polygon #2"
470 2 : EXPECT_EQ(ostr.str(), "{ { (1.625,1.5) (1.5,1.625) (1.375,1.5) "
471 : "(1.5,1.375) (1.625,1.5) } } ");
472 : }
473 1 : }
474 :
475 4 : TEST_F(test_ms_polygon, three_nested_rings)
476 : {
477 : // Three nested rings
478 : std::vector<double> data = {2, 2, 2, 2, 2, 2, 4, 4, 4, 2, 2, 4, 6,
479 2 : 4, 2, 2, 4, 4, 4, 2, 2, 2, 2, 2, 2};
480 2 : TestPolygonWriter w;
481 : {
482 2 : PolygonRingAppender<TestPolygonWriter> appender(w);
483 : IntervalLevelRangeIterator levels(
484 1 : 1.0, 2.0, -std::numeric_limits<double>::infinity());
485 : SegmentMerger<PolygonRingAppender<TestPolygonWriter>,
486 : IntervalLevelRangeIterator>
487 2 : writer(appender, levels, /* polygonize */ true);
488 : ContourGenerator<decltype(writer), IntervalLevelRangeIterator> cg(
489 2 : 5, 5, false, NaN, writer, levels);
490 6 : for (int i = 0; i < 5; i++)
491 : {
492 5 : cg.feedLine(&data[5 * i]);
493 : }
494 : }
495 : {
496 2 : std::ostringstream ostr;
497 1 : w.out(ostr, 1.0);
498 : // "Polygon #0"
499 2 : EXPECT_EQ(ostr.str(), "");
500 : }
501 : {
502 2 : std::ostringstream ostr;
503 1 : w.out(ostr, 3.0);
504 : // "Polygon #1"
505 2 : EXPECT_EQ(
506 : ostr.str(),
507 : "{ { (4.5,5) (5,5) (5,4.5) (5,4) (5,3.5) (5,3) (5,2.5) (5,2) "
508 : "(5,1.5) (5,1) (5,0.5) (5,0) (4.5,0) (4,0) (3.5,0) (3,0) (2.5,0) "
509 : "(2,0) (1.5,0) (1,0) (0.5,0) (0,0) (0,0.5) (0,1) (0,1.5) (0,2) "
510 : "(0,2.5) (0,3) (0,3.5) (0,4) (0,4.5) (0,5) (0.5,5) (1,5) (1.5,5) "
511 : "(2,5) (2.5,5) (3,5) (3.5,5) (4,5) (4.5,5) } { (4,3.5) (3.5,4) "
512 : "(2.5,4) (1.5,4) (1,3.5) (1,2.5) (1,1.5) (1.5,1) (2.5,1) (3.5,1) "
513 : "(4,1.5) (4,2.5) (4,3.5) } } ");
514 : }
515 : {
516 2 : std::ostringstream ostr;
517 1 : w.out(ostr, 5.0);
518 : // "Polygon #2"
519 2 : EXPECT_EQ(ostr.str(),
520 : "{ { (4,3.5) (3.5,4) (2.5,4) (1.5,4) (1,3.5) (1,2.5) (1,1.5) "
521 : "(1.5,1) (2.5,1) (3.5,1) (4,1.5) (4,2.5) (4,3.5) } { (3,2.5) "
522 : "(2.5,3) (2,2.5) (2.5,2) (3,2.5) } } ");
523 : }
524 : {
525 2 : std::ostringstream ostr;
526 1 : w.out(ostr, 7.0);
527 : // "Polygon #3"
528 2 : EXPECT_EQ(ostr.str(),
529 : "{ { (3,2.5) (2.5,3) (2,2.5) (2.5,2) (3,2.5) } } ");
530 : }
531 :
532 : // "Inner ring of polygon #1 = exterioring ring of polygon #2"
533 1 : EXPECT_TRUE(
534 : equal_linestrings(w.polygons_[3.0][0][1], w.polygons_[5.0][0][0]));
535 : // "Inner ring of polygon #2 = exterioring ring of polygon #3"
536 1 : EXPECT_TRUE(
537 : equal_linestrings(w.polygons_[5.0][0][1], w.polygons_[7.0][0][0]));
538 1 : }
539 : } // namespace
|
