1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 // Unit Test
3
4 // Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands.
5
6 // This file was modified by Oracle on 2017.
7 // Modifications copyright (c) 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
15 #include <iostream>
16 #include <iomanip>
17 #include <fstream>
18 #include <sstream>
19 #include <string>
20
21 #include <boost/type_traits/is_same.hpp>
22
23 #if defined(TEST_WITH_SVG)
24 # include <boost/geometry/io/svg/svg_mapper.hpp>
25 #endif
26
27 #include <geometry_test_common.hpp>
28 #include <algorithms/check_validity.hpp>
29
30 #include <boost/geometry.hpp>
31 #include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
32 #include <boost/geometry/geometries/geometries.hpp>
33
34 //#include <boost/geometry/extensions/algorithms/inverse.hpp>
35
36 #if defined(TEST_WITH_SVG)
37 # include <boost/geometry/io/svg/svg_mapper.hpp>
38 #endif
39
40 #include "multi_overlay_cases.hpp"
41
42
43 #if defined(TEST_WITH_SVG)
44 template <typename Mapper>
45 struct map_visitor
46 {
map_visitormap_visitor47 map_visitor(Mapper& mapper)
48 : m_mapper(mapper)
49 , m_traverse_seq(0)
50 , m_do_output(true)
51 {}
52
printmap_visitor53 void print(char const* header)
54 {}
55
56 template <typename Turns>
printmap_visitor57 void print(char const* header, Turns const& turns, int turn_index)
58 {
59 std::string style = "fill:rgb(0,0,0);font-family:Arial;font-size:6px";
60 stream(turns, turns[turn_index], turns[turn_index].operations[0], header, style);
61 }
62
63 template <typename Turns>
printmap_visitor64 void print(char const* header, Turns const& turns, int turn_index, int op_index)
65 {
66 std::string style = "fill:rgb(0,0,0);font-family:Arial;font-size:6px";
67 stream(turns, turns[turn_index], turns[turn_index].operations[op_index], header, style);
68 }
69
70 template <typename Turns>
visit_turnsmap_visitor71 void visit_turns(int phase, Turns const& turns)
72 {
73 typedef typename boost::range_value<Turns>::type turn_type;
74 int index = 0;
75 BOOST_FOREACH(turn_type const& turn, turns)
76 {
77 switch (phase)
78 {
79 case 1 :
80 m_mapper.map(turn.point, "fill:rgb(255,128,0);"
81 "stroke:rgb(0,0,0);stroke-width:1", 3);
82 break;
83 case 11 :
84 m_mapper.map(turn.point, "fill:rgb(92,255,0);" // Greenish
85 "stroke:rgb(0,0,0);stroke-width:1", 3);
86 break;
87 case 21 :
88 m_mapper.map(turn.point, "fill:rgb(0,128,255);" // Blueish
89 "stroke:rgb(0,0,0);stroke-width:1", 3);
90 break;
91 case 3 :
92 label_turn(index, turn);
93 break;
94 }
95 index++;
96 }
97 }
98
99 template <typename Turns, typename Turn, typename Operation>
stream_turn_indexmap_visitor100 std::string stream_turn_index(Turns const& turns, Turn const& turn, Operation const& op)
101 {
102 std::ostringstream out;
103
104 if (turn.cluster_id >= 0)
105 {
106 out << "cl=" << turn.cluster_id << " ";
107 }
108
109 // Because turn index is unknown here, and still useful for debugging,
110 std::size_t index = 0;
111 for (typename Turns::const_iterator it = turns.begin();
112 it != turns.end(); ++it, ++index)
113 {
114 Turn const& t = *it;
115 if (&t == &turn)
116 {
117 out << index;
118 break;
119 }
120 }
121
122 if (&op == &turn.operations[0]) { out << "[0]"; }
123 if (&op == &turn.operations[1]) { out << "[1]"; }
124 return out.str();
125 }
126
127 template <typename Clusters, typename Turns>
visit_clustersmap_visitor128 void visit_clusters(Clusters const& clusters, Turns const& turns)
129 {
130 typedef typename boost::range_value<Turns>::type turn_type;
131 int index = 0;
132 BOOST_FOREACH(turn_type const& turn, turns)
133 {
134 if (turn.cluster_id >= 0)
135 {
136 std::cout << " TURN: " << index << " part of cluster " << turn.cluster_id << std::endl;
137 }
138 index++;
139 }
140
141 for (typename Clusters::const_iterator it = clusters.begin(); it != clusters.end(); ++it)
142 {
143 std::cout << " CLUSTER " << it->first << ": ";
144 for (typename std::set<bg::signed_size_type>::const_iterator sit
145 = it->second.turn_indices.begin();
146 sit != it->second.turn_indices.end(); ++sit)
147 {
148 std::cout << " " << *sit;
149 }
150 std::cout << std::endl;
151 }
152
153 std::cout << std::endl;
154
155 }
156
157 template <typename Turns, typename Turn, typename Operation>
visit_traversemap_visitor158 void visit_traverse(Turns const& turns, Turn const& turn, Operation const& op, const std::string& header)
159 {
160 typedef typename boost::range_value<Turns>::type turn_type;
161
162 if (! m_do_output)
163 {
164 return;
165 }
166
167 std::cout << "Visit turn " << stream_turn_index(turns, turn, op)
168 << " " << bg::operation_char(turn.operations[0].operation)
169 << bg::operation_char(turn.operations[1].operation)
170 << " (" << bg::operation_char(op.operation) << ")"
171 << " " << header << std::endl;
172
173 // Uncomment for more detailed debug info in SVG on traversal
174 std::string style
175 = header == "Visit" ? "fill:rgb(80,80,80)" : "fill:rgb(0,0,0)";
176
177 style += ";font-family:Arial;font-size:6px";
178
179 stream(turns, turn, op, header.substr(0, 1), style);
180 }
181
182 template <typename Turns, typename Turn, typename Operation>
visit_traverse_rejectmap_visitor183 void visit_traverse_reject(Turns const& turns, Turn const& turn, Operation const& op,
184 bg::detail::overlay::traverse_error_type error)
185 {
186 if (! m_do_output)
187 {
188 return;
189 }
190 std::cout << "Reject turn " << stream_turn_index(turns, turn, op)
191 << bg::operation_char(turn.operations[0].operation)
192 << bg::operation_char(turn.operations[1].operation)
193 << " (" << bg::operation_char(op.operation) << ")"
194 << " " << bg::detail::overlay::traverse_error_string(error) << std::endl;
195 //return;
196
197 std::string style = "fill:rgb(255,0,0);font-family:Arial;font-size:7px";
198 stream(turns, turn, op, bg::detail::overlay::traverse_error_string(error), style);
199
200 m_do_output = false;
201 }
202
203 template <typename Turns, typename Turn, typename Operation>
visit_traverse_select_turn_from_clustermap_visitor204 void visit_traverse_select_turn_from_cluster(Turns const& turns, Turn const& turn, Operation const& op)
205 {
206 std::cout << "Visit turn from cluster " << stream_turn_index(turns, turn, op)
207 << " " << bg::operation_char(turn.operations[0].operation)
208 << bg::operation_char(turn.operations[1].operation)
209 << " (" << bg::operation_char(op.operation) << ")"
210 << std::endl;
211 return;
212 }
213
214 template <typename Turns, typename Turn, typename Operation>
streammap_visitor215 void stream(Turns const& turns, Turn const& turn, Operation const& op, const std::string& header, const std::string& style)
216 {
217 std::ostringstream out;
218 out << m_traverse_seq++ << " " << header
219 << " " << stream_turn_index(turns, turn, op);
220
221 out << " " << bg::visited_char(op.visited);
222
223 add_text(turn, out.str(), style);
224 }
225
226 template <typename Turn>
label_operationmap_visitor227 bool label_operation(Turn const& turn, int index, std::ostream& os)
228 {
229 os << bg::operation_char(turn.operations[index].operation);
230 bool result = false;
231 if (! turn.discarded)
232 {
233 if (turn.operations[index].enriched.next_ip_index != -1)
234 {
235 os << "->" << turn.operations[index].enriched.next_ip_index;
236 if (turn.operations[index].enriched.next_ip_index != -1)
237 {
238 result = true;
239 }
240 }
241 else
242 {
243 os << "->" << turn.operations[index].enriched.travels_to_ip_index;
244 if (turn.operations[index].enriched.travels_to_ip_index != -1)
245 {
246 result = true;
247 }
248 }
249
250 os << " {" << turn.operations[index].enriched.region_id
251 << (turn.operations[index].enriched.isolated ? " ISO" : "")
252 << "}";
253
254 if (! turn.operations[index].enriched.startable)
255 {
256 os << "$";
257 }
258 }
259
260 return result;
261 }
262
263 template <typename Turn>
label_turnmap_visitor264 void label_turn(int index, Turn const& turn)
265 {
266 std::ostringstream out;
267 out << index << " ";
268 if (turn.cluster_id != -1)
269 {
270 out << " c=" << turn.cluster_id << " ";
271 }
272 bool lab1 = label_operation(turn, 0, out);
273 out << " / ";
274 bool lab2 = label_operation(turn, 1, out);
275 if (turn.discarded)
276 {
277 out << "!";
278 }
279 if (turn.has_colocated_both)
280 {
281 out << "+";
282 }
283 bool const self_turn = bg::detail::overlay::is_self_turn<bg::overlay_union>(turn);
284 if (self_turn)
285 {
286 out << "@";
287 }
288
289 std::string font8 = "font-family:Arial;font-size:6px";
290 std::string font6 = "font-family:Arial;font-size:4px";
291 std::string style = "fill:rgb(0,0,255);" + font8;
292 if (self_turn)
293 {
294 if (turn.discarded)
295 {
296 style = "fill:rgb(128,28,128);" + font6;
297 }
298 else
299 {
300 style = "fill:rgb(255,0,255);" + font8;
301 }
302 }
303 else if (turn.discarded)
304 {
305 style = "fill:rgb(92,92,92);" + font6;
306 }
307 else if (turn.cluster_id != -1)
308 {
309 style = "fill:rgb(0,0,255);" + font8;
310 }
311 else if (! lab1 || ! lab2)
312 {
313 style = "fill:rgb(0,0,255);" + font6;
314 }
315
316 add_text(turn, out.str(), style);
317 }
318
319 template <typename Turn>
add_textmap_visitor320 void add_text(Turn const& turn, std::string const& text, std::string const& style)
321 {
322 int const margin = 5;
323 int const lineheight = 6;
324 double const half = 0.5;
325 double const ten = 10;
326
327 // Map characteristics
328 // Create a rounded off point
329 std::pair<int, int> p
330 = std::make_pair(
331 boost::numeric_cast<int>(half
332 + ten * bg::get<0>(turn.point)),
333 boost::numeric_cast<int>(half
334 + ten * bg::get<1>(turn.point))
335 );
336 m_mapper.text(turn.point, text, style, margin, m_offsets[p], lineheight);
337 m_offsets[p] += lineheight;
338 }
339
340
341 Mapper& m_mapper;
342 std::map<std::pair<int, int>, int> m_offsets;
343 int m_traverse_seq;
344 bool m_do_output;
345
346 };
347 #endif
348
349 template <typename Geometry, bg::overlay_type OverlayType>
test_overlay(std::string const & caseid,std::string const & wkt1,std::string const & wkt2,double expected_area,std::size_t expected_clip_count,std::size_t expected_hole_count)350 void test_overlay(std::string const& caseid,
351 std::string const& wkt1, std::string const& wkt2,
352 double expected_area,
353 std::size_t expected_clip_count,
354 std::size_t expected_hole_count)
355 {
356 Geometry g1;
357 bg::read_wkt(wkt1, g1);
358
359 Geometry g2;
360 bg::read_wkt(wkt2, g2);
361
362 // Reverse if necessary
363 bg::correct(g1);
364 bg::correct(g2);
365
366 #if defined(TEST_WITH_SVG)
367 bool const ccw = bg::point_order<Geometry>::value == bg::counterclockwise;
368 bool const open = bg::closure<Geometry>::value == bg::open;
369
370 std::ostringstream filename;
371 filename << "overlay"
372 << "_" << caseid
373 << "_" << string_from_type<typename bg::coordinate_type<Geometry>::type>::name()
374 << (ccw ? "_ccw" : "")
375 << (open ? "_open" : "")
376 #if defined(BOOST_GEOMETRY_USE_RESCALING)
377 << "_rescaled"
378 #endif
379 << ".svg";
380
381 std::ofstream svg(filename.str().c_str());
382
383 typedef bg::svg_mapper<typename bg::point_type<Geometry>::type> svg_mapper;
384
385 svg_mapper mapper(svg, 500, 500);
386 mapper.add(g1);
387 mapper.add(g2);
388
389 // Input shapes in green (src=0) / blue (src=1)
390 mapper.map(g1, "fill-opacity:0.5;fill:rgb(153,204,0);"
391 "stroke:rgb(153,204,0);stroke-width:3");
392 mapper.map(g2, "fill-opacity:0.3;fill:rgb(51,51,153);"
393 "stroke:rgb(51,51,153);stroke-width:3");
394 #endif
395
396
397 typedef typename boost::range_value<Geometry>::type geometry_out;
398 typedef bg::detail::overlay::overlay
399 <
400 Geometry, Geometry,
401 bg::detail::overlay::do_reverse<bg::point_order<Geometry>::value>::value,
402 OverlayType == bg::overlay_difference
403 ? ! bg::detail::overlay::do_reverse<bg::point_order<Geometry>::value>::value
404 : bg::detail::overlay::do_reverse<bg::point_order<Geometry>::value>::value,
405 bg::detail::overlay::do_reverse<bg::point_order<Geometry>::value>::value,
406 geometry_out,
407 OverlayType
408 > overlay;
409
410 typedef typename bg::strategy::intersection::services::default_strategy
411 <
412 typename bg::cs_tag<Geometry>::type
413 >::type strategy_type;
414
415 strategy_type strategy;
416
417 typedef typename bg::rescale_overlay_policy_type
418 <
419 Geometry,
420 Geometry
421 >::type rescale_policy_type;
422
423 rescale_policy_type robust_policy
424 = bg::get_rescale_policy<rescale_policy_type>(g1, g2);
425
426 #if defined(TEST_WITH_SVG)
427 map_visitor<svg_mapper> visitor(mapper);
428 #else
429 bg::detail::overlay::overlay_null_visitor visitor;
430 #endif
431
432 Geometry result;
433 overlay::apply(g1, g2, robust_policy, std::back_inserter(result),
434 strategy, visitor);
435
436 std::string message;
437 bool const valid = check_validity<Geometry>::apply(result, caseid, g1, g2, message);
438 BOOST_CHECK_MESSAGE(valid,
439 "overlay: " << caseid << " not valid: " << message
440 << " type: " << (type_for_assert_message<Geometry, Geometry>()));
441
442 BOOST_CHECK_CLOSE(bg::area(result), expected_area, 0.001);
443 BOOST_CHECK_MESSAGE((bg::num_interior_rings(result) == expected_hole_count),
444 caseid
445 << " hole count: detected: " << bg::num_interior_rings(result)
446 << " expected: " << expected_hole_count);
447 BOOST_CHECK_MESSAGE((result.size() == expected_clip_count),
448 caseid
449 << " clip count: detected: " << result.size()
450 << " expected: " << expected_clip_count);
451
452 #if defined(TEST_WITH_SVG)
453 mapper.map(result, "fill-opacity:0.2;stroke-opacity:0.4;fill:rgb(255,0,0);"
454 "stroke:rgb(255,0,255);stroke-width:8");
455
456 #endif
457 }
458
459 #define TEST_INTERSECTION(caseid, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_intersection>) \
460 ( #caseid "_int", caseid[0], caseid[1], area, clips, holes)
461 #define TEST_UNION(caseid, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_union>) \
462 ( #caseid "_union", caseid[0], caseid[1], area, clips, holes)
463 #define TEST_DIFFERENCE_A(caseid, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_difference>) \
464 ( #caseid "_diff_a", caseid[0], caseid[1], area, clips, holes)
465 #define TEST_DIFFERENCE_B(caseid, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_difference>) \
466 ( #caseid "_diff_b", caseid[1], caseid[0], area, clips, holes)
467
468 #define TEST_INTERSECTION_WITH(caseid, index1, index2, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_intersection>) \
469 ( #caseid "_int_" #index1 "_" #index2, caseid[index1], caseid[index2], area, clips, holes)
470 #define TEST_UNION_WITH(caseid, index1, index2, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_union>) \
471 ( #caseid "_union" #index1 "_" #index2, caseid[index1], caseid[index2], area, clips, holes)
472
473 template <typename T, bool Clockwise>
test_all()474 void test_all()
475 {
476 typedef bg::model::point<T, 2, bg::cs::cartesian> point_type;
477 typedef bg::model::polygon<point_type, Clockwise> polygon;
478 typedef bg::model::multi_polygon<polygon> multi_polygon;
479
480 TEST_UNION(case_multi_simplex, 14.58, 1, 0);
481 TEST_INTERSECTION(case_multi_simplex, 6.42, 2, 0);
482
483 TEST_DIFFERENCE_A(case_multi_simplex, 5.58, 5, 0);
484 TEST_DIFFERENCE_B(case_multi_simplex, 2.58, 4, 0);
485
486 // Contains 5 clusters, needing immediate selection of next turn
487 TEST_UNION_WITH(case_58_multi, 0, 3, 19.8333333, 2, 0);
488
489 // Contains many clusters, needing to exclude u/u turns
490 TEST_UNION(case_recursive_boxes_3, 56.5, 17, 6);
491
492 // Contains 4 clusters, one of which having 4 turns
493 TEST_UNION(case_recursive_boxes_7, 7.0, 2, 0);
494
495 // Contains 5 clusters, needing immediate selection of next turn
496 TEST_UNION(case_89_multi, 6.0, 1, 0);
497
498 // Needs ux/next_turn_index==-1 to be filtered out
499 TEST_INTERSECTION(case_77_multi, 9.0, 5, 0);
500 TEST_UNION(case_101_multi, 22.25, 1, 3);
501 TEST_INTERSECTION(case_101_multi, 4.75, 4, 0);
502
503 TEST_INTERSECTION(case_recursive_boxes_11, 1.0, 2, 0);
504 TEST_INTERSECTION(case_recursive_boxes_30, 6.0, 4, 0);
505
506 TEST_UNION(case_recursive_boxes_4, 96.75, 1, 2);
507 TEST_INTERSECTION_WITH(case_58_multi, 2, 6, 13.25, 1, 1);
508 TEST_INTERSECTION_WITH(case_72_multi, 1, 2, 6.15, 3, 1);
509 TEST_UNION(case_recursive_boxes_12, 6.0, 6, 0);
510 TEST_UNION(case_recursive_boxes_13, 10.25, 3, 0);
511
512
513 // std::cout
514 // << " \""
515 // << bg::inverse<multi_polygon>(case_65_multi[0], 1.0)
516 // << "\"" << std::endl;
517 }
518
test_main(int,char * [])519 int test_main(int, char* [])
520 {
521 test_all<double, true>();
522 // test_all<double, false>();
523 return 0;
524 }
525