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