1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 // Unit Test
3 
4 // Copyright (c) 2010-2015 Barend Gehrels, Amsterdam, the Netherlands.
5 
6 // This file was modified by Oracle on 2015.
7 // Modifications copyright (c) 2015, Oracle and/or its affiliates.
8 
9 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
10 
11 // Use, modification and distribution is subject to the Boost Software License,
12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
13 // http://www.boost.org/LICENSE_1_0.txt)
14 
15 #include <iomanip>
16 #include <iostream>
17 #include <sstream>
18 #include <string>
19 
20 // If defined, tests are run without rescaling-to-integer or robustness policy
21 // Test which would fail then are disabled automatically
22 // #define BOOST_GEOMETRY_NO_ROBUSTNESS
23 
24 #include <boost/geometry/algorithms/correct.hpp>
25 #include <boost/geometry/algorithms/is_valid.hpp>
26 
27 #include <boost/geometry/io/wkt/wkt.hpp>
28 
29 #include <boost/geometry/geometries/point_xy.hpp>
30 
31 #include "test_difference.hpp"
32 #include <algorithms/test_overlay.hpp>
33 #include <algorithms/overlay/overlay_cases.hpp>
34 #include <algorithms/overlay/multi_overlay_cases.hpp>
35 
36 
37 #ifdef HAVE_TTMATH
38 #  include <boost/geometry/extensions/contrib/ttmath_stub.hpp>
39 #endif
40 
41 
42 
43 template <typename Polygon, typename LineString>
test_areal_linear()44 void test_areal_linear()
45 {
46     std::string const poly_simplex = "POLYGON((1 1,1 3,3 3,3 1,1 1))";
47     test_one_lp<LineString, LineString, Polygon>("simplex", "LINESTRING(0 2,4 2)", poly_simplex, 2, 4, 2.0);
48     test_one_lp<LineString, LineString, Polygon>("case2",  "LINESTRING(0 1,4 3)", poly_simplex, 2, 4, sqrt(5.0));
49     test_one_lp<LineString, LineString, Polygon>("case3", "LINESTRING(0 1,1 2,3 2,4 3,6 3,7 4)", "POLYGON((2 0,2 5,5 5,5 0,2 0))", 2, 6, 2.0 + 2.0 * sqrt(2.0));
50     test_one_lp<LineString, LineString, Polygon>("case4", "LINESTRING(1 1,3 2,1 3)", "POLYGON((0 0,0 4,2 4,2 0,0 0))", 1, 3, sqrt(5.0));
51 
52     test_one_lp<LineString, LineString, Polygon>("case5", "LINESTRING(0 1,3 4)", poly_simplex, 2, 4, 2.0 * sqrt(2.0));
53     test_one_lp<LineString, LineString, Polygon>("case6", "LINESTRING(1 1,10 3)", "POLYGON((2 0,2 4,3 4,3 1,4 1,4 3,5 3,5 1,6 1,6 3,7 3,7 1,8 1,8 3,9 3,9 0,2 0))", 5, 10,
54             // Pieces are 1 x 2/9:
55             5.0 * sqrt(1.0 + 4.0/81.0));
56 
57 
58     test_one_lp<LineString, LineString, Polygon>("case7", "LINESTRING(1.5 1.5,2.5 2.5)", poly_simplex, 0, 0, 0.0);
59     test_one_lp<LineString, LineString, Polygon>("case8", "LINESTRING(1 0,2 0)", poly_simplex, 1, 2, 1.0);
60 
61     std::string const poly_9 = "POLYGON((1 1,1 4,4 4,4 1,1 1))";
62     test_one_lp<LineString, LineString, Polygon>("case9", "LINESTRING(0 1,1 2,2 2)", poly_9, 1, 2, sqrt(2.0));
63     test_one_lp<LineString, LineString, Polygon>("case10", "LINESTRING(0 1,1 2,0 2)", poly_9, 1, 3, 1.0 + sqrt(2.0));
64     test_one_lp<LineString, LineString, Polygon>("case11", "LINESTRING(2 2,4 2,3 3)", poly_9, 0, 0, 0.0);
65     test_one_lp<LineString, LineString, Polygon>("case12", "LINESTRING(2 3,4 4,5 6)", poly_9, 1, 2, sqrt(5.0));
66 
67     test_one_lp<LineString, LineString, Polygon>("case13", "LINESTRING(3 2,4 4,2 3)", poly_9, 0, 0, 0.0);
68     test_one_lp<LineString, LineString, Polygon>("case14", "LINESTRING(5 6,4 4,6 5)", poly_9, 1, 3, 2.0 * sqrt(5.0));
69 
70     test_one_lp<LineString, LineString, Polygon>("case15", "LINESTRING(0 2,1 2,1 3,0 3)", poly_9, 2, 4, 2.0);
71     test_one_lp<LineString, LineString, Polygon>("case16", "LINESTRING(2 2,1 2,1 3,2 3)", poly_9, 0, 0, 0.0);
72 
73     std::string const angly = "LINESTRING(2 2,2 1,4 1,4 2,5 2,5 3,4 3,4 4,5 4,3 6,3 5,2 5,2 6,0 4)";
74     test_one_lp<LineString, LineString, Polygon>("case17", angly, "POLYGON((1 1,1 5,4 5,4 1,1 1))", 3, 11, 6.0 + 4.0 * sqrt(2.0));
75     test_one_lp<LineString, LineString, Polygon>("case18", angly, "POLYGON((1 1,1 5,5 5,5 1,1 1))", 2, 6, 2.0 + 3.0 * sqrt(2.0));
76     test_one_lp<LineString, LineString, Polygon>("case19", "LINESTRING(1 2,1 3,0 3)", poly_9, 1, 2, 1.0);
77     test_one_lp<LineString, LineString, Polygon>("case20", "LINESTRING(1 2,1 3,2 3)", poly_9, 0, 0, 0.0);
78 
79     // PROPERTIES CHANGED BY switch_to_integer
80     // TODO test_one_lp<LineString, LineString, Polygon>("case21", "LINESTRING(1 2,1 4,4 4,4 1,2 1,2 2)", poly_9, 0, 0, 0.0);
81 
82     // More collinear (opposite) cases
83     test_one_lp<LineString, LineString, Polygon>("case22", "LINESTRING(4 1,4 4,7 4)", poly_9, 1, 2, 3.0);
84     test_one_lp<LineString, LineString, Polygon>("case23", "LINESTRING(4 0,4 4,7 4)", poly_9, 2, 4, 4.0);
85     test_one_lp<LineString, LineString, Polygon>("case24", "LINESTRING(4 1,4 5,7 5)", poly_9, 1, 3, 4.0);
86     test_one_lp<LineString, LineString, Polygon>("case25", "LINESTRING(4 0,4 5,7 5)", poly_9, 2, 5, 5.0);
87     test_one_lp<LineString, LineString, Polygon>("case26", "LINESTRING(4 0,4 3,4 5,7 5)", poly_9, 2, 5, 5.0);
88     test_one_lp<LineString, LineString, Polygon>("case27", "LINESTRING(4 4,4 5,5 5)", poly_9, 1, 3, 2.0);
89 }
90 
91 template <typename CoordinateType>
test_ticket_10658(std::string const & wkt_out)92 void test_ticket_10658(std::string const& wkt_out)
93 {
94     typedef bg::model::point<CoordinateType, 2, bg::cs::cartesian> point_type;
95     typedef bg::model::polygon
96         <
97             point_type, /*ClockWise*/false, /*Closed*/false
98         > polygon_type;
99     typedef bg::model::multi_polygon<polygon_type> multipolygon_type;
100 
101     polygon_type polygon1;
102     bg::read_wkt(ticket_10658[0], polygon1);
103     polygon_type polygon2;
104     bg::read_wkt(ticket_10658[1], polygon2);
105 
106     multipolygon_type multipolygon_out;
107     bg::sym_difference(polygon1, polygon2, multipolygon_out);
108     std::stringstream stream;
109     stream << bg::wkt(multipolygon_out);
110 
111     BOOST_CHECK_EQUAL(stream.str(), wkt_out);
112 }
113 
114 template <typename CoordinateType>
test_ticket_10835(std::string const & wkt_out1,std::string const & wkt_out2)115 void test_ticket_10835(std::string const& wkt_out1, std::string const& wkt_out2)
116 {
117     typedef bg::model::point<CoordinateType, 2, bg::cs::cartesian> point_type;
118     typedef bg::model::linestring<point_type> linestring_type;
119     typedef bg::model::multi_linestring<linestring_type> multilinestring_type;
120     typedef bg::model::polygon
121         <
122             point_type, /*ClockWise*/false, /*Closed*/false
123         > polygon_type;
124 
125     multilinestring_type multilinestring;
126     bg::read_wkt(ticket_10835[0], multilinestring);
127     polygon_type polygon1;
128     bg::read_wkt(ticket_10835[1], polygon1);
129     polygon_type polygon2;
130     bg::read_wkt(ticket_10835[2], polygon2);
131 
132     multilinestring_type multilinestringOut1;
133     bg::difference(multilinestring, polygon1, multilinestringOut1);
134     std::stringstream stream;
135     stream << bg::wkt(multilinestringOut1);
136 
137     BOOST_CHECK_EQUAL(stream.str(), wkt_out1);
138 
139     multilinestring_type multilinestringOut2;
140     bg::difference(multilinestringOut1, polygon2, multilinestringOut2);
141     stream.str("");
142     stream.clear();
143     stream << bg::wkt(multilinestringOut2);
144 
145     BOOST_CHECK_EQUAL(stream.str(), wkt_out2);
146 }
147 
148 template <typename CoordinateType>
test_ticket_11121()149 void test_ticket_11121()
150 {
151     typedef bg::model::point<CoordinateType,2,bg::cs::cartesian> point_type;
152     typedef bg::model::polygon
153         <
154             point_type, /*ClockWise*/false, /*Closed*/false
155         > polygon_type;
156     typedef bg::model::multi_polygon<polygon_type> multipolygon_type;
157 
158     polygon_type polygon1;
159     bg::read_wkt(ticket_11121[0], polygon1);
160     polygon_type polygon2;
161     bg::read_wkt(ticket_11121[1], polygon2);
162 
163     multipolygon_type diff12, diff21, sym_diff;
164     bg::difference(polygon1, polygon2, diff12);
165     bg::difference(polygon2, polygon1, diff21);
166     bg::sym_difference(polygon1, polygon2, sym_diff);
167 
168     BOOST_CHECK(bg::is_valid(diff12));
169     BOOST_CHECK(bg::is_valid(diff21));
170     BOOST_CHECK(bg::is_valid(sym_diff));
171 }
172 
173 template <typename CoordinateType>
test_bug21155501()174 void test_bug21155501()
175 {
176     typedef bg::model::point<CoordinateType,2,bg::cs::cartesian> point_type;
177     typedef bg::model::polygon
178         <
179         point_type, /*ClockWise*/false, /*Closed*/false
180         > polygon_type;
181     typedef bg::model::multi_polygon<polygon_type> multipolygon_type;
182 
183     polygon_type g1;
184     bg::read_wkt("POLYGON((-8.3935546875 27.449790329784214,4.9658203125 18.729501999072138,11.8212890625 23.563987128451217,9.7119140625 25.48295117535531,9.8876953125 31.728167146023935,8.3056640625 32.99023555965106,8.5693359375 37.16031654673677,-1.8896484375 35.60371874069731,-0.5712890625 32.02670629333614,-8.9208984375 29.458731185355344,-8.3935546875 27.449790329784214))", g1);
185     multipolygon_type g2;
186     bg::read_wkt("MULTIPOLYGON(((4.9658203125 18.729501999072138,-3.4868710311820115 24.246968623627644,8.3589904332912 33.833614418115445,8.3056640625 32.99023555965106,9.8876953125 31.728167146023935,9.7119140625 25.48295117535531,11.8212890625 23.563987128451217,4.9658203125 18.729501999072138)),((-3.88714525609152 24.508246314579743,-8.3935546875 27.449790329784214,-8.9208984375 29.458731185355344,-0.5712890625 32.02670629333614,-1.8896484375 35.60371874069731,8.5693359375 37.16031654673677,8.362166569827938 33.883846345901595,-3.88714525609152 24.508246314579743)))", g2);
187     bg::correct(g1);
188     bg::correct(g2);
189 
190     multipolygon_type diff12, diff21, sym_diff;
191     bg::difference(g1, g2, diff12);
192     bg::difference(g2, g1, diff21);
193     bg::sym_difference(g1, g2, sym_diff);
194 
195     BOOST_CHECK(bg::is_valid(diff12));
196     BOOST_CHECK(bg::is_valid(diff21));
197     BOOST_CHECK(bg::is_valid(sym_diff));
198 }
199 
200 template <typename P>
test_all()201 void test_all()
202 {
203     typedef bg::model::box<P> box;
204     typedef bg::model::polygon<P> polygon;
205     typedef bg::model::linestring<P> linestring;
206     typedef bg::model::ring<P> ring;
207 
208     typedef typename bg::coordinate_type<P>::type ct;
209 
210     test_areal_linear<polygon, linestring>();
211 
212     test_one<polygon, polygon, polygon>("simplex_normal",
213         simplex_normal[0], simplex_normal[1],
214         3, 12, 2.52636706856656,
215         3, 12, 3.52636706856656);
216 
217     test_one<polygon, polygon, polygon>("simplex_with_empty",
218         simplex_normal[0], polygon_empty,
219         1, 4, 8.0,
220         0, 0, 0.0);
221 
222     test_one<polygon, polygon, polygon>(
223             "star_ring", example_star, example_ring,
224             5, 22, 1.1901714,
225             5, 27, 1.6701714);
226 
227     test_one<polygon, polygon, polygon>("two_bends",
228         two_bends[0], two_bends[1],
229         1, 5, 8.0,
230         1, 5, 8.0);
231 
232 #if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
233     test_one<polygon, polygon, polygon>("star_comb_15",
234         star_comb_15[0], star_comb_15[1],
235         30, 160, 227.658275102812,
236         30, 198, 480.485775259312);
237 #endif
238 
239     test_one<polygon, polygon, polygon>("new_hole",
240         new_hole[0], new_hole[1],
241         1, 9, 7.0,
242         1, 13, 14.0);
243 
244 
245     test_one<polygon, polygon, polygon>("crossed",
246         crossed[0], crossed[1],
247         1, 18, 19.5,
248         1, 7, 2.5);
249 
250     test_one<polygon, polygon, polygon>("disjoint",
251         disjoint[0], disjoint[1],
252         1, 5, 1.0,
253         1, 5, 1.0);
254 
255     // The too small one might be discarded (depending on point-type / compiler)
256     // We check area only
257     test_one<polygon, polygon, polygon>("distance_zero",
258         distance_zero[0], distance_zero[1],
259         -1, -1, 8.7048386,
260         -1, -1, 0.0098387,
261         0.001);
262 
263     test_one<polygon, polygon, polygon>("equal_holes_disjoint",
264         equal_holes_disjoint[0], equal_holes_disjoint[1],
265         1, 5, 9.0,
266         1, 5, 9.0);
267 
268     test_one<polygon, polygon, polygon>("only_hole_intersections1",
269         only_hole_intersections[0], only_hole_intersections[1],
270         2, 10,  1.9090909,
271         4, 16, 10.9090909);
272 
273     test_one<polygon, polygon, polygon>("only_hole_intersection2",
274         only_hole_intersections[0], only_hole_intersections[2],
275         3, 20, 30.9090909,
276         4, 16, 10.9090909);
277 
278     test_one<polygon, polygon, polygon>("first_within_second",
279         first_within_second[1], first_within_second[0],
280         1, 10, 24,
281         0, 0, 0);
282 
283     test_one<polygon, polygon, polygon>("fitting",
284         fitting[0], fitting[1],
285         1, 9, 21.0,
286         1, 4, 4.0,
287         1, 5, 25.0);
288 
289     test_one<polygon, polygon, polygon>("identical",
290         identical[0], identical[1],
291         0, 0, 0.0,
292         0, 0, 0.0);
293 
294     test_one<polygon, polygon, polygon>("intersect_exterior_and_interiors_winded",
295         intersect_exterior_and_interiors_winded[0], intersect_exterior_and_interiors_winded[1],
296         4, 20, 11.533333,
297         5, 26, 29.783333);
298 
299     test_one<polygon, polygon, polygon>("intersect_holes_intersect_and_disjoint",
300         intersect_holes_intersect_and_disjoint[0], intersect_holes_intersect_and_disjoint[1],
301         2, 16, 15.75,
302         3, 17, 6.75);
303 
304     test_one<polygon, polygon, polygon>("intersect_holes_intersect_and_touch",
305         intersect_holes_intersect_and_touch[0], intersect_holes_intersect_and_touch[1],
306         3, 21, 16.25,
307         3, 17, 6.25);
308 
309     test_one<polygon, polygon, polygon>("intersect_holes_new_ring",
310         intersect_holes_new_ring[0], intersect_holes_new_ring[1],
311         3, 15, 9.8961,
312         4, 25, 121.8961, 0.01);
313 
314     test_one<polygon, polygon, polygon>("first_within_hole_of_second",
315         first_within_hole_of_second[0], first_within_hole_of_second[1],
316         1, 5, 1,
317         1, 10, 16);
318 
319     test_one<polygon, polygon, polygon>("intersect_holes_disjoint",
320         intersect_holes_disjoint[0], intersect_holes_disjoint[1],
321         2, 14, 16.0,
322         2, 10, 6.0);
323 
324     test_one<polygon, polygon, polygon>("intersect_holes_intersect",
325         intersect_holes_intersect[0], intersect_holes_intersect[1],
326         2, 16, 15.75,
327         2, 12, 5.75);
328 
329     test_one<polygon, polygon, polygon>(
330             "case4", case_4[0], case_4[1],
331             6, 28, 2.77878787878788,
332             4, 22, 4.77878787878788);
333 
334     test_one<polygon, polygon, polygon>(
335             "case5", case_5[0], case_5[1],
336             8, 36, 2.43452380952381,
337             7, 33, 3.18452380952381);
338 
339     test_one<polygon, polygon, polygon>("winded",
340         winded[0], winded[1],
341         3, 37, 61,
342         1, 15, 13);
343 
344     test_one<polygon, polygon, polygon>("within_holes_disjoint",
345         within_holes_disjoint[0], within_holes_disjoint[1],
346         2, 15, 25,
347         1, 5, 1);
348 
349     test_one<polygon, polygon, polygon>("side_side",
350         side_side[0], side_side[1],
351         1, 5, 1,
352         1, 5, 1,
353         1, 7, 2);
354 
355 #if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
356     test_one<polygon, polygon, polygon>("buffer_mp1",
357         buffer_mp1[0], buffer_mp1[1],
358         1, 61, 10.2717,
359         1, 61, 10.2717);
360 
361     if ( BOOST_GEOMETRY_CONDITION((boost::is_same<ct, double>::value)) )
362     {
363         test_one<polygon, polygon, polygon>("buffer_mp2",
364             buffer_mp2[0], buffer_mp2[1],
365             1, 91, 12.09857,
366             1, 155, 24.19714);
367     }
368 #endif
369 
370     /*** TODO: self-tangencies for difference
371     test_one<polygon, polygon, polygon>("wrapped_a",
372         wrapped[0], wrapped[1],
373         3, 1, 61,
374         1, 0, 13);
375 
376     test_one<polygon, polygon, polygon>("wrapped_b",
377         wrapped[0], wrapped[2],
378         3, 1, 61,
379         1, 0, 13);
380     ***/
381 
382     // Isovist - the # output polygons differ per compiler/pointtype, (very) small
383     // rings might be discarded. We check area only
384     test_one<polygon, polygon, polygon>("isovist",
385         isovist1[0], isovist1[1],
386         -1, -1, 0.279132,
387         -1, -1, 224.8892,
388 #if defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
389         0.1);
390 #else
391         0.001);
392 #endif
393     // SQL Server gives:    0.279121891701124 and 224.889211358929
394     // PostGIS gives:       0.279121991127244 and 224.889205853156
395     // No robustness gives: 0.279121991127106 and 224.825363749290
396 
397 #ifdef GEOMETRY_TEST_INCLUDE_FAILING_TESTS
398     test_one<polygon, polygon, polygon>("geos_1",
399         geos_1[0], geos_1[1],
400         21, -1, 0.31640625,
401          9, -1, 0.01953125);
402 
403     // Excluded this test in the normal suite, it is OK like this for many clang/gcc/msvc
404     // versions, but NOT OK for many other clang/gcc/msvc versions on other platforms
405     // It might depend on partition (order)
406     //        10, -1, 0.02148439); // change in partition might give these results
407 
408     // SQL Server gives: 0.28937764436705 and 0.000786406897532288 with 44/35 rings
409     // PostGIS gives:    0.30859375       and 0.033203125 with 35/35 rings
410 #endif
411 
412 #if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
413     test_one<polygon, polygon, polygon>("geos_2",
414         geos_2[0], geos_2[1],
415         1, -1, 138.6923828,
416         1, -1, 211.859375,
417         0.01); // MSVC 14 expects 138.69214 and 211.85913
418 
419     test_one<polygon, polygon, polygon>("geos_3",
420         geos_3[0], geos_3[1],
421         1, -1, 16211128.5,
422         1, -1, 13180420.0,
423         1, -1, 16211128.5 + 13180420.0);
424 #endif
425 
426     test_one<polygon, polygon, polygon>("geos_4",
427         geos_4[0], geos_4[1],
428         1, -1, 971.9163115,
429         1, -1, 1332.4163115);
430 
431     test_one<polygon, polygon, polygon>("ggl_list_20110306_javier",
432         ggl_list_20110306_javier[0], ggl_list_20110306_javier[1],
433         1, -1, 71495.3331,
434         2, -1, 8960.49049,
435         2, -1, 71495.3331 + 8960.49049);
436 
437     test_one<polygon, polygon, polygon>("ggl_list_20110307_javier",
438         ggl_list_20110307_javier[0], ggl_list_20110307_javier[1],
439         1, if_typed<ct, float>(14, 13), 16815.6,
440         1, 4, 3200.4,
441         0.01);
442 
443     if ( BOOST_GEOMETRY_CONDITION((! boost::is_same<ct, float>::value)) )
444     {
445         test_one<polygon, polygon, polygon>("ggl_list_20110716_enrico",
446             ggl_list_20110716_enrico[0], ggl_list_20110716_enrico[1],
447             3, -1, 35723.8506317139,
448             1, -1, 58456.4964294434,
449             1, -1, 35723.8506317139 + 58456.4964294434);
450     }
451 
452 #if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
453     test_one<polygon, polygon, polygon>("ggl_list_20110820_christophe",
454         ggl_list_20110820_christophe[0], ggl_list_20110820_christophe[1],
455         1, -1, 2.8570121719168924,
456         1, -1, 64.498061986388564);
457 #endif
458 
459     test_one<polygon, polygon, polygon>("ggl_list_20120717_volker",
460         ggl_list_20120717_volker[0], ggl_list_20120717_volker[1],
461         1, 11, 3370866.2295081965,
462         1, 5, 384.2295081964694, 0.01);
463 
464 #if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
465     // 2011-07-02 / 2014-06-19
466     // Interesting FP-precision case.
467     // sql server gives: 6.62295817619452E-05
468     // PostGIS gives: 0.0 (no output)
469     // Boost.Geometry gave results depending on FP-type, and compiler, and operating system.
470     // Since rescaling to integer results are equal w.r.t. compiler/FP type,
471     // however, some long spikes are still generated in the resulting difference
472     test_one<polygon, polygon, polygon>("ggl_list_20110627_phillip",
473         ggl_list_20110627_phillip[0], ggl_list_20110627_phillip[1],
474         if_typed_tt<ct>(1, 1), -1,
475         if_typed_tt<ct>(0.0000000000001105367, 0.000125137888971949),
476         1, -1, 3577.40960816756,
477         0.01
478         );
479 #endif
480 
481     // Ticket 8310, one should be completely subtracted from the other.
482     test_one<polygon, polygon, polygon>("ticket_8310a",
483         ticket_8310a[0], ticket_8310a[1],
484         1, 10, 10.11562724,
485         0, 0, 0);
486     test_one<polygon, polygon, polygon>("ticket_8310b",
487         ticket_8310b[0], ticket_8310b[1],
488         1, 10, 10.12655608,
489         0, 0, 0);
490     test_one<polygon, polygon, polygon>("ticket_8310c",
491         ticket_8310c[0], ticket_8310c[1],
492         1, 10, 10.03103292,
493         0, 0, 0);
494 
495 #if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
496     test_one<polygon, polygon, polygon>("ticket_9081_15",
497             ticket_9081_15[0], ticket_9081_15[1],
498             2, 10, 0.0334529710902111,
499             1, 4, 5.3469555172380723e-010);
500 #endif
501 
502     test_one<polygon, polygon, polygon>("ticket_9081_314",
503             ticket_9081_314[0], ticket_9081_314[1],
504             2, 12, 0.0451236449624935,
505             0, 0, 0);
506 
507 #if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
508     test_one<polygon, polygon, polygon>("ticket_9563",
509             ticket_9563[0], ticket_9563[1],
510             0, 0, 0,
511             6, 24, 20.096189);
512 
513     test_one<polygon, polygon, polygon>("ticket_10108_a",
514             ticket_10108_a[0], ticket_10108_a[1],
515             1, 4,  0.0145037,
516             1, 4,  0.029019232);
517     test_one<polygon, polygon, polygon>("ticket_10108_b",
518             ticket_10108_b[0], ticket_10108_b[1],
519             1, 5, 1081.68697,
520             1, 5, 1342.65795);
521 #endif
522 
523     // From assemble-test, with a u/u case
524     test_one<polygon, polygon, polygon>("assemble_0210",
525             "POLYGON((0 0,0 10,10 10,10 0,0 0),(8.5 1,9.5 1,9.5 2,8.5 2,8.5 1))",
526             "POLYGON((2 0.5,0.5 2,0.5 8,2 9.5,6 9.5,8.5 8,8.5 2,7 0.5,2 0.5),(2 2,7 2,7 8,2 8,2 2))",
527             2, 23, 62.25,
528             0, 0, 0.0);
529 
530     // Other combi's
531     {
532         test_one<polygon, polygon, ring>(
533                 "star_ring_ring", example_star, example_ring,
534                 5, 22, 1.1901714, 5, 27, 1.6701714);
535 
536         test_one<polygon, ring, polygon>(
537                 "ring_star_ring", example_ring, example_star,
538                 5, 27, 1.6701714, 5, 22, 1.1901714);
539 
540         static std::string const clip = "POLYGON((2.5 0.5,5.5 2.5))";
541 
542         test_one<polygon, box, ring>("star_box",
543             clip, example_star,
544             4, 20, 2.833333, 4, 16, 0.833333);
545 
546         test_one<polygon, ring, box>("box_star",
547             example_star, clip,
548             4, 16, 0.833333, 4, 20, 2.833333);
549     }
550 
551     // Counter clockwise
552     {
553         typedef bg::model::polygon<P, false> polygon_ccw;
554         test_one<polygon, polygon_ccw, polygon_ccw>(
555                 "star_ring_ccw", example_star, example_ring,
556                 5, 22, 1.1901714, 5, 27, 1.6701714);
557         test_one<polygon, polygon, polygon_ccw>(
558                 "star_ring_ccw1", example_star, example_ring,
559                 5, 22, 1.1901714, 5, 27, 1.6701714);
560         test_one<polygon, polygon_ccw, polygon>(
561                 "star_ring_ccw2", example_star, example_ring,
562                 5, 22, 1.1901714, 5, 27, 1.6701714);
563     }
564 
565     // Multi/box (should be moved to multi)
566     {
567         /* Tested with SQL Geometry:
568                 with viewy as (select geometry::STGeomFromText(
569                         'MULTIPOLYGON(((0 1,2 5,5 3,0 1)),((1 1,5 2,5 0,1 1)))',0) as  p,
570                   geometry::STGeomFromText(
571                         'POLYGON((2 2,2 4,4 4,4 2,2 2))',0) as q)
572 
573                 select
574                     p.STDifference(q).STArea(),p.STDifference(q).STNumGeometries(),p.STDifference(q) as p_min_q,
575                     q.STDifference(p).STArea(),q.STDifference(p).STNumGeometries(),q.STDifference(p) as q_min_p,
576                     p.STSymDifference(q).STArea(),q.STSymDifference(p) as p_xor_q
577                 from viewy
578 
579         */
580         typedef bg::model::multi_polygon<polygon> mp;
581 
582         static std::string const clip = "POLYGON((2 2,4 4))";
583 
584         test_one<polygon, box, mp>("simplex_multi_box_mp",
585             clip, case_multi_simplex[0],
586             2, -1, 0.53333333333, 3, -1, 8.53333333333);
587         test_one<polygon, mp, box>("simplex_multi_mp_box",
588             case_multi_simplex[0], clip,
589             3, -1, 8.53333333333, 2, -1, 0.53333333333);
590 
591     }
592 
593     /***
594     Experimental (cut), does not work:
595     test_one<polygon, polygon, polygon>(
596             "polygon_pseudo_line",
597             "POLYGON((0 0,0 4,4 4,4 0,0 0))",
598             "POLYGON((2 -2,2 -1,2 6,2 -2))",
599             5, 22, 1.1901714,
600             5, 27, 1.6701714);
601     ***/
602 }
603 
604 /*******
605 // To be moved to another file
606 template <typename T>
607 void test_difference_parcel_precision()
608 {
609     typedef bg::model::d2::point_xy<T> point_type;
610     typedef bg::model::polygon<point_type> polygon_type;
611     typedef bg::model::linestring<point_type> linestring_type;
612     typedef std::vector<boost::uint8_t> byte_vector;
613 
614     polygon_type parcel, buffer;
615 
616     {
617         byte_vector wkb;
618         bg::hex2wkb("0103000000010000001A00000023DBF97EE316064146B6F3FDD32513415A643BDFD216064175931804E225134196438B6C52150641C976BE9F34261341F6285C8F06150641022B871641261341F853E3A5D3140641E17A14AE50261341B81E85EBFB120641A4703D8A142713414E6210584D120641AC1C5A64602713414E621058431106414E621058C9271341A01A2FDD1B11064121B07268D8271341F4FDD478571006411904560ECF271341448B6CE7DD0F06418195438BC1271341F6285C8F6A0F06413BDF4F0DA72713410E2DB29D360F06416F1283C091271341E5D022DB070F0641F6285C0F7227134160E5D022DA0E06416F1283404F271341448B6CE7D30E0641F853E3A52427134154E3A59BE60E06411904568E07271341643BDF4F0C0F0641D7A3703DFC2613414A0C022B100F064125068115FB26134191ED7C3F310F0641B6F3FDD4F42613414C378941F11006414A0C022BA0261341EC51B81ECC1206413BDF4F0D40261341022B87167514064125068115F1251341B4C876BE8C160641C74B37897F25134121B07268C6160641508D976E7525134123DBF97EE316064146B6F3FDD3251341", std::back_inserter(wkb));
619         bg::read_wkb(wkb.begin(), wkb.end(), parcel);
620     }
621     {
622         byte_vector wkb;
623         bg::hex2wkb("01030000000100000083000000000032FCD716064100009E998F25134100000706D81606410040A4998F2513410000DA0FD816064100C0E6998F2513410000A819D81606410080659A8F25134100806A23D816064100C0209B8F25134100801E2DD81606410080189C8F2513410000BE36D816064100404D9D8F25134100004540D816064100C0BE9E8F2513410000AF49D816064100806DA08F2513410000F752D8160641008059A28F2513410000195CD816064100C082A48F25134100800F65D81606410080E9A68F2513410000D66DD816064100408EA98F25134100006876D816064100C070AC8F2513410000C17ED8160641000091AF8F2513410080DC86D816064100C0EFB28F25134100009E8ED816064100C081B68F2513410080EC95D816064100803ABA8F2513410080C79CD8160641000018BE8F25134100002FA3D8160641008017C28F251341008022A9D8160641000037C68F2513410080A1AED8160641000074CA8F2513410000ACB3D81606410040CCCE8F251341000042B8D816064100403DD38F251341000062BCD81606410000C5D78F25134100000DC0D8160641000061DC8F251341000042C3D816064100000FE18F251341000001C6D81606410080CCE58F251341008049C8D8160641004097EA8F25134100001BCAD816064100006DEF8F251341008075CBD816064100804BF48F251341008058CCD8160641004030F98F2513410000C4CCD8160641000019FE8F2513410080B7CCD81606410080030390251341008032CCD81606410000ED0790251341000035CBD81606410000D40C902513410080BEC9D81606410040B511902513410000CFC7D816064100408F1690251341008065C5D816064100005F1B90251341008082C2D81606410080222090251341000025BFD81606410080D7249025134100004DBBD816064100807B29902513410080FAB6D816064100800C2E9025134100002DB2D816064100C08732902513410080E3ACD81606410000EB369025134100801EA7D81606410000343B902513410000DEA0D81606410080603F902513410080209AD816064100406E43902513410080209AC015064100406E43302613410080FC92C015064100004F473026134100008B8BC01506410040F64A302613410000D083C015064100C0634E302613410000D17BC0150641008097513026134100009273C015064100409154302613410000186BC015064100C050573026134100806762C01506410000D6593026134100808559C01506410000215C3026134100007650C01506410000315E3026134100003E47C015064100800660302613410000E23DC01506410000A1613026134100006734C015064100800063302613410080D12AC015064100C024643026134100002621C015064100800D653026134100006917C015064100C0BA653026134100809F0DC015064100402C66302613410000CE03C015064100006266302613410000F9F9BF15064100C05B6630261341000026F0BF1506410040196630261341000058E6BF15064100809A6530261341008095DCBF1506410040DF64302613410080E1D2BF1506410080E76330261341000042C9BF15064100C0B262302613410000BBBFBF1506410040416130261341000051B6BF1506410080925F30261341000009ADBF1506410080A65D302613410000E7A3BF15064100407D5B302613410080F09ABF150641008016593026134100002A92BF15064100C071563026134100009889BF15064100408F533026134100003F81BF15064100006F503026134100802379BF1506410040104D3026134100006271BF15064100407E49302613410080136ABF1506410080C5453026134100803863BF1506410000E841302613410000D15CBF1506410080E83D302613410080DD56BF1506410000C9393026134100805E51BF15064100008C35302613410000544CBF15064100C03331302613410000BE47BF15064100C0C22C3026134100009E43BF15064100003B28302613410000F33FBF15064100009F23302613410000BE3CBF1506410000F11E302613410000FF39BF1506410080331A302613410080B637BF15064100C06815302613410000E535BF150641000093103026134100808A34BF1506410080B40B302613410080A733BF15064100C0CF063026134100003C33BF1506410000E7013026134100804833BF1506410080FCFC2F2613410080CD33BF150641000013F82F2613410000CB34BF15064100002CF32F26134100804136BF15064100C04AEE2F26134100003138BF15064100C070E92F26134100809A3ABF1506410000A1E42F26134100807D3DBF1506410080DDDF2F2613410000DB40BF150641008028DB2F2613410000B344BF150641008084D62F26134100800549BF1506410080F3D12F2613410000D34DBF150641004078CD2F26134100801C53BF150641000015C92F2613410080E158BF1506410000CCC42F2613410000225FBF15064100809FC02F2613410080DF65BF15064100C091BC2F2613410080DF65D716064100C091BC8F2513410080036DD71606410000B1B88F25134100007574D716064100C009B58F2513410000307CD716064100409CB18F25134100002F84D7160641008068AE8F25134100006E8CD716064100C06EAB8F2513410000E894D71606410040AFA88F2513410080989DD716064100002AA68F25134100807AA6D71606410000DFA38F25134100008AAFD71606410000CFA18F2513410000C2B8D71606410080F99F8F25134100001EC2D716064100005F9E8F251341000099CBD71606410080FF9C8F25134100802ED5D71606410040DB9B8F2513410000DADED71606410080F29A8F251341000097E8D71606410040459A8F251341008060F2D716064100C0D3998F251341000032FCD716064100009E998F251341", std::back_inserter(wkb));
624         bg::read_wkb(wkb.begin(), wkb.end(), buffer);
625     }
626     bg::correct(parcel);
627     bg::correct(buffer);
628 
629     std::vector<polygon_type> pieces;
630     bg::difference(parcel, buffer, pieces);
631 
632     std::vector<polygon_type> filled_out;
633     bg::difference(parcel, pieces.back(), filled_out);
634 
635 #if defined(TEST_OUTPUT)
636     std::cout << bg::area(parcel) << std::endl;
637     std::cout << bg::area(buffer) << std::endl;
638     std::cout << pieces.size() << std::endl;
639     std::cout << bg::area(pieces.front()) << std::endl;
640     std::cout << filled_out.size() << std::endl;
641     std::cout << std::setprecision(16) << bg::wkt(filled_out.front()) << std::endl;
642     std::cout << bg::wkt(filled_out.front()) << std::endl;
643     std::cout << bg::area(filled_out.front()) << std::endl;
644     std::cout << bg::perimeter(filled_out.front()) << std::endl;
645 #endif
646 
647 #if defined(TEST_WITH_SVG)
648     {
649         linestring_type cut_line;
650         bg::read_wkt("linestring(180955 313700,180920 313740)", cut_line);
651 
652         std::ostringstream filename;
653         filename << "difference_precision_"
654             << string_from_type<T>::name()
655             << ".svg";
656 
657         std::ofstream svg(filename.str().c_str());
658 
659         bg::svg_mapper<point_type> mapper(svg, 500, 500);
660 
661         mapper.add(cut_line);
662 
663         //mapper.map(parcel, "fill-opacity:0.5;fill:rgb(153,204,0);stroke:rgb(153,204,0);stroke-width:3");
664         mapper.map(pieces.front(), "fill-opacity:0.5;fill:rgb(153,204,0);stroke:rgb(153,204,0);stroke-width:1");
665         mapper.map(pieces.back(), "fill-opacity:0.5;fill:rgb(153,204,0);stroke:rgb(153,204,0);stroke-width:1");
666         mapper.map(filled_out.front(), "fill-opacity:0.3;fill:rgb(51,51,153);stroke:rgb(51,51,153);stroke-width:3");
667 
668         mapper.map(cut_line, "opacity:0.8;fill:none;stroke:rgb(255,128,0);stroke-width:5;stroke-dasharray:1,7;stroke-linecap:round");
669         //mapper.map(cut_line, "opacity:0.8;fill:none;stroke:rgb(255,128,0);stroke-width:2");
670     }
671 #endif
672 }
673 *****/
674 
675 
676 template <typename P, bool clockwise, bool closed>
test_specific()677 void test_specific()
678 {
679     typedef bg::model::polygon<P, clockwise, closed> polygon;
680 
681     test_one<polygon, polygon, polygon>("ggl_list_20120717_volker",
682         ggl_list_20120717_volker[0], ggl_list_20120717_volker[1],
683         1, 11, 3371540,
684         1, 4, 385,
685         1, 16, 3371540 + 385,
686         0.001);
687 
688     test_one<polygon, polygon, polygon>("ticket_10658",
689         ticket_10658[0], ticket_10658[1],
690         1, 6, 1510434,
691         0, 0, 0);
692 
693     test_one<polygon, polygon, polygon>("ticket_11121",
694         ticket_11121[0], ticket_11121[1],
695         2, 8, 489763.5,
696         1, 4, 6731652.0);
697 }
698 
699 
test_main(int,char * [])700 int test_main(int, char* [])
701 {
702     //test_difference_parcel_precision<float>();
703     //test_difference_parcel_precision<double>();
704 
705     test_all<bg::model::d2::point_xy<double> >();
706 
707     test_specific<bg::model::d2::point_xy<int>, false, false>();
708 
709     test_ticket_10658<int>
710         ("MULTIPOLYGON(((516 2484,516 1608,1308 1932,2094 2466,2094 3150,1308 3066,516 2484)))");
711 
712     test_ticket_10658<double>
713         ("MULTIPOLYGON(((516 2484,516 1608,1308 1932,2094 2466,2094 3150,1308 3066,516 2484)))");
714 
715     test_ticket_10835<int>
716         ("MULTILINESTRING((5239 2113,5233 2114),(4794 2205,1020 2986))",
717          "MULTILINESTRING((5239 2113,5233 2114),(4794 2205,1460 2895))");
718 
719     test_ticket_10835<double>
720         ("MULTILINESTRING((5239 2113,5232.52 2114.34),(4794.39 2205,1020 2986))",
721          "MULTILINESTRING((5239 2113,5232.52 2114.34),(4794.39 2205,1459.78 2895))");
722 
723     test_ticket_11121<int>();
724 
725 #ifdef BOOST_GEOMETRY_TEST_ENABLE_FAILING
726     test_bug21155501<double>();
727 #endif
728 
729 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
730     test_all<bg::model::d2::point_xy<float> >();
731 
732 #ifdef HAVE_TTMATH
733     std::cout << "Testing TTMATH" << std::endl;
734     test_all<bg::model::d2::point_xy<ttmath_big> >();
735     //test_difference_parcel_precision<ttmath_big>();
736 #endif
737 #endif
738 
739     return 0;
740 }
741