1
// Boost.Geometry (aka GGL, Generic Geometry Library)
4
// Copyright (c) 2010-2012 Barend Gehrels, Amsterdam, the Netherlands.
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)
17
#include <boost/type_traits/is_same.hpp>
20
# include <boost/geometry/extensions/contrib/ttmath_stub.hpp>
23
#include <geometry_test_common.hpp>
26
// #define BOOST_GEOMETRY_DEBUG_ENRICH
27
//#define BOOST_GEOMETRY_DEBUG_RELATIVE_ORDER
29
// #define BOOST_GEOMETRY_REPORT_OVERLAY_ERROR
30
// #define BOOST_GEOMETRY_DEBUG_SEGMENT_IDENTIFIER
33
#define BOOST_GEOMETRY_TEST_OVERLAY_NOT_EXCHANGED
35
#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
36
# define BOOST_GEOMETRY_DEBUG_IDENTIFIER
39
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
40
#include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
41
#include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
42
#include <boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp>
44
#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
45
#include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
46
#include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
48
#include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
51
#include <boost/geometry/algorithms/area.hpp>
52
#include <boost/geometry/algorithms/correct.hpp>
54
#include <boost/geometry/geometries/geometries.hpp>
56
#include <boost/geometry/io/wkt/read.hpp>
57
#include <boost/geometry/io/wkt/write.hpp>
60
#if defined(TEST_WITH_SVG)
61
# include <boost/geometry/extensions/io/svg/svg_mapper.hpp>
64
#include <boost/geometry/strategies/strategies.hpp>
66
#include <algorithms/overlay/overlay_cases.hpp>
68
static inline std::string operation(int d)
70
return d == 1 ? "union" : "intersection";
78
typename G1, typename G2,
79
bg::detail::overlay::operation_type Direction,
80
bool Reverse1, bool Reverse2
85
static void apply(std::string const& id,
86
int expected_count, double expected_area,
87
G1 const& g1, G2 const& g2,
90
// DEBUG ONE or FEW CASE(S) ONLY
91
//if (! boost::contains(id, "36") || Direction != 1) return;
92
//if (! boost::contains(id, "iet_") || boost::contains(id, "st")) return;
93
//if (! boost::contains(id, "66") || Direction != 1) return;
94
//if (! boost::contains(id, "92") && ! boost::contains(id, "96") ) return;
95
//if (! (boost::contains(id, "58_st") || boost::contains(id, "59_st") || boost::contains(id, "60_st") || boost::contains(id, "83")) ) return;
96
//if (! (boost::contains(id, "81") || boost::contains(id, "82") || boost::contains(id, "84") || boost::contains(id, "85") || boost::contains(id, "68")) ) return;
97
//if (! (boost::contains(id, "81") || boost::contains(id, "86") || boost::contains(id, "88")) ) return;
98
//if (! boost::contains(id, "58_") || Direction != 1) return;
99
//if (! boost::contains(id, "55") || Direction != 1) return;
100
//if (! boost::contains(id, "55_iet_iet") || Direction != 1) return;
101
//if (! boost::contains(id, "55_st_iet") || Direction != 1) return;
102
//if (! boost::contains(id, "55_iet_st") || Direction != 1) return;
103
//if (! boost::contains(id, "54_st_st") || Direction != 1) return;
104
//if (! boost::contains(id, "54_iet_st") || Direction != 1) return;
105
//if (! (boost::contains(id, "54_") || boost::contains(id, "55_")) || Direction != 1) return;
106
//if (Direction != 1) return;
110
/*** FOR REVERSING ONLY
112
// If one or both are invalid (e.g. ccw),
113
// they can be corrected by uncommenting this section
118
std::cout << std::setprecision(12)
119
<< bg::wkt(cg1) << std::endl
120
<< bg::wkt(cg2) << std::endl;
124
#if defined(BOOST_GEOMETRY_DEBUG_OVERLAY) || defined(BOOST_GEOMETRY_DEBUG_ENRICH)
126
bg::point_order<G1>::value == bg::counterclockwise
127
|| bg::point_order<G2>::value == bg::counterclockwise;
129
std::cout << std::endl
132
<< (ccw ? "_ccw" : "")
133
<< " " << string_from_type<typename bg::coordinate_type<G1>::type>::name()
134
<< "(" << operation(Direction) << ")" << std::endl;
136
//std::cout << bg::area(g1) << " " << bg::area(g2) << std::endl;
139
typedef typename bg::strategy::side::services::default_strategy
141
typename bg::cs_tag<G1>::type
142
>::type side_strategy_type;
145
typedef bg::detail::overlay::traversal_turn_info
147
typename bg::point_type<G2>::type
149
std::vector<turn_info> turns;
151
bg::detail::get_turns::no_interrupt_policy policy;
152
bg::get_turns<Reverse1, Reverse2, bg::detail::overlay::calculate_distance_policy>(g1, g2, turns, policy);
153
bg::enrich_intersection_points<Reverse1, Reverse2>(turns,
154
Direction == 1 ? bg::detail::overlay::operation_union
155
: bg::detail::overlay::operation_intersection,
156
g1, g2, side_strategy_type());
158
typedef bg::model::ring<typename bg::point_type<G2>::type> ring_type;
159
typedef std::vector<ring_type> out_vector;
163
bg::detail::overlay::traverse
167
>::apply(g1, g2, Direction, turns, v);
169
// Check number of resulting rings
170
BOOST_CHECK_MESSAGE(expected_count == boost::size(v),
172
<< " #shapes expected: " << expected_count
173
<< " detected: " << boost::size(v)
174
<< " type: " << string_from_type
175
<typename bg::coordinate_type<G1>::type>::name()
178
// Check total area of resulting rings
179
typename bg::default_area_result<G1>::type total_area = 0;
180
BOOST_FOREACH(ring_type const& ring, v)
182
total_area += bg::area(ring);
183
//std::cout << bg::wkt(ring) << std::endl;
186
BOOST_CHECK_CLOSE(expected_area, total_area, precision);
188
#if defined(TEST_WITH_SVG)
190
std::ostringstream filename;
191
filename << "traverse_" << operation(Direction)
193
<< "_" << string_from_type<typename bg::coordinate_type<G1>::type>::name()
196
std::ofstream svg(filename.str().c_str());
198
bg::svg_mapper<typename bg::point_type<G2>::type> mapper(svg, 500, 500);
202
// Input shapes in green/blue
203
mapper.map(g1, "fill-opacity:0.5;fill:rgb(153,204,0);"
204
"stroke:rgb(153,204,0);stroke-width:3");
205
mapper.map(g2, "fill-opacity:0.3;fill:rgb(51,51,153);"
206
"stroke:rgb(51,51,153);stroke-width:3");
208
// Traversal rings in magenta outline/red fill -> over blue/green this gives brown
209
BOOST_FOREACH(ring_type const& ring, v)
211
mapper.map(ring, "fill-opacity:0.2;stroke-opacity:0.4;fill:rgb(255,0,0);"
212
"stroke:rgb(255,0,255);stroke-width:8");
215
// turn points in orange, + enrichment/traversal info
216
typedef typename bg::coordinate_type<G1>::type coordinate_type;
218
// Simple map to avoid two texts at same place (note that can still overlap!)
219
std::map<std::pair<int, int>, int> offsets;
221
int const margin = 5;
223
BOOST_FOREACH(turn_info const& turn, turns)
226
mapper.map(turn.point, "fill:rgb(255,128,0);"
227
"stroke:rgb(0,0,0);stroke-width:1", 3);
230
coordinate_type half = 0.5;
231
coordinate_type ten = 10;
232
// Map characteristics
233
// Create a rounded off point
234
std::pair<int, int> p
236
boost::numeric_cast<int>(half
237
+ ten * bg::get<0>(turn.point)),
238
boost::numeric_cast<int>(half
239
+ ten * bg::get<1>(turn.point))
241
std::string style = "fill:rgb(0,0,0);font-family:Arial;font-size:10px";
245
style = "fill:rgb(92,92,92);font-family:Arial;font-size:6px";
249
//if (! turn.is_discarded() && ! turn.blocked() && ! turn.both(bg::detail::overlay::operation_union))
250
//if (! turn.discarded)
252
std::ostringstream out;
254
<< ": " << bg::method_char(turn.method)
256
<< "op: " << bg::operation_char(turn.operations[0].operation)
257
<< " / " << bg::operation_char(turn.operations[1].operation)
258
<< (turn.is_discarded() ? " (discarded) " : turn.blocked() ? " (blocked)" : "")
261
if (turn.operations[0].enriched.next_ip_index != -1)
263
out << "ip: " << turn.operations[0].enriched.next_ip_index;
267
out << "vx: " << turn.operations[0].enriched.travels_to_vertex_index
268
<< " -> ip: " << turn.operations[0].enriched.travels_to_ip_index;
271
if (turn.operations[1].enriched.next_ip_index != -1)
273
out << "ip: " << turn.operations[1].enriched.next_ip_index;
277
out << "vx: " << turn.operations[1].enriched.travels_to_vertex_index
278
<< " -> ip: " << turn.operations[1].enriched.travels_to_ip_index;
285
<< std::setprecision(3)
286
<< "dist: " << boost::numeric_cast<double>(turn.operations[0].enriched.distance)
287
<< " / " << boost::numeric_cast<double>(turn.operations[1].enriched.distance)
289
<< "vis: " << bg::visited_char(turn.operations[0].visited)
290
<< " / " << bg::visited_char(turn.operations[1].visited);
295
<< ": " << bg::operation_char(turn.operations[0].operation)
296
<< " " << bg::operation_char(turn.operations[1].operation)
297
<< " (" << bg::method_char(turn.method) << ")"
298
<< (turn.ignore() ? " (ignore) " : " ")
301
<< "ip: " << turn.operations[0].enriched.travels_to_ip_index
302
<< "/" << turn.operations[1].enriched.travels_to_ip_index;
304
if (turn.operations[0].enriched.next_ip_index != -1
305
|| turn.operations[1].enriched.next_ip_index != -1)
307
out << " [" << turn.operations[0].enriched.next_ip_index
308
<< "/" << turn.operations[1].enriched.next_ip_index
316
<< "vx:" << turn.operations[0].enriched.travels_to_vertex_index
317
<< "/" << turn.operations[1].enriched.travels_to_vertex_index
320
<< std::setprecision(3)
321
<< "dist: " << turn.operations[0].enriched.distance
322
<< " / " << turn.operations[1].enriched.distance
328
offsets[p] += lineheight;
329
int offset = offsets[p];
330
offsets[p] += lineheight * 3;
331
mapper.text(turn.point, out.str(), style, margin, offset, lineheight);
344
typename G1, typename G2,
345
bg::detail::overlay::operation_type Direction,
346
bool Reverse1 = false,
347
bool Reverse2 = false
351
typedef detail::test_traverse
353
G1, G2, Direction, Reverse1, Reverse2
354
> detail_test_traverse;
356
inline static void apply(std::string const& id, int expected_count, double expected_area,
357
std::string const& wkt1, std::string const& wkt2,
358
double precision = 0.001)
360
if (wkt1.empty() || wkt2.empty())
366
bg::read_wkt(wkt1, g1);
369
bg::read_wkt(wkt2, g2);
374
//std::cout << bg::wkt(g1) << std::endl;
375
//std::cout << bg::wkt(g2) << std::endl;
377
// Try the overlay-function in both ways
378
std::string caseid = id;
379
//goto case_reversed;
381
#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
382
std::cout << std::endl << std::endl << "# " << caseid << std::endl;
384
detail_test_traverse::apply(caseid, expected_count, expected_area, g1, g2, precision);
386
#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
391
#if ! defined(BOOST_GEOMETRY_TEST_OVERLAY_NOT_EXCHANGED)
392
caseid = id + "_rev";
393
#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
394
std::cout << std::endl << std::endl << "# " << caseid << std::endl;
397
detail_test_traverse::apply(caseid, expected_count, expected_area, g2, g1, precision);
402
#if ! defined(BOOST_GEOMETRY_TEST_MULTI)
403
template <typename T>
404
void test_all(bool test_self_tangencies = true, bool test_mixed = false)
406
using namespace bg::detail::overlay;
408
typedef bg::model::point<T, 2, bg::cs::cartesian> P;
409
typedef bg::model::polygon<P> polygon;
410
typedef bg::model::box<P> box;
413
test_traverse<polygon, polygon, operation_intersection>::apply("1", 1, 5.4736, case_1[0], case_1[1]);
414
test_traverse<polygon, polygon, operation_intersection>::apply("2", 1, 12.0545, case_2[0], case_2[1]);
415
test_traverse<polygon, polygon, operation_intersection>::apply("3", 1, 5, case_3[0], case_3[1]);
416
test_traverse<polygon, polygon, operation_intersection>::apply("4", 1, 10.2212, case_4[0], case_4[1]);
417
test_traverse<polygon, polygon, operation_intersection>::apply("5", 2, 12.8155, case_5[0], case_5[1]);
418
test_traverse<polygon, polygon, operation_intersection>::apply("6", 1, 4.5, case_6[0], case_6[1]);
421
test_traverse<polygon, polygon, operation_intersection>::apply("7", 0, 0, case_7[0], case_7[1]);
422
test_traverse<polygon, polygon, operation_intersection>::apply("8", 0, 0, case_8[0], case_8[1]);
423
test_traverse<polygon, polygon, operation_intersection>::apply("9", 0, 0, case_9[0], case_9[1]);
424
test_traverse<polygon, polygon, operation_intersection>::apply("10", 0, 0, case_10[0], case_10[1]);
425
test_traverse<polygon, polygon, operation_intersection>::apply("11", 1, 1, case_11[0], case_11[1]);
426
test_traverse<polygon, polygon, operation_intersection>::apply("12", 2, 0.63333, case_12[0], case_12[1]);
429
test_traverse<polygon, polygon, operation_intersection>::apply("13", 0, 0, case_13[0], case_13[1]);
430
test_traverse<polygon, polygon, operation_intersection>::apply("14", 0, 0, case_14[0], case_14[1]);
431
test_traverse<polygon, polygon, operation_intersection>::apply("15", 0, 0, case_15[0], case_15[1]);
432
test_traverse<polygon, polygon, operation_intersection>::apply("16", 0, 0, case_16[0], case_16[1]);
433
test_traverse<polygon, polygon, operation_intersection>::apply("17", 1, 2, case_17[0], case_17[1]);
434
test_traverse<polygon, polygon, operation_intersection>::apply("18", 1, 2, case_18[0], case_18[1]);
437
test_traverse<polygon, polygon, operation_intersection>::apply("19", 0, 0, case_19[0], case_19[1]);
438
test_traverse<polygon, polygon, operation_intersection>::apply("20", 1, 5.5, case_20[0], case_20[1]);
439
test_traverse<polygon, polygon, operation_intersection>::apply("21", 0, 0, case_21[0], case_21[1]);
440
test_traverse<polygon, polygon, operation_intersection>::apply("22", 0, 0, case_22[0], case_22[1]);
441
test_traverse<polygon, polygon, operation_intersection>::apply("23", 1, 1.4, case_23[0], case_23[1]);
442
test_traverse<polygon, polygon, operation_intersection>::apply("24", 1, 1.0, case_24[0], case_24[1]);
445
test_traverse<polygon, polygon, operation_intersection>::apply("25", 0, 0, case_25[0], case_25[1]);
446
test_traverse<polygon, polygon, operation_intersection>::apply("26", 0, 0, case_26[0], case_26[1]);
447
test_traverse<polygon, polygon, operation_intersection>::apply("27", 1, 0.9545454, case_27[0], case_27[1]);
448
test_traverse<polygon, polygon, operation_intersection>::apply("28", 1, 0.9545454, case_28[0], case_28[1]);
449
test_traverse<polygon, polygon, operation_intersection>::apply("29", 1, 1.4, case_29[0], case_29[1]);
450
test_traverse<polygon, polygon, operation_intersection>::apply("30", 1, 0.5, case_30[0], case_30[1]);
453
test_traverse<polygon, polygon, operation_intersection>::apply("31", 0, 0, case_31[0], case_31[1]);
454
test_traverse<polygon, polygon, operation_intersection>::apply("32", 0, 0, case_32[0], case_32[1]);
455
test_traverse<polygon, polygon, operation_intersection>::apply("33", 0, 0, case_33[0], case_33[1]);
456
test_traverse<polygon, polygon, operation_intersection>::apply("34", 1, 0.5, case_34[0], case_34[1]);
457
test_traverse<polygon, polygon, operation_intersection>::apply("35", 1, 1.0, case_35[0], case_35[1]);
458
test_traverse<polygon, polygon, operation_intersection>::apply("36", 1, 1.625, case_36[0], case_36[1]);
461
test_traverse<polygon, polygon, operation_intersection>::apply("37", 2, 0.666666, case_37[0], case_37[1]);
462
test_traverse<polygon, polygon, operation_intersection>::apply("38", 2, 0.971429, case_38[0], case_38[1]);
463
test_traverse<polygon, polygon, operation_intersection>::apply("39", 1, 24, case_39[0], case_39[1]);
464
test_traverse<polygon, polygon, operation_intersection>::apply("40", 0, 0, case_40[0], case_40[1]);
465
test_traverse<polygon, polygon, operation_intersection>::apply("41", 1, 5, case_41[0], case_41[1]);
466
test_traverse<polygon, polygon, operation_intersection>::apply("42", 1, 5, case_42[0], case_42[1]);
468
// 43-48 - invalid polygons
469
//test_traverse<polygon, polygon, operation_intersection>::apply("43", 2, 0.75, case_43[0], case_43[1]);
470
//test_traverse<polygon, polygon, operation_intersection>::apply("44", 1, 44, case_44[0], case_44[1]);
471
//test_traverse<polygon, polygon, operation_intersection>::apply("45", 1, 45, case_45[0], case_45[1]);
472
//test_traverse<polygon, polygon, operation_intersection>::apply("46", 1, 46, case_46[0], case_46[1]);
473
//test_traverse<polygon, polygon, operation_intersection>::apply("47", 1, 47, case_47[0], case_47[1]);
477
test_traverse<polygon, polygon, operation_intersection>::apply("50", 0, 0, case_50[0], case_50[1]);
478
test_traverse<polygon, polygon, operation_intersection>::apply("51", 0, 0, case_51[0], case_51[1]);
479
test_traverse<polygon, polygon, operation_intersection>::apply("52", 1, 10.5, case_52[0], case_52[1]);
480
if (test_self_tangencies)
482
test_traverse<polygon, polygon, operation_intersection>::apply("53_st", 0, 0, case_53[0], case_53[1]);
484
test_traverse<polygon, polygon, operation_intersection>::apply("53_iet", 0, 0, case_53[0], case_53[2]);
486
test_traverse<polygon, polygon, operation_intersection>::apply("54_iet_iet", 1, 2, case_54[1], case_54[3]);
487
if (test_self_tangencies)
489
test_traverse<polygon, polygon, operation_intersection>::apply("54_st_iet", 1, 2, case_54[0], case_54[3]);
490
test_traverse<polygon, polygon, operation_intersection>::apply("54_iet_st", 1, 2, case_54[1], case_54[2]);
491
test_traverse<polygon, polygon, operation_intersection>::apply("54_st_st", 1, 2, case_54[0], case_54[2]);
494
if (test_self_tangencies)
497
test_traverse<polygon, polygon, operation_intersection>::apply("55_st_st", 1, 2, case_55[0], case_55[2]);
500
test_traverse<polygon, polygon, operation_intersection>::apply("55_st_iet", 1, 2, case_55[0], case_55[3]);
501
test_traverse<polygon, polygon, operation_intersection>::apply("55_iet_st", 1, 2, case_55[1], case_55[2]);
502
if (test_self_tangencies)
504
test_traverse<polygon, polygon, operation_intersection>::apply("56", 2, 4.5, case_56[0], case_56[1]);
506
test_traverse<polygon, polygon, operation_intersection>::apply("55_iet_iet", 1, 2, case_55[1], case_55[3]);
507
test_traverse<polygon, polygon, operation_intersection>::apply("57", 2, 5.9705882, case_57[0], case_57[1]);
509
if (test_self_tangencies)
511
test_traverse<polygon, polygon, operation_intersection>::apply("58_st",
512
2, 0.333333, case_58[0], case_58[1]);
513
test_traverse<polygon, polygon, operation_intersection>::apply("59_st",
514
2, 1.5416667, case_59[0], case_59[1]);
515
test_traverse<polygon, polygon, operation_intersection>::apply("60_st",
516
3, 2, case_60[0], case_60[1]);
518
test_traverse<polygon, polygon, operation_intersection>::apply("58_iet",
519
2, 0.333333, case_58[0], case_58[2]);
520
test_traverse<polygon, polygon, operation_intersection>::apply("59_iet",
521
2, 1.5416667, case_59[0], case_59[2]);
522
test_traverse<polygon, polygon, operation_intersection>::apply("60_iet",
523
3, 2, case_60[0], case_60[2]);
524
test_traverse<polygon, polygon, operation_intersection>::apply("61_st",
525
0, 0, case_61[0], case_61[1]);
527
test_traverse<polygon, polygon, operation_intersection>::apply("70",
528
2, 4, case_70[0], case_70[1]);
529
test_traverse<polygon, polygon, operation_intersection>::apply("71",
530
2, 2, case_71[0], case_71[1]);
531
test_traverse<polygon, polygon, operation_intersection>::apply("72",
532
3, 2.85, case_72[0], case_72[1]);
533
test_traverse<polygon, polygon, operation_intersection>::apply("79",
534
2, 20, case_79[0], case_79[1]);
539
// pies (went wrong when not all cases where implemented, especially some collinear (opposite) cases
540
test_traverse<polygon, polygon, operation_intersection>::apply("pie_16_4_12",
541
1, 491866.5, pie_16_4_12[0], pie_16_4_12[1]);
542
test_traverse<polygon, polygon, operation_intersection>::apply("pie_23_21_12_500",
543
2, 2363199.3313, pie_23_21_12_500[0], pie_23_21_12_500[1]);
544
test_traverse<polygon, polygon, operation_intersection>::apply("pie_23_23_3_2000",
545
2, 1867779.9349, pie_23_23_3_2000[0], pie_23_23_3_2000[1]);
546
test_traverse<polygon, polygon, operation_intersection>::apply("pie_23_16_16",
547
2, 2128893.9555, pie_23_16_16[0], pie_23_16_16[1]);
548
test_traverse<polygon, polygon, operation_intersection>::apply("pie_16_2_15_0",
549
0, 0, pie_16_2_15_0[0], pie_16_2_15_0[1]);
550
test_traverse<polygon, polygon, operation_intersection>::apply("pie_4_13_15",
551
1, 490887.06678, pie_4_13_15[0], pie_4_13_15[1]);
552
test_traverse<polygon, polygon, operation_intersection>::apply("pie_20_20_7_100",
553
2, 2183372.2718, pie_20_20_7_100[0], pie_20_20_7_100[1]);
558
test_traverse<polygon, polygon, operation_union>::apply("1", 1, 11.5264, case_1[0], case_1[1]);
559
test_traverse<polygon, polygon, operation_union>::apply("2", 1, 17.9455, case_2[0], case_2[1]);
560
test_traverse<polygon, polygon, operation_union>::apply("3", 1, 9, case_3[0], case_3[1]);
561
test_traverse<polygon, polygon, operation_union>::apply("4", 3, 17.7788, case_4[0], case_4[1]);
562
test_traverse<polygon, polygon, operation_union>::apply("5", 2, 18.4345, case_5[0], case_5[1]);
563
test_traverse<polygon, polygon, operation_union>::apply("6", 1, 9, case_6[0], case_6[1]);
566
test_traverse<polygon, polygon, operation_union>::apply("7", 1, 9, case_7[0], case_7[1]);
567
test_traverse<polygon, polygon, operation_union>::apply("8", 1, 12, case_8[0], case_8[1]);
568
test_traverse<polygon, polygon, operation_union>::apply("9", 0, 0 /*UU 2, 11*/, case_9[0], case_9[1]);
569
test_traverse<polygon, polygon, operation_union>::apply("10", 1, 9, case_10[0], case_10[1]);
570
test_traverse<polygon, polygon, operation_union>::apply("11", 1, 8, case_11[0], case_11[1]);
571
test_traverse<polygon, polygon, operation_union>::apply("12", 2, 8.36667, case_12[0], case_12[1]);
574
test_traverse<polygon, polygon, operation_union>::apply("13", 1, 4, case_13[0], case_13[1]);
575
test_traverse<polygon, polygon, operation_union>::apply("14", 1, 12, case_14[0], case_14[1]);
576
test_traverse<polygon, polygon, operation_union>::apply("15", 1, 12, case_15[0], case_15[1]);
577
test_traverse<polygon, polygon, operation_union>::apply("16", 1, 9, case_16[0], case_16[1]);
578
test_traverse<polygon, polygon, operation_union>::apply("17", 1, 8, case_17[0], case_17[1]);
579
test_traverse<polygon, polygon, operation_union>::apply("18", 1, 8, case_18[0], case_18[1]);
582
test_traverse<polygon, polygon, operation_union>::apply("19", 1, 10, case_19[0], case_19[1]);
583
test_traverse<polygon, polygon, operation_union>::apply("20", 1, 5.5, case_20[0], case_20[1]);
584
test_traverse<polygon, polygon, operation_union>::apply("21", 0, 0, case_21[0], case_21[1]);
585
test_traverse<polygon, polygon, operation_union>::apply("22", 0, 0 /*UU 2, 9.5*/, case_22[0], case_22[1]);
586
test_traverse<polygon, polygon, operation_union>::apply("23", 1, 6.1, case_23[0], case_23[1]);
587
test_traverse<polygon, polygon, operation_union>::apply("24", 1, 5.5, case_24[0], case_24[1]);
590
test_traverse<polygon, polygon, operation_union>::apply("25", 0, 0 /*UU 2, 7*/, case_25[0], case_25[1]);
591
test_traverse<polygon, polygon, operation_union>::apply("26", 0, 0 /*UU 2, 7.5 */, case_26[0], case_26[1]);
592
test_traverse<polygon, polygon, operation_union>::apply("27", 1, 8.04545, case_27[0], case_27[1]);
593
test_traverse<polygon, polygon, operation_union>::apply("28", 1, 10.04545, case_28[0], case_28[1]);
594
test_traverse<polygon, polygon, operation_union>::apply("29", 1, 8.1, case_29[0], case_29[1]);
595
test_traverse<polygon, polygon, operation_union>::apply("30", 1, 6.5, case_30[0], case_30[1]);
598
test_traverse<polygon, polygon, operation_union>::apply("31", 0, 0 /*UU 2, 4.5 */, case_31[0], case_31[1]);
599
test_traverse<polygon, polygon, operation_union>::apply("32", 0, 0 /*UU 2, 4.5 */, case_32[0], case_32[1]);
600
test_traverse<polygon, polygon, operation_union>::apply("33", 0, 0 /*UU 2, 4.5 */, case_33[0], case_33[1]);
601
test_traverse<polygon, polygon, operation_union>::apply("34", 1, 6.0, case_34[0], case_34[1]);
602
test_traverse<polygon, polygon, operation_union>::apply("35", 1, 10.5, case_35[0], case_35[1]);
603
test_traverse<polygon, polygon, operation_union>::apply("36", 1 /*UU 2*/, 14.375, case_36[0], case_36[1]);
606
test_traverse<polygon, polygon, operation_union>::apply("37", 1, 7.33333, case_37[0], case_37[1]);
607
test_traverse<polygon, polygon, operation_union>::apply("38", 1, 9.52857, case_38[0], case_38[1]);
608
test_traverse<polygon, polygon, operation_union>::apply("39", 1, 40.0, case_39[0], case_39[1]);
609
test_traverse<polygon, polygon, operation_union>::apply("40", 0, 0 /*UU 2, 11 */, case_40[0], case_40[1]);
610
test_traverse<polygon, polygon, operation_union>::apply("41", 1, 5, case_41[0], case_41[1]);
611
test_traverse<polygon, polygon, operation_union>::apply("42", 1, 5, case_42[0], case_42[1]);
614
//test_traverse<polygon, polygon, operation_union>::apply("43", 3, 8.1875, case_43[0], case_43[1]);
615
//test_traverse<polygon, polygon, operation_union>::apply("44", 1, 44, case_44[0], case_44[1]);
616
//test_traverse<polygon, polygon, operation_union>::apply("45", 1, 45, case_45[0], case_45[1]);
617
//test_traverse<polygon, polygon, operation_union>::apply("46", 1, 46, case_46[0], case_46[1]);
618
//test_traverse<polygon, polygon, operation_union>::apply("47", 1, 47, case_47[0], case_47[1]);
622
test_traverse<polygon, polygon, operation_union>::apply("50", 1, 25, case_50[0], case_50[1]);
623
test_traverse<polygon, polygon, operation_union>::apply("51", 0, 0, case_51[0], case_51[1]);
624
test_traverse<polygon, polygon, operation_union>::apply("52", 1, 15.5, case_52[0], case_52[1]);
625
if (test_self_tangencies)
627
test_traverse<polygon, polygon, operation_union>::apply("53_st", 2, 16, case_53[0], case_53[1]);
629
test_traverse<polygon, polygon, operation_union>::apply("53_iet",
630
2, 16, case_53[0], case_53[2]);
631
if (test_self_tangencies)
633
// The st_st version might generate one ring with area zero, which is OK
634
test_traverse<polygon, polygon, operation_union>::apply("54_st_st", 3, 20, case_54[0], case_54[2]);
635
test_traverse<polygon, polygon, operation_union>::apply("54_st_iet", 2, 20, case_54[0], case_54[3]);
636
test_traverse<polygon, polygon, operation_union>::apply("54_iet_st", 2, 20, case_54[1], case_54[2]);
638
test_traverse<polygon, polygon, operation_union>::apply("54_iet_iet", 2, 20, case_54[1], case_54[3]);
642
test_traverse<polygon, polygon, operation_union>::apply("55_st_iet", 2, 18, case_55[0], case_55[3]);
643
test_traverse<polygon, polygon, operation_union>::apply("55_iet_st", 2, 18, case_55[1], case_55[2]);
645
test_traverse<polygon, polygon, operation_union>::apply("55_iet_iet", 3, 18, case_55[1], case_55[3]);
649
if (test_self_tangencies)
651
// 55 with both input polygons having self tangencies (st_st) generates 1 correct shape
652
test_traverse<polygon, polygon, operation_union>::apply("55_st_st", 1, 18, case_55[0], case_55[2]);
653
// 55 with one of them self-tangency, other int/ext ring tangency generate 2 correct shapes
655
test_traverse<polygon, polygon, operation_union>::apply("56", 2, 14, case_56[0], case_56[1]);
657
test_traverse<polygon, polygon, operation_union>::apply("57", 1, 14.029412, case_57[0], case_57[1]);
659
if (test_self_tangencies)
661
test_traverse<polygon, polygon, operation_union>::apply("58_st",
662
4, 12.16666, case_58[0], case_58[1]);
663
test_traverse<polygon, polygon, operation_union>::apply("59_st",
664
2, 17.208333, case_59[0], case_59[1]);
665
test_traverse<polygon, polygon, operation_union>::apply("60_st",
666
3, 19, case_60[0], case_60[1]);
668
test_traverse<polygon, polygon, operation_union>::apply("58_iet",
669
4, 12.16666, case_58[0], case_58[2]);
670
test_traverse<polygon, polygon, operation_union>::apply("59_iet",
671
1, -3.791666, // 2, 17.208333), outer ring (ii/ix) is done by ASSEMBLE
672
case_59[0], case_59[2]);
673
test_traverse<polygon, polygon, operation_union>::apply("60_iet",
674
3, 19, case_60[0], case_60[2]);
675
test_traverse<polygon, polygon, operation_union>::apply("61_st",
676
1, 4, case_61[0], case_61[1]);
678
test_traverse<polygon, polygon, operation_union>::apply("70",
679
1, 9, case_70[0], case_70[1]);
680
test_traverse<polygon, polygon, operation_union>::apply("71",
681
2, 9, case_71[0], case_71[1]);
682
test_traverse<polygon, polygon, operation_union>::apply("72",
683
1, 10.65, case_72[0], case_72[1]);
688
test_traverse<polygon, polygon, operation_intersection>::apply("collinear_overlaps",
690
collinear_overlaps[0], collinear_overlaps[1]);
691
test_traverse<polygon, polygon, operation_union>::apply("collinear_overlaps",
693
collinear_overlaps[0], collinear_overlaps[1]);
695
test_traverse<polygon, polygon, operation_intersection>::apply("many_situations", 1, 184, case_many_situations[0], case_many_situations[1]);
696
test_traverse<polygon, polygon, operation_union>::apply("many_situations",
697
1, 207, case_many_situations[0], case_many_situations[1]);
700
// From "intersection piets", robustness test.
701
// This all went wrong in the past
702
// (when not all cases (get_turns) where implemented,
703
// especially important are some collinear (opposite) cases)
704
test_traverse<polygon, polygon, operation_union>::apply("pie_16_4_12",
705
1, 3669665.5, pie_16_4_12[0], pie_16_4_12[1]);
706
test_traverse<polygon, polygon, operation_union>::apply("pie_23_21_12_500",
707
1, 6295516.7185, pie_23_21_12_500[0], pie_23_21_12_500[1]);
708
test_traverse<polygon, polygon, operation_union>::apply("pie_23_23_3_2000",
709
1, 7118735.0530, pie_23_23_3_2000[0], pie_23_23_3_2000[1]);
710
test_traverse<polygon, polygon, operation_union>::apply("pie_23_16_16",
711
1, 5710474.5406, pie_23_16_16[0], pie_23_16_16[1]);
712
test_traverse<polygon, polygon, operation_union>::apply("pie_16_2_15_0",
713
1, 3833641.5, pie_16_2_15_0[0], pie_16_2_15_0[1]);
714
test_traverse<polygon, polygon, operation_union>::apply("pie_4_13_15",
715
1, 2208122.43322, pie_4_13_15[0], pie_4_13_15[1]);
716
test_traverse<polygon, polygon, operation_union>::apply("pie_20_20_7_100",
717
1, 5577158.72823, pie_20_20_7_100[0], pie_20_20_7_100[1]);
722
test_traverse<polygon, polygon, operation_union>::apply("pie_5_12_12_0_7s",
723
1, 3271710.48516, pie_5_12_12_0_7s[0], pie_5_12_12_0_7s[1]);
727
static const bool is_float
728
= boost::is_same<T, float>::value;
729
static const bool is_double
730
= boost::is_same<T, double>::value
731
|| boost::is_same<T, long double>::value;
733
static const double float_might_deviate_more = is_float ? 0.1 : 0.001; // In some cases up to 1 promille permitted
735
// GCC: does not everywhere handle float correctly (in our algorithms)
736
bool const is_float_on_non_msvc =
737
#if defined(_MSC_VER)
745
// From "Random Ellipse Stars", robustness test.
746
// This all went wrong in the past
747
// when using Determinant/ra/rb and comparing with 0/1
748
// Solved now by avoiding determinant / using sides
749
// ("hv" means "high volume")
751
double deviation = is_float ? 0.01 : 0.001;
752
test_traverse<polygon, polygon, operation_union>::apply("hv1", 1, 1624.508688461573, hv_1[0], hv_1[1], deviation);
753
test_traverse<polygon, polygon, operation_intersection>::apply("hv1", 1, 1622.7200125123809, hv_1[0], hv_1[1], deviation);
755
test_traverse<polygon, polygon, operation_union>::apply("hv2", 1, 1622.9193392726836, hv_2[0], hv_2[1], deviation);
756
test_traverse<polygon, polygon, operation_intersection>::apply("hv2", 1, 1622.1733591429329, hv_2[0], hv_2[1], deviation);
758
test_traverse<polygon, polygon, operation_union>::apply("hv3", 1, 1624.22079205664, hv_3[0], hv_3[1], deviation);
759
test_traverse<polygon, polygon, operation_intersection>::apply("hv3", 1, 1623.8265057282042, hv_3[0], hv_3[1], deviation);
764
test_traverse<polygon, polygon, operation_union>::apply("hv4", 1, 1626.5146964146334, hv_4[0], hv_4[1], deviation);
765
test_traverse<polygon, polygon, operation_intersection>::apply("hv4", 1, 1626.2580370864305, hv_4[0], hv_4[1], deviation);
766
test_traverse<polygon, polygon, operation_union>::apply("hv5", 1, 1624.2158307261871, hv_5[0], hv_5[1], deviation);
767
test_traverse<polygon, polygon, operation_intersection>::apply("hv5", 1, 1623.4506071521519, hv_5[0], hv_5[1], deviation);
770
test_traverse<polygon, polygon, operation_intersection>::apply("hv6", 1, 1604.6318757402121, hv_6[0], hv_6[1], deviation);
771
test_traverse<polygon, polygon, operation_union>::apply("hv6", 1, 1790.091872401327, hv_6[0], hv_6[1], deviation);
773
// Case 2009-12-08, needing sorting on side in enrich_intersection_points
774
test_traverse<polygon, polygon, operation_union>::apply("hv7", 1, 1624.5779453641017, hv_7[0], hv_7[1], deviation);
775
test_traverse<polygon, polygon, operation_intersection>::apply("hv7", 1, 1623.6936420295772, hv_7[0], hv_7[1], deviation);
779
// From "Random Ellipse Stars", robustness test.
780
// This all went wrong in the past when distances (see below) were zero (dz)
781
// "Distance zero", dz, means: the distance between two intersection points
782
// on a same segment is 0, therefore it can't be sorted normally, therefore
783
// the chance is 50% that the segments are not sorted correctly and the wrong
784
// decision is taken.
785
// Solved now (by sorting on sides in those cases)
787
test_traverse<polygon, polygon, operation_intersection>::apply("dz_1",
788
3, 16.887537949472005, dz_1[0], dz_1[1]);
789
test_traverse<polygon, polygon, operation_union>::apply("dz_1",
790
3, 1444.2621305732864, dz_1[0], dz_1[1]);
792
test_traverse<polygon, polygon, operation_intersection>::apply("dz_2",
793
2, 68.678921274288541, dz_2[0], dz_2[1]);
794
test_traverse<polygon, polygon, operation_union>::apply("dz_2",
795
2, 1505.4202304878663, dz_2[0], dz_2[1]);
797
test_traverse<polygon, polygon, operation_intersection>::apply("dz_3",
798
6, 192.49316937645651, dz_3[0], dz_3[1]);
799
test_traverse<polygon, polygon, operation_union>::apply("dz_3",
800
6, 1446.496005965641, dz_3[0], dz_3[1]);
802
test_traverse<polygon, polygon, operation_intersection>::apply("dz_4",
803
1, 473.59423868207693, dz_4[0], dz_4[1]);
804
test_traverse<polygon, polygon, operation_union>::apply("dz_4",
805
1, 1871.6125138873476, dz_4[0], dz_4[1]);
808
// Real-life problems
810
// SNL (Subsidiestelsel Natuur & Landschap - verAANnen)
812
if (! is_float_on_non_msvc)
814
test_traverse<polygon, polygon, operation_intersection>::apply("snl-1",
817
float_might_deviate_more);
819
test_traverse<polygon, polygon, operation_union>::apply("snl-1",
822
float_might_deviate_more);
826
// Note: values are checked with SQL Server,
828
select geometry::STGeomFromText('POLYGON((...))', 0)
829
.STIntersection(geometry::STGeomFromText('...))', 0))
835
// Boost.List during Formal Review, isovists Brandon
836
// For FP, they may deviate more.
837
test_traverse<polygon, polygon, operation_intersection>::apply("isov",
838
1, 88.1920416352664, isovist[0], isovist[1],
839
float_might_deviate_more);
840
test_traverse<polygon, polygon, operation_union>::apply("isov",
841
1, 313.360374193241, isovist[0], isovist[1],
842
float_might_deviate_more);
848
test_traverse<polygon, polygon, operation_intersection>::apply("geos_1_test_overlay",
849
1, 3461.02330171138, geos_1_test_overlay[0], geos_1_test_overlay[1]);
850
test_traverse<polygon, polygon, operation_union>::apply("geos_1_test_overlay",
851
1, 3461.31592235516, geos_1_test_overlay[0], geos_1_test_overlay[1]);
855
test_traverse<polygon, polygon, operation_intersection>::apply("geos_2",
856
2, 2.157e-6, // by bg/ttmath; sql server reports: 2.20530228034477E-06
857
geos_2[0], geos_2[1]);
859
test_traverse<polygon, polygon, operation_union>::apply("geos_2",
861
geos_2[0], geos_2[1]);
864
if (! is_float && ! is_double)
866
test_traverse<polygon, polygon, operation_intersection>::apply("geos_3",
868
geos_3[0], geos_3[1]);
871
if (! is_float_on_non_msvc)
873
// Sometimes output is reported as 29229056
874
test_traverse<polygon, polygon, operation_union>::apply("geos_3",
876
geos_3[0], geos_3[1],
877
float_might_deviate_more);
879
// Sometimes output is reported as 0.078125
880
test_traverse<polygon, polygon, operation_intersection>::apply("geos_4",
881
1, 0.0836884926070727,
882
geos_4[0], geos_4[1],
883
float_might_deviate_more);
886
test_traverse<polygon, polygon, operation_union>::apply("geos_4",
888
geos_4[0], geos_4[1]);
893
#if defined(_MSC_VER)
894
double const expected = if_typed_tt<T>(3.63794e-17, 0.0);
896
double const expected = if_typed<T, long double>(2.77555756156289135106e-17, 0.0);
899
// Calculate intersection/union of two triangles. Robustness case.
900
// ttmath can form a very small intersection triangle
901
// (which is even not accomplished by SQL Server/PostGIS)
902
std::string const caseid = "ggl_list_20110820_christophe";
903
test_traverse<polygon, polygon, operation_intersection>::apply(caseid,
905
ggl_list_20110820_christophe[0], ggl_list_20110820_christophe[1]);
906
test_traverse<polygon, polygon, operation_union>::apply(caseid,
908
ggl_list_20110820_christophe[0], ggl_list_20110820_christophe[1]);
912
template <typename T>
915
using namespace bg::detail::overlay;
917
typedef bg::model::polygon
919
bg::model::point<T, 2, bg::cs::cartesian>,
923
test_traverse<polygon, polygon, operation_intersection>::apply("open_1", 1, 5.4736,
924
open_case_1[0], open_case_1[1]);
925
test_traverse<polygon, polygon, operation_union>::apply("open_1", 1, 11.5264,
926
open_case_1[0], open_case_1[1]);
930
template <typename T>
933
using namespace bg::detail::overlay;
935
typedef bg::model::polygon
937
bg::model::point<T, 2, bg::cs::cartesian>,
941
test_traverse<polygon, polygon, operation_intersection, true, true>::apply("ccw_1", 1, 5.4736,
942
ccw_case_1[0], ccw_case_1[1]);
943
test_traverse<polygon, polygon, operation_union, true, true>::apply("ccw_1", 1, 11.5264,
944
ccw_case_1[0], ccw_case_1[1]);
949
int test_main(int, char* [])
951
#if defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
959
#if ! defined(_MSC_VER)
960
test_all<long double>();
964
test_all<ttmath_big>();