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