1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 // Unit Test
3
4 // Copyright (c) 2010-2015 Barend Gehrels, Amsterdam, the Netherlands.
5
6 // Use, modification and distribution is subject to the Boost Software License,
7 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9
10 #define BOOST_GEOMETRY_DEFINE_STREAM_OPERATOR_SEGMENT_RATIO
11 //#define BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE
12 //#define BOOST_GEOMETRY_OVERLAY_NO_THROW
13 //#define HAVE_TTMATH
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 #ifdef HAVE_TTMATH
24 # include <boost/geometry/contrib/ttmath_stub.hpp>
25 #endif
26
27 #include <geometry_test_common.hpp>
28
29
30 // #define BOOST_GEOMETRY_DEBUG_ENRICH
31 //#define BOOST_GEOMETRY_DEBUG_RELATIVE_ORDER
32
33 // #define BOOST_GEOMETRY_DEBUG_SEGMENT_IDENTIFIER
34
35
36 #define BOOST_GEOMETRY_TEST_OVERLAY_NOT_EXCHANGED
37
38 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
39 # define BOOST_GEOMETRY_DEBUG_IDENTIFIER
40 #endif
41
42 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
43 #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
44 #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
45
46 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
47 #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
48 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
49 #include <boost/geometry/algorithms/detail/overlay/overlay.hpp>
50 #include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
51
52 #include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
53
54 #include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
55
56 #include <boost/geometry/algorithms/area.hpp>
57 #include <boost/geometry/algorithms/correct.hpp>
58
59 #include <boost/geometry/geometries/geometries.hpp>
60
61 #include <boost/geometry/io/wkt/wkt.hpp>
62
63
64 #if defined(TEST_WITH_SVG)
65 # include <boost/geometry/io/svg/svg_mapper.hpp>
66 #endif
67
68 #include <boost/geometry/strategies/strategies.hpp>
69
70 #include <algorithms/overlay/overlay_cases.hpp>
71
72 template <bg::overlay_type Op>
operation()73 static inline std::string operation()
74 {
75 switch(Op)
76 {
77 case bg::overlay_union : return "union";
78 case bg::overlay_intersection : return "intersection";
79 case bg::overlay_difference : return "difference";
80 }
81 return "unknown";
82 }
83
84
85 namespace detail
86 {
87
88 template
89 <
90 typename G1, typename G2,
91 bg::overlay_type OverlayType,
92 bool Reverse1, bool Reverse2
93 >
94 struct test_traverse
95 {
96
applydetail::test_traverse97 static void apply(std::string const& id,
98 std::size_t expected_count, double expected_area,
99 G1 const& g1, G2 const& g2,
100 double precision)
101 {
102 // DEBUG ONE or FEW CASE(S) ONLY
103 //if (! boost::contains(id, "36") || Direction != 1) return;
104 //if (! boost::contains(id, "iet_") || boost::contains(id, "st")) return;
105 //if (! boost::contains(id, "66") || Direction != 1) return;
106 //if (! boost::contains(id, "92") && ! boost::contains(id, "96") ) return;
107 //if (! (boost::contains(id, "58_st") || boost::contains(id, "59_st") || boost::contains(id, "60_st") || boost::contains(id, "83")) ) return;
108 //if (! (boost::contains(id, "81") || boost::contains(id, "82") || boost::contains(id, "84") || boost::contains(id, "85") || boost::contains(id, "68")) ) return;
109 //if (! (boost::contains(id, "81") || boost::contains(id, "86") || boost::contains(id, "88")) ) return;
110 //if (! boost::contains(id, "58_") || Direction != 1) return;
111 //if (! boost::contains(id, "55") || Direction != 1) return;
112 //if (! boost::contains(id, "55_iet_iet") || Direction != 1) return;
113 //if (! boost::contains(id, "55_st_iet") || Direction != 1) return;
114 //if (! boost::contains(id, "55_iet_st") || Direction != 1) return;
115 //if (! boost::contains(id, "54_st_st") || Direction != 1) return;
116 //if (! boost::contains(id, "54_iet_st") || Direction != 1) return;
117 //if (! (boost::contains(id, "54_") || boost::contains(id, "55_")) || Direction != 1) return;
118 //if (Direction != 1) return;
119 // END DEBUG ONE ...
120
121
122 /*** FOR REVERSING ONLY
123 {
124 // If one or both are invalid (e.g. ccw),
125 // they can be corrected by uncommenting this section
126 G1 cg1 = g1;
127 G2 cg2 = g2;
128 bg::correct(cg1);
129 bg::correct(cg2);
130 std::cout << std::setprecision(12)
131 << bg::wkt(cg1) << std::endl
132 << bg::wkt(cg2) << std::endl;
133 }
134 ***/
135
136 #if defined(BOOST_GEOMETRY_DEBUG_OVERLAY) || defined(BOOST_GEOMETRY_DEBUG_ENRICH)
137 bool const ccw =
138 bg::point_order<G1>::value == bg::counterclockwise
139 || bg::point_order<G2>::value == bg::counterclockwise;
140
141 std::cout << std::endl
142 << "TRAVERSE"
143 << " " << id
144 << (ccw ? "_ccw" : "")
145 << " " << string_from_type<typename bg::coordinate_type<G1>::type>::name()
146 << "(" << OverlayType << ")" << std::endl;
147
148 //std::cout << bg::area(g1) << " " << bg::area(g2) << std::endl;
149 #endif
150
151 typedef typename bg::strategy::side::services::default_strategy
152 <
153 typename bg::cs_tag<G1>::type
154 >::type side_strategy_type;
155
156 typedef typename bg::point_type<G2>::type point_type;
157 typedef typename bg::rescale_policy_type<point_type>::type
158 rescale_policy_type;
159
160 rescale_policy_type rescale_policy
161 = bg::get_rescale_policy<rescale_policy_type>(g1, g2);
162
163 typedef bg::detail::overlay::traversal_turn_info
164 <
165 point_type,
166 typename bg::detail::segment_ratio_type<point_type, rescale_policy_type>::type
167 > turn_info;
168 std::vector<turn_info> turns;
169
170 bg::detail::overlay::operation_type const op =
171 OverlayType == bg::overlay_union
172 ? bg::detail::overlay::operation_union
173 : bg::detail::overlay::operation_intersection;
174
175 bg::detail::get_turns::no_interrupt_policy policy;
176 bg::get_turns<Reverse1, Reverse2, bg::detail::overlay::assign_null_policy>(g1, g2, rescale_policy, turns, policy);
177 bg::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turns, op,
178 g1, g2, rescale_policy, side_strategy_type());
179
180 typedef bg::model::ring<typename bg::point_type<G2>::type> ring_type;
181 typedef std::vector<ring_type> out_vector;
182 out_vector v;
183
184 bg::detail::overlay::overlay_null_visitor visitor;
185
186 bg::detail::overlay::traverse
187 <
188 Reverse1, Reverse2,
189 G1, G2
190 >::apply(g1, g2, op, rescale_policy, turns, v, visitor);
191
192 // Check number of resulting rings
193 BOOST_CHECK_MESSAGE(expected_count == boost::size(v),
194 "traverse: " << id
195 << " (" << operation<OverlayType>() << ")"
196 << " #shapes expected: " << expected_count
197 << " detected: " << boost::size(v)
198 << " type: " << string_from_type
199 <typename bg::coordinate_type<G1>::type>::name()
200 );
201
202 // Check total area of resulting rings
203 typename bg::default_area_result<G1>::type total_area = 0;
204 BOOST_FOREACH(ring_type const& ring, v)
205 {
206 total_area += bg::area(ring);
207 //std::cout << bg::wkt(ring) << std::endl;
208 }
209
210 BOOST_CHECK_CLOSE(expected_area, total_area, precision);
211
212 #if defined(TEST_WITH_SVG)
213 {
214 std::ostringstream filename;
215 filename << "traverse_" << operation<OverlayType>()
216 << "_" << id
217 << "_" << string_from_type<typename bg::coordinate_type<G1>::type>::name()
218 << ".svg";
219
220 std::ofstream svg(filename.str().c_str());
221
222 bg::svg_mapper<typename bg::point_type<G2>::type> mapper(svg, 500, 500);
223 mapper.add(g1);
224 mapper.add(g2);
225
226 // Input shapes in green (src=0) / blue (src=1)
227 mapper.map(g1, "fill-opacity:0.5;fill:rgb(153,204,0);"
228 "stroke:rgb(153,204,0);stroke-width:3");
229 mapper.map(g2, "fill-opacity:0.3;fill:rgb(51,51,153);"
230 "stroke:rgb(51,51,153);stroke-width:3");
231
232 // Traversal rings in magenta outline/red fill -> over blue/green this gives brown
233 BOOST_FOREACH(ring_type const& ring, v)
234 {
235 mapper.map(ring, "fill-opacity:0.2;stroke-opacity:0.4;fill:rgb(255,0,0);"
236 "stroke:rgb(255,0,255);stroke-width:8");
237 }
238
239 // turn points in orange, + enrichment/traversal info
240 typedef typename bg::coordinate_type<G1>::type coordinate_type;
241
242 // Simple map to avoid two texts at same place (note that can still overlap!)
243 std::map<std::pair<int, int>, int> offsets;
244 int index = 0;
245 int const margin = 5;
246
247 BOOST_FOREACH(turn_info const& turn, turns)
248 {
249 int lineheight = 8;
250 mapper.map(turn.point, "fill:rgb(255,128,0);"
251 "stroke:rgb(0,0,0);stroke-width:1", 3);
252
253 {
254 coordinate_type half = 0.5;
255 coordinate_type ten = 10;
256 // Map characteristics
257 // Create a rounded off point
258 std::pair<int, int> p
259 = std::make_pair(
260 boost::numeric_cast<int>(half
261 + ten * bg::get<0>(turn.point)),
262 boost::numeric_cast<int>(half
263 + ten * bg::get<1>(turn.point))
264 );
265 std::string style = "fill:rgb(0,0,0);font-family:Arial;font-size:8px";
266
267 if (turn.colocated)
268 {
269 style = "fill:rgb(255,0,0);font-family:Arial;font-size:8px";
270 }
271 else if (turn.discarded)
272 {
273 style = "fill:rgb(92,92,92);font-family:Arial;font-size:6px";
274 lineheight = 6;
275 }
276
277 //if (! turn.is_discarded() && ! turn.blocked() && ! turn.both(bg::detail::overlay::operation_union))
278 //if (! turn.discarded)
279 {
280 std::ostringstream out;
281 out << index
282 << ": " << bg::method_char(turn.method)
283 << std::endl
284 << "op: " << bg::operation_char(turn.operations[0].operation)
285 << " / " << bg::operation_char(turn.operations[1].operation)
286 //<< (turn.is_discarded() ? " (discarded) " : turn.blocked() ? " (blocked)" : "")
287 << std::endl;
288
289 out << "r: " << turn.operations[0].fraction
290 << " ; " << turn.operations[1].fraction
291 << std::endl;
292 if (turn.operations[0].enriched.next_ip_index != -1)
293 {
294 out << "ip: " << turn.operations[0].enriched.next_ip_index;
295 }
296 else
297 {
298 out << "vx: " << turn.operations[0].enriched.travels_to_vertex_index
299 << " -> ip: " << turn.operations[0].enriched.travels_to_ip_index;
300 }
301 out << " / ";
302 if (turn.operations[1].enriched.next_ip_index != -1)
303 {
304 out << "ip: " << turn.operations[1].enriched.next_ip_index;
305 }
306 else
307 {
308 out << "vx: " << turn.operations[1].enriched.travels_to_vertex_index
309 << " -> ip: " << turn.operations[1].enriched.travels_to_ip_index;
310 }
311
312 out << std::endl;
313
314 /*out
315
316 << std::setprecision(3)
317 << "dist: " << boost::numeric_cast<double>(turn.operations[0].enriched.distance)
318 << " / " << boost::numeric_cast<double>(turn.operations[1].enriched.distance)
319 << std::endl
320 << "vis: " << bg::visited_char(turn.operations[0].visited)
321 << " / " << bg::visited_char(turn.operations[1].visited);
322 */
323
324 /*
325 out << index
326 << ": " << bg::operation_char(turn.operations[0].operation)
327 << " " << bg::operation_char(turn.operations[1].operation)
328 << " (" << bg::method_char(turn.method) << ")"
329 << (turn.ignore() ? " (ignore) " : " ")
330 << std::endl
331
332 << "ip: " << turn.operations[0].enriched.travels_to_ip_index
333 << "/" << turn.operations[1].enriched.travels_to_ip_index;
334
335 if (turn.operations[0].enriched.next_ip_index != -1
336 || turn.operations[1].enriched.next_ip_index != -1)
337 {
338 out << " [" << turn.operations[0].enriched.next_ip_index
339 << "/" << turn.operations[1].enriched.next_ip_index
340 << "]"
341 ;
342 }
343 out << std::endl;
344
345
346 out
347 << "vx:" << turn.operations[0].enriched.travels_to_vertex_index
348 << "/" << turn.operations[1].enriched.travels_to_vertex_index
349 << std::endl
350
351 << std::setprecision(3)
352 << "dist: " << turn.operations[0].fraction
353 << " / " << turn.operations[1].fraction
354 << std::endl;
355 */
356
357
358
359 offsets[p] += lineheight;
360 int offset = offsets[p];
361 offsets[p] += lineheight * 3;
362 mapper.text(turn.point, out.str(), style, margin, offset, lineheight);
363 }
364 index++;
365 }
366 }
367 }
368 #endif
369 }
370 };
371 }
372
373 template
374 <
375 typename G1, typename G2,
376 bg::overlay_type OverlayType,
377 bool Reverse1 = false,
378 bool Reverse2 = false
379 >
380 struct test_traverse
381 {
382 typedef detail::test_traverse
383 <
384 G1, G2, OverlayType, Reverse1, Reverse2
385 > detail_test_traverse;
386
applytest_traverse387 inline static void apply(std::string const& id, std::size_t expected_count, double expected_area,
388 std::string const& wkt1, std::string const& wkt2,
389 double precision = 0.001)
390 {
391 if (wkt1.empty() || wkt2.empty())
392 {
393 return;
394 }
395
396 G1 g1;
397 bg::read_wkt(wkt1, g1);
398
399 G2 g2;
400 bg::read_wkt(wkt2, g2);
401
402 bg::correct(g1);
403 bg::correct(g2);
404
405 //std::cout << bg::wkt(g1) << std::endl;
406 //std::cout << bg::wkt(g2) << std::endl;
407
408 // Try the overlay-function in both ways
409 std::string caseid = id;
410 //goto case_reversed;
411
412 #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
413 std::cout << std::endl << std::endl << "# " << caseid << std::endl;
414 #endif
415 detail_test_traverse::apply(caseid, expected_count, expected_area, g1, g2, precision);
416
417 #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
418 return;
419 #endif
420
421 //case_reversed:
422 #if ! defined(BOOST_GEOMETRY_TEST_OVERLAY_NOT_EXCHANGED)
423 caseid = id + "_rev";
424 #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
425 std::cout << std::endl << std::endl << "# " << caseid << std::endl;
426 #endif
427
428 detail_test_traverse::apply(caseid, expected_count, expected_area, g2, g1, precision);
429 #endif
430 }
431 };
432
433 #if ! defined(BOOST_GEOMETRY_TEST_MULTI)
434 template <typename T>
test_all(bool test_self_tangencies=true,bool test_mixed=false)435 void test_all(bool test_self_tangencies = true, bool test_mixed = false)
436 {
437 typedef bg::model::point<T, 2, bg::cs::cartesian> P;
438 typedef bg::model::polygon<P> polygon;
439 //typedef bg::model::box<P> box;
440
441 typedef test_traverse
442 <
443 polygon, polygon, bg::overlay_intersection
444 > test_traverse_intersection;
445 typedef test_traverse
446 <
447 polygon, polygon, bg::overlay_union
448 > test_traverse_union;
449
450 // 1-6
451 test_traverse_intersection::apply("1", 1, 5.4736, case_1[0], case_1[1]);
452 test_traverse_intersection::apply("2", 1, 12.0545, case_2[0], case_2[1]);
453 test_traverse_intersection::apply("3", 1, 5, case_3[0], case_3[1]);
454 test_traverse_intersection::apply("4", 1, 10.2212, case_4[0], case_4[1]);
455 test_traverse_intersection::apply("5", 2, 12.8155, case_5[0], case_5[1]);
456 test_traverse_intersection::apply("6", 1, 4.5, case_6[0], case_6[1]);
457
458 // 7-12
459 test_traverse_intersection::apply("7", 0, 0, case_7[0], case_7[1]);
460 test_traverse_intersection::apply("8", 0, 0, case_8[0], case_8[1]);
461 test_traverse_intersection::apply("9", 0, 0, case_9[0], case_9[1]);
462 test_traverse_intersection::apply("10", 0, 0, case_10[0], case_10[1]);
463 test_traverse_intersection::apply("11", 1, 1, case_11[0], case_11[1]);
464 test_traverse_intersection::apply("12", 2, 0.63333, case_12[0], case_12[1]);
465
466 // 13-18
467 test_traverse_intersection::apply("13", 0, 0, case_13[0], case_13[1]);
468 test_traverse_intersection::apply("14", 0, 0, case_14[0], case_14[1]);
469 test_traverse_intersection::apply("15", 0, 0, case_15[0], case_15[1]);
470 test_traverse_intersection::apply("16", 0, 0, case_16[0], case_16[1]);
471 test_traverse_intersection::apply("17", 1, 2, case_17[0], case_17[1]);
472 test_traverse_intersection::apply("18", 1, 2, case_18[0], case_18[1]);
473
474 // 19-24
475 test_traverse_intersection::apply("19", 0, 0, case_19[0], case_19[1]);
476 test_traverse_intersection::apply("20", 1, 5.5, case_20[0], case_20[1]);
477 test_traverse_intersection::apply("21", 0, 0, case_21[0], case_21[1]);
478 test_traverse_intersection::apply("22", 0, 0, case_22[0], case_22[1]);
479 test_traverse_intersection::apply("23", 1, 1.4, case_23[0], case_23[1]);
480 test_traverse_intersection::apply("24", 1, 1.0, case_24[0], case_24[1]);
481
482 // 25-30
483 test_traverse_intersection::apply("25", 0, 0, case_25[0], case_25[1]);
484 test_traverse_intersection::apply("26", 0, 0, case_26[0], case_26[1]);
485 test_traverse_intersection::apply("27", 1, 0.9545454, case_27[0], case_27[1]);
486 test_traverse_intersection::apply("28", 1, 0.9545454, case_28[0], case_28[1]);
487 test_traverse_intersection::apply("29", 1, 1.4, case_29[0], case_29[1]);
488 test_traverse_intersection::apply("30", 1, 0.5, case_30[0], case_30[1]);
489
490 // 31-36
491 test_traverse_intersection::apply("31", 0, 0, case_31[0], case_31[1]);
492 test_traverse_intersection::apply("32", 0, 0, case_32[0], case_32[1]);
493 test_traverse_intersection::apply("33", 0, 0, case_33[0], case_33[1]);
494 test_traverse_intersection::apply("34", 1, 0.5, case_34[0], case_34[1]);
495 test_traverse_intersection::apply("35", 1, 1.0, case_35[0], case_35[1]);
496 test_traverse_intersection::apply("36", 1, 1.625, case_36[0], case_36[1]);
497
498 // 37-42
499 test_traverse_intersection::apply("37", 2, 0.666666, case_37[0], case_37[1]);
500 test_traverse_intersection::apply("38", 2, 0.971429, case_38[0], case_38[1]);
501 test_traverse_intersection::apply("39", 1, 24, case_39[0], case_39[1]);
502 test_traverse_intersection::apply("40", 0, 0, case_40[0], case_40[1]);
503 test_traverse_intersection::apply("41", 1, 5, case_41[0], case_41[1]);
504 test_traverse_intersection::apply("42", 1, 5, case_42[0], case_42[1]);
505
506 // 43-48 - invalid polygons
507 //test_traverse_intersection::apply("43", 2, 0.75, case_43[0], case_43[1]);
508 //test_traverse_intersection::apply("44", 1, 44, case_44[0], case_44[1]);
509 //test_traverse_intersection::apply("45", 1, 45, case_45[0], case_45[1]);
510 //test_traverse_intersection::apply("46", 1, 46, case_46[0], case_46[1]);
511 //test_traverse_intersection::apply("47", 1, 47, case_47[0], case_47[1]);
512
513 // 49-54
514
515 test_traverse_intersection::apply("50", 0, 0, case_50[0], case_50[1]);
516 test_traverse_intersection::apply("51", 0, 0, case_51[0], case_51[1]);
517 test_traverse_intersection::apply("52", 1, 10.5, case_52[0], case_52[1]);
518 if (test_self_tangencies)
519 {
520 test_traverse_intersection::apply("53_st", 0, 0, case_53[0], case_53[1]);
521 }
522 test_traverse_intersection::apply("53_iet", 0, 0, case_53[0], case_53[2]);
523
524 test_traverse_intersection::apply("54_iet_iet", 1, 2, case_54[1], case_54[3]);
525 if (test_self_tangencies)
526 {
527 test_traverse_intersection::apply("54_st_iet", 1, 2, case_54[0], case_54[3]);
528 test_traverse_intersection::apply("54_iet_st", 1, 2, case_54[1], case_54[2]);
529 test_traverse_intersection::apply("54_st_st", 1, 2, case_54[0], case_54[2]);
530 }
531
532 if (test_self_tangencies)
533 {
534 // 55-60
535 test_traverse_intersection::apply("55_st_st", 1, 2, case_55[0], case_55[2]);
536 }
537
538 test_traverse_intersection::apply("55_st_iet", 1, 2, case_55[0], case_55[3]);
539 test_traverse_intersection::apply("55_iet_st", 1, 2, case_55[1], case_55[2]);
540 if (test_self_tangencies)
541 {
542 test_traverse_intersection::apply("56", 2, 4.5, case_56[0], case_56[1]);
543 }
544 test_traverse_intersection::apply("55_iet_iet", 1, 2, case_55[1], case_55[3]);
545 test_traverse_intersection::apply("57", 2, 5.9705882, case_57[0], case_57[1]);
546
547 if (test_self_tangencies)
548 {
549 test_traverse_intersection::apply("58_st",
550 2, 0.333333, case_58[0], case_58[1]);
551 test_traverse_intersection::apply("59_st",
552 2, 1.5416667, case_59[0], case_59[1]);
553 test_traverse_intersection::apply("60_st",
554 3, 2, case_60[0], case_60[1]);
555 }
556 test_traverse_intersection::apply("58_iet",
557 2, 0.333333, case_58[0], case_58[2]);
558 test_traverse_intersection::apply("59_iet",
559 2, 1.5416667, case_59[0], case_59[2]);
560 test_traverse_intersection::apply("60_iet",
561 3, 2, case_60[0], case_60[2]);
562 test_traverse_intersection::apply("61_st",
563 0, 0, case_61[0], case_61[1]);
564
565 test_traverse_intersection::apply("70",
566 2, 4, case_70[0], case_70[1]);
567 test_traverse_intersection::apply("71",
568 2, 2, case_71[0], case_71[1]);
569 test_traverse_intersection::apply("72",
570 3, 2.85, case_72[0], case_72[1]);
571 test_traverse_intersection::apply("79",
572 2, 20, case_79[0], case_79[1]);
573
574 // Should be 3 shapes
575 test_traverse_intersection::apply("82a",
576 2, 2.0, case_82[0], case_82[1]);
577 // Should be 3 shapes
578 test_traverse_intersection::apply("82b",
579 2, 2.0, case_82[0], case_82[2]);
580 // other
581
582 #ifdef BOOST_GEOMETRY_TEST_FAILURES
583 // simplified version of 82, area should be different
584 // missing IP at (1.5 3.5) from (1 4,1.5 3.5,2 4)x(2 4,1 3)
585 test_traverse_intersection::apply("83",
586 1, 0.0, case_83[0], case_83[1]);
587 #endif
588
589 // pies (went wrong when not all cases where implemented, especially some collinear (opposite) cases
590 test_traverse_intersection::apply("pie_16_4_12",
591 1, 491866.5, pie_16_4_12[0], pie_16_4_12[1]);
592 test_traverse_intersection::apply("pie_23_21_12_500",
593 2, 2363199.3313, pie_23_21_12_500[0], pie_23_21_12_500[1]);
594 test_traverse_intersection::apply("pie_23_23_3_2000",
595 2, 1867779.9349, pie_23_23_3_2000[0], pie_23_23_3_2000[1]);
596 test_traverse_intersection::apply("pie_23_16_16",
597 2, 2128893.9555, pie_23_16_16[0], pie_23_16_16[1]);
598 test_traverse_intersection::apply("pie_16_2_15_0",
599 0, 0, pie_16_2_15_0[0], pie_16_2_15_0[1]);
600 test_traverse_intersection::apply("pie_4_13_15",
601 1, 490887.06678, pie_4_13_15[0], pie_4_13_15[1]);
602 test_traverse_intersection::apply("pie_20_20_7_100",
603 2, 2183372.2718, pie_20_20_7_100[0], pie_20_20_7_100[1]);
604
605
606
607 // 1-6
608 test_traverse_union::apply("1", 1, 11.5264, case_1[0], case_1[1]);
609 test_traverse_union::apply("2", 1, 17.9455, case_2[0], case_2[1]);
610 test_traverse_union::apply("3", 1, 9, case_3[0], case_3[1]);
611 test_traverse_union::apply("4", 3, 17.7788, case_4[0], case_4[1]);
612 test_traverse_union::apply("5", 2, 18.4345, case_5[0], case_5[1]);
613 test_traverse_union::apply("6", 1, 9, case_6[0], case_6[1]);
614
615 // 7-12
616 test_traverse_union::apply("7", 1, 9, case_7[0], case_7[1]);
617 test_traverse_union::apply("8", 1, 12, case_8[0], case_8[1]);
618 test_traverse_union::apply("9", 0, 0 /*UU 2, 11*/, case_9[0], case_9[1]);
619 test_traverse_union::apply("10", 1, 9, case_10[0], case_10[1]);
620 test_traverse_union::apply("11", 1, 8, case_11[0], case_11[1]);
621 test_traverse_union::apply("12", 2, 8.36667, case_12[0], case_12[1]);
622
623 // 13-18
624 test_traverse_union::apply("13", 1, 4, case_13[0], case_13[1]);
625 test_traverse_union::apply("14", 1, 12, case_14[0], case_14[1]);
626 test_traverse_union::apply("15", 1, 12, case_15[0], case_15[1]);
627 test_traverse_union::apply("16", 1, 9, case_16[0], case_16[1]);
628 test_traverse_union::apply("17", 1, 8, case_17[0], case_17[1]);
629 test_traverse_union::apply("18", 1, 8, case_18[0], case_18[1]);
630
631 // 19-24
632 test_traverse_union::apply("19", 1, 10, case_19[0], case_19[1]);
633 test_traverse_union::apply("20", 1, 5.5, case_20[0], case_20[1]);
634 test_traverse_union::apply("21", 0, 0, case_21[0], case_21[1]);
635 test_traverse_union::apply("22", 0, 0 /*UU 2, 9.5*/, case_22[0], case_22[1]);
636 test_traverse_union::apply("23", 1, 6.1, case_23[0], case_23[1]);
637 test_traverse_union::apply("24", 1, 5.5, case_24[0], case_24[1]);
638
639 // 25-30
640 test_traverse_union::apply("25", 0, 0 /*UU 2, 7*/, case_25[0], case_25[1]);
641 test_traverse_union::apply("26", 0, 0 /*UU 2, 7.5 */, case_26[0], case_26[1]);
642 test_traverse_union::apply("27", 1, 8.04545, case_27[0], case_27[1]);
643 test_traverse_union::apply("28", 1, 10.04545, case_28[0], case_28[1]);
644 test_traverse_union::apply("29", 1, 8.1, case_29[0], case_29[1]);
645 test_traverse_union::apply("30", 1, 6.5, case_30[0], case_30[1]);
646
647 // 31-36
648 test_traverse_union::apply("31", 0, 0 /*UU 2, 4.5 */, case_31[0], case_31[1]);
649 test_traverse_union::apply("32", 0, 0 /*UU 2, 4.5 */, case_32[0], case_32[1]);
650 test_traverse_union::apply("33", 0, 0 /*UU 2, 4.5 */, case_33[0], case_33[1]);
651 test_traverse_union::apply("34", 1, 6.0, case_34[0], case_34[1]);
652 test_traverse_union::apply("35", 1, 10.5, case_35[0], case_35[1]);
653 test_traverse_union::apply("36", 1 /*UU 2*/, 14.375, case_36[0], case_36[1]);
654
655 // 37-42
656 test_traverse_union::apply("37", 1, 7.33333, case_37[0], case_37[1]);
657 test_traverse_union::apply("38", 1, 9.52857, case_38[0], case_38[1]);
658 test_traverse_union::apply("39", 1, 40.0, case_39[0], case_39[1]);
659 test_traverse_union::apply("40", 0, 0 /*UU 2, 11 */, case_40[0], case_40[1]);
660 test_traverse_union::apply("41", 1, 5, case_41[0], case_41[1]);
661 test_traverse_union::apply("42", 1, 5, case_42[0], case_42[1]);
662
663 // 43-48
664 //test_traverse_union::apply("43", 3, 8.1875, case_43[0], case_43[1]);
665 //test_traverse_union::apply("44", 1, 44, case_44[0], case_44[1]);
666 //test_traverse_union::apply("45", 1, 45, case_45[0], case_45[1]);
667 //test_traverse_union::apply("46", 1, 46, case_46[0], case_46[1]);
668 //test_traverse_union::apply("47", 1, 47, case_47[0], case_47[1]);
669
670 // 49-54
671
672 test_traverse_union::apply("50", 1, 25, case_50[0], case_50[1]);
673 test_traverse_union::apply("51", 0, 0, case_51[0], case_51[1]);
674 test_traverse_union::apply("52", 1, 15.5, case_52[0], case_52[1]);
675 if (test_self_tangencies)
676 {
677 test_traverse_union::apply("53_st", 2, 16, case_53[0], case_53[1]);
678 }
679 test_traverse_union::apply("53_iet",
680 2, 16, case_53[0], case_53[2]);
681 if (test_self_tangencies)
682 {
683 test_traverse_union::apply("54_st_st", 2, 20, case_54[0], case_54[2]);
684 test_traverse_union::apply("54_st_iet", 2, 20, case_54[0], case_54[3]);
685 test_traverse_union::apply("54_iet_st", 2, 20, case_54[1], case_54[2]);
686 }
687 test_traverse_union::apply("54_iet_iet", 2, 20, case_54[1], case_54[3]);
688
689 if (test_mixed)
690 {
691 test_traverse_union::apply("55_st_iet", 2, 18, case_55[0], case_55[3]);
692 test_traverse_union::apply("55_iet_st", 2, 18, case_55[1], case_55[2]);
693 // moved to mixed
694 test_traverse_union::apply("55_iet_iet", 3, 18, case_55[1], case_55[3]);
695 }
696
697 // 55-60
698 if (test_self_tangencies)
699 {
700 // 55 with both input polygons having self tangencies (st_st) generates 1 correct shape
701 test_traverse_union::apply("55_st_st", 1, 18, case_55[0], case_55[2]);
702 // 55 with one of them self-tangency, other int/ext ring tangency generate 2 correct shapes
703
704 test_traverse_union::apply("56", 2, 14, case_56[0], case_56[1]);
705 }
706 test_traverse_union::apply("57", 1, 14.029412, case_57[0], case_57[1]);
707
708 if (test_self_tangencies)
709 {
710 test_traverse_union::apply("58_st",
711 4, 12.16666, case_58[0], case_58[1]);
712 test_traverse_union::apply("59_st",
713 2, 17.208333, case_59[0], case_59[1]);
714 test_traverse_union::apply("60_st",
715 3, 19, case_60[0], case_60[1]);
716 }
717 test_traverse_union::apply("58_iet",
718 4, 12.16666, case_58[0], case_58[2]);
719 test_traverse_union::apply("59_iet",
720 1, -3.791666, // 2, 17.208333), outer ring (ii/ix) is done by ASSEMBLE
721 case_59[0], case_59[2]);
722 test_traverse_union::apply("60_iet",
723 3, 19, case_60[0], case_60[2]);
724 test_traverse_union::apply("61_st",
725 1, 4, case_61[0], case_61[1]);
726
727 test_traverse_union::apply("70",
728 1, 9, case_70[0], case_70[1]);
729 test_traverse_union::apply("71",
730 2, 9, case_71[0], case_71[1]);
731 test_traverse_union::apply("72",
732 1, 10.65, case_72[0], case_72[1]);
733
734 // other
735 test_traverse_union::apply("box_poly5",
736 2, 4.7191,
737 "POLYGON((1.5 1.5, 1.5 2.5, 4.5 2.5, 4.5 1.5, 1.5 1.5))",
738 "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 2.5,4.5 2.5,4.5 2.3,5.0 2.3,5.0 2.1,4.5 2.1,4.5 1.9,4.0 1.9,4.5 1.2,4.9 0.8,2.9 0.7,2 1.3))");
739
740 test_traverse_intersection::apply("collinear_overlaps",
741 1, 24,
742 collinear_overlaps[0], collinear_overlaps[1]);
743 test_traverse_union::apply("collinear_overlaps",
744 1, 50,
745 collinear_overlaps[0], collinear_overlaps[1]);
746
747 test_traverse_intersection::apply("many_situations", 1, 184, case_many_situations[0], case_many_situations[1]);
748 test_traverse_union::apply("many_situations",
749 1, 207, case_many_situations[0], case_many_situations[1]);
750
751
752 // From "intersection piets", robustness test.
753 // This all went wrong in the past
754 // (when not all cases (get_turns) where implemented,
755 // especially important are some collinear (opposite) cases)
756 test_traverse_union::apply("pie_16_4_12",
757 1, 3669665.5, pie_16_4_12[0], pie_16_4_12[1]);
758 test_traverse_union::apply("pie_23_21_12_500",
759 1, 6295516.7185, pie_23_21_12_500[0], pie_23_21_12_500[1]);
760 test_traverse_union::apply("pie_23_23_3_2000",
761 1, 7118735.0530, pie_23_23_3_2000[0], pie_23_23_3_2000[1]);
762 test_traverse_union::apply("pie_23_16_16",
763 1, 5710474.5406, pie_23_16_16[0], pie_23_16_16[1]);
764 test_traverse_union::apply("pie_16_2_15_0",
765 1, 3833641.5, pie_16_2_15_0[0], pie_16_2_15_0[1]);
766 test_traverse_union::apply("pie_4_13_15",
767 1, 2208122.43322, pie_4_13_15[0], pie_4_13_15[1]);
768 test_traverse_union::apply("pie_20_20_7_100",
769 1, 5577158.72823, pie_20_20_7_100[0], pie_20_20_7_100[1]);
770
771 /*
772 if (test_not_valid)
773 {
774 test_traverse_union::apply("pie_5_12_12_0_7s",
775 1, 3271710.48516, pie_5_12_12_0_7s[0], pie_5_12_12_0_7s[1]);
776 }
777 */
778
779 static const bool is_float
780 = boost::is_same<T, float>::value;
781
782 static const double float_might_deviate_more = is_float ? 0.1 : 0.001; // In some cases up to 1 promille permitted
783
784 // GCC: does not everywhere handle float correctly (in our algorithms)
785 static bool const is_float_on_non_msvc =
786 #if defined(_MSC_VER)
787 false;
788 #else
789 is_float;
790 #endif
791
792
793
794 // From "Random Ellipse Stars", robustness test.
795 // This all went wrong in the past
796 // when using Determinant/ra/rb and comparing with 0/1
797 // Solved now by avoiding determinant / using sides
798 // ("hv" means "high volume")
799 {
800 double deviation = is_float ? 0.01 : 0.001;
801 test_traverse_union::apply("hv1", 1, 1624.508688461573, hv_1[0], hv_1[1], deviation);
802 test_traverse_intersection::apply("hv1", 1, 1622.7200125123809, hv_1[0], hv_1[1], deviation);
803
804 test_traverse_union::apply("hv2", 1, 1622.9193392726836, hv_2[0], hv_2[1], deviation);
805 test_traverse_intersection::apply("hv2", 1, 1622.1733591429329, hv_2[0], hv_2[1], deviation);
806
807 test_traverse_union::apply("hv3", 1, 1624.22079205664, hv_3[0], hv_3[1], deviation);
808 test_traverse_intersection::apply("hv3", 1, 1623.8265057282042, hv_3[0], hv_3[1], deviation);
809
810
811 if ( BOOST_GEOMETRY_CONDITION(! is_float) )
812 {
813 test_traverse_union::apply("hv4", 1, 1626.5146964146334, hv_4[0], hv_4[1], deviation);
814 test_traverse_intersection::apply("hv4", 1, 1626.2580370864305, hv_4[0], hv_4[1], deviation);
815 test_traverse_union::apply("hv5", 1, 1624.2158307261871, hv_5[0], hv_5[1], deviation);
816 test_traverse_intersection::apply("hv5", 1, 1623.4506071521519, hv_5[0], hv_5[1], deviation);
817
818 // Case 2009-12-07
819 test_traverse_intersection::apply("hv6", 1, 1604.6318757402121, hv_6[0], hv_6[1], deviation);
820 test_traverse_union::apply("hv6", 1, 1790.091872401327, hv_6[0], hv_6[1], deviation);
821
822 // Case 2009-12-08, needing sorting on side in enrich_intersection_points
823 test_traverse_union::apply("hv7", 1, 1624.5779453641017, hv_7[0], hv_7[1], deviation);
824 test_traverse_intersection::apply("hv7", 1, 1623.6936420295772, hv_7[0], hv_7[1], deviation);
825 }
826 }
827
828 // From "Random Ellipse Stars", robustness test.
829 // This all went wrong in the past when distances (see below) were zero (dz)
830 // "Distance zero", dz, means: the distance between two intersection points
831 // on a same segment is 0, therefore it can't be sorted normally, therefore
832 // the chance is 50% that the segments are not sorted correctly and the wrong
833 // decision is taken.
834 // Solved now (by sorting on sides in those cases)
835 if ( BOOST_GEOMETRY_CONDITION(! is_float_on_non_msvc) )
836 {
837 test_traverse_intersection::apply("dz_1",
838 2, 16.887537949472005, dz_1[0], dz_1[1]);
839 test_traverse_union::apply("dz_1",
840 3, 1444.2621305732864, dz_1[0], dz_1[1]);
841
842 test_traverse_intersection::apply("dz_2",
843 2, 68.678921274288541, dz_2[0], dz_2[1]);
844 test_traverse_union::apply("dz_2",
845 1, 1505.4202304878663, dz_2[0], dz_2[1]);
846
847 test_traverse_intersection::apply("dz_3",
848 5, 192.49316937645651, dz_3[0], dz_3[1]);
849 test_traverse_union::apply("dz_3",
850 5, 1446.496005965641, dz_3[0], dz_3[1]);
851
852 test_traverse_intersection::apply("dz_4",
853 1, 473.59423868207693, dz_4[0], dz_4[1]);
854 test_traverse_union::apply("dz_4",
855 1, 1871.6125138873476, dz_4[0], dz_4[1]);
856 }
857
858 // Real-life problems
859
860 // SNL (Subsidiestelsel Natuur & Landschap - verAANnen)
861
862 test_traverse_intersection::apply("snl-1",
863 2, 286.996062095888,
864 snl_1[0], snl_1[1],
865 float_might_deviate_more);
866
867 test_traverse_union::apply("snl-1",
868 2, 51997.5408506132,
869 snl_1[0], snl_1[1],
870 float_might_deviate_more);
871
872 {
873 test_traverse_intersection::apply("isov",
874 1, 88.1920, isovist[0], isovist[1],
875 float_might_deviate_more);
876 test_traverse_union::apply("isov",
877 1, 313.3604, isovist[0], isovist[1],
878 float_might_deviate_more);
879 }
880
881 if ( BOOST_GEOMETRY_CONDITION(! is_float) )
882 {
883
884 /* TODO check this BSG 2013-09-24
885 #if defined(_MSC_VER)
886 double const expected = if_typed_tt<T>(3.63794e-17, 0.0);
887 int expected_count = if_typed_tt<T>(1, 0);
888 #else
889 double const expected = if_typed<T, long double>(2.77555756156289135106e-17, 0.0);
890 int expected_count = if_typed<T, long double>(1, 0);
891 #endif
892
893 // Calculate intersection/union of two triangles. Robustness case.
894 // ttmath can form a very small intersection triangle
895 // (which is even not accomplished by SQL Server/PostGIS)
896 std::string const caseid = "ggl_list_20110820_christophe";
897 test_traverse_intersection::apply(caseid,
898 expected_count, expected,
899 ggl_list_20110820_christophe[0], ggl_list_20110820_christophe[1]);
900 test_traverse_union::apply(caseid,
901 1, 67.3550722317627,
902 ggl_list_20110820_christophe[0], ggl_list_20110820_christophe[1]);
903 */
904 }
905
906 test_traverse_union::apply("buffer_rt_f",
907 1, 4.60853,
908 buffer_rt_f[0], buffer_rt_f[1]);
909 test_traverse_intersection::apply("buffer_rt_f",
910 1, 0.0002943725152286,
911 buffer_rt_f[0], buffer_rt_f[1], 0.01);
912
913 test_traverse_union::apply("buffer_rt_g",
914 1, 16.571,
915 buffer_rt_g[0], buffer_rt_g[1]);
916
917 test_traverse_union::apply("buffer_rt_g_boxes1",
918 1, 20,
919 buffer_rt_g_boxes[0], buffer_rt_g_boxes[1]);
920 test_traverse_union::apply("buffer_rt_g_boxes2",
921 1, 24,
922 buffer_rt_g_boxes[0], buffer_rt_g_boxes[2]);
923 test_traverse_union::apply("buffer_rt_g_boxes3",
924 1, 28,
925 buffer_rt_g_boxes[0], buffer_rt_g_boxes[3]);
926
927 test_traverse_union::apply("buffer_rt_g_boxes43",
928 1, 30,
929 buffer_rt_g_boxes[4], buffer_rt_g_boxes[3]);
930
931 test_traverse_union::apply("buffer_rt_l",
932 1, 19.3995, buffer_rt_l[0], buffer_rt_l[1]);
933
934 test_traverse_union::apply("buffer_mp2",
935 1, 36.7535642, buffer_mp2[0], buffer_mp2[1], 0.01);
936 test_traverse_union::apply("collinear_opposite_rr",
937 1, 6.41, collinear_opposite_right[0], collinear_opposite_right[1]);
938 test_traverse_union::apply("collinear_opposite_ll",
939 1, 11.75, collinear_opposite_left[0], collinear_opposite_left[1]);
940 test_traverse_union::apply("collinear_opposite_ss",
941 1, 6, collinear_opposite_straight[0], collinear_opposite_straight[1]);
942 test_traverse_union::apply("collinear_opposite_lr",
943 1, 8.66, collinear_opposite_left[0], collinear_opposite_right[1]);
944 test_traverse_union::apply("collinear_opposite_rl",
945 1, 9, collinear_opposite_right[0], collinear_opposite_left[1]);
946
947 test_traverse_intersection::apply("ticket_7462", 1, 0.220582, ticket_7462[0], ticket_7462[1]);
948
949 test_traverse_intersection::apply
950 ("ticket_9081_15", 1, 0.006889578,
951 ticket_9081_15[0], ticket_9081_15[1]);
952
953 #ifdef BOOST_GEOMETRY_OVERLAY_NO_THROW
954 {
955 // NOTE: currently throws (normally)
956 std::string caseid = "ggl_list_20120229_volker";
957 test_traverse_union::apply(caseid,
958 1, 99,
959 ggl_list_20120229_volker[0], ggl_list_20120229_volker[1]);
960 test_traverse_intersection::apply(caseid,
961 1, 99,
962 ggl_list_20120229_volker[0], ggl_list_20120229_volker[1]);
963 caseid = "ggl_list_20120229_volker_2";
964 test_traverse_union::apply(caseid,
965 1, 99,
966 ggl_list_20120229_volker[2], ggl_list_20120229_volker[1]);
967 test_traverse_intersection::apply(caseid,
968 1, 99,
969 ggl_list_20120229_volker[2], ggl_list_20120229_volker[1]);
970 }
971 #endif
972 }
973
974 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
975 template <typename T>
test_open()976 void test_open()
977 {
978 typedef bg::model::polygon
979 <
980 bg::model::point<T, 2, bg::cs::cartesian>,
981 true, false
982 > polygon;
983
984 typedef test_traverse
985 <
986 polygon, polygon, bg::overlay_intersection
987 > test_traverse_intersection;
988 typedef test_traverse
989 <
990 polygon, polygon, bg::overlay_union
991 > test_traverse_union;
992
993 test_traverse_intersection::apply("open_1", 1, 5.4736,
994 open_case_1[0], open_case_1[1]);
995 test_traverse_union::apply("open_1", 1, 11.5264,
996 open_case_1[0], open_case_1[1]);
997 }
998
999
1000 template <typename T>
test_ccw()1001 void test_ccw()
1002 {
1003 typedef bg::model::polygon
1004 <
1005 bg::model::point<T, 2, bg::cs::cartesian>,
1006 false, true
1007 > polygon;
1008
1009 test_traverse<polygon, polygon, bg::overlay_intersection, true, true>::apply("ccw_1", 1, 5.4736,
1010 ccw_case_1[0], ccw_case_1[1]);
1011 test_traverse<polygon, polygon, bg::overlay_union, true, true>::apply("ccw_1", 1, 11.5264,
1012 ccw_case_1[0], ccw_case_1[1]);
1013 }
1014 #endif
1015
1016
test_main(int,char * [])1017 int test_main(int, char* [])
1018 {
1019 #if defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
1020 test_all<double>();
1021 #else
1022 test_all<float>();
1023 test_all<double>();
1024 test_open<double>();
1025 test_ccw<double>();
1026
1027 #if ! defined(_MSC_VER)
1028 test_all<long double>();
1029 #endif
1030
1031 #ifdef HAVE_TTMATH
1032 test_all<ttmath_big>();
1033 #endif
1034 #endif
1035
1036 return 0;
1037 }
1038
1039 #endif
1040