1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 // Unit Test
3
4 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
5 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
6
7 // This file was modified by Oracle on 2016, 2017, 2019.
8 // Modifications copyright (c) 2016-2019, Oracle and/or its affiliates.
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
10
11 // Use, modification and distribution is subject to the Boost Software License,
12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
13 // http://www.boost.org/LICENSE_1_0.txt)
14
15 #ifndef BOOST_GEOMETRY_TEST_DIFFERENCE_HPP
16 #define BOOST_GEOMETRY_TEST_DIFFERENCE_HPP
17
18 #include <fstream>
19 #include <iomanip>
20
21 #include <geometry_test_common.hpp>
22 #include <algorithms/check_validity.hpp>
23 #include "../setop_output_type.hpp"
24
25 #include <boost/core/ignore_unused.hpp>
26 #include <boost/foreach.hpp>
27
28 #include <boost/range/algorithm/copy.hpp>
29
30 #include <boost/geometry/algorithms/correct.hpp>
31 #include <boost/geometry/algorithms/difference.hpp>
32 #include <boost/geometry/algorithms/sym_difference.hpp>
33
34 #include <boost/geometry/algorithms/area.hpp>
35 #include <boost/geometry/algorithms/is_valid.hpp>
36 #include <boost/geometry/algorithms/length.hpp>
37 #include <boost/geometry/algorithms/num_points.hpp>
38 #include <boost/geometry/algorithms/num_interior_rings.hpp>
39 #include <boost/geometry/algorithms/remove_spikes.hpp>
40
41 #include <boost/geometry/geometries/geometries.hpp>
42
43
44 #include <boost/geometry/geometries/multi_point.hpp>
45 #include <boost/geometry/geometries/multi_linestring.hpp>
46 #include <boost/geometry/geometries/multi_polygon.hpp>
47
48 #include <boost/geometry/strategies/strategies.hpp>
49
50 #include <boost/geometry/io/wkt/wkt.hpp>
51
52
53 #if defined(TEST_WITH_SVG)
54 # define BOOST_GEOMETRY_DEBUG_SEGMENT_IDENTIFIER
55 # define BOOST_GEOMETRY_DEBUG_IDENTIFIER
56 # include <boost/geometry/io/svg/svg_mapper.hpp>
57 # include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
58 #endif
59
60
61 struct ut_settings
62 {
63 double percentage;
64 bool sym_difference;
65 bool remove_spikes;
66
67 bool test_validity;
68
ut_settingsut_settings69 ut_settings()
70 : percentage(0.0001)
71 , sym_difference(true)
72 , remove_spikes(false)
73 , test_validity(true)
74 {}
75
76 };
77
tolerance(double percentage)78 inline ut_settings tolerance(double percentage)
79 {
80 ut_settings result;
81 result.percentage = percentage;
82 return result;
83 }
84
85
86 template <typename Output, typename G1, typename G2>
difference_output(std::string const & caseid,G1 const & g1,G2 const & g2,Output const & output)87 void difference_output(std::string const& caseid, G1 const& g1, G2 const& g2, Output const& output)
88 {
89 boost::ignore_unused(caseid, g1, g2, output);
90
91 #if defined(TEST_WITH_SVG)
92 {
93 typedef typename bg::coordinate_type<G1>::type coordinate_type;
94 typedef typename bg::point_type<G1>::type point_type;
95
96 bool const ccw =
97 bg::point_order<G1>::value == bg::counterclockwise
98 || bg::point_order<G2>::value == bg::counterclockwise;
99 bool const open =
100 bg::closure<G1>::value == bg::open
101 || bg::closure<G2>::value == bg::open;
102
103 std::ostringstream filename;
104 filename << "difference_"
105 << caseid << "_"
106 << string_from_type<coordinate_type>::name()
107 << (ccw ? "_ccw" : "")
108 << (open ? "_open" : "")
109 #if defined(BOOST_GEOMETRY_USE_RESCALING)
110 << "_rescaled"
111 #endif
112 << ".svg";
113
114 std::ofstream svg(filename.str().c_str());
115
116 bg::svg_mapper<point_type> mapper(svg, 500, 500);
117
118 mapper.add(g1);
119 mapper.add(g2);
120
121 mapper.map(g1, "fill-opacity:0.3;fill:rgb(51,51,153);stroke:rgb(51,51,153);stroke-width:3");
122 mapper.map(g2, "fill-opacity:0.5;fill:rgb(153,204,0);stroke:rgb(153,204,0);stroke-width:3");
123
124
125 for (typename Output::const_iterator it = output.begin(); it != output.end(); ++it)
126 {
127 mapper.map(*it,
128 //sym ? "fill-opacity:0.2;stroke-opacity:0.4;fill:rgb(255,255,0);stroke:rgb(255,0,255);stroke-width:8" :
129 "fill-opacity:0.2;stroke-opacity:0.4;fill:rgb(255,0,0);stroke:rgb(255,0,255);stroke-width:8");
130 }
131 }
132 #endif
133 }
134
135 template <typename OutputType, typename G1, typename G2>
test_difference(std::string const & caseid,G1 const & g1,G2 const & g2,int expected_count,int expected_rings_count,int expected_point_count,double expected_area,bool sym,ut_settings const & settings)136 std::string test_difference(std::string const& caseid, G1 const& g1, G2 const& g2,
137 int expected_count, int expected_rings_count, int expected_point_count,
138 double expected_area,
139 bool sym,
140 ut_settings const& settings)
141 {
142 typedef typename bg::coordinate_type<G1>::type coordinate_type;
143 boost::ignore_unused<coordinate_type>();
144
145 bg::model::multi_polygon<OutputType> result;
146
147
148 if (sym)
149 {
150 bg::sym_difference(g1, g2, result);
151 }
152 else
153 {
154 bg::difference(g1, g2, result);
155 }
156
157 if (settings.remove_spikes)
158 {
159 bg::remove_spikes(result);
160 }
161
162 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
163 {
164 bg::model::multi_polygon<OutputType> result_s;
165 typedef typename bg::strategy::relate::services::default_strategy
166 <
167 G1, G2
168 >::type strategy_type;
169 if (sym)
170 {
171 bg::sym_difference(g1, g2, result_s, strategy_type());
172 }
173 else
174 {
175 bg::difference(g1, g2, result_s, strategy_type());
176 }
177
178 if (settings.remove_spikes)
179 {
180 bg::remove_spikes(result_s);
181 }
182 BOOST_CHECK_EQUAL(bg::num_points(result), bg::num_points(result_s));
183 }
184 #endif
185
186
187 std::ostringstream return_string;
188 return_string << bg::wkt(result);
189
190 typename bg::default_area_result<G1>::type const area = bg::area(result);
191
192 #if ! defined(BOOST_GEOMETRY_NO_BOOST_TEST)
193 #if ! defined(BOOST_GEOMETRY_TEST_ALWAYS_CHECK_VALIDITY)
194 if (settings.test_validity)
195 #endif
196 {
197 // std::cout << bg::dsv(result) << std::endl;
198 typedef bg::model::multi_polygon<OutputType> result_type;
199 std::string message;
200 bool const valid = check_validity<result_type>::apply(result, caseid, g1, g2, message);
201 BOOST_CHECK_MESSAGE(valid,
202 "difference: " << caseid << " not valid " << message
203 << " type: " << (type_for_assert_message<G1, G2>()));
204 }
205 #endif
206
207 difference_output(caseid, g1, g2, result);
208
209 #if ! (defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE) \
210 || defined(BOOST_GEOMETRY_DEBUG_ASSEMBLE))
211 {
212 // Test inserter functionality
213 // Test if inserter returns output-iterator (using Boost.Range copy)
214 typename setop_output_type<OutputType>::type
215 inserted, array_with_one_empty_geometry;
216 array_with_one_empty_geometry.push_back(OutputType());
217 if (sym)
218 {
219 boost::copy(array_with_one_empty_geometry,
220 bg::detail::sym_difference::sym_difference_insert<OutputType>
221 (g1, g2, std::back_inserter(inserted)));
222 }
223 else
224 {
225 boost::copy(array_with_one_empty_geometry,
226 bg::detail::difference::difference_insert<OutputType>(
227 g1, g2, std::back_inserter(inserted)));
228 }
229
230 BOOST_CHECK_EQUAL(boost::size(result), boost::size(inserted) - 1);
231 }
232 #endif
233
234
235
236 #if ! defined(BOOST_GEOMETRY_NO_BOOST_TEST)
237 #if defined(BOOST_GEOMETRY_USE_RESCALING)
238 if (expected_point_count >= 0)
239 {
240 std::size_t const n = bg::num_points(result);
241 BOOST_CHECK_MESSAGE(bg::math::abs(int(n) - expected_point_count) < 3,
242 "difference: " << caseid
243 << " #points expected: " << expected_point_count
244 << " detected: " << n
245 << " type: " << (type_for_assert_message<G1, G2>())
246 );
247 }
248 #endif
249
250 if (expected_count >= 0)
251 {
252 BOOST_CHECK_MESSAGE(int(boost::size(result)) == expected_count,
253 "difference: " << caseid
254 << " #outputs expected: " << expected_count
255 << " detected: " << result.size()
256 << " type: " << (type_for_assert_message<G1, G2>())
257 );
258 }
259
260 if (expected_rings_count >= 0)
261 {
262 int nrings = int(boost::size(result) + bg::num_interior_rings(result));
263 BOOST_CHECK_MESSAGE(nrings == expected_rings_count,
264 "difference: " << caseid
265 << " #rings expected: " << expected_rings_count
266 << " detected: " << nrings
267 << " type: " << (type_for_assert_message<G1, G2>())
268 );
269 }
270
271 if (expected_area > 0)
272 {
273 BOOST_CHECK_CLOSE(area, expected_area, settings.percentage);
274 }
275 else
276 {
277 // Compare 0 with 0 or a very small detected area
278 BOOST_CHECK_LE(area, settings.percentage);
279 }
280 #endif
281
282 return return_string.str();
283 }
284
285 template <typename OutputType, typename G1, typename G2>
test_difference(std::string const & caseid,G1 const & g1,G2 const & g2,int expected_count,int expected_point_count,double expected_area,bool sym,ut_settings const & settings)286 std::string test_difference(std::string const& caseid, G1 const& g1, G2 const& g2,
287 int expected_count, int expected_point_count,
288 double expected_area,
289 bool sym,
290 ut_settings const& settings)
291 {
292 return test_difference<OutputType>(caseid, g1, g2,
293 expected_count, -1, expected_point_count, expected_area,
294 sym, settings);
295 }
296
297 #ifdef BOOST_GEOMETRY_CHECK_WITH_POSTGIS
298 static int counter = 0;
299 #endif
300
301
302 template <typename OutputType, typename G1, typename G2>
test_one(std::string const & caseid,std::string const & wkt1,std::string const & wkt2,int expected_count1,int expected_rings_count1,int expected_point_count1,double expected_area1,int expected_count2,int expected_rings_count2,int expected_point_count2,double expected_area2,int expected_count_s,int expected_rings_count_s,int expected_point_count_s,double expected_area_s,ut_settings const & settings=ut_settings ())303 std::string test_one(std::string const& caseid,
304 std::string const& wkt1, std::string const& wkt2,
305 int expected_count1,
306 int expected_rings_count1,
307 int expected_point_count1,
308 double expected_area1,
309 int expected_count2,
310 int expected_rings_count2,
311 int expected_point_count2,
312 double expected_area2,
313 int expected_count_s,
314 int expected_rings_count_s,
315 int expected_point_count_s,
316 double expected_area_s,
317 ut_settings const& settings = ut_settings())
318 {
319 G1 g1;
320 bg::read_wkt(wkt1, g1);
321
322 G2 g2;
323 bg::read_wkt(wkt2, g2);
324
325 bg::correct(g1);
326 bg::correct(g2);
327
328 std::string result = test_difference<OutputType>(caseid + "_a", g1, g2,
329 expected_count1, expected_rings_count1, expected_point_count1,
330 expected_area1, false, settings);
331
332 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
333 return result;
334 #endif
335
336 test_difference<OutputType>(caseid + "_b", g2, g1,
337 expected_count2, expected_rings_count2, expected_point_count2,
338 expected_area2, false, settings);
339
340 #if ! defined(BOOST_GEOMETRY_TEST_ALWAYS_CHECK_SYMDIFFERENCE)
341 if (settings.sym_difference)
342 #endif
343 {
344 test_difference<OutputType>(caseid + "_s", g1, g2,
345 expected_count_s,
346 expected_rings_count_s,
347 expected_point_count_s,
348 expected_area_s,
349 true, settings);
350 }
351 return result;
352 }
353
354 template <typename OutputType, typename G1, typename G2>
test_one(std::string const & caseid,std::string const & wkt1,std::string const & wkt2,int expected_count1,int expected_rings_count1,int expected_point_count1,double expected_area1,int expected_count2,int expected_rings_count2,int expected_point_count2,double expected_area2,ut_settings const & settings=ut_settings ())355 std::string test_one(std::string const& caseid,
356 std::string const& wkt1, std::string const& wkt2,
357 int expected_count1,
358 int expected_rings_count1,
359 int expected_point_count1,
360 double expected_area1,
361 int expected_count2,
362 int expected_rings_count2,
363 int expected_point_count2,
364 double expected_area2,
365 ut_settings const& settings = ut_settings())
366 {
367 return test_one<OutputType, G1, G2>(caseid, wkt1, wkt2,
368 expected_count1, expected_rings_count1, expected_point_count1, expected_area1,
369 expected_count2, expected_rings_count2, expected_point_count2, expected_area2,
370 expected_count1 + expected_count2,
371 expected_rings_count1 + expected_rings_count2,
372 expected_point_count1 >= 0 && expected_point_count2 >= 0
373 ? (expected_point_count1 + expected_point_count2) : -1,
374 expected_area1 + expected_area2,
375 settings);
376 }
377
378 template <typename OutputType, typename G1, typename G2>
test_one(std::string const & caseid,std::string const & wkt1,std::string const & wkt2,int expected_count1,int expected_point_count1,double expected_area1,int expected_count2,int expected_point_count2,double expected_area2,int expected_count_s,int expected_point_count_s,double expected_area_s,ut_settings const & settings=ut_settings ())379 std::string test_one(std::string const& caseid,
380 std::string const& wkt1, std::string const& wkt2,
381 int expected_count1,
382 int expected_point_count1,
383 double expected_area1,
384 int expected_count2,
385 int expected_point_count2,
386 double expected_area2,
387 int expected_count_s,
388 int expected_point_count_s,
389 double expected_area_s,
390 ut_settings const& settings = ut_settings())
391 {
392 return test_one<OutputType, G1, G2>(caseid, wkt1, wkt2,
393 expected_count1, -1, expected_point_count1, expected_area1,
394 expected_count2, -1, expected_point_count2, expected_area2,
395 expected_count_s, -1, expected_point_count_s, expected_area_s,
396 settings);
397 }
398
399 template <typename OutputType, typename G1, typename G2>
test_one(std::string const & caseid,std::string const & wkt1,std::string const & wkt2,int expected_count1,int expected_point_count1,double expected_area1,int expected_count2,int expected_point_count2,double expected_area2,ut_settings const & settings=ut_settings ())400 std::string test_one(std::string const& caseid,
401 std::string const& wkt1, std::string const& wkt2,
402 int expected_count1,
403 int expected_point_count1,
404 double expected_area1,
405 int expected_count2,
406 int expected_point_count2,
407 double expected_area2,
408 ut_settings const& settings = ut_settings())
409 {
410 return test_one<OutputType, G1, G2>(caseid, wkt1, wkt2,
411 expected_count1, expected_point_count1, expected_area1,
412 expected_count2, expected_point_count2, expected_area2,
413 expected_count1 + expected_count2,
414 expected_point_count1 >= 0 && expected_point_count2 >= 0
415 ? (expected_point_count1 + expected_point_count2) : -1,
416 expected_area1 + expected_area2,
417 settings);
418 }
419
420 template <typename OutputType, typename G1, typename G2>
test_one_lp(std::string const & caseid,std::string const & wkt1,std::string const & wkt2,std::size_t expected_count,int expected_point_count,double expected_length)421 void test_one_lp(std::string const& caseid,
422 std::string const& wkt1, std::string const& wkt2,
423 std::size_t expected_count,
424 int expected_point_count,
425 double expected_length)
426 {
427 G1 g1;
428 bg::read_wkt(wkt1, g1);
429
430 G2 g2;
431 bg::read_wkt(wkt2, g2);
432
433 bg::correct(g1);
434 bg::correct(g2);
435
436 typedef typename setop_output_type<OutputType>::type result_type;
437 result_type pieces;
438 bg::difference(g1, g2, pieces);
439
440 typename bg::default_length_result<G1>::type length = 0;
441 std::size_t n = 0;
442 std::size_t piece_count = 0;
443 for (typename result_type::iterator it = pieces.begin();
444 it != pieces.end();
445 ++it)
446 {
447 if (expected_point_count >= 0)
448 {
449 n += bg::num_points(*it);
450 }
451 piece_count++;
452 length += bg::length(*it);
453 }
454
455 BOOST_CHECK_MESSAGE(piece_count == expected_count,
456 "difference: " << caseid
457 << " #outputs expected: " << expected_count
458 << " detected: " << pieces.size()
459 );
460
461 if (expected_point_count >= 0)
462 {
463 BOOST_CHECK_MESSAGE(n == std::size_t(expected_point_count),
464 "difference: " << caseid
465 << " #points expected: " << std::size_t(expected_point_count)
466 << " detected: " << n
467 << " type: " << (type_for_assert_message<G1, G2>())
468 );
469 }
470
471 BOOST_CHECK_CLOSE(length, expected_length, 0.001);
472
473 std::string lp = "lp_";
474 difference_output(lp + caseid, g1, g2, pieces);
475 }
476
477
478 #endif
479