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