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 : PolygonRingAppender<TestPolygonWriter> appender(w, -100, -100, 100,
159 2 : 100);
160 : IntervalLevelRangeIterator levels(
161 1 : 0.0, 10.0, -std::numeric_limits<double>::infinity());
162 : SegmentMerger<PolygonRingAppender<TestPolygonWriter>,
163 : IntervalLevelRangeIterator>
164 2 : writer(appender, levels, /* polygonize */ true);
165 : ContourGenerator<decltype(writer), IntervalLevelRangeIterator> cg(
166 2 : 1, 1, false, NaN, writer, levels);
167 1 : cg.feedLine(&data[0]);
168 : }
169 :
170 : {
171 2 : std::ostringstream ostr;
172 1 : w.out(ostr, 10.0);
173 : // "Polygon #0",
174 2 : EXPECT_EQ(ostr.str(), "{ { (0.5,1) (1,1) (1,0.5) (1,0) (0.5,0) (0,0) "
175 : "(0,0.5) (0,1) (0.5,1) } } ");
176 : }
177 1 : }
178 :
179 4 : TEST_F(test_ms_polygon, four_pixels)
180 : {
181 : // four pixels
182 : // two rings
183 : // 5 10
184 : // 10 5
185 : // levels = 0, 10
186 : //
187 : // legend:
188 : // : contour
189 : // # border (level 0)
190 : // = border (level 10)
191 : //
192 : // NaN NaN NaN
193 : // +------------------+------------------+------------------+
194 : // | | | |
195 : // | (0,0) | (1,0) | (2,0) |
196 : // | 5 5| 7.5 10| 10 |
197 : // | +#########+########+########o+========++ |
198 : // | # | | : || |
199 : // | # | | : || |
200 : // | # | | : || |
201 : // +--------+---------+--------+---------o........o+--------+
202 : // |NaN 5 # 5| 10| 10# NaN|
203 : // | # | | # |
204 : // | # | | # |
205 : // | 7.5++---------+ 7.5 7.5+--------+ |
206 : // | # | | # |
207 : // | # | | # |
208 : // | # | 7.5 | # |
209 : // +-------++.........o--------+---------+--------+---------+
210 : // |NaN 10|| 10: | 5| 5 # NaN|
211 : // | || : | | # |
212 : // | || : | | # |
213 : // | ++=========o########+#########+########+ |
214 : // | 10 10| 7.5 5| 5 |
215 : // | (0,2) | (1,2) | (2,2) |
216 : // | | | |
217 : // +------------------+------------------+------------------+
218 : // NaN NaN NaN NaN
219 :
220 2 : std::vector<double> data = {5.0, 10.0, 10.0, 5.0};
221 2 : TestPolygonWriter w;
222 : {
223 : PolygonRingAppender<TestPolygonWriter> appender(w, -100, -100, 100,
224 2 : 100);
225 : IntervalLevelRangeIterator levels(
226 1 : 0.0, 10.0, -std::numeric_limits<double>::infinity());
227 : SegmentMerger<PolygonRingAppender<TestPolygonWriter>,
228 : IntervalLevelRangeIterator>
229 2 : writer(appender, levels, /* polygonize */ true);
230 : ContourGenerator<decltype(writer), IntervalLevelRangeIterator> cg(
231 2 : 2, 2, false, NaN, writer, levels);
232 1 : cg.feedLine(&data[0]);
233 1 : cg.feedLine(&data[2]);
234 : }
235 :
236 : {
237 2 : std::ostringstream ostr;
238 1 : w.out(ostr, 10.0);
239 : // "Polygon #1"
240 2 : EXPECT_EQ(ostr.str(),
241 : "{ { (1.5,2) (2,2) (2,1.5) (2,1) (2,0.5) (1.5,0.5) (1.5,0.5) "
242 : "(1.5,0) (1,0) (0.5,0) (0,0) (0,0.5) (0,1) (0,1.5) (0.5,1.5) "
243 : "(0.5,1.5) (0.5,2) (1,2) (1.5,2) } } ");
244 : }
245 : {
246 2 : std::ostringstream ostr;
247 1 : w.out(ostr, 20.0);
248 : // "Polygon #2"
249 2 : EXPECT_EQ(ostr.str(),
250 : "{ { (2,0.5) (2,0.5) (2,0) (1.5,0) (1.5,0) (1.5,0.5) "
251 : "(1.5,0.5) (2,0.5) } } { { (0.5,1.5) (0.5,1.5) (0,1.5) "
252 : "(0,1.5) (0,2) (0.5,2) (0.5,2) (0.5,1.5) } } ");
253 : }
254 1 : }
255 :
256 4 : TEST_F(test_ms_polygon, four_pixels_2)
257 : {
258 : // four pixels
259 : // 155 155.01
260 : // 154.99 155
261 : // levels = 155
262 :
263 : // NaN NaN NaN
264 : // +------------------+------------------+------------------+
265 : // | | | |
266 : // | (0,0) | (1,0) | (2,0) |
267 : // | 155 | 155.005 | 155.01 |
268 : // | +---------+--------+---------+---------+ |
269 : // | | 155 | 155.01 | |
270 : // | | | | | | |
271 : // | | | 155.005 | | |
272 : // +--------+---------+--------+---------+---------+--------+
273 : // |NaN 155 155 155.01 155.01 NaN|
274 : // | | | | | |
275 : // | 154.995 | | 155.005 |
276 : // | +-------154.995 155.005------+ |
277 : // | | | | | |
278 : // | | | | | |
279 : // | | | | | |
280 : // +--------+---------+--------+---------+---------+--------+
281 : // |NaN 154.99 154.99 154.995 155 155 NaN|
282 : // | | | | | | |
283 : // | | | | | | |
284 : // | +---------+--------+---------+---------+ |
285 : // | 154.99 154.99 154.995 155 155 |
286 : // | (0,2) | (1,2) | (2,2) |
287 : // | | | |
288 : // +------------------+------------------+------------------+
289 : // NaN NaN NaN NaN
290 :
291 1 : std::vector<double> data = {155.0, 155.01, 154.99, 155.0};
292 : {
293 2 : TestPolygonWriter w;
294 : {
295 : PolygonRingAppender<TestPolygonWriter> appender(w, -100, -100, 100,
296 2 : 100);
297 1 : const double levels[] = {155.0};
298 : FixedLevelRangeIterator levelGenerator(
299 1 : levels, 1, -std::numeric_limits<double>::infinity(),
300 2 : std::numeric_limits<double>::infinity());
301 : SegmentMerger<PolygonRingAppender<TestPolygonWriter>,
302 : FixedLevelRangeIterator>
303 2 : writer(appender, levelGenerator, /* polygonize */ true);
304 : ContourGenerator<decltype(writer), FixedLevelRangeIterator> cg(
305 2 : 2, 2, false, NaN, writer, levelGenerator);
306 1 : cg.feedLine(&data[0]);
307 1 : cg.feedLine(&data[2]);
308 : }
309 1 : EXPECT_EQ(w.polygons_.size(), 2U);
310 : {
311 2 : std::ostringstream ostr;
312 1 : w.out(ostr, 155.0);
313 : // "Polygon #0"
314 2 : EXPECT_EQ(
315 : ostr.str(),
316 : "{ { (1.4999,2) (1.4999,1.5) (0.5,0.5001) (0,0.5001) (0,1) "
317 : "(0,1.5) (0,2) (0.5,2) (1,2) (1.4999,2) } } ");
318 : }
319 : {
320 2 : std::ostringstream ostr;
321 1 : w.out(ostr, Inf);
322 : // "Polygon #1"
323 2 : EXPECT_EQ(
324 : ostr.str(),
325 : "{ { (1.5,2) (2,2) (2,1.5) (2,1) (2,0.5) (2,0) (1.5,0) (1,0) "
326 : "(0.5,0) (0,0) (0,0.5) (0,0.5001) (0.5,0.5001) (1.4999,1.5) "
327 : "(1.4999,2) (1.5,2) } } ");
328 : }
329 : }
330 :
331 : {
332 1 : TestPolygonWriter w;
333 : {
334 : PolygonRingAppender<TestPolygonWriter> appender(w, -100, -100, 100,
335 2 : 100);
336 1 : const double levels[] = {155.0};
337 : FixedLevelRangeIterator levelGenerator(
338 1 : levels, 1, -std::numeric_limits<double>::infinity(),
339 2 : std::numeric_limits<double>::infinity());
340 : SegmentMerger<PolygonRingAppender<TestPolygonWriter>,
341 : FixedLevelRangeIterator>
342 2 : writer(appender, levelGenerator, /* polygonize */ true);
343 1 : writer.setSkipLevels({1});
344 : ContourGenerator<decltype(writer), FixedLevelRangeIterator> cg(
345 2 : 2, 2, false, NaN, writer, levelGenerator);
346 1 : cg.feedLine(&data[0]);
347 1 : cg.feedLine(&data[2]);
348 : }
349 : {
350 1 : EXPECT_EQ(w.polygons_.size(), 2U);
351 1 : auto iter = w.polygons_.find(Inf);
352 1 : ASSERT_TRUE(iter != w.polygons_.end());
353 1 : EXPECT_TRUE(iter->second.empty());
354 : }
355 :
356 : {
357 2 : std::ostringstream ostr;
358 1 : w.out(ostr, 155.0);
359 : // "Polygon #0"
360 2 : EXPECT_EQ(
361 : ostr.str(),
362 : "{ { (1.4999,2) (1.4999,1.5) (0.5,0.5001) (0,0.5001) (0,1) "
363 : "(0,1.5) (0,2) (0.5,2) (1,2) (1.4999,2) } } ");
364 : }
365 : }
366 : }
367 :
368 4 : TEST_F(test_ms_polygon, nine_pixels)
369 : {
370 : // nine pixels
371 : // two nested rings
372 : // levels = 1, 11, 21
373 : // pixels
374 : // +-----+-----+-----+-----+-----+
375 : // | | | | | |
376 : // | NaN | NaN | NaN | NaN | NaN |
377 : // | | | | | |
378 : // +-----+-----+-----+-----+-----+
379 : // | | | | | |
380 : // | NaN | 0 | 4 | 0 | NaN |
381 : // | | | | | |
382 : // +-----+-----+-----+-----+-----+
383 : // | | | | | |
384 : // | NaN | 4 | 12 | 4 | NaN |
385 : // | | | | | |
386 : // +-----+-----+-----+-----+-----+
387 : // | | | | | |
388 : // | NaN | 0 | 4 | 0 | NaN |
389 : // | | | | | |
390 : // +-----+-----+-----+-----+-----+
391 : // | | | | | |
392 : // | NaN | NaN | NaN | NaN | NaN |
393 : // | | | | | |
394 : // +-----+-----+-----+-----+-----+
395 : //
396 : // NaN NaN NaN NaN NaN
397 : // +------------------+------------------+------------------+------------------+
398 : // | | | | | | (0,0)
399 : // | (1,0) | (2,0) | | | 0
400 : // 0| 2 4| 2 0| 0 | |
401 : // +---------+---o----+---------+---------+----o---+---------+ |
402 : // | | | : | | | : | | |
403 : // | | | : | | | : | | |
404 : // | | | : | | | : | | |
405 : // +--------+---------+---o----+---------+---------+----o---+---------+--------+
406 : // NaN |NaN 0| 0| _/ 2 4| 2 \_0| |0 | |
407 : // o.........o/ | \o.........o |
408 : // | | | | | | |
409 : // | 2+---------+ 2 | 2+---------+2
410 : // | | | | | | |
411 : // | | | | _o_ | |
412 : // | | | | / | \ | |
413 : // |
414 : // +--------+---------+---------------o--+--o---------------+---------+--------+
415 : // NaN |NaN 4| 4| \12 / 4| |4 | |
416 : // | | -o- | | |
417 : // | | | | | | |
418 : // | 2+---------+ 2 | 2+---------+2
419 : // | | | | | | |
420 : // | | o.........o_ | _o.........o
421 : // | | | | \_ 2 | 2 _/ | |
422 : // |
423 : // +--------+---------+---o----+---------+--------+----o/---+---------+--------+
424 : // NaN |NaN 0| 0| : | 4| | : 0| |0 | |
425 : // | | : | | | : | | |
426 : // | | | : | | | : | | |
427 : // | +---------+---o----+---------+--------+----o----+---------+ |
428 : // | 0 0| 2 4| 2 0| 0 |
429 : // | (0,3) | (1,3) | (2,3) | | | | | | |
430 : // +------------------+------------------+------------------+------------------+
431 : // NaN NaN NaN NaN NaN
432 2 : std::vector<double> data = {0.0, 4.0, 0.0, 4.0, 12.0, 4.0, 0.0, 4.0, 0.0};
433 2 : TestPolygonWriter w;
434 : {
435 : PolygonRingAppender<TestPolygonWriter> appender(w, -100, -100, 100,
436 2 : 100);
437 : IntervalLevelRangeIterator levels(
438 1 : 1.0, 10.0, -std::numeric_limits<double>::infinity());
439 : SegmentMerger<PolygonRingAppender<TestPolygonWriter>,
440 : IntervalLevelRangeIterator>
441 2 : writer(appender, levels, /* polygonize */ true);
442 : ContourGenerator<decltype(writer), IntervalLevelRangeIterator> cg(
443 2 : 3, 3, false, NaN, writer, levels);
444 1 : cg.feedLine(&data[0]);
445 1 : cg.feedLine(&data[3]);
446 1 : cg.feedLine(&data[6]);
447 : }
448 :
449 : {
450 2 : std::ostringstream ostr;
451 1 : w.out(ostr, 1.0);
452 : // "Polygon #0"
453 2 : EXPECT_EQ(ostr.str(),
454 : "{ { (0.5,0.75) (0.75,0.5) (0.75,0) (0.5,0) (0,0) (0,0.5) "
455 : "(0,0.75) (0.5,0.75) } } { { (2.5,0.75) (3,0.75) (3,0.5) "
456 : "(3,0) (2.5,0) (2.25,0) (2.25,0.5) (2.5,0.75) } } { { "
457 : "(0.75,3) (0.75,2.5) (0.5,2.25) (0,2.25) (0,2.5) (0,3) "
458 : "(0.5,3) (0.75,3) } } { { (2.5,3) (3,3) (3,2.5) (3,2.25) "
459 : "(2.5,2.25) (2.25,2.5) (2.25,3) (2.5,3) } } ");
460 : }
461 : {
462 2 : std::ostringstream ostr;
463 1 : w.out(ostr, 11.0);
464 : // "Polygon #1"
465 2 : EXPECT_EQ(ostr.str(),
466 : "{ { (2.25,2.5) (2.5,2.25) (3,2.25) (3,2) (3,1.5) (3,1) "
467 : "(3,0.75) (2.5,0.75) (2.25,0.5) (2.25,0) (2,0) (1.5,0) (1,0) "
468 : "(0.75,0) (0.75,0.5) (0.5,0.75) (0,0.75) (0,1) (0,1.5) (0,2) "
469 : "(0,2.25) (0.5,2.25) (0.75,2.5) (0.75,3) (1,3) (1.5,3) (2,3) "
470 : "(2.25,3) (2.25,2.5) } { (1.625,1.5) (1.5,1.625) (1.375,1.5) "
471 : "(1.5,1.375) (1.625,1.5) } } ");
472 : }
473 : {
474 2 : std::ostringstream ostr;
475 1 : w.out(ostr, 21.0);
476 : // "Polygon #2"
477 2 : EXPECT_EQ(ostr.str(), "{ { (1.625,1.5) (1.5,1.625) (1.375,1.5) "
478 : "(1.5,1.375) (1.625,1.5) } } ");
479 : }
480 1 : }
481 :
482 4 : TEST_F(test_ms_polygon, three_nested_rings)
483 : {
484 : // Three nested rings
485 : std::vector<double> data = {2, 2, 2, 2, 2, 2, 4, 4, 4, 2, 2, 4, 6,
486 2 : 4, 2, 2, 4, 4, 4, 2, 2, 2, 2, 2, 2};
487 2 : TestPolygonWriter w;
488 : {
489 : PolygonRingAppender<TestPolygonWriter> appender(w, -100, -100, 100,
490 2 : 100);
491 : IntervalLevelRangeIterator levels(
492 1 : 1.0, 2.0, -std::numeric_limits<double>::infinity());
493 : SegmentMerger<PolygonRingAppender<TestPolygonWriter>,
494 : IntervalLevelRangeIterator>
495 2 : writer(appender, levels, /* polygonize */ true);
496 : ContourGenerator<decltype(writer), IntervalLevelRangeIterator> cg(
497 2 : 5, 5, false, NaN, writer, levels);
498 6 : for (int i = 0; i < 5; i++)
499 : {
500 5 : cg.feedLine(&data[5 * i]);
501 : }
502 : }
503 : {
504 2 : std::ostringstream ostr;
505 1 : w.out(ostr, 1.0);
506 : // "Polygon #0"
507 2 : EXPECT_EQ(ostr.str(), "");
508 : }
509 : {
510 2 : std::ostringstream ostr;
511 1 : w.out(ostr, 3.0);
512 : // "Polygon #1"
513 2 : EXPECT_EQ(
514 : ostr.str(),
515 : "{ { (4.5,5) (5,5) (5,4.5) (5,4) (5,3.5) (5,3) (5,2.5) (5,2) "
516 : "(5,1.5) (5,1) (5,0.5) (5,0) (4.5,0) (4,0) (3.5,0) (3,0) (2.5,0) "
517 : "(2,0) (1.5,0) (1,0) (0.5,0) (0,0) (0,0.5) (0,1) (0,1.5) (0,2) "
518 : "(0,2.5) (0,3) (0,3.5) (0,4) (0,4.5) (0,5) (0.5,5) (1,5) (1.5,5) "
519 : "(2,5) (2.5,5) (3,5) (3.5,5) (4,5) (4.5,5) } { (4,3.5) (3.5,4) "
520 : "(2.5,4) (1.5,4) (1,3.5) (1,2.5) (1,1.5) (1.5,1) (2.5,1) (3.5,1) "
521 : "(4,1.5) (4,2.5) (4,3.5) } } ");
522 : }
523 : {
524 2 : std::ostringstream ostr;
525 1 : w.out(ostr, 5.0);
526 : // "Polygon #2"
527 2 : EXPECT_EQ(ostr.str(),
528 : "{ { (4,3.5) (3.5,4) (2.5,4) (1.5,4) (1,3.5) (1,2.5) (1,1.5) "
529 : "(1.5,1) (2.5,1) (3.5,1) (4,1.5) (4,2.5) (4,3.5) } { (3,2.5) "
530 : "(2.5,3) (2,2.5) (2.5,2) (3,2.5) } } ");
531 : }
532 : {
533 2 : std::ostringstream ostr;
534 1 : w.out(ostr, 7.0);
535 : // "Polygon #3"
536 2 : EXPECT_EQ(ostr.str(),
537 : "{ { (3,2.5) (2.5,3) (2,2.5) (2.5,2) (3,2.5) } } ");
538 : }
539 :
540 : // "Inner ring of polygon #1 = exterioring ring of polygon #2"
541 1 : EXPECT_TRUE(
542 : equal_linestrings(w.polygons_[3.0][0][1], w.polygons_[5.0][0][0]));
543 : // "Inner ring of polygon #2 = exterioring ring of polygon #3"
544 1 : EXPECT_TRUE(
545 : equal_linestrings(w.polygons_[5.0][0][1], w.polygons_[7.0][0][0]));
546 1 : }
547 : } // namespace
|
