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/segment_merger.h"
36 : #include "marching_squares/contour_generator.h"
37 :
38 : #include "gtest_include.h"
39 :
40 : namespace marching_squares
41 : {
42 : class TestRingAppender
43 : {
44 : public:
45 : struct Point
46 : {
47 172 : Point(double xx, double yy) : x(xx), y(yy)
48 : {
49 172 : }
50 :
51 : double x;
52 : double y;
53 :
54 : bool operator<(const Point &b) const
55 : {
56 : return x == b.x ? y < b.y : x < b.x;
57 : }
58 :
59 169 : bool operator==(const Point &b) const
60 : {
61 169 : return std::fabs(x - b.x) < 0.001 && std::fabs(y - b.y) < 0.001;
62 : }
63 :
64 169 : bool operator!=(const Point &b) const
65 : {
66 169 : return !(*this == b);
67 : }
68 : };
69 :
70 8 : void addLine(double level, LineString &ls, bool /* closed */)
71 : {
72 8 : auto &v = points_[level];
73 16 : std::vector<Point> ring;
74 98 : for (const auto &pt : ls)
75 : {
76 90 : ring.push_back(Point(pt.x, pt.y));
77 : }
78 8 : v.push_back(ring);
79 8 : }
80 :
81 8 : bool hasRing(double level, const std::vector<Point> &other) const
82 : {
83 8 : auto it = points_.find(level);
84 8 : if (it == points_.end())
85 : {
86 0 : return false;
87 : }
88 :
89 8 : const auto &rings = it->second;
90 9 : for (const auto &ring : rings)
91 : {
92 9 : if (ringEquals_(ring, other))
93 : {
94 8 : return true;
95 : }
96 : else
97 : {
98 : // test also the reverse ring
99 5 : auto rev = other;
100 5 : std::reverse(rev.begin(), rev.end());
101 5 : if (ringEquals_(ring, rev))
102 : {
103 4 : return true;
104 : }
105 : }
106 : }
107 0 : return false;
108 : }
109 :
110 : void out(std::ostream &o, double level)
111 : {
112 : for (const auto &p : points_[level])
113 : {
114 : out_(o, p);
115 : }
116 : }
117 :
118 : private:
119 : // level -> vector of rings
120 : std::map<double, std::vector<std::vector<Point>>> points_;
121 :
122 14 : bool ringEquals_(const std::vector<Point> &aRing,
123 : const std::vector<Point> &bRing) const
124 : {
125 14 : if (aRing.size() - 1 != bRing.size())
126 : {
127 0 : return false;
128 : }
129 :
130 : // rings do not really have a "first" point, but since
131 : // we represent them with a vector, we need to find a common "first"
132 : // point
133 14 : Point pfirst = aRing[0];
134 14 : size_t offset = 0;
135 73 : while (offset < bRing.size() && pfirst != bRing[offset])
136 59 : offset++;
137 14 : if (offset >= bRing.size())
138 : {
139 : // can't find a common point
140 2 : return false;
141 : }
142 : // now compare each point of the two rings
143 106 : for (size_t i = 0; i < aRing.size(); i++)
144 : {
145 98 : const Point &p2 = bRing[(i + offset) % bRing.size()];
146 98 : if (aRing[i] != p2)
147 : {
148 4 : return false;
149 : }
150 : }
151 8 : return true;
152 : }
153 :
154 : void out_(std::ostream &o, const std::vector<Point> &points) const
155 : {
156 : o << "{ ";
157 : for (const auto &pt : points)
158 : {
159 : o << "{" << pt.x << "," << pt.y << "}, ";
160 : }
161 : o << "}, ";
162 : }
163 : };
164 : } // namespace marching_squares
165 :
166 : namespace
167 : {
168 : using namespace marching_squares;
169 :
170 : // Common fixture with test data
171 : struct test_ms_contour : public ::testing::Test
172 : {
173 : };
174 :
175 : // Dummy test
176 4 : TEST_F(test_ms_contour, dummy)
177 : {
178 : // one pixel
179 2 : std::vector<double> data = {2.0};
180 2 : TestRingAppender w;
181 : {
182 1 : IntervalLevelRangeIterator levels(0.0, 10.0);
183 : SegmentMerger<TestRingAppender, IntervalLevelRangeIterator> writer(
184 2 : w, levels, /* polygonize */ true);
185 : ContourGenerator<decltype(writer), IntervalLevelRangeIterator> cg(
186 2 : 1, 1, /* hasNoData */ false, NaN, writer, levels);
187 1 : cg.feedLine(&data[0]);
188 :
189 : // "Polygon ring"
190 1 : EXPECT_TRUE(w.hasRing(10.0, {{0.0, 0.0},
191 : {0.5, 0.0},
192 : {1.0, 0.0},
193 : {1.0, 0.5},
194 : {1.0, 1.0},
195 : {0.5, 1.0},
196 : {0.0, 1.0},
197 : {0.0, 0.5}}));
198 : }
199 1 : }
200 :
201 4 : TEST_F(test_ms_contour, two_pixels)
202 : {
203 : // two pixels
204 : // 10 7
205 : // levels = 8
206 2 : std::vector<double> data = {10.0, 7.0};
207 2 : TestRingAppender w;
208 :
209 : {
210 1 : IntervalLevelRangeIterator levels(8.0, 10.0);
211 : SegmentMerger<TestRingAppender, IntervalLevelRangeIterator> writer(
212 2 : w, levels, /* polygonize */ true);
213 : ContourGenerator<decltype(writer), IntervalLevelRangeIterator> cg(
214 2 : 2, 1, /* hasNoData */ false, NaN, writer, levels);
215 1 : cg.feedLine(&data[0]);
216 :
217 : // "Polygon #0"
218 1 : EXPECT_TRUE(w.hasRing(8.0, {{1.166, 0.0},
219 : {1.5, 0.0},
220 : {2.0, 0.0},
221 : {2.0, 0.5},
222 : {2.0, 1.0},
223 : {1.5, 1.0},
224 : {1.166, 1.0},
225 : {1.166, 0.5}}));
226 : // "Polygon #1"
227 1 : EXPECT_TRUE(w.hasRing(18.0, {{1.166, 0.0},
228 : {1.0, 0.0},
229 : {0.5, 0.0},
230 : {0.0, 0.0},
231 : {0.0, 0.5},
232 : {0.0, 1.0},
233 : {0.5, 1.0},
234 : {1.0, 1.0},
235 : {1.166, 1.0},
236 : {1.166, 0.5}}));
237 : }
238 1 : }
239 :
240 4 : TEST_F(test_ms_contour, four_pixels)
241 : {
242 : // four pixels
243 : // 10 7
244 : // 4 5
245 : // levels = 8
246 : // pixels
247 : // +-----+-----+-----+-----+
248 : // | | | | |
249 : // | NaN | NaN | NaN | NaN |
250 : // | | | | |
251 : // +-----+-----+-----+-----+
252 : // | | | | |
253 : // | NaN | 10 | 7 | NaN |
254 : // | | | | |
255 : // +-----+-----+-----+-----+
256 : // | | | | |
257 : // | NaN | 4 | 5 | NaN |
258 : // | | | | |
259 : // +-----+-----+-----+-----+
260 : // | | | | |
261 : // | NaN | NaN | NaN | NaN |
262 : // | | | | |
263 : // +-----+-----+-----+-----+
264 : //
265 : // squares
266 : // +-----+-----+-----+-----+
267 : // |NaN | NaN | NaN | NaN |
268 : // | +.....+.....+.....+ |
269 : // | : | : | : | : |
270 : // +--:--+--:--+--:--+--:--+
271 : // | : |10: | 7: |NaN |
272 : // NaN+.....+.....+.....+ |
273 : // | : | : | : | : |
274 : // +--:--+--:--+--:--+--:--+
275 : // | : | 4: | 5: |NaN |
276 : // NaN+.....+.....+.....+ |
277 : // | : | : | : | : |
278 : // +--:--+--:--+--:--+--:--+
279 : // | : | : | : | : |
280 : // | +.....+.....+.....+ |
281 : // | NaN | NaN | NaN | NaN |
282 : // +-----+-----+-----+-----+
283 : //
284 : // subsquares
285 : // legend:
286 : // : contour
287 : // = border (level 8)
288 : // # border (level 18)
289 : //
290 : // NaN NaN NaN
291 : // +------------------+------------------+------------------+
292 : // | | | |
293 : // | (0,0) | (1,0) | (2,0) |
294 : // | 10 10| 8.5 7| 7 |
295 : // | +#########+########+###o=====+========++ |
296 : // | # | | : | || |
297 : // | # | | : | || |
298 : // | # | | : | || |
299 : // +--------+---------+--------+---o-----+--------++--------+
300 : // |NaN 10# 10| ........: 7| 7 || NaN|
301 : // | o.........o..: | || |
302 : // | || | | || |
303 : // | 7++---------+ 7 6 +--------++ |
304 : // | || | | || |
305 : // | || | | || |
306 : // | || | 4.5 | || |
307 : // +-------++---------+--------+---------+--------++--------+
308 : // |NaN 4|| 4 | | 5| 5 || NaN|
309 : // | || | | | || |
310 : // | || | | | || |
311 : // | ++=========+========+=========+========++ |
312 : // | 4 4 | 4.5 5| 5 |
313 : // | (0,2) | (1,2) | (2,2) |
314 : // | | | |
315 : // +------------------+------------------+------------------+
316 : // NaN NaN NaN NaN
317 :
318 2 : std::vector<double> data = {10.0, 7.0, 4.0, 5.0};
319 2 : TestRingAppender w;
320 :
321 : {
322 1 : IntervalLevelRangeIterator levels(8.0, 10.0);
323 : SegmentMerger<TestRingAppender, IntervalLevelRangeIterator> writer(
324 2 : w, levels, /* polygonize */ true);
325 : ContourGenerator<decltype(writer), IntervalLevelRangeIterator> cg(
326 2 : 2, 2, /* hasNoData */ false, NaN, writer, levels);
327 1 : cg.feedLine(&data[0]);
328 1 : cg.feedLine(&data[2]);
329 :
330 : // "Polygon #0"
331 1 : EXPECT_TRUE(w.hasRing(8.0, {{2.0, 0.0},
332 : {2.0, 0.5},
333 : {2.0, 1.0},
334 : {2.0, 1.5},
335 : {2.0, 2.0},
336 : {1.5, 2.0},
337 : {1.0, 2.0},
338 : {0.5, 2.0},
339 : {0.0, 2.0},
340 : {0.0, 1.5},
341 : {0.0, 1.0},
342 : {0.0, 0.833},
343 : {0.5, 0.833},
344 : {1.167, 0.5},
345 : {1.167, 0.0},
346 : {1.5, 0.0}}));
347 : // "Polygon #1"
348 1 : EXPECT_TRUE(w.hasRing(18.0, {{0.0, 0.0},
349 : {0.5, 0.0},
350 : {1.0, 0.0},
351 : {1.167, 0.0},
352 : {1.167, 0.5},
353 : {0.5, 0.833},
354 : {0, 0.833},
355 : {0.0, 0.5}}));
356 : }
357 1 : }
358 :
359 4 : TEST_F(test_ms_contour, saddle_point)
360 : {
361 : // four pixels
362 : // two rings
363 : // with a saddle point
364 : // 5 10
365 : // 10 5
366 : // levels = 8
367 : // pixels
368 : // +-----+-----+-----+-----+
369 : // | | | | |
370 : // | NaN | NaN | NaN | NaN |
371 : // | | | | |
372 : // +-----+-----+-----+-----+
373 : // | | | | |
374 : // | NaN | 5 | 10 | NaN |
375 : // | | | | |
376 : // +-----+-----+-----+-----+
377 : // | | | | |
378 : // | NaN | 10 | 5 | NaN |
379 : // | | | | |
380 : // +-----+-----+-----+-----+
381 : // | | | | |
382 : // | NaN | NaN | NaN | NaN |
383 : // | | | | |
384 : // +-----+-----+-----+-----+
385 : //
386 : // squares
387 : // +-----+-----+-----+-----+
388 : // |NaN | NaN | NaN | NaN |
389 : // | +.....+.....+.....+ |
390 : // | : | : | : | : |
391 : // +--:--+--:--+--:--+--:--+
392 : // | : | 5: |10: |NaN |
393 : // NaN+.....+.....+.....+ |
394 : // | : | : | : | : |
395 : // +--:--+--:--+--:--+--:--+
396 : // | : |10: | 5: |NaN |
397 : // NaN+.....+.....+.....+ |
398 : // | : | : | : | : |
399 : // +--:--+--:--+--:--+--:--+
400 : // | : | : | : | : |
401 : // | +.....+.....+.....+ |
402 : // | NaN | NaN | NaN | NaN |
403 : // +-----+-----+-----+-----+
404 : //
405 : // subsquares
406 : // legend:
407 : // : contour
408 : // # border (level 8)
409 : // = border (level 18)
410 : //
411 : // NaN NaN NaN
412 : // +------------------+------------------+------------------+
413 : // | | | |
414 : // | (0,0) | (1,0) | (2,0) |
415 : // | 5 5| 7.5 10| 10 |
416 : // | +#########+########+###o=====+========++ |
417 : // | # | | : | || |
418 : // | # | | : | || |
419 : // | # | | : | || |
420 : // +--------+---------+--------+---o-----+--------++--------+
421 : // |NaN 5 # 5| \ 10| 10|| NaN|
422 : // | # | \___o........o |
423 : // | # | | # |
424 : // | 7.5++---------+7.5 7.5+--------+ |
425 : // | # | | # |
426 : // | o.........o\_ | # |
427 : // | || | \_ 7.5 | # |
428 : // +-------++---------+----\o--+---------+--------+---------+
429 : // |NaN 10|| 10| : | 5| 5 # NaN|
430 : // | || | : | | # |
431 : // | || | : | | # |
432 : // | ++=========+=====o##+#########+########+ |
433 : // | 10 10| 7.5 5| 5 |
434 : // | (0,2) | (1,2) | (2,2) |
435 : // | | | |
436 : // +------------------+------------------+------------------+
437 : // NaN NaN NaN NaN
438 :
439 2 : std::vector<double> data = {5.0, 10.0, 10.0, 5.0};
440 2 : TestRingAppender w;
441 :
442 : {
443 1 : IntervalLevelRangeIterator levels(8.0, 10.0);
444 : SegmentMerger<TestRingAppender, IntervalLevelRangeIterator> writer(
445 2 : w, levels, /* polygonize */ true);
446 : ContourGenerator<decltype(writer), IntervalLevelRangeIterator> cg(
447 2 : 2, 2, /* hasNoData */ false, NaN, writer, levels);
448 1 : cg.feedLine(&data[0]);
449 1 : cg.feedLine(&data[2]);
450 :
451 : // "Polygon #0"
452 1 : EXPECT_TRUE(w.hasRing(8.0, {{1.5, 2},
453 : {2, 2},
454 : {2, 1.5},
455 : {2, 1},
456 : {2, 0.9},
457 : {1.5, 0.9},
458 : {1.1, 0.5},
459 : {1.1, 0},
460 : {1, 0},
461 : {0.5, 0},
462 : {0, 0},
463 : {0, 0.5},
464 : {0, 1},
465 : {0, 1.1},
466 : {0.5, 1.1},
467 : {0.9, 1.5},
468 : {0.9, 2},
469 : {1, 2}}));
470 : // "Polygon #1, Ring #0"
471 1 : EXPECT_TRUE(w.hasRing(18.0, {{2, 0.9},
472 : {2, 0.5},
473 : {2, 0},
474 : {1.5, 0},
475 : {1.1, 0},
476 : {1.1, 0.5},
477 : {1.5, 0.9}}));
478 : // "Polygon #1, Ring #1"
479 1 : EXPECT_TRUE(w.hasRing(18.0, {{0.9, 1.5},
480 : {0.5, 1.1},
481 : {0, 1.1},
482 : {0, 1.5},
483 : {0, 2},
484 : {0.5, 2},
485 : {0.9, 2}}));
486 : }
487 1 : }
488 : } // namespace
|
