1 // Boost.Geometry (aka GGL, Generic Geometry Library)
4 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
5 // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
6 // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
8 // This file was modified by Oracle on 2015-2022.
9 // Modifications copyright (c) 2015-2022, Oracle and/or its affiliates.
10 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
13 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
14 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
16 // Use, modification and distribution is subject to the Boost Software License,
17 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
18 // http://www.boost.org/LICENSE_1_0.txt)
24 #include <boost/config.hpp>
25 #include <boost/core/ignore_unused.hpp>
27 #include <boost/geometry/geometries/point_xy.hpp>
28 #include <boost/geometry/geometries/register/linestring.hpp>
30 #include <boost/geometry/util/condition.hpp>
31 #include <boost/geometry/util/rational.hpp>
33 #include "test_intersection.hpp"
34 #include <algorithms/test_overlay.hpp>
36 #include <algorithms/overlay/overlay_cases.hpp>
38 #include <test_common/test_point.hpp>
39 #include <test_common/with_pointer.hpp>
40 #include <test_geometries/custom_segment.hpp>
43 BOOST_GEOMETRY_REGISTER_LINESTRING_TEMPLATED(std::vector
)
45 #define TEST_INTERSECTION(caseid, clips, points, area) \
46 (test_one<Polygon, Polygon, Polygon>) \
47 ( #caseid, caseid[0], caseid[1], clips, points, area)
49 #define TEST_INTERSECTION_REV(caseid, clips, points, area) \
50 (test_one<Polygon, Polygon, Polygon>) \
51 ( #caseid "_rev", caseid[1], caseid[0], clips, points, area)
53 #define TEST_INTERSECTION_IGNORE(caseid, clips, points, area) \
54 { ut_settings ignore_validity; ignore_validity.set_test_validity(false); \
55 (test_one<Polygon, Polygon, Polygon>) \
56 ( #caseid, caseid[0], caseid[1], clips, points, area, ignore_validity); }
58 #define TEST_INTERSECTION_WITH(caseid, index1, index2, \
59 clips, points, area, settings) \
60 (test_one<Polygon, Polygon, Polygon>) \
61 ( #caseid "_" #index1 "_" #index2, caseid[index1], caseid[index2], \
62 clips, points, area, settings)
64 template <typename Polygon
>
67 test_one
<Polygon
, Polygon
, Polygon
>("simplex_with_empty_1",
68 simplex_normal
[0], polygon_empty
,
70 test_one
<Polygon
, Polygon
, Polygon
>("simplex_with_empty_2",
71 polygon_empty
, simplex_normal
[0],
74 test_one
<Polygon
, Polygon
, Polygon
>("simplex_normal",
75 simplex_normal
[0], simplex_normal
[1],
77 test_one
<Polygon
, Polygon
, Polygon
>("star_ring", example_star
, example_ring
,
80 test_one
<Polygon
, Polygon
, Polygon
>("star_poly", example_star
, example_polygon
,
81 1, 0, // CLN: 23 points, other types: 22 point (one is merged)
83 test_one
<Polygon
, Polygon
, Polygon
>("first_within_second1",
84 first_within_second
[0], first_within_second
[1],
87 test_one
<Polygon
, Polygon
, Polygon
>("first_within_second2",
88 first_within_second
[1], first_within_second
[0],
91 test_one
<Polygon
, Polygon
, Polygon
>("first_within_hole_of_second",
92 first_within_hole_of_second
[0], first_within_hole_of_second
[1],
95 // Two forming new hole
96 test_one
<Polygon
, Polygon
, Polygon
>("new_hole",
97 new_hole
[0], new_hole
[1],
101 test_one
<Polygon
, Polygon
, Polygon
>("identical",
102 identical
[0], identical
[1],
105 test_one
<Polygon
, Polygon
, Polygon
>("intersect_exterior_and_interiors_winded",
106 intersect_exterior_and_interiors_winded
[0], intersect_exterior_and_interiors_winded
[1],
109 test_one
<Polygon
, Polygon
, Polygon
>("intersect_holes_disjoint",
110 intersect_holes_disjoint
[0], intersect_holes_disjoint
[1],
113 test_one
<Polygon
, Polygon
, Polygon
>("intersect_holes_intersect",
114 intersect_holes_intersect
[0], intersect_holes_intersect
[1],
117 test_one
<Polygon
, Polygon
, Polygon
>("intersect_holes_intersect_and_disjoint",
118 intersect_holes_intersect_and_disjoint
[0], intersect_holes_intersect_and_disjoint
[1],
121 test_one
<Polygon
, Polygon
, Polygon
>("intersect_holes_intersect_and_touch",
122 intersect_holes_intersect_and_touch
[0], intersect_holes_intersect_and_touch
[1],
125 test_one
<Polygon
, Polygon
, Polygon
>("intersect_holes_new_ring",
126 intersect_holes_new_ring
[0], intersect_holes_new_ring
[1],
129 test_one
<Polygon
, Polygon
, Polygon
>("winded",
130 winded
[0], winded
[1],
133 test_one
<Polygon
, Polygon
, Polygon
>("within_holes_disjoint",
134 within_holes_disjoint
[0], within_holes_disjoint
[1],
137 test_one
<Polygon
, Polygon
, Polygon
>("side_side",
138 side_side
[0], side_side
[1],
141 test_one
<Polygon
, Polygon
, Polygon
>("two_bends",
142 two_bends
[0], two_bends
[1],
145 test_one
<Polygon
, Polygon
, Polygon
>("star_comb_15",
146 star_comb_15
[0], star_comb_15
[1],
147 28, 150, 189.952883);
149 test_one
<Polygon
, Polygon
, Polygon
>("simplex_normal",
150 simplex_normal
[0], simplex_normal
[1],
153 #if ! defined(BOOST_GEOMETRY_USE_RESCALING) || defined(BOOST_GEOMETRY_TEST_FAILURES)
154 // Fails if rescaling is used in combination with get_clusters, because a cluster is generated
155 // and use as the start of the traversal
156 test_one
<Polygon
, Polygon
, Polygon
>("distance_zero",
157 distance_zero
[0], distance_zero
[1],
161 test_one
<Polygon
, Polygon
, Polygon
>("equal_holes_disjoint",
162 equal_holes_disjoint
[0], equal_holes_disjoint
[1],
163 1, 20, 81.0 - 2.0 * 3.0 * 3.0 - 3.0 * 7.0);
165 test_one
<Polygon
, Polygon
, Polygon
>("only_hole_intersections1",
166 only_hole_intersections
[0], only_hole_intersections
[1],
168 test_one
<Polygon
, Polygon
, Polygon
>("only_hole_intersection2",
169 only_hole_intersections
[0], only_hole_intersections
[2],
172 test_one
<Polygon
, Polygon
, Polygon
>("fitting",
173 fitting
[0], fitting
[1],
176 test_one
<Polygon
, Polygon
, Polygon
>("crossed",
177 crossed
[0], crossed
[1],
180 test_one
<Polygon
, Polygon
, Polygon
>("pie_2_3_23_0",
181 pie_2_3_23_0
[0], pie_2_3_23_0
[1],
182 1, 4, 163292.679042133, ut_settings(0.1));
184 #if defined(BOOST_GEOMETRY_USE_RESCALING) || defined(BOOST_GEOMETRY_TEST_FAILURES)
185 TEST_INTERSECTION(isovist
, 1, 19, expectation_limits(88.19202, 88.19206));
187 // Reported as invalid without rescaling and get_clusters
188 TEST_INTERSECTION_IGNORE(isovist
, 1, 19, expectation_limits(88.19202, 88.19206));
191 TEST_INTERSECTION_IGNORE(geos_1
, 1, -1, expectation_limits(3454, 3462));
193 // Can, in some cases, create small slivers
194 // In some cases: 1.430511474609375e-05 (clang/gcc on Xubuntu using b2)
195 // In some cases: 5.6022983000000002e-05 (powerpc64le-gcc-6-0)
196 TEST_INTERSECTION(geos_2
, count_set(0, 1, 2), 0, optional_sliver(6.0e-5));
198 TEST_INTERSECTION(geos_3
, optional(), 0, optional_sliver(3.0e-7));
199 TEST_INTERSECTION(geos_4
, 1, -1, expectation_limits(0.08368, 0.08370));
201 TEST_INTERSECTION(ggl_list_20110306_javier
, 1, -1, expectation_limits(0.6649, 0.6670));
203 // SQL Server reports: 0.400390625
204 // PostGIS reports 0.4
205 // BG did report 0.4 but with rescaling 0.397
206 // when selecting other IP closer at endpoint or if segment B is smaller than A
207 test_one
<Polygon
, Polygon
, Polygon
>("ggl_list_20110307_javier",
208 ggl_list_20110307_javier
[0], ggl_list_20110307_javier
[1],
209 1, 4, {0.397162651, 0.40});
211 test_one
<Polygon
, Polygon
, Polygon
>("ggl_list_20110627_phillip",
212 ggl_list_20110627_phillip
[0], ggl_list_20110627_phillip
[1],
215 test_one
<Polygon
, Polygon
, Polygon
>("ggl_list_20110716_enrico",
216 ggl_list_20110716_enrico
[0], ggl_list_20110716_enrico
[1],
217 3, 16, 35723.8506317139);
219 test_one
<Polygon
, Polygon
, Polygon
>("ggl_list_20131119_james",
220 ggl_list_20131119_james
[0], ggl_list_20131119_james
[1],
223 test_one
<Polygon
, Polygon
, Polygon
>("ggl_list_20140223_shalabuda",
224 ggl_list_20140223_shalabuda
[0], ggl_list_20140223_shalabuda
[1],
225 1, 4, {3.771058, 3.771066});
227 // Mailed to the Boost.Geometry list on 2014/03/21 by 7415963@gmail.com
228 test_one
<Polygon
, Polygon
, Polygon
>("ggl_list_20140321_7415963",
229 ggl_list_20140321_7415963
[0], ggl_list_20140321_7415963
[1],
232 TEST_INTERSECTION(ggl_list_20190307_matthieu_1
, 2, -1, 0.035136);
233 TEST_INTERSECTION(ggl_list_20190307_matthieu_2
, 1, -1, 3.64285);
235 test_one
<Polygon
, Polygon
, Polygon
>("buffer_rt_f", buffer_rt_f
[0], buffer_rt_f
[1],
236 1, 4, expectation_limits(0.00029437, 0.000294380));
237 test_one
<Polygon
, Polygon
, Polygon
>("buffer_rt_g", buffer_rt_g
[0], buffer_rt_g
[1],
238 1, 0, 2.914213562373);
240 test_one
<Polygon
, Polygon
, Polygon
>("ticket_8254", ticket_8254
[0], ticket_8254
[1],
241 optional(), -1, optional_sliver(1e-07));
242 test_one
<Polygon
, Polygon
, Polygon
>("ticket_6958", ticket_6958
[0], ticket_6958
[1],
243 optional(), -1, optional_sliver());
244 test_one
<Polygon
, Polygon
, Polygon
>("ticket_8652", ticket_8652
[0], ticket_8652
[1],
247 TEST_INTERSECTION(ticket_8310a
, 1, 5, 0.3843747);
248 TEST_INTERSECTION(ticket_8310b
, 1, 5, 0.3734379);
249 TEST_INTERSECTION(ticket_8310c
, 1, 5, 0.4689541);
250 TEST_INTERSECTION_REV(ticket_8310a
, 1, 5, 0.3843747);
251 TEST_INTERSECTION_REV(ticket_8310b
, 1, 5, 0.3734379);
252 TEST_INTERSECTION_REV(ticket_8310c
, 1, 5, 0.4689541);
254 test_one
<Polygon
, Polygon
, Polygon
>("ticket_9081_15",
255 ticket_9081_15
[0], ticket_9081_15
[1],
256 1, 4, 0.0068895780745301394);
258 test_one
<Polygon
, Polygon
, Polygon
>("ticket_10108_a",
259 ticket_10108_a
[0], ticket_10108_a
[1],
263 // mingw 5.6022954e-5
264 test_one
<Polygon
, Polygon
, Polygon
>("ticket_10108_b",
265 ticket_10108_b
[0], ticket_10108_b
[1],
266 optional(), 0, optional_sliver(1.0e-4));
268 test_one
<Polygon
, Polygon
, Polygon
>("ticket_10747_a",
269 ticket_10747_a
[0], ticket_10747_a
[1],
270 1, 4, 70368744177664.0);
271 test_one
<Polygon
, Polygon
, Polygon
>("ticket_10747_b",
272 ticket_10747_b
[0], ticket_10747_b
[1],
273 1, 4, 7036874417766400.0);
274 test_one
<Polygon
, Polygon
, Polygon
>("ticket_10747_c",
275 ticket_10747_c
[0], ticket_10747_c
[1],
276 1, 4, 17592186044416.0);
277 test_one
<Polygon
, Polygon
, Polygon
>("ticket_10747_d",
278 ticket_10747_d
[0], ticket_10747_d
[1],
279 1, 4, 703687777321.0);
281 // Delivers very small triangle < 1.0e-13, or zero
282 test_one
<Polygon
, Polygon
, Polygon
>("ticket_10747_e",
283 ticket_10747_e
[0], ticket_10747_e
[1],
284 optional(), -1, optional_sliver(1.0e-13));
286 test_one
<Polygon
, Polygon
, Polygon
>("ticket_11576",
287 ticket_11576
[0], ticket_11576
[1],
288 1, -1, expectation_limits(5.5856173e-07, 5.5856175e-07));
291 // Not yet valid when rescaling is turned off
292 ut_settings settings
;
293 settings
.set_test_validity(BG_IF_RESCALED(true, false));
294 test_one
<Polygon
, Polygon
, Polygon
>("ticket_9563", ticket_9563
[0], ticket_9563
[1],
295 1, 8, 129.90381, settings
);
298 #if ! defined(BOOST_GEOMETRY_USE_RESCALING) || defined(BOOST_GEOMETRY_TEST_FAILURES)
299 // With rescaling the output is empty
300 TEST_INTERSECTION(issue_548
, 1, -1, expectation_limits(1958821942, 1958824416));
303 TEST_INTERSECTION(issue_566_a
, 1, -1, 70.7107);
304 TEST_INTERSECTION(issue_566_b
, 1, -1, 70.7107);
306 TEST_INTERSECTION(issue_838
, 1, -1, (expectation_limits
{0.6582, 0.6650}));
308 #if ! defined(BOOST_GEOMETRY_USE_RESCALING) || defined(BOOST_GEOMETRY_TEST_FAILURES)
309 // With rescaling the output is wrong
310 TEST_INTERSECTION(issue_861
, 1, -1, 1.4715007684573677693e-10);
313 test_one
<Polygon
, Polygon
, Polygon
>("buffer_mp1", buffer_mp1
[0], buffer_mp1
[1],
315 test_one
<Polygon
, Polygon
, Polygon
>("buffer_mp2", buffer_mp2
[0], buffer_mp2
[1],
318 test_one
<Polygon
, Polygon
, Polygon
>("case_58_iet",
319 case_58
[0], case_58
[2],
322 test_one
<Polygon
, Polygon
, Polygon
>("case_80",
323 case_80
[0], case_80
[1],
326 test_one
<Polygon
, Polygon
, Polygon
>("case_81",
327 case_81
[0], case_81
[1],
330 test_one
<Polygon
, Polygon
, Polygon
>("case_101",
331 case_101
[0], case_101
[1],
333 test_one
<Polygon
, Polygon
, Polygon
>("case_102",
334 case_102
[0], case_102
[1],
335 count_set(1, 2), -1, 3.1875);
337 test_one
<Polygon
, Polygon
, Polygon
>("case_103",
338 case_103
[0], case_103
[1],
340 test_one
<Polygon
, Polygon
, Polygon
>("case_104",
341 case_104
[0], case_104
[1],
344 TEST_INTERSECTION(case_105
, 1, 34, 76.0);
345 TEST_INTERSECTION(case_106
, 2, -1, 3.5);
346 TEST_INTERSECTION(case_107
, 3, -1, 3.0);
348 TEST_INTERSECTION(case_precision_1
, optional(), 0, optional_sliver(1.0e-4));
349 TEST_INTERSECTION(case_precision_2
, optional(), 0, optional_sliver(1.0e-5));
350 TEST_INTERSECTION(case_precision_3
, optional(), 0, optional_sliver(1.0e-7));
351 TEST_INTERSECTION(case_precision_4
, 0, 0, 0.0);
352 TEST_INTERSECTION(case_precision_5
, optional(), 0, optional_sliver(1.0e-6));
353 TEST_INTERSECTION(case_precision_6
, 1, -1, 14.0);
354 TEST_INTERSECTION(case_precision_7
, 0, -1, 0.0);
355 TEST_INTERSECTION(case_precision_8
, 1, -1, 14.0);
356 TEST_INTERSECTION(case_precision_9
, 1, -1, 14.0);
357 TEST_INTERSECTION(case_precision_10
, 1, -1, 14.0);
358 TEST_INTERSECTION(case_precision_11
, 1, -1, 14.0);
359 TEST_INTERSECTION(case_precision_12
, 1, -1, 2.0);
360 TEST_INTERSECTION(case_precision_13
, 1, -1, 1.99998);
361 TEST_INTERSECTION(case_precision_14
, 0, -1, 0.0);
362 TEST_INTERSECTION(case_precision_15
, 1, -1, 14.0);
363 TEST_INTERSECTION(case_precision_16
, 1, -1, 14.0);
364 TEST_INTERSECTION(case_precision_17
, 1, -1, 14.0);
365 TEST_INTERSECTION(case_precision_18
, 1, -1, 14.0);
366 TEST_INTERSECTION(case_precision_19
, 1, -1, 14.0);
367 TEST_INTERSECTION(case_precision_20
, 0, 0, 0.0);
368 TEST_INTERSECTION(case_precision_21
, 0, 0, 0.0);
369 TEST_INTERSECTION(case_precision_22
, 1, -1, 14.0);
370 TEST_INTERSECTION(case_precision_23
, 1, -1, 14.0);
371 TEST_INTERSECTION(case_precision_24
, 0, 0, 0.0);
372 TEST_INTERSECTION(case_precision_25
, 0, 0, 0.0);
373 TEST_INTERSECTION(case_precision_26
, 1, -1, 14.0);
375 TEST_INTERSECTION_REV(case_precision_1
, optional(), 0, optional_sliver(1.0e-4));
376 TEST_INTERSECTION_REV(case_precision_2
, optional(), 0, optional_sliver(1.0e-5));
377 TEST_INTERSECTION_REV(case_precision_3
, optional(), 0, optional_sliver(1.0e-7));
378 TEST_INTERSECTION_REV(case_precision_4
, 0, 0, 0.0);
379 TEST_INTERSECTION_REV(case_precision_5
, optional(), 0, optional_sliver(1.0e-6));
380 TEST_INTERSECTION_REV(case_precision_6
, 1, -1, 14.0);
381 TEST_INTERSECTION_REV(case_precision_7
, 0, -1, 0.0);
382 TEST_INTERSECTION_REV(case_precision_8
, 1, -1, 14.0);
383 TEST_INTERSECTION_REV(case_precision_9
, 1, -1, 14.0);
384 TEST_INTERSECTION_REV(case_precision_10
, 1, -1, 14.0);
385 TEST_INTERSECTION_REV(case_precision_11
, 1, -1, 14.0);
386 TEST_INTERSECTION_REV(case_precision_12
, 1, -1, 2.0);
387 TEST_INTERSECTION_REV(case_precision_13
, 1, -1, 1.99998);
388 TEST_INTERSECTION_REV(case_precision_14
, 0, -1, 0.0);
389 TEST_INTERSECTION_REV(case_precision_15
, 1, -1, 14.0);
390 TEST_INTERSECTION_REV(case_precision_16
, 1, -1, 14.0);
391 TEST_INTERSECTION_REV(case_precision_17
, 1, -1, 14.0);
392 TEST_INTERSECTION_REV(case_precision_18
, 1, -1, 14.0);
393 TEST_INTERSECTION_REV(case_precision_19
, 1, -1, 14.0);
394 TEST_INTERSECTION_REV(case_precision_20
, 0, 0, 0.0);
395 TEST_INTERSECTION_REV(case_precision_21
, 0, 0, 0.0);
396 TEST_INTERSECTION_REV(case_precision_22
, 1, -1, 14.0);
397 TEST_INTERSECTION_REV(case_precision_23
, 1, -1, 14.0);
398 TEST_INTERSECTION_REV(case_precision_24
, 0, 0, 0.0);
399 TEST_INTERSECTION_REV(case_precision_25
, 0, 0, 0.0);
400 TEST_INTERSECTION_REV(case_precision_26
, 1, -1, 14.0);
402 test_one
<Polygon
, Polygon
, Polygon
>("mysql_21964049",
403 mysql_21964049
[0], mysql_21964049
[1],
406 test_one
<Polygon
, Polygon
, Polygon
>("mysql_21964465",
407 mysql_21964465
[0], mysql_21964465
[1],
410 test_one
<Polygon
, Polygon
, Polygon
>("mysql_21965285_b_inv",
411 mysql_21965285_b_inv
[0],
412 mysql_21965285_b_inv
[1],
413 2, -1, 183.71376870369406);
415 TEST_INTERSECTION(mysql_23023665_6
, 2, 0, 11.812440191387557);
417 // Formation of an interior ring is optional
418 test_one
<Polygon
, Polygon
, Polygon
>("mysql_23023665_10",
419 mysql_23023665_10
[0], mysql_23023665_10
[1],
420 1, optional(), -1, 54.701340543162523);
422 // Formation of an interior ring is optional
423 test_one
<Polygon
, Polygon
, Polygon
>("mysql_23023665_11",
424 mysql_23023665_11
[0], mysql_23023665_11
[1],
425 1, optional(), -1, 35.933385462482065);
427 // test_one<Polygon, Polygon, Polygon>(
428 // "polygon_pseudo_line",
429 // "Polygon((0 0,0 4,4 4,4 0,0 0))",
430 // "Polygon((2 -2,2 -1,2 6,2 -2))",
431 // 5, 22, 1.1901714);
434 template <typename Polygon
, typename Box
>
435 void test_areal_clip()
437 test_one
<Polygon
, Box
, Polygon
>("boxring", example_box
, example_ring
,
439 test_one
<Polygon
, Polygon
, Box
>("boxring2", example_ring
,example_box
,
442 test_one
<Polygon
, Box
, Polygon
>("boxpoly", example_box
, example_polygon
,
445 test_one
<Polygon
, Box
, Polygon
>("poly1", example_box
,
446 "POLYGON((3.4 2,4.1 3,5.3 2.6,5.4 1.2,4.9 0.8,2.9 0.7,2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2))",
449 test_one
<Polygon
, Box
, Polygon
>("clip_poly2", example_box
,
450 "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 2.5,5.3 2.5,5.4 1.2,4.9 0.8,2.9 0.7,2 1.3))",
453 test_one
<Polygon
, Box
, Polygon
>("clip_poly3", example_box
,
454 "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 2.5,4.5 2.5,4.5 1.2,4.9 0.8,2.9 0.7,2 1.3))",
457 test_one
<Polygon
, Box
, Polygon
>("clip_poly4", example_box
,
458 "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 2.5,4.5 2.5,4.5 2.3,5.0 2.3,5.0 2.1,4.5 2.1,4.5 1.9,4.0 1.9,4.5 1.2,4.9 0.8,2.9 0.7,2 1.3))",
461 test_one
<Polygon
, Box
, Polygon
>("clip_poly5", example_box
,
462 "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 2.5,4.5 1.2,2.9 0.7,2 1.3))",
465 test_one
<Polygon
, Box
, Polygon
>("clip_poly6", example_box
,
466 "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.0 3.0,5.0 2.0,2.9 0.7,2 1.3))",
469 test_one
<Polygon
, Box
, Polygon
>("clip_poly7", "Box(0 0, 3 3)",
470 "POLYGON((2 2, 1 4, 2 4, 3 3, 2 2))",
475 template <typename P
>
476 void test_point_output()
478 typedef bg::model::linestring
<P
> linestring
;
479 typedef bg::model::polygon
<P
> polygon
;
480 typedef bg::model::box
<P
> box
;
481 //typedef bg::model::segment<P> segment;
483 test_point_output
<polygon
, polygon
>(simplex_normal
[0], simplex_normal
[1], 6);
484 test_point_output
<box
, polygon
>("box(1 1,6 4)", simplex_normal
[0], 4);
485 test_point_output
<linestring
, polygon
>("linestring(0 2,6 2)", simplex_normal
[0], 2);
486 // NYI because of sectionize:
487 // test_point_output<segment, polygon>("linestring(0 2,6 2)", simplex_normal[0], 2);
488 // NYI because needs special treatment:
489 // test_point_output<box, box>("box(0 0,4 4)", "box(2 2,6 6)", 2);
493 template <typename Polygon
, typename LineString
>
494 void test_areal_linear()
496 std::string
const poly_simplex
= "POLYGON((1 1,1 3,3 3,3 1,1 1))";
498 test_one_lp
<LineString
, Polygon
, LineString
>("simplex", poly_simplex
, "LINESTRING(0 2,4 2)", 1, 2, 2.0);
499 test_one_lp
<LineString
, Polygon
, LineString
>("case2", poly_simplex
, "LINESTRING(0 1,4 3)", 1, 2, sqrt(5.0));
500 test_one_lp
<LineString
, Polygon
, LineString
>("case3", "POLYGON((2 0,2 5,5 5,5 0,2 0))", "LINESTRING(0 1,1 2,3 2,4 3,6 3,7 4)", 1, 4, 2 + sqrt(2.0));
501 test_one_lp
<LineString
, Polygon
, LineString
>("case4", "POLYGON((0 0,0 4,2 4,2 0,0 0))", "LINESTRING(1 1,3 2,1 3)", 2, 4, sqrt(5.0));
503 test_one_lp
<LineString
, Polygon
, LineString
>("case5", poly_simplex
, "LINESTRING(0 1,3 4)", 1, 2, sqrt(2.0));
504 test_one_lp
<LineString
, Polygon
, LineString
>("case6", "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))", "LINESTRING(1 1,10 3)", 4, 8,
505 // Pieces are 1 x 2/9:
506 4.0 * sqrt(1.0 + 4.0/81.0));
507 test_one_lp
<LineString
, Polygon
, LineString
>("case7", poly_simplex
, "LINESTRING(1.5 1.5,2.5 2.5)", 1, 2, sqrt(2.0));
508 test_one_lp
<LineString
, Polygon
, LineString
>("case8", poly_simplex
, "LINESTRING(1 0,2 0)", 0, 0, 0.0);
510 std::string
const poly_9
= "POLYGON((1 1,1 4,4 4,4 1,1 1))";
511 test_one_lp
<LineString
, Polygon
, LineString
>("case9", poly_9
, "LINESTRING(0 1,1 2,2 2)", 1, 2, 1.0);
512 test_one_lp
<LineString
, Polygon
, LineString
>("case10", poly_9
, "LINESTRING(0 1,1 2,0 2)", 0, 0, 0.0);
513 test_one_lp
<LineString
, Polygon
, LineString
>("case11", poly_9
, "LINESTRING(2 2,4 2,3 3)", 1, 3, 2.0 + sqrt(2.0));
514 test_one_lp
<LineString
, Polygon
, LineString
>("case12", poly_9
, "LINESTRING(2 3,4 4,5 6)", 1, 2, sqrt(5.0));
516 test_one_lp
<LineString
, Polygon
, LineString
>("case13", poly_9
, "LINESTRING(3 2,4 4,2 3)", 1, 3, 2.0 * sqrt(5.0));
517 test_one_lp
<LineString
, Polygon
, LineString
>("case14", poly_9
, "LINESTRING(5 6,4 4,6 5)", 0, 0, 0.0);
518 test_one_lp
<LineString
, Polygon
, LineString
>("case15", poly_9
, "LINESTRING(0 2,1 2,1 3,0 3)", 1, 2, 1.0);
519 test_one_lp
<LineString
, Polygon
, LineString
>("case16", poly_9
, "LINESTRING(2 2,1 2,1 3,2 3)", 1, 4, 3.0);
521 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)";
522 // PROPERTIES CHANGED BY switch_to_integer
523 // TODO test_one_lp<LineString, Polygon, LineString>("case17", "POLYGON((1 1,1 5,4 5,4 1,1 1))", angly, 3, 8, 6.0);
524 test_one_lp
<LineString
, Polygon
, LineString
>("case18", "POLYGON((1 1,1 5,5 5,5 1,1 1))", angly
, 2, 12, 10.0 + sqrt(2.0));
525 test_one_lp
<LineString
, Polygon
, LineString
>("case19", poly_9
, "LINESTRING(1 2,1 3,0 3)", 1, 2, 1.0);
526 test_one_lp
<LineString
, Polygon
, LineString
>("case20", poly_9
, "LINESTRING(1 2,1 3,2 3)", 1, 3, 2.0);
528 test_one_lp
<LineString
, Polygon
, LineString
>("case21",
529 "POLYGON((2 3,-9 -7,12 -13,2 3))",
530 "LINESTRING(-1.3 0,-15 0,-1.3 0)",
533 test_one_lp
<LineString
, Polygon
, LineString
>("case22",
534 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
535 "LINESTRING(5 5,-10 5,5 5)",
538 test_one_lp
<LineString
, Polygon
, LineString
>("case22a",
539 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
540 "LINESTRING(1 1,5 5,-10 5,5 5,6 6)",
543 test_one_lp
<LineString
, Polygon
, LineString
>("case23",
544 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
545 "LINESTRING(-10 5,5 5,-10 5)",
548 test_one_lp
<LineString
, Polygon
, LineString
>("case23a",
549 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
550 "LINESTRING(-20 10,-10 5,5 5,-10 5,-20 -10)",
553 test_one_lp
<LineString
, Polygon
, LineString
>("case24",
554 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
555 "LINESTRING(0 5,5 5,0 5)",
558 test_one_lp
<LineString
, Polygon
, LineString
>("case24",
559 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
560 "LINESTRING(0 5,5 5,1 1,9 1,5 5,0 5)",
563 test_one_lp
<LineString
, Polygon
, LineString
>("case25",
564 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
565 "LINESTRING(5 5,0 5,5 5)",
568 test_one_lp
<LineString
, Polygon
, LineString
>("case25a",
569 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
570 "LINESTRING(-10 10,5 5,0 5,5 5,20 10)",
573 test_one_lp
<LineString
, Polygon
, LineString
>("case25b",
574 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
575 "LINESTRING(-10 10,5 5,1 5,5 5,20 10)",
578 test_one_lp
<LineString
, Polygon
, LineString
>("case25c",
579 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
580 "LINESTRING(-10 10,5 5,-1 5,5 5,20 10)",
583 test_one_lp
<LineString
, Polygon
, LineString
>("case26",
584 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
585 "LINESTRING(-5 5,0 5,-5 5)",
588 test_one_lp
<LineString
, Polygon
, LineString
>("case26a",
589 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
590 "LINESTRING(-10 10,-5 5,0 5,-5 5,-10 -10)",
593 test_one_lp
<LineString
, Polygon
, LineString
>("case27",
594 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
595 "LINESTRING(5 5,0 5,5 5,5 4,0 4,5 4)",
598 test_one_lp
<LineString
, Polygon
, LineString
>("case28",
599 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
600 "LINESTRING(5 5,0 5,5 5,5 4,0 4,5 3)",
603 test_one_lp
<LineString
, Polygon
, LineString
>("case29",
604 "POLYGON((5 5,15 15,15 5,5 5))",
605 "LINESTRING(0 0,10 10)",
606 1, 2, 5 * std::sqrt(2.0));
608 // PROPERTIES CHANGED BY switch_to_integer
609 // TODO test_one_lp<LineString, Polygon, LineString>("case21", poly_9, "LINESTRING(1 2,1 4,4 4,4 1,2 1,2 2)", 1, 6, 11.0);
611 // Compile test - arguments in any order:
612 test_one
<LineString
, Polygon
, LineString
>("simplex", poly_simplex
, "LINESTRING(0 2,4 2)", 1, 2, 2.0);
613 test_one
<LineString
, LineString
, Polygon
>("simplex", "LINESTRING(0 2,4 2)", poly_simplex
, 1, 2, 2.0);
615 typedef typename
bg::point_type
<Polygon
>::type Point
;
616 test_one
<LineString
, bg::model::ring
<Point
>, LineString
>("simplex", poly_simplex
, "LINESTRING(0 2,4 2)", 1, 2, 2.0);
618 test_one_lp
<LineString
, Polygon
, LineString
>("case30",
619 "POLYGON((25 0,0 15,30 15,22 10,25 0))",
620 "LINESTRING(10 15,20 15)",
623 test_one_lp
<LineString
, Polygon
, LineString
>("case31",
624 "POLYGON((25 0,0 15,30 15,22 10,25 0))",
625 "LINESTRING(0 15,20 15)",
628 test_one_lp
<LineString
, Polygon
, LineString
>("case32",
629 "POLYGON((25 0,0 15,30 15,22 10,25 0))",
630 "LINESTRING(25 0, 0 15,20 15)",
631 1, 3, 49.15475947422650 /*sqrt(25^2+15^2)+20*/);
633 typedef typename
bg::point_type
<Polygon
>::type P
;
635 test_one_lp
<P
, Polygon
, LineString
>("case30p",
636 "POLYGON((25 0,0 15,30 15,22 10,25 0))",
637 "LINESTRING(10 15,20 15)",
642 template <typename Linestring
, typename Box
>
643 void test_linear_box()
645 typedef bg::model::multi_linestring
<Linestring
> multi_linestring_type
;
647 test_one_lp
<Linestring
, Box
, Linestring
>
649 "BOX(-10 -10,10 10)",
650 "LINESTRING(-20 -20, 0 0,20 20)",
651 1, 3, 20 * sqrt(2.0));
653 test_one_lp
<Linestring
, Box
, Linestring
>
655 "BOX(-10 -10,10 10)",
656 "LINESTRING(-20 -20, 20 20)",
657 1, 2, 20.0 * sqrt(2.0));
659 test_one_lp
<Linestring
, Box
, Linestring
>
661 "BOX(-10 -10,10 10)",
662 "LINESTRING(-20 -20, 20 20,15 0,0 -15)",
663 2, 4, 25.0 * sqrt(2.0));
665 test_one_lp
<Linestring
, Box
, multi_linestring_type
>
667 "BOX(-10 -10,10 10)",
668 "MULTILINESTRING((-20 -20, 20 20),(0 -15,15 0))",
669 2, 4, 25.0 * sqrt(2.0));
673 template <typename P
>
676 typedef bg::model::linestring
<P
> linestring
;
677 typedef bg::model::polygon
<P
> polygon
;
678 typedef bg::model::box
<P
> box
;
679 typedef bg::model::segment
<P
> segment
;
681 typedef bg::model::polygon
<P
, false> polygon_ccw
;
682 typedef bg::model::polygon
<P
, true, false> polygon_open
;
683 typedef bg::model::polygon
<P
, false, false> polygon_ccw_open
;
684 boost::ignore_unused
<polygon_ccw
, polygon_open
, polygon_ccw_open
>();
686 std::string clip
= "box(2 2,8 8)";
688 test_areal_linear
<polygon
, linestring
>();
689 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
690 test_areal_linear
<polygon_open
, linestring
>();
691 test_areal_linear
<polygon_ccw
, linestring
>();
692 test_areal_linear
<polygon_ccw_open
, linestring
>();
695 test_linear_box
<linestring
, box
>();
697 // Test polygons clockwise and counter clockwise
698 test_areal
<polygon
>();
700 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
701 test_areal
<polygon_ccw
>();
702 test_areal
<polygon_open
>();
703 test_areal
<polygon_ccw_open
>();
706 test_areal_clip
<polygon
, box
>();
707 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
708 test_areal_clip
<polygon_ccw
, box
>();
711 #if defined(TEST_FAIL_DIFFERENT_ORIENTATIONS)
712 // Should NOT compile
713 // NOTE: this can probably be relaxed later on.
714 test_one
<polygon
, polygon_ccw
, polygon
>("simplex_normal",
715 simplex_normal
[0], simplex_normal
[1],
717 // Output ccw, nyi (should be just reversing afterwards)
718 test_one
<polygon
, polygon
, polygon_ccw
>("simplex_normal",
719 simplex_normal
[0], simplex_normal
[1],
723 // Basic check: box/linestring, is clipping OK? should compile in any order
724 test_one
<linestring
, linestring
, box
>("llb", "LINESTRING(0 0,10 10)", clip
, 1, 2, sqrt(2.0 * 6.0 * 6.0));
725 test_one
<linestring
, box
, linestring
>("lbl", clip
, "LINESTRING(0 0,10 10)", 1, 2, sqrt(2.0 * 6.0 * 6.0));
728 test_one
<linestring
, segment
, box
>("lsb", "LINESTRING(0 0,10 10)", clip
, 1, 2, sqrt(2.0 * 6.0 * 6.0));
729 test_one
<linestring
, box
, segment
>("lbs", clip
, "LINESTRING(0 0,10 10)", 1, 2, sqrt(2.0 * 6.0 * 6.0));
732 test_one
<linestring
, linestring
, box
>("llbi", "LINESTRING(3 3,7 7)", clip
, 1, 2, sqrt(2.0 * 4.0 * 4.0));
734 // Completely outside
735 test_one
<linestring
, linestring
, box
>("llbo", "LINESTRING(9 9,10 10)", clip
, 0, 0, 0.0);
737 // Touching with point (-> output linestring with ONE point)
738 test_one
<linestring
, linestring
, box
>("llb_touch", "LINESTRING(8 8,10 10)", clip
, 1, 1, 0.0,
739 ut_settings(0.0001, false));
742 test_one
<linestring
, linestring
, box
>("llb_along", "LINESTRING(2 2,2 8)", clip
, 1, 2, 6.0);
744 // Outputting two lines (because of 3-4-5 constructions (0.3,0.4,0.5)
745 // which occur 4 times, the length is expected to be 2.0)
746 test_one
<linestring
, linestring
, box
>("llb_2", "LINESTRING(1.7 1.6,2.3 2.4,2.9 1.6,3.5 2.4,4.1 1.6)", clip
, 2, 6, 4.0 * 0.5);
749 test_one
<P
, linestring
, linestring
>("llp1", "LINESTRING(0 0,1 1)", "LINESTRING(0 1,1 0)", 1, 1, 0.0);
750 test_one
<P
, segment
, segment
>("ssp1", "LINESTRING(0 0,1 1)", "LINESTRING(0 1,1 0)", 1, 1, 0.0);
751 test_one
<P
, linestring
, linestring
>("llp2", "LINESTRING(0 0,1 1)", "LINESTRING(0 0,2 2)", 2, 2, 0.0);
753 // polygons outputing points
754 //test_one<P, polygon, polygon>("ppp1", simplex_normal[0], simplex_normal[1], 1, 7, 5.47363293);
756 test_point_output
<P
>();
759 test_one<polygon, box, polygon>(99, "box(115041.10 471900.10, 118334.60 474523.40)",
760 "POLYGON ((115483.40 474533.40, 116549.40 474059.20, 117199.90 473762.50, 117204.90 473659.50, 118339.40 472796.90, 118334.50 472757.90, 118315.10 472604.00, 118344.60 472520.90, 118277.90 472419.10, 118071.40 472536.80, 118071.40 472536.80, 117943.10 472287.70, 117744.90 472248.40, 117708.00 472034.50, 117481.90 472056.90, 117481.90 472056.90, 117272.30 471890.10, 117077.90 472161.20, 116146.60 473054.50, 115031.10 473603.30, 115483.40 474533.40))",
765 void test_pointer_version()
767 std::vector
<test::test_point_xy
*> ln
;
768 test::test_point_xy
* p
;
769 p
= new test::test_point_xy
; p
->x
= 0; p
->y
= 0; ln
.push_back(p
);
770 p
= new test::test_point_xy
; p
->x
= 10; p
->y
= 10; ln
.push_back(p
);
772 bg::model::box
<bg::model::d2::point_xy
<double> > box
;
773 bg::assign_values(box
, 2, 2, 8, 8);
775 typedef bg::model::linestring
<bg::model::d2::point_xy
<double> > output_type
;
776 std::vector
<output_type
> clip
;
777 bg::detail::intersection::intersection_insert
<output_type
>(box
, ln
, std::back_inserter(clip
));
781 for (std::vector
<output_type
>::const_iterator it
= clip
.begin();
782 it
!= clip
.end(); ++it
)
784 length
+= bg::length(*it
);
785 n
+= bg::num_points(*it
);
788 BOOST_CHECK_EQUAL(clip
.size(), 1u);
789 BOOST_CHECK_EQUAL(n
, 2u);
790 BOOST_CHECK_CLOSE(length
, sqrt(2.0 * 6.0 * 6.0), 0.001);
792 for (std::size_t i
= 0; i
< ln
.size(); i
++)
799 template <typename P
>
800 void test_exception()
802 typedef bg::model::polygon
<P
> polygon
;
806 // Define polygon with a spike (= invalid)
807 std::string spike
= "POLYGON((0 0,0 4,2 4,2 6,2 4,4 4,4 0,0 0))";
809 test_one
<polygon
, polygon
, polygon
>("with_spike",
810 simplex_normal
[0], spike
,
813 catch(bg::overlay_invalid_input_exception
const& )
817 BOOST_CHECK_MESSAGE(false, "No exception thrown");
820 template <typename Point
>
823 typedef bg::model::polygon
<Point
> polygon
;
824 test_one
<polygon
, polygon
, polygon
>("simplex_normal",
825 simplex_normal
[0], simplex_normal
[1],
829 template <typename CoordinateType
>
830 void test_ticket_10868(std::string
const& wkt_out
)
832 typedef bg::model::point
<CoordinateType
, 2, bg::cs::cartesian
> point_type
;
833 typedef bg::model::polygon
835 point_type
, /*ClockWise*/false, /*Closed*/false
837 typedef bg::model::multi_polygon
<polygon_type
> multipolygon_type
;
839 polygon_type polygon1
;
840 bg::read_wkt(ticket_10868
[0], polygon1
);
841 polygon_type polygon2
;
842 bg::read_wkt(ticket_10868
[1], polygon2
);
844 multipolygon_type multipolygon_out
;
845 bg::intersection(polygon1
, polygon2
, multipolygon_out
);
846 std::stringstream stream
;
847 stream
<< bg::wkt(multipolygon_out
);
849 BOOST_CHECK_EQUAL(stream
.str(), wkt_out
);
851 test_one
<polygon_type
, polygon_type
, polygon_type
>("ticket_10868",
852 ticket_10868
[0], ticket_10868
[1],
853 1, 7, 20266195244586.0);
856 int test_main(int, char* [])
858 BoostGeometryWriteTestConfiguration();
859 test_all
<bg::model::d2::point_xy
<default_test_type
> >();
861 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
862 test_all
<bg::model::d2::point_xy
<float> >();
864 // Commented, because exception is now disabled:
865 // test_exception<bg::model::d2::point_xy<double> >();
867 test_pointer_version();
868 #if ! defined(BOOST_GEOMETRY_RESCALE_TO_ROBUST)
869 test_rational
<bg::model::d2::point_xy
<boost::rational
<int> > >();
872 #if defined(BOOST_GEOMETRY_TEST_FAILURES)
873 // ticket #10868 still fails for 32-bit integers
874 test_ticket_10868
<int32_t>("MULTIPOLYGON(((33520458 6878575,33480192 14931538,31446819 18947953,30772384 19615678,30101303 19612322,30114725 16928001,33520458 6878575)))");
876 #if !defined(BOOST_NO_INT64_T) || defined(BOOST_HAS_MS_INT64)
877 test_ticket_10868
<int64_t>("MULTIPOLYGON(((33520458 6878575,33480192 14931538,31446819 18947953,30772384 19615678,30101303 19612322,30114725 16928001,33520458 6878575)))");
880 if (BOOST_GEOMETRY_CONDITION(sizeof(long) * CHAR_BIT
>= 64))
882 test_ticket_10868
<long>("MULTIPOLYGON(((33520458 6878575,33480192 14931538,31446819 18947953,30772384 19615678,30101303 19612322,30114725 16928001,33520458 6878575)))");
885 test_ticket_10868
<long long>("MULTIPOLYGON(((33520458 6878575,33480192 14931538,31446819 18947953,30772384 19615678,30101303 19612322,30114725 16928001,33520458 6878575)))");
889 #if defined(BOOST_GEOMETRY_TEST_FAILURES)
890 // llb_touch generates a polygon with 1 point and is therefore invalid everywhere
891 // TODO: this should be easy to fix
892 BoostGeometryWriteExpectedFailures(6, 2, 7, 1);