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