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