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