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