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/point.h"
18 : #include "marching_squares/level_generator.h"
19 : #include "marching_squares/contour_generator.h"
20 : #include <limits>
21 : #include <map>
22 : #include <fstream>
23 :
24 : #include "gtest_include.h"
25 :
26 : #if defined(__clang__)
27 : #pragma clang diagnostic push
28 : #pragma clang diagnostic ignored "-Wweak-vtables"
29 : #endif
30 :
31 : namespace test_marching_squares_tile
32 : {
33 : using namespace marching_squares;
34 :
35 : struct Writer
36 : {
37 : typedef std::pair<Point, Point> Segment;
38 :
39 620 : static bool coordEquals(double a, double b)
40 : {
41 620 : return (a - b) * (a - b) < 0.001;
42 : }
43 :
44 16 : void addSegment(int levelIdx, const Point &first, const Point &second)
45 : {
46 16 : contours[levelIdx].push_back(Segment(first, second));
47 16 : }
48 :
49 74 : void addBorderSegment(int levelIdx, const Point &first, const Point &second)
50 : {
51 74 : borders[levelIdx].push_back(Segment(first, second));
52 74 : }
53 :
54 : // check if a segment is in a set of borders
55 43 : bool segmentInBorders(int levelIdx, const Segment &segmentToTest) const
56 : {
57 43 : const auto iter = borders.find(levelIdx);
58 43 : if (iter == borders.end())
59 : {
60 0 : CPLAssert(false);
61 : return false;
62 : }
63 43 : const auto &segments = iter->second;
64 180 : for (const Segment &s : segments)
65 : {
66 : // (A,B) == (A,B) || (A,B) == (B,A)
67 248 : if (((coordEquals(s.first.x, segmentToTest.first.x)) &&
68 97 : (coordEquals(s.first.y, segmentToTest.first.y)) &&
69 45 : (coordEquals(s.second.x, segmentToTest.second.x)) &&
70 444 : (coordEquals(s.second.y, segmentToTest.second.y))) ||
71 236 : ((coordEquals(s.second.x, segmentToTest.first.x)) &&
72 105 : (coordEquals(s.second.y, segmentToTest.first.y)) &&
73 70 : (coordEquals(s.first.x, segmentToTest.second.x)) &&
74 33 : (coordEquals(s.first.y, segmentToTest.second.y))))
75 43 : return true;
76 : }
77 0 : return false;
78 : }
79 :
80 : // check if a segment is in a set of contours
81 3 : bool segmentInContours(int levelIdx, const Segment &segmentToTest) const
82 : {
83 3 : const auto iter = contours.find(levelIdx);
84 3 : if (iter == contours.end())
85 : {
86 0 : CPLAssert(false);
87 : return false;
88 : }
89 3 : const auto &segments = iter->second;
90 6 : for (const Segment &s : segments)
91 : {
92 : // (A,B) == (A,B) || (A,B) == (B,A)
93 10 : if (((coordEquals(s.first.x, segmentToTest.first.x)) &&
94 7 : (coordEquals(s.first.y, segmentToTest.first.y)) &&
95 6 : (coordEquals(s.second.x, segmentToTest.second.x)) &&
96 16 : (coordEquals(s.second.y, segmentToTest.second.y))) ||
97 4 : ((coordEquals(s.second.x, segmentToTest.first.x)) &&
98 2 : (coordEquals(s.second.y, segmentToTest.first.y)) &&
99 1 : (coordEquals(s.first.x, segmentToTest.second.x)) &&
100 0 : (coordEquals(s.first.y, segmentToTest.second.y))))
101 3 : return true;
102 : }
103 0 : return false;
104 : }
105 :
106 14 : void beginningOfLine()
107 : {
108 14 : }
109 :
110 14 : void endOfLine()
111 : {
112 14 : }
113 :
114 : std::map<int, std::vector<Segment>> contours;
115 : std::map<int, std::vector<Segment>> borders;
116 : const bool polygonize = true;
117 : };
118 :
119 : // Common fixture with test data
120 : struct test_ms_tile : public ::testing::Test
121 : {
122 : };
123 :
124 : // Dummy test
125 4 : TEST_F(test_ms_tile, dummy)
126 : {
127 :
128 : // only one pixel of value 2.0
129 : // levels = 0, 10
130 2 : std::vector<double> data = {2.0};
131 : IntervalLevelRangeIterator levels(0.0, 10.0,
132 1 : -std::numeric_limits<double>::infinity());
133 2 : Writer writer;
134 :
135 : ContourGenerator<Writer, IntervalLevelRangeIterator> cg(
136 2 : 1, 1, /* hasNoData */ false, NaN, writer, levels);
137 1 : cg.feedLine(&data[0]);
138 :
139 1 : EXPECT_EQ(writer.borders.size(), size_t(1));
140 1 : EXPECT_EQ(writer.borders[1].size(), size_t(8));
141 1 : EXPECT_TRUE(writer.segmentInBorders(
142 : 1, std::make_pair(Point(0.0, 0.0), Point(0.5, 0.0))));
143 1 : EXPECT_TRUE(writer.segmentInBorders(
144 : 1, std::make_pair(Point(0.5, 0.0), Point(1.0, 0.0))));
145 1 : EXPECT_TRUE(writer.segmentInBorders(
146 : 1, std::make_pair(Point(1.0, 0.0), Point(1.0, 0.5))));
147 1 : EXPECT_TRUE(writer.segmentInBorders(
148 : 1, std::make_pair(Point(1.0, 0.5), Point(1.0, 1.0))));
149 1 : EXPECT_TRUE(writer.segmentInBorders(
150 : 1, std::make_pair(Point(1.0, 1.0), Point(0.5, 1.0))));
151 1 : EXPECT_TRUE(writer.segmentInBorders(
152 : 1, std::make_pair(Point(0.5, 1.0), Point(0.0, 1.0))));
153 1 : EXPECT_TRUE(writer.segmentInBorders(
154 : 1, std::make_pair(Point(0.0, 1.0), Point(0.0, 0.5))));
155 1 : EXPECT_TRUE(writer.segmentInBorders(
156 : 1, std::make_pair(Point(0.0, 0.5), Point(0.0, 0.0))));
157 1 : }
158 :
159 4 : TEST_F(test_ms_tile, tile_one_pixel)
160 : {
161 : // Tile with one pixel, value below
162 : // only one pixel of value 2.0
163 : // levels = 0, 10
164 2 : std::vector<double> data = {2.0};
165 1 : const double levels[] = {0.0};
166 : FixedLevelRangeIterator levelGenerator(
167 1 : levels, 1, -std::numeric_limits<double>::infinity(),
168 2 : std::numeric_limits<double>::infinity());
169 2 : Writer writer;
170 :
171 : ContourGenerator<Writer, FixedLevelRangeIterator> cg(
172 2 : 1, 1, /* hasNoData */ false, NaN, writer, levelGenerator);
173 1 : cg.feedLine(&data[0]);
174 :
175 1 : EXPECT_EQ(writer.borders.size(), size_t(1));
176 1 : EXPECT_TRUE(levelGenerator.level(1) == Inf);
177 1 : EXPECT_EQ(writer.borders[1].size(), size_t(8));
178 1 : EXPECT_TRUE(writer.segmentInBorders(
179 : 1, std::make_pair(Point(0.0, 0.0), Point(0.5, 0.0))));
180 1 : EXPECT_TRUE(writer.segmentInBorders(
181 : 1, std::make_pair(Point(0.5, 0.0), Point(1.0, 0.0))));
182 1 : EXPECT_TRUE(writer.segmentInBorders(
183 : 1, std::make_pair(Point(1.0, 0.0), Point(1.0, 0.5))));
184 1 : EXPECT_TRUE(writer.segmentInBorders(
185 : 1, std::make_pair(Point(1.0, 0.5), Point(1.0, 1.0))));
186 1 : EXPECT_TRUE(writer.segmentInBorders(
187 : 1, std::make_pair(Point(1.0, 1.0), Point(0.5, 1.0))));
188 1 : EXPECT_TRUE(writer.segmentInBorders(
189 : 1, std::make_pair(Point(0.5, 1.0), Point(0.0, 1.0))));
190 1 : EXPECT_TRUE(writer.segmentInBorders(
191 : 1, std::make_pair(Point(0.0, 1.0), Point(0.0, 0.5))));
192 1 : EXPECT_TRUE(writer.segmentInBorders(
193 : 1, std::make_pair(Point(0.0, 0.5), Point(0.0, 0.0))));
194 1 : }
195 :
196 4 : TEST_F(test_ms_tile, tile_one_pixel_two)
197 : {
198 : // Tile with one pixel (2)
199 : // only one pixel of value 2.0
200 : // levels = 2, 10
201 2 : std::vector<double> data = {2.0};
202 : IntervalLevelRangeIterator levels(2.0, 10.0,
203 1 : -std::numeric_limits<double>::infinity());
204 2 : Writer writer;
205 :
206 : ContourGenerator<Writer, IntervalLevelRangeIterator> cg(
207 2 : 1, 1, /* hasNoData */ false, NaN, writer, levels);
208 1 : cg.feedLine(&data[0]);
209 :
210 1 : EXPECT_EQ(writer.borders.size(), size_t(1));
211 1 : EXPECT_EQ(writer.borders[1].size(), size_t(8));
212 1 : EXPECT_TRUE(writer.segmentInBorders(
213 : 1, std::make_pair(Point(0.0, 0.0), Point(0.5, 0.0))));
214 1 : EXPECT_TRUE(writer.segmentInBorders(
215 : 1, std::make_pair(Point(0.5, 0.0), Point(1.0, 0.0))));
216 1 : EXPECT_TRUE(writer.segmentInBorders(
217 : 1, std::make_pair(Point(1.0, 0.0), Point(1.0, 0.5))));
218 1 : EXPECT_TRUE(writer.segmentInBorders(
219 : 1, std::make_pair(Point(1.0, 0.5), Point(1.0, 1.0))));
220 1 : EXPECT_TRUE(writer.segmentInBorders(
221 : 1, std::make_pair(Point(1.0, 1.0), Point(0.5, 1.0))));
222 1 : EXPECT_TRUE(writer.segmentInBorders(
223 : 1, std::make_pair(Point(0.5, 1.0), Point(0.0, 1.0))));
224 1 : EXPECT_TRUE(writer.segmentInBorders(
225 : 1, std::make_pair(Point(0.0, 1.0), Point(0.0, 0.5))));
226 1 : EXPECT_TRUE(writer.segmentInBorders(
227 : 1, std::make_pair(Point(0.0, 0.5), Point(0.0, 0.0))));
228 1 : }
229 :
230 4 : TEST_F(test_ms_tile, tile_two_pixels)
231 : {
232 : // Tile with two pixels
233 : // two pixels
234 : // 10 7
235 : // levels = 8
236 : //
237 : // pixels
238 : // +-----+-----+-----+-----+
239 : // | | | | |
240 : // | NaN | NaN | NaN | NaN |
241 : // | | | | |
242 : // +-----+-----+-----+-----+
243 : // | | | | |
244 : // | NaN | 10 | 7 | NaN |
245 : // | | | | |
246 : // +-----+-----+-----+-----+
247 : // | | | | |
248 : // | NaN | NaN | NaN | NaN |
249 : // | | | | |
250 : // +-----+-----+-----+-----+
251 : //
252 : // squares
253 : // +-----+-----+-----+-----+
254 : // |NaN | NaN | NaN | NaN |
255 : // | +.....+.....+.....+ |
256 : // | : | : | : | : |
257 : // +--:--+--:--+--:--+--:--+
258 : // | : |10: | 7: |NaN |
259 : // NaN+.....+.....+.....+ |
260 : // | : | : | : | : |
261 : // +--:--+--:--+--:--+--:--+
262 : // | : | : | : | : |
263 : // | +.....+.....+.....+ |
264 : // | NaN | NaN | NaN | NaN |
265 : // +-----+-----+-----+-----+
266 : //
267 : // subsquares
268 : // legend:
269 : // : contour
270 : // = border (level 8)
271 : // # border (level 18)
272 : //
273 : // NaN NaN NaN
274 : // +------------------+------------------+------------------+
275 : // | | | |
276 : // | (0,0) | (1,0) | (2,0) |
277 : // | 10 10| 8.5 7| 7 |
278 : // | +#########+########+###o=====+========+ |
279 : // | # | | : | || |
280 : // | # | | : | || |
281 : // | # | | : | || |
282 : // +--------+---------+--------+---o-----+--------+|--------+
283 : // |NaN 10# 10| 8.5 : 7| 7 || NaN|
284 : // | # | | : | || |
285 : // | # | | : | || |
286 : // | +#########+########+###o=====+========+ |
287 : // | 10 10| 8.5 7| 7 |
288 : // | (0,1) | (1,1) | (2,1) |
289 : // | | | |
290 : // +------------------+------------------+------------------+
291 : // NaN NaN NaN NaN
292 :
293 2 : std::vector<double> data = {10.0, 7.0};
294 : {
295 : IntervalLevelRangeIterator levels(
296 1 : 8.0, 10.0, -std::numeric_limits<double>::infinity());
297 2 : Writer writer;
298 : ContourGenerator<Writer, IntervalLevelRangeIterator> cg(
299 2 : 2, 1, /* hasNoData */ false, NaN, writer, levels);
300 1 : cg.feedLine(&data[0]);
301 :
302 : // check borders
303 1 : EXPECT_EQ(writer.borders.size(), size_t(2));
304 1 : EXPECT_EQ(writer.borders[0].size(), size_t(6));
305 1 : EXPECT_EQ(writer.borders[1].size(), size_t(8));
306 :
307 1 : EXPECT_TRUE(writer.segmentInBorders(
308 : 0, std::make_pair(Point(1.166, 0.0), Point(1.5, 0.0))));
309 1 : EXPECT_TRUE(writer.segmentInBorders(
310 : 0, std::make_pair(Point(1.5, 0.0), Point(2.0, 0.0))));
311 1 : EXPECT_TRUE(writer.segmentInBorders(
312 : 0, std::make_pair(Point(2.0, 0.0), Point(2.0, 0.5))));
313 1 : EXPECT_TRUE(writer.segmentInBorders(
314 : 0, std::make_pair(Point(2.0, 0.5), Point(2.0, 1.0))));
315 1 : EXPECT_TRUE(writer.segmentInBorders(
316 : 0, std::make_pair(Point(2.0, 1.0), Point(1.5, 1.0))));
317 1 : EXPECT_TRUE(writer.segmentInBorders(
318 : 0, std::make_pair(Point(1.5, 1.0), Point(1.166, 1.0))));
319 :
320 1 : EXPECT_TRUE(writer.segmentInBorders(
321 : 1, std::make_pair(Point(1.166, 0.0), Point(1.0, 0.0))));
322 1 : EXPECT_TRUE(writer.segmentInBorders(
323 : 1, std::make_pair(Point(1.0, 0.0), Point(0.5, 0.0))));
324 1 : EXPECT_TRUE(writer.segmentInBorders(
325 : 1, std::make_pair(Point(0.5, 0.0), Point(0.0, 0.0))));
326 1 : EXPECT_TRUE(writer.segmentInBorders(
327 : 1, std::make_pair(Point(0.0, 0.0), Point(0.0, 0.5))));
328 1 : EXPECT_TRUE(writer.segmentInBorders(
329 : 1, std::make_pair(Point(0.0, 0.5), Point(0.0, 1.0))));
330 1 : EXPECT_TRUE(writer.segmentInBorders(
331 : 1, std::make_pair(Point(0.0, 1.0), Point(0.5, 1.0))));
332 1 : EXPECT_TRUE(writer.segmentInBorders(
333 : 1, std::make_pair(Point(0.5, 1.0), Point(1.0, 1.0))));
334 1 : EXPECT_TRUE(writer.segmentInBorders(
335 : 1, std::make_pair(Point(1.0, 1.0), Point(1.166, 1.0))));
336 : }
337 1 : }
338 :
339 4 : TEST_F(test_ms_tile, tile_four_pixels)
340 : {
341 : // four pixels
342 : // 10 7
343 : // 4 5
344 : // levels = 8
345 : // pixels
346 : // +-----+-----+-----+-----+
347 : // | | | | |
348 : // | NaN | NaN | NaN | NaN |
349 : // | | | | |
350 : // +-----+-----+-----+-----+
351 : // | | | | |
352 : // | NaN | 10 | 7 | NaN |
353 : // | | | | |
354 : // +-----+-----+-----+-----+
355 : // | | | | |
356 : // | NaN | 4 | 5 | NaN |
357 : // | | | | |
358 : // +-----+-----+-----+-----+
359 : // | | | | |
360 : // | NaN | NaN | NaN | NaN |
361 : // | | | | |
362 : // +-----+-----+-----+-----+
363 : //
364 : // squares
365 : // +-----+-----+-----+-----+
366 : // |NaN | NaN | NaN | NaN |
367 : // | +.....+.....+.....+ |
368 : // | : | : | : | : |
369 : // +--:--+--:--+--:--+--:--+
370 : // | : |10: | 7: |NaN |
371 : // NaN+.....+.....+.....+ |
372 : // | : | : | : | : |
373 : // +--:--+--:--+--:--+--:--+
374 : // | : | 4: | 5: |NaN |
375 : // NaN+.....+.....+.....+ |
376 : // | : | : | : | : |
377 : // +--:--+--:--+--:--+--:--+
378 : // | : | : | : | : |
379 : // | +.....+.....+.....+ |
380 : // | NaN | NaN | NaN | NaN |
381 : // +-----+-----+-----+-----+
382 : //
383 : // subsquares
384 : // legend:
385 : // : contour
386 : // = border (level 8)
387 : // # border (level 18)
388 : //
389 : // NaN NaN NaN
390 : // +------------------+------------------+------------------+
391 : // | | | |
392 : // | (0,0) | (1,0) | (2,0) |
393 : // | 10 10| 8.5 7| 7 |
394 : // | +#########+########+###o=====+========++ |
395 : // | # | | : | || |
396 : // | # | | : | || |
397 : // | # | | : | || |
398 : // +--------+---------+--------+---o-----+--------++--------+
399 : // |NaN 10# 10| ........: 7| 7 || NaN|
400 : // | o.........o..: | || |
401 : // | || | | || |
402 : // | 7++---------+ 7 6 +--------++ |
403 : // | || | | || |
404 : // | || | | || |
405 : // | || | 4.5 | || |
406 : // +-------++---------+--------+---------+--------++--------+
407 : // |NaN 4|| 4 | | 5| 5 || NaN|
408 : // | || | | | || |
409 : // | || | | | || |
410 : // | ++=========+========+=========+========++ |
411 : // | 4 4 | 4.5 5| 5 |
412 : // | (0,2) | (1,2) | (2,2) |
413 : // | | | |
414 : // +------------------+------------------+------------------+
415 : // NaN NaN NaN NaN
416 2 : std::vector<double> data = {10.0, 7.0, 4.0, 5.0};
417 : {
418 : IntervalLevelRangeIterator levels(
419 1 : 8.0, 10.0, -std::numeric_limits<double>::infinity());
420 2 : Writer writer;
421 : ContourGenerator<Writer, IntervalLevelRangeIterator> cg(
422 2 : 2, 2, /* hasNoData */ false, NaN, writer, levels);
423 1 : cg.feedLine(&data[0]);
424 1 : cg.feedLine(&data[2]);
425 :
426 : // check borders
427 1 : EXPECT_EQ(writer.borders.size(), size_t(2));
428 1 : EXPECT_EQ(writer.borders[0].size(), size_t(13));
429 1 : EXPECT_EQ(writer.borders[1].size(), size_t(5));
430 :
431 1 : EXPECT_TRUE(writer.segmentInBorders(
432 : 1, std::make_pair(Point(1.166, 0.0), Point(1.0, 0.0))));
433 1 : EXPECT_TRUE(writer.segmentInBorders(
434 : 1, std::make_pair(Point(1.0, 0.0), Point(0.5, 0.0))));
435 1 : EXPECT_TRUE(writer.segmentInBorders(
436 : 1, std::make_pair(Point(0.5, 0.0), Point(0.0, 0.0))));
437 1 : EXPECT_TRUE(writer.segmentInBorders(
438 : 1, std::make_pair(Point(0.0, 0.0), Point(0.0, 0.5))));
439 1 : EXPECT_TRUE(writer.segmentInBorders(
440 : 1, std::make_pair(Point(0.0, 0.5), Point(0.0, 0.833))));
441 :
442 : // check contour
443 1 : EXPECT_EQ(writer.contours.size(), size_t(2));
444 1 : EXPECT_EQ(writer.contours[0].size(), size_t(3));
445 1 : EXPECT_TRUE(writer.segmentInContours(
446 : 0, std::make_pair(Point(1.166, 0.0), Point(1.166, 0.5))));
447 1 : EXPECT_TRUE(writer.segmentInContours(
448 : 0, std::make_pair(Point(1.166, 0.5), Point(0.5, 0.833))));
449 1 : EXPECT_TRUE(writer.segmentInContours(
450 : 0, std::make_pair(Point(0.5, 0.833), Point(0.0, 0.833))));
451 : }
452 1 : }
453 :
454 4 : TEST_F(test_ms_tile, tile_four_pixels_2)
455 : {
456 : // four pixels
457 : // 155 155.01
458 : // 154.99 155
459 : // levels = 155
460 :
461 : // NaN NaN NaN
462 : // +------------------+------------------+------------------+
463 : // | | | |
464 : // | (0,0) | (1,0) | (2,0) |
465 : // | 155 | 155.005 | 155.01 |
466 : // | +---------+--------+---------+---------+ |
467 : // | | 155 | 155.01 | |
468 : // | | | | | | |
469 : // | | | 155.005 | | |
470 : // +--------+---------+--------+---------+---------+--------+
471 : // |NaN 155 155 155.01 155.01 NaN|
472 : // | | | | | |
473 : // | 154.995 | | 155.005 |
474 : // | +-------154.995 155.005------+ |
475 : // | | | | | |
476 : // | | | | | |
477 : // | | | | | |
478 : // +--------+---------+--------+---------+---------+--------+
479 : // |NaN 154.99 154.99 154.995 155 155 NaN|
480 : // | | | | | | |
481 : // | | | | | | |
482 : // | +---------+--------+---------+---------+ |
483 : // | 154.99 154.99 154.995 155 155 |
484 : // | (0,2) | (1,2) | (2,2) |
485 : // | | | |
486 : // +------------------+------------------+------------------+
487 : // NaN NaN NaN NaN
488 :
489 2 : std::vector<double> data = {155.0, 155.01, 154.99, 155.0};
490 : {
491 1 : const double levels[] = {155.0};
492 : FixedLevelRangeIterator levelGenerator(
493 1 : levels, 1, -std::numeric_limits<double>::infinity(),
494 2 : std::numeric_limits<double>::infinity());
495 2 : Writer writer;
496 : ContourGenerator<Writer, FixedLevelRangeIterator> cg(
497 2 : 2, 2, /* hasNoData */ false, NaN, writer, levelGenerator);
498 1 : cg.feedLine(&data[0]);
499 1 : cg.feedLine(&data[2]);
500 :
501 : // check borders
502 1 : EXPECT_EQ(writer.borders.size(), size_t(2));
503 1 : EXPECT_EQ(levelGenerator.level(0), 155.0);
504 1 : EXPECT_TRUE(levelGenerator.level(1) == Inf);
505 1 : EXPECT_EQ(writer.borders[0].size(), size_t(6));
506 1 : EXPECT_EQ(writer.borders[1].size(), size_t(12));
507 : }
508 1 : }
509 : } // namespace test_marching_squares_tile
510 :
511 : #if defined(__clang__)
512 : #pragma clang diagnostic pop
513 : #endif
|
