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