1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 // Unit Test
3
4 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
5
6 // This file was modified by Oracle on 2016, 2017.
7 // Modifications copyright (c) 2016-2017, Oracle and/or its affiliates.
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
9
10 // Use, modification and distribution is subject to the Boost Software License,
11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
12 // http://www.boost.org/LICENSE_1_0.txt)
13
14 #ifndef BOOST_GEOMETRY_TEST_INTERSECTION_HPP
15 #define BOOST_GEOMETRY_TEST_INTERSECTION_HPP
16
17 #include <fstream>
18 #include <iomanip>
19
20 #include <boost/foreach.hpp>
21 #include <boost/variant/variant.hpp>
22
23 #include <boost/geometry/algorithms/intersection.hpp>
24 #include <boost/geometry/algorithms/area.hpp>
25 #include <boost/geometry/algorithms/correct.hpp>
26 #include <boost/geometry/algorithms/is_valid.hpp>
27 #include <boost/geometry/algorithms/length.hpp>
28 #include <boost/geometry/algorithms/num_points.hpp>
29 #include <boost/geometry/algorithms/num_interior_rings.hpp>
30
31 #include <boost/geometry/geometries/geometries.hpp>
32
33 #include <boost/geometry/strategies/strategies.hpp>
34
35 #include <boost/geometry/io/wkt/wkt.hpp>
36
37
38 #if defined(TEST_WITH_SVG)
39 # include <boost/geometry/io/svg/svg_mapper.hpp>
40 #endif
41
42 #include <geometry_test_common.hpp>
43 #include <algorithms/check_validity.hpp>
44 #include "../setop_output_type.hpp"
45
46 struct ut_settings : ut_base_settings
47 {
48 double percentage;
49 bool debug;
50
ut_settingsut_settings51 explicit ut_settings(double p = 0.0001, bool tv = true)
52 : ut_base_settings(tv)
53 , percentage(p)
54 , debug(false)
55 {}
56
57 };
58
59 template<typename IntersectionOutput, typename G1, typename G2>
check_result(IntersectionOutput const & intersection_output,std::string const & caseid,G1 const & g1,G2 const & g2,std::size_t expected_count,std::size_t expected_holes_count,int expected_point_count,double expected_length_or_area,ut_settings const & settings)60 void check_result(IntersectionOutput const& intersection_output,
61 std::string const& caseid,
62 G1 const& g1, G2 const& g2,
63 std::size_t expected_count, std::size_t expected_holes_count,
64 int expected_point_count, double expected_length_or_area,
65 ut_settings const& settings)
66 {
67 typedef typename boost::range_value<IntersectionOutput>::type OutputType;
68 bool const is_line = bg::geometry_id<OutputType>::type::value == 2;
69
70 typename bg::default_area_result<G1>::type length_or_area = 0;
71 int n = 0;
72 std::size_t nholes = 0;
73 for (typename IntersectionOutput::const_iterator it = intersection_output.begin();
74 it != intersection_output.end();
75 ++it)
76 {
77 if (expected_point_count > 0)
78 {
79 // here n should rather be of type std::size_t, but expected_point_count
80 // is set to -1 in some test cases so type int was left for now
81 n += static_cast<int>(bg::num_points(*it, true));
82 }
83
84 if (expected_holes_count > 0)
85 {
86 nholes += bg::num_interior_rings(*it);
87 }
88
89 // instead of specialization we check it run-time here
90 length_or_area += is_line
91 ? bg::length(*it)
92 : bg::area(*it);
93
94 if (settings.debug)
95 {
96 std::cout << std::setprecision(20) << bg::wkt(*it) << std::endl;
97 }
98 }
99
100 if (settings.test_validity())
101 {
102 std::string message;
103 bool const valid = check_validity<IntersectionOutput>
104 ::apply(intersection_output, caseid, g1, g2, message);
105
106 BOOST_CHECK_MESSAGE(valid,
107 "intersection: " << caseid << " not valid: " << message
108 << " type: " << (type_for_assert_message<G1, G2>()));
109 }
110
111 #if ! defined(BOOST_GEOMETRY_NO_BOOST_TEST)
112 #if defined(BOOST_GEOMETRY_USE_RESCALING)
113 // Without rescaling, point count might easily differ (which is no problem)
114 if (expected_point_count > 0)
115 {
116 BOOST_CHECK_MESSAGE(bg::math::abs(n - expected_point_count) < 3,
117 "intersection: " << caseid
118 << " #points expected: " << expected_point_count
119 << " detected: " << n
120 << " type: " << (type_for_assert_message<G1, G2>())
121 );
122 }
123 #endif
124
125 if (expected_count > 0)
126 {
127 BOOST_CHECK_MESSAGE(intersection_output.size() == expected_count,
128 "intersection: " << caseid
129 << " #outputs expected: " << expected_count
130 << " detected: " << intersection_output.size()
131 << " type: " << (type_for_assert_message<G1, G2>())
132 );
133 }
134
135 if (expected_holes_count > 0)
136 {
137
138 BOOST_CHECK_MESSAGE(nholes == expected_holes_count,
139 "intersection: " << caseid
140 << " #holes expected: " << expected_holes_count
141 << " detected: " << nholes
142 << " type: " << (type_for_assert_message<G1, G2>())
143 );
144 }
145
146 double const detected_length_or_area = boost::numeric_cast<double>(length_or_area);
147 if (settings.percentage > 0.0)
148 {
149 if (expected_length_or_area > 0)
150 {
151 BOOST_CHECK_CLOSE(detected_length_or_area, expected_length_or_area, settings.percentage);
152 }
153 else
154 {
155 // Compare 0 with 0 or a very small detected area
156 BOOST_CHECK_LE(detected_length_or_area, settings.percentage);
157 }
158 }
159 else
160 {
161 // In some cases (geos_2) the intersection is either 0, or a tiny rectangle,
162 // depending on compiler/settings. That cannot be tested by CLOSE
163 BOOST_CHECK_LE(detected_length_or_area, expected_length_or_area);
164 }
165 #endif
166
167 }
168
169
170 template <typename OutputType, typename CalculationType, typename G1, typename G2>
test_intersection(std::string const & caseid,G1 const & g1,G2 const & g2,std::size_t expected_count=0,std::size_t expected_holes_count=0,int expected_point_count=0,double expected_length_or_area=0,ut_settings const & settings=ut_settings ())171 typename bg::default_area_result<G1>::type test_intersection(std::string const& caseid,
172 G1 const& g1, G2 const& g2,
173 std::size_t expected_count = 0, std::size_t expected_holes_count = 0,
174 int expected_point_count = 0, double expected_length_or_area = 0,
175 ut_settings const& settings = ut_settings())
176 {
177 if (settings.debug)
178 {
179 std::cout << std::endl << "case " << caseid << std::endl;
180 }
181
182 typedef typename setop_output_type<OutputType>::type result_type;
183
184 typedef typename bg::point_type<G1>::type point_type;
185 boost::ignore_unused<point_type>();
186
187 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
188 if (! settings.debug)
189 {
190 // Check _inserter behaviour with stratey
191 typedef typename bg::strategy::intersection::services::default_strategy
192 <
193 typename bg::cs_tag<point_type>::type
194 >::type strategy_type;
195 result_type clip;
196 bg::detail::intersection::intersection_insert<OutputType>(g1, g2, std::back_inserter(clip), strategy_type());
197 }
198 #endif
199
200 typename bg::default_area_result<G1>::type length_or_area = 0;
201
202 // Check normal behaviour
203 result_type intersection_output;
204 bg::intersection(g1, g2, intersection_output);
205
206 check_result(intersection_output, caseid, g1, g2, expected_count,
207 expected_holes_count, expected_point_count, expected_length_or_area,
208 settings);
209
210 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
211 // Check variant behaviour
212 intersection_output.clear();
213 bg::intersection(boost::variant<G1>(g1), g2, intersection_output);
214
215 check_result(intersection_output, caseid, g1, g2, expected_count,
216 expected_holes_count, expected_point_count, expected_length_or_area,
217 settings);
218
219 intersection_output.clear();
220 bg::intersection(g1, boost::variant<G2>(g2), intersection_output);
221
222 check_result(intersection_output, caseid, g1, g2, expected_count,
223 expected_holes_count, expected_point_count, expected_length_or_area,
224 settings);
225
226 intersection_output.clear();
227 bg::intersection(boost::variant<G1>(g1), boost::variant<G2>(g2), intersection_output);
228
229 check_result(intersection_output, caseid, g1, g2, expected_count,
230 expected_holes_count, expected_point_count, expected_length_or_area,
231 settings);
232 #endif
233
234 #if defined(TEST_WITH_SVG)
235 {
236 bool const is_line = bg::geometry_id<OutputType>::type::value == 2;
237 typedef typename bg::coordinate_type<G1>::type coordinate_type;
238
239 bool const ccw =
240 bg::point_order<G1>::value == bg::counterclockwise
241 || bg::point_order<G2>::value == bg::counterclockwise;
242 bool const open =
243 bg::closure<G1>::value == bg::open
244 || bg::closure<G2>::value == bg::open;
245
246 std::ostringstream filename;
247 filename << "intersection_"
248 << caseid << "_"
249 << string_from_type<coordinate_type>::name()
250 << string_from_type<CalculationType>::name()
251 << (ccw ? "_ccw" : "")
252 << (open ? "_open" : "")
253 #if defined(BOOST_GEOMETRY_USE_RESCALING)
254 << "_rescaled"
255 #endif
256 << ".svg";
257
258 std::ofstream svg(filename.str().c_str());
259
260 bg::svg_mapper<point_type> mapper(svg, 500, 500);
261
262 mapper.add(g1);
263 mapper.add(g2);
264
265 mapper.map(g1, is_line
266 ? "opacity:0.6;stroke:rgb(0,255,0);stroke-width:5"
267 : "fill-opacity:0.5;fill:rgb(153,204,0);"
268 "stroke:rgb(153,204,0);stroke-width:3");
269 mapper.map(g2, "fill-opacity:0.3;fill:rgb(51,51,153);"
270 "stroke:rgb(51,51,153);stroke-width:3");
271
272 for (typename result_type::const_iterator it = intersection_output.begin();
273 it != intersection_output.end(); ++it)
274 {
275 mapper.map(*it, "fill-opacity:0.2;stroke-opacity:0.4;fill:rgb(255,0,0);"
276 "stroke:rgb(255,0,255);stroke-width:8");
277 }
278 }
279 #endif
280
281
282 if (settings.debug)
283 {
284 std::cout << "end case " << caseid << std::endl;
285 }
286
287 return length_or_area;
288 }
289
290 template <typename OutputType, typename CalculationType, typename G1, typename G2>
test_intersection(std::string const & caseid,G1 const & g1,G2 const & g2,std::size_t expected_count=0,int expected_point_count=0,double expected_length_or_area=0,ut_settings const & settings=ut_settings ())291 typename bg::default_area_result<G1>::type test_intersection(std::string const& caseid,
292 G1 const& g1, G2 const& g2,
293 std::size_t expected_count = 0, int expected_point_count = 0,
294 double expected_length_or_area = 0,
295 ut_settings const& settings = ut_settings())
296 {
297 return test_intersection<OutputType, CalculationType>(
298 caseid, g1, g2, expected_count, 0, expected_point_count,
299 expected_length_or_area, settings
300 );
301 }
302
303 template <typename OutputType, typename G1, typename G2>
test_one(std::string const & caseid,std::string const & wkt1,std::string const & wkt2,std::size_t expected_count=0,std::size_t expected_holes_count=0,int expected_point_count=0,double expected_length_or_area=0,ut_settings const & settings=ut_settings ())304 typename bg::default_area_result<G1>::type test_one(std::string const& caseid,
305 std::string const& wkt1, std::string const& wkt2,
306 std::size_t expected_count = 0, std::size_t expected_holes_count = 0,
307 int expected_point_count = 0, double expected_length_or_area = 0,
308 ut_settings const& settings = ut_settings())
309 {
310 G1 g1;
311 bg::read_wkt(wkt1, g1);
312
313 G2 g2;
314 bg::read_wkt(wkt2, g2);
315
316 // Reverse if necessary
317 bg::correct(g1);
318 bg::correct(g2);
319
320 return test_intersection<OutputType, void>(caseid, g1, g2,
321 expected_count, expected_holes_count, expected_point_count,
322 expected_length_or_area, settings);
323 }
324
325 template <typename OutputType, typename G1, typename G2>
test_one(std::string const & caseid,std::string const & wkt1,std::string const & wkt2,std::size_t expected_count=0,int expected_point_count=0,double expected_length_or_area=0,ut_settings const & settings=ut_settings ())326 typename bg::default_area_result<G1>::type test_one(std::string const& caseid,
327 std::string const& wkt1, std::string const& wkt2,
328 std::size_t expected_count = 0, int expected_point_count = 0,
329 double expected_length_or_area = 0,
330 ut_settings const& settings = ut_settings())
331 {
332 return test_one<OutputType, G1, G2>(caseid, wkt1, wkt2,
333 expected_count, 0, expected_point_count,
334 expected_length_or_area,
335 settings);
336 }
337
338 template <typename OutputType, typename Areal, typename Linear>
test_one_lp(std::string const & caseid,std::string const & wkt_areal,std::string const & wkt_linear,std::size_t expected_count=0,int expected_point_count=0,double expected_length=0,ut_settings const & settings=ut_settings ())339 void test_one_lp(std::string const& caseid,
340 std::string const& wkt_areal, std::string const& wkt_linear,
341 std::size_t expected_count = 0, int expected_point_count = 0,
342 double expected_length = 0,
343 ut_settings const& settings = ut_settings())
344 {
345 #ifdef BOOST_GEOMETRY_TEST_DEBUG
346 std::cout << caseid << " -- start" << std::endl;
347 #endif
348 Areal areal;
349 bg::read_wkt(wkt_areal, areal);
350 bg::correct(areal);
351
352 Linear linear;
353 bg::read_wkt(wkt_linear, linear);
354
355 test_intersection<OutputType, void>(caseid, areal, linear,
356 expected_count, expected_point_count,
357 expected_length, settings);
358
359 // A linestring reversed should deliver exactly the same.
360 bg::reverse(linear);
361
362 test_intersection<OutputType, void>(caseid + "_rev", areal, linear,
363 expected_count, expected_point_count,
364 expected_length, settings);
365 #ifdef BOOST_GEOMETRY_TEST_DEBUG
366 std::cout << caseid << " -- end" << std::endl;
367 #endif
368 }
369
370 template <typename Geometry1, typename Geometry2>
test_point_output(std::string const & wkt1,std::string const & wkt2,unsigned int expected_count)371 void test_point_output(std::string const& wkt1, std::string const& wkt2, unsigned int expected_count)
372 {
373 Geometry1 g1;
374 bg::read_wkt(wkt1, g1);
375 bg::correct(g1);
376
377 Geometry2 g2;
378 bg::read_wkt(wkt2, g2);
379 bg::correct(g2);
380
381 bg::model::multi_point<typename bg::point_type<Geometry1>::type> points;
382 bg::intersection(g1, g2, points);
383 BOOST_CHECK_EQUAL(points.size(), expected_count);
384 }
385
386
387 #endif
388