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, 2016.
9 // Modifications copyright (c) 2015-2016, 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
)
46 template <typename Polygon
>
49 typedef typename
bg::coordinate_type
<Polygon
>::type ct
;
50 bool const ccw
= bg::point_order
<Polygon
>::value
== bg::counterclockwise
;
51 bool const open
= bg::closure
<Polygon
>::value
== bg::open
;
53 ut_settings ignore_validity
;
54 ignore_validity
.test_validity
= false;
57 test_one
<Polygon
, Polygon
, Polygon
>("simplex_with_empty_1",
58 simplex_normal
[0], polygon_empty
,
60 test_one
<Polygon
, Polygon
, Polygon
>("simplex_with_empty_2",
61 polygon_empty
, simplex_normal
[0],
64 test_one
<Polygon
, Polygon
, Polygon
>("simplex_normal",
65 simplex_normal
[0], simplex_normal
[1],
67 test_one
<Polygon
, Polygon
, Polygon
>("star_ring", example_star
, example_ring
,
70 test_one
<Polygon
, Polygon
, Polygon
>("star_poly", example_star
, example_polygon
,
71 1, 0, // CLN: 23 points, other types: 22 point (one is merged)
73 test_one
<Polygon
, Polygon
, Polygon
>("first_within_second1",
74 first_within_second
[0], first_within_second
[1],
77 test_one
<Polygon
, Polygon
, Polygon
>("first_within_second2",
78 first_within_second
[1], first_within_second
[0],
81 test_one
<Polygon
, Polygon
, Polygon
>("first_within_hole_of_second",
82 first_within_hole_of_second
[0], first_within_hole_of_second
[1],
85 // Two forming new hole
86 test_one
<Polygon
, Polygon
, Polygon
>("new_hole",
87 new_hole
[0], new_hole
[1],
91 test_one
<Polygon
, Polygon
, Polygon
>("identical",
92 identical
[0], identical
[1],
95 test_one
<Polygon
, Polygon
, Polygon
>("intersect_exterior_and_interiors_winded",
96 intersect_exterior_and_interiors_winded
[0], intersect_exterior_and_interiors_winded
[1],
99 test_one
<Polygon
, Polygon
, Polygon
>("intersect_holes_disjoint",
100 intersect_holes_disjoint
[0], intersect_holes_disjoint
[1],
103 test_one
<Polygon
, Polygon
, Polygon
>("intersect_holes_intersect",
104 intersect_holes_intersect
[0], intersect_holes_intersect
[1],
107 test_one
<Polygon
, Polygon
, Polygon
>("intersect_holes_intersect_and_disjoint",
108 intersect_holes_intersect_and_disjoint
[0], intersect_holes_intersect_and_disjoint
[1],
111 test_one
<Polygon
, Polygon
, Polygon
>("intersect_holes_intersect_and_touch",
112 intersect_holes_intersect_and_touch
[0], intersect_holes_intersect_and_touch
[1],
115 test_one
<Polygon
, Polygon
, Polygon
>("intersect_holes_new_ring",
116 intersect_holes_new_ring
[0], intersect_holes_new_ring
[1],
119 test_one
<Polygon
, Polygon
, Polygon
>("winded",
120 winded
[0], winded
[1],
123 test_one
<Polygon
, Polygon
, Polygon
>("within_holes_disjoint",
124 within_holes_disjoint
[0], within_holes_disjoint
[1],
127 test_one
<Polygon
, Polygon
, Polygon
>("side_side",
128 side_side
[0], side_side
[1],
131 test_one
<Polygon
, Polygon
, Polygon
>("two_bends",
132 two_bends
[0], two_bends
[1],
135 test_one
<Polygon
, Polygon
, Polygon
>("star_comb_15",
136 star_comb_15
[0], star_comb_15
[1],
137 28, 150, 189.952883);
139 test_one
<Polygon
, Polygon
, Polygon
>("simplex_normal",
140 simplex_normal
[0], simplex_normal
[1],
143 test_one
<Polygon
, Polygon
, Polygon
>("distance_zero",
144 distance_zero
[0], distance_zero
[1],
145 1, 0 /* f: 4, other: 5 */, 0.29516139, ut_settings(0.01));
147 test_one
<Polygon
, Polygon
, Polygon
>("equal_holes_disjoint",
148 equal_holes_disjoint
[0], equal_holes_disjoint
[1],
149 1, 20, 81.0 - 2.0 * 3.0 * 3.0 - 3.0 * 7.0);
151 test_one
<Polygon
, Polygon
, Polygon
>("only_hole_intersections1",
152 only_hole_intersections
[0], only_hole_intersections
[1],
154 test_one
<Polygon
, Polygon
, Polygon
>("only_hole_intersection2",
155 only_hole_intersections
[0], only_hole_intersections
[2],
158 test_one
<Polygon
, Polygon
, Polygon
>("fitting",
159 fitting
[0], fitting
[1],
162 test_one
<Polygon
, Polygon
, Polygon
>("crossed",
163 crossed
[0], crossed
[1],
166 test_one
<Polygon
, Polygon
, Polygon
>("pie_2_3_23_0",
167 pie_2_3_23_0
[0], pie_2_3_23_0
[1],
168 1, 4, 163292.679042133, ut_settings(0.1));
170 #if defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
171 test_one
<Polygon
, Polygon
, Polygon
>("isovist",
172 isovist1
[0], isovist1
[1],
176 // SQL Server gives: 88.1920416352664
177 // PostGIS gives: 88.19203677911
178 test_one
<Polygon
, Polygon
, Polygon
>("isovist",
179 isovist1
[0], isovist1
[1],
181 ut_settings(if_typed_tt
<ct
>(0.01, 0.1)));
184 test_one
<Polygon
, Polygon
, Polygon
>("geos_1",
185 geos_1
[0], geos_1
[1],
186 1, -1, 3461.0214843, // MSVC 14 reports 3461.025390625
187 ut_settings(0.005, false));
190 // In most cases: 0 (no intersection)
191 // In some cases: 1.430511474609375e-05 (clang/gcc on Xubuntu using b2)
192 // In some cases: 5.6022983000000002e-05 (powerpc64le-gcc-6-0)
193 test_one
<Polygon
, Polygon
, Polygon
>("geos_2",
194 geos_2
[0], geos_2
[1],
195 0, 0, 6.0e-5, ut_settings(-1.0)); // -1 denotes: compare with <=
197 #if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
198 test_one
<Polygon
, Polygon
, Polygon
>("geos_3",
199 geos_3
[0], geos_3
[1],
202 test_one
<Polygon
, Polygon
, Polygon
>("geos_4",
203 geos_4
[0], geos_4
[1],
207 if ( BOOST_GEOMETRY_CONDITION(! ccw
&& open
) )
209 // Pointcount for ttmath/double (both 5) or float (4)
210 // double returns 5 (since method append_no_dups_or_spikes)
211 // but not for ccw/open. Those cases has to be adapted once, anyway,
212 // because for open always one point too much is generated...
213 test_one
<Polygon
, Polygon
, Polygon
>("ggl_list_20110306_javier",
214 ggl_list_20110306_javier
[0], ggl_list_20110306_javier
[1],
215 1, if_typed
<ct
, float>(4, 5),
217 ut_settings(if_typed
<ct
, float>(1.0, 0.01)));
220 // SQL Server reports: 0.400390625
221 // PostGIS reports 0.4
222 // BG did report 0.4 but is changed to 0.397
223 // when selecting other IP closer at endpoint or if segment B is smaller than A
224 test_one
<Polygon
, Polygon
, Polygon
>("ggl_list_20110307_javier",
225 ggl_list_20110307_javier
[0], ggl_list_20110307_javier
[1],
227 #if defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
230 0.397162651, ut_settings(0.01)
234 #if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
235 test_one
<Polygon
, Polygon
, Polygon
>("ggl_list_20110627_phillip",
236 ggl_list_20110627_phillip
[0], ggl_list_20110627_phillip
[1],
237 1, if_typed_tt
<ct
>(6, 5), 11151.6618);
240 test_one
<Polygon
, Polygon
, Polygon
>("ggl_list_20110716_enrico",
241 ggl_list_20110716_enrico
[0], ggl_list_20110716_enrico
[1],
242 3, 16, 35723.8506317139);
244 test_one
<Polygon
, Polygon
, Polygon
>("ggl_list_20131119_james",
245 ggl_list_20131119_james
[0], ggl_list_20131119_james
[1],
246 1, 4, 6.6125873045, ut_settings(0.1));
248 test_one
<Polygon
, Polygon
, Polygon
>("ggl_list_20140223_shalabuda",
249 ggl_list_20140223_shalabuda
[0], ggl_list_20140223_shalabuda
[1],
250 1, 4, 3.77106, ut_settings(0.001));
252 // Mailed to the Boost.Geometry list on 2014/03/21 by 7415963@gmail.com
253 test_one
<Polygon
, Polygon
, Polygon
>("ggl_list_20140321_7415963",
254 ggl_list_20140321_7415963
[0], ggl_list_20140321_7415963
[1],
255 0, 0, 0, ut_settings(0.1));
257 #if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
258 test_one
<Polygon
, Polygon
, Polygon
>("buffer_rt_f", buffer_rt_f
[0], buffer_rt_f
[1],
259 1, 4, 0.00029437899183903937, ut_settings(0.01));
261 test_one
<Polygon
, Polygon
, Polygon
>("buffer_rt_g", buffer_rt_g
[0], buffer_rt_g
[1],
262 1, 0, 2.914213562373);
265 test_one
<Polygon
, Polygon
, Polygon
>("ticket_8254", ticket_8254
[0], ticket_8254
[1],
266 1, 4, 3.635930e-08, ut_settings(0.01));
267 test_one
<Polygon
, Polygon
, Polygon
>("ticket_6958", ticket_6958
[0], ticket_6958
[1],
268 1, 4, 4.34355e-05, ut_settings(0.01));
269 test_one
<Polygon
, Polygon
, Polygon
>("ticket_8652", ticket_8652
[0], ticket_8652
[1],
272 test_one
<Polygon
, Polygon
, Polygon
>("ticket_8310a", ticket_8310a
[0], ticket_8310a
[1],
274 test_one
<Polygon
, Polygon
, Polygon
>("ticket_8310b", ticket_8310b
[0], ticket_8310b
[1],
276 test_one
<Polygon
, Polygon
, Polygon
>("ticket_8310c", ticket_8310c
[0], ticket_8310c
[1],
279 test_one
<Polygon
, Polygon
, Polygon
>("ticket_9081_15",
280 ticket_9081_15
[0], ticket_9081_15
[1],
281 1, 4, 0.0068895780745301394);
283 test_one
<Polygon
, Polygon
, Polygon
>("ticket_10108_a",
284 ticket_10108_a
[0], ticket_10108_a
[1],
287 #if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
289 // mingw 5.6022954e-5
290 test_one
<Polygon
, Polygon
, Polygon
>("ticket_10108_b",
291 ticket_10108_b
[0], ticket_10108_b
[1],
295 test_one
<Polygon
, Polygon
, Polygon
>("ticket_10747_a",
296 ticket_10747_a
[0], ticket_10747_a
[1],
297 1, 4, 70368744177664);
298 test_one
<Polygon
, Polygon
, Polygon
>("ticket_10747_b",
299 ticket_10747_b
[0], ticket_10747_b
[1],
300 1, 4, 7036874417766400);
301 test_one
<Polygon
, Polygon
, Polygon
>("ticket_10747_c",
302 ticket_10747_c
[0], ticket_10747_c
[1],
303 1, 4, 17592186044416);
304 test_one
<Polygon
, Polygon
, Polygon
>("ticket_10747_d",
305 ticket_10747_d
[0], ticket_10747_d
[1],
307 test_one
<Polygon
, Polygon
, Polygon
>("ticket_10747_e",
308 ticket_10747_e
[0], ticket_10747_e
[1],
309 1, 4, 7.0368748575710959e-15);
311 test_one
<Polygon
, Polygon
, Polygon
>("ticket_11576",
312 ticket_11576
[0], ticket_11576
[1],
313 1, 0, 5.585617332907136e-07);
315 test_one
<Polygon
, Polygon
, Polygon
>("ticket_9563", ticket_9563
[0], ticket_9563
[1],
318 test_one
<Polygon
, Polygon
, Polygon
>("buffer_mp1", buffer_mp1
[0], buffer_mp1
[1],
320 test_one
<Polygon
, Polygon
, Polygon
>("buffer_mp2", buffer_mp2
[0], buffer_mp2
[1],
323 test_one
<Polygon
, Polygon
, Polygon
>("case_58_iet",
324 case_58
[0], case_58
[2],
327 test_one
<Polygon
, Polygon
, Polygon
>("case_80",
328 case_80
[0], case_80
[1],
331 test_one
<Polygon
, Polygon
, Polygon
>("case_81",
332 case_81
[0], case_81
[1],
335 test_one
<Polygon
, Polygon
, Polygon
>("mysql_21964049",
336 mysql_21964049
[0], mysql_21964049
[1],
339 test_one
<Polygon
, Polygon
, Polygon
>("mysql_21964465",
340 mysql_21964465
[0], mysql_21964465
[1],
343 test_one
<Polygon
, Polygon
, Polygon
>("mysql_21965285_b_inv",
344 mysql_21965285_b_inv
[0],
345 mysql_21965285_b_inv
[1],
346 2, -1, 183.71376870369406);
348 test_one
<Polygon
, Polygon
, Polygon
>("mysql_23023665_6",
349 mysql_23023665_6
[0], mysql_23023665_6
[1],
350 1, -1, 11.812440191387557,
353 test_one
<Polygon
, Polygon
, Polygon
>("mysql_23023665_10",
354 mysql_23023665_10
[0], mysql_23023665_10
[1],
355 1, 0, -1, 54.701340543162523,
358 test_one
<Polygon
, Polygon
, Polygon
>("mysql_23023665_11",
359 mysql_23023665_11
[0], mysql_23023665_11
[1],
360 1, 0, -1, 35.933385462482065,
363 // test_one<Polygon, Polygon, Polygon>(
364 // "polygon_pseudo_line",
365 // "Polygon((0 0,0 4,4 4,4 0,0 0))",
366 // "Polygon((2 -2,2 -1,2 6,2 -2))",
367 // 5, 22, 1.1901714);
370 template <typename Polygon
, typename Box
>
371 void test_areal_clip()
373 test_one
<Polygon
, Box
, Polygon
>("boxring", example_box
, example_ring
,
375 test_one
<Polygon
, Polygon
, Box
>("boxring2", example_ring
,example_box
,
378 test_one
<Polygon
, Box
, Polygon
>("boxpoly", example_box
, example_polygon
,
381 test_one
<Polygon
, Box
, Polygon
>("poly1", example_box
,
382 "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))",
385 test_one
<Polygon
, Box
, Polygon
>("clip_poly2", example_box
,
386 "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))",
389 test_one
<Polygon
, Box
, Polygon
>("clip_poly3", example_box
,
390 "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))",
393 test_one
<Polygon
, Box
, Polygon
>("clip_poly4", example_box
,
394 "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))",
397 test_one
<Polygon
, Box
, Polygon
>("clip_poly5", example_box
,
398 "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))",
401 test_one
<Polygon
, Box
, Polygon
>("clip_poly6", example_box
,
402 "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))",
405 test_one
<Polygon
, Box
, Polygon
>("clip_poly7", "Box(0 0, 3 3)",
406 "POLYGON((2 2, 1 4, 2 4, 3 3, 2 2))",
411 template <typename Box
>
412 void test_boxes(std::string
const& wkt1
, std::string
const& wkt2
, double expected_area
, bool expected_result
)
415 bg::read_wkt(wkt1
, box1
);
416 bg::read_wkt(wkt2
, box2
);
419 bg::assign_zero(box_out
);
420 bool detected
= bg::intersection(box1
, box2
, box_out
);
421 typename
bg::default_area_result
<Box
>::type area
= bg::area(box_out
);
423 BOOST_CHECK_EQUAL(detected
, expected_result
);
424 if (detected
&& expected_result
)
426 BOOST_CHECK_CLOSE(area
, expected_area
, 0.01);
430 template <typename P
>
431 void test_point_output()
433 typedef bg::model::linestring
<P
> linestring
;
434 typedef bg::model::polygon
<P
> polygon
;
435 typedef bg::model::box
<P
> box
;
436 //typedef bg::model::segment<P> segment;
438 test_point_output
<polygon
, polygon
>(simplex_normal
[0], simplex_normal
[1], 6);
439 test_point_output
<box
, polygon
>("box(1 1,6 4)", simplex_normal
[0], 4);
440 test_point_output
<linestring
, polygon
>("linestring(0 2,6 2)", simplex_normal
[0], 2);
441 // NYI because of sectionize:
442 // test_point_output<segment, polygon>("linestring(0 2,6 2)", simplex_normal[0], 2);
443 // NYI because needs special treatment:
444 // test_point_output<box, box>("box(0 0,4 4)", "box(2 2,6 6)", 2);
448 template <typename Polygon
, typename LineString
>
449 void test_areal_linear()
451 std::string
const poly_simplex
= "POLYGON((1 1,1 3,3 3,3 1,1 1))";
453 test_one_lp
<LineString
, Polygon
, LineString
>("simplex", poly_simplex
, "LINESTRING(0 2,4 2)", 1, 2, 2.0);
454 test_one_lp
<LineString
, Polygon
, LineString
>("case2", poly_simplex
, "LINESTRING(0 1,4 3)", 1, 2, sqrt(5.0));
455 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));
456 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));
458 test_one_lp
<LineString
, Polygon
, LineString
>("case5", poly_simplex
, "LINESTRING(0 1,3 4)", 1, 2, sqrt(2.0));
459 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,
460 // Pieces are 1 x 2/9:
461 4.0 * sqrt(1.0 + 4.0/81.0));
462 test_one_lp
<LineString
, Polygon
, LineString
>("case7", poly_simplex
, "LINESTRING(1.5 1.5,2.5 2.5)", 1, 2, sqrt(2.0));
463 test_one_lp
<LineString
, Polygon
, LineString
>("case8", poly_simplex
, "LINESTRING(1 0,2 0)", 0, 0, 0.0);
465 std::string
const poly_9
= "POLYGON((1 1,1 4,4 4,4 1,1 1))";
466 test_one_lp
<LineString
, Polygon
, LineString
>("case9", poly_9
, "LINESTRING(0 1,1 2,2 2)", 1, 2, 1.0);
467 test_one_lp
<LineString
, Polygon
, LineString
>("case10", poly_9
, "LINESTRING(0 1,1 2,0 2)", 0, 0, 0.0);
468 test_one_lp
<LineString
, Polygon
, LineString
>("case11", poly_9
, "LINESTRING(2 2,4 2,3 3)", 1, 3, 2.0 + sqrt(2.0));
469 test_one_lp
<LineString
, Polygon
, LineString
>("case12", poly_9
, "LINESTRING(2 3,4 4,5 6)", 1, 2, sqrt(5.0));
471 test_one_lp
<LineString
, Polygon
, LineString
>("case13", poly_9
, "LINESTRING(3 2,4 4,2 3)", 1, 3, 2.0 * sqrt(5.0));
472 test_one_lp
<LineString
, Polygon
, LineString
>("case14", poly_9
, "LINESTRING(5 6,4 4,6 5)", 0, 0, 0.0);
473 test_one_lp
<LineString
, Polygon
, LineString
>("case15", poly_9
, "LINESTRING(0 2,1 2,1 3,0 3)", 1, 2, 1.0);
474 test_one_lp
<LineString
, Polygon
, LineString
>("case16", poly_9
, "LINESTRING(2 2,1 2,1 3,2 3)", 1, 4, 3.0);
476 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)";
477 // PROPERTIES CHANGED BY switch_to_integer
478 // TODO test_one_lp<LineString, Polygon, LineString>("case17", "POLYGON((1 1,1 5,4 5,4 1,1 1))", angly, 3, 8, 6.0);
479 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));
480 test_one_lp
<LineString
, Polygon
, LineString
>("case19", poly_9
, "LINESTRING(1 2,1 3,0 3)", 1, 2, 1.0);
481 test_one_lp
<LineString
, Polygon
, LineString
>("case20", poly_9
, "LINESTRING(1 2,1 3,2 3)", 1, 3, 2.0);
483 test_one_lp
<LineString
, Polygon
, LineString
>("case21",
484 "POLYGON((2 3,-9 -7,12 -13,2 3))",
485 "LINESTRING(-1.3 0,-15 0,-1.3 0)",
488 test_one_lp
<LineString
, Polygon
, LineString
>("case22",
489 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
490 "LINESTRING(5 5,-10 5,5 5)",
493 test_one_lp
<LineString
, Polygon
, LineString
>("case22a",
494 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
495 "LINESTRING(1 1,5 5,-10 5,5 5,6 6)",
498 test_one_lp
<LineString
, Polygon
, LineString
>("case23",
499 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
500 "LINESTRING(-10 5,5 5,-10 5)",
503 test_one_lp
<LineString
, Polygon
, LineString
>("case23a",
504 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
505 "LINESTRING(-20 10,-10 5,5 5,-10 5,-20 -10)",
508 test_one_lp
<LineString
, Polygon
, LineString
>("case24",
509 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
510 "LINESTRING(0 5,5 5,0 5)",
513 test_one_lp
<LineString
, Polygon
, LineString
>("case24",
514 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
515 "LINESTRING(0 5,5 5,1 1,9 1,5 5,0 5)",
518 test_one_lp
<LineString
, Polygon
, LineString
>("case25",
519 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
520 "LINESTRING(5 5,0 5,5 5)",
523 test_one_lp
<LineString
, Polygon
, LineString
>("case25a",
524 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
525 "LINESTRING(-10 10,5 5,0 5,5 5,20 10)",
528 test_one_lp
<LineString
, Polygon
, LineString
>("case25b",
529 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
530 "LINESTRING(-10 10,5 5,1 5,5 5,20 10)",
533 test_one_lp
<LineString
, Polygon
, LineString
>("case25c",
534 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
535 "LINESTRING(-10 10,5 5,-1 5,5 5,20 10)",
538 test_one_lp
<LineString
, Polygon
, LineString
>("case26",
539 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
540 "LINESTRING(-5 5,0 5,-5 5)",
543 test_one_lp
<LineString
, Polygon
, LineString
>("case26a",
544 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
545 "LINESTRING(-10 10,-5 5,0 5,-5 5,-10 -10)",
548 test_one_lp
<LineString
, Polygon
, LineString
>("case27",
549 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
550 "LINESTRING(5 5,0 5,5 5,5 4,0 4,5 4)",
553 test_one_lp
<LineString
, Polygon
, LineString
>("case28",
554 "POLYGON((0 0,0 10,10 10,10 0,0 0))",
555 "LINESTRING(5 5,0 5,5 5,5 4,0 4,5 3)",
558 test_one_lp
<LineString
, Polygon
, LineString
>("case29",
559 "POLYGON((5 5,15 15,15 5,5 5))",
560 "LINESTRING(0 0,10 10)",
561 1, 2, 5 * std::sqrt(2.0));
563 // PROPERTIES CHANGED BY switch_to_integer
564 // 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);
566 // Compile test - arguments in any order:
567 test_one
<LineString
, Polygon
, LineString
>("simplex", poly_simplex
, "LINESTRING(0 2,4 2)", 1, 2, 2.0);
568 test_one
<LineString
, LineString
, Polygon
>("simplex", "LINESTRING(0 2,4 2)", poly_simplex
, 1, 2, 2.0);
570 typedef typename
bg::point_type
<Polygon
>::type Point
;
571 test_one
<LineString
, bg::model::ring
<Point
>, LineString
>("simplex", poly_simplex
, "LINESTRING(0 2,4 2)", 1, 2, 2.0);
576 template <typename Linestring
, typename Box
>
577 void test_linear_box()
579 typedef bg::model::multi_linestring
<Linestring
> multi_linestring_type
;
581 test_one_lp
<Linestring
, Box
, Linestring
>
583 "BOX(-10 -10,10 10)",
584 "LINESTRING(-20 -20, 0 0,20 20)",
585 1, 3, 20 * sqrt(2.0));
587 test_one_lp
<Linestring
, Box
, Linestring
>
589 "BOX(-10 -10,10 10)",
590 "LINESTRING(-20 -20, 20 20)",
591 1, 2, 20.0 * sqrt(2.0));
593 test_one_lp
<Linestring
, Box
, Linestring
>
595 "BOX(-10 -10,10 10)",
596 "LINESTRING(-20 -20, 20 20,15 0,0 -15)",
597 2, 4, 25.0 * sqrt(2.0));
599 test_one_lp
<Linestring
, Box
, multi_linestring_type
>
601 "BOX(-10 -10,10 10)",
602 "MULTILINESTRING((-20 -20, 20 20),(0 -15,15 0))",
603 2, 4, 25.0 * sqrt(2.0));
607 template <typename P
>
610 typedef bg::model::linestring
<P
> linestring
;
611 typedef bg::model::polygon
<P
> polygon
;
612 typedef bg::model::box
<P
> box
;
613 typedef bg::model::segment
<P
> segment
;
615 typedef bg::model::polygon
<P
, false> polygon_ccw
;
616 typedef bg::model::polygon
<P
, true, false> polygon_open
;
617 typedef bg::model::polygon
<P
, false, false> polygon_ccw_open
;
618 boost::ignore_unused
<polygon_ccw
, polygon_open
, polygon_ccw_open
>();
620 ut_settings ignore_validity
;
621 ignore_validity
.test_validity
= false;
623 std::string clip
= "box(2 2,8 8)";
625 test_areal_linear
<polygon
, linestring
>();
626 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
627 test_areal_linear
<polygon_open
, linestring
>();
628 test_areal_linear
<polygon_ccw
, linestring
>();
629 test_areal_linear
<polygon_ccw_open
, linestring
>();
632 test_linear_box
<linestring
, box
>();
634 // Test polygons clockwise and counter clockwise
635 test_areal
<polygon
>();
637 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
638 test_areal
<polygon_ccw
>();
639 test_areal
<polygon_open
>();
640 test_areal
<polygon_ccw_open
>();
643 test_areal_clip
<polygon
, box
>();
644 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
645 test_areal_clip
<polygon_ccw
, box
>();
648 #if defined(TEST_FAIL_DIFFERENT_ORIENTATIONS)
649 // Should NOT compile
650 // NOTE: this can probably be relaxed later on.
651 test_one
<polygon
, polygon_ccw
, polygon
>("simplex_normal",
652 simplex_normal
[0], simplex_normal
[1],
654 // Output ccw, nyi (should be just reversing afterwards)
655 test_one
<polygon
, polygon
, polygon_ccw
>("simplex_normal",
656 simplex_normal
[0], simplex_normal
[1],
660 // Basic check: box/linestring, is clipping OK? should compile in any order
661 test_one
<linestring
, linestring
, box
>("llb", "LINESTRING(0 0,10 10)", clip
, 1, 2, sqrt(2.0 * 6.0 * 6.0));
662 test_one
<linestring
, box
, linestring
>("lbl", clip
, "LINESTRING(0 0,10 10)", 1, 2, sqrt(2.0 * 6.0 * 6.0));
665 test_one
<linestring
, segment
, box
>("lsb", "LINESTRING(0 0,10 10)", clip
, 1, 2, sqrt(2.0 * 6.0 * 6.0));
666 test_one
<linestring
, box
, segment
>("lbs", clip
, "LINESTRING(0 0,10 10)", 1, 2, sqrt(2.0 * 6.0 * 6.0));
669 test_one
<linestring
, linestring
, box
>("llbi", "LINESTRING(3 3,7 7)", clip
, 1, 2, sqrt(2.0 * 4.0 * 4.0));
671 // Completely outside
672 test_one
<linestring
, linestring
, box
>("llbo", "LINESTRING(9 9,10 10)", clip
, 0, 0, 0.0);
674 // Touching with point (-> output linestring with ONE point)
675 test_one
<linestring
, linestring
, box
>("llb_touch", "LINESTRING(8 8,10 10)", clip
, 1, 1, 0.0, ignore_validity
);
678 test_one
<linestring
, linestring
, box
>("llb_along", "LINESTRING(2 2,2 8)", clip
, 1, 2, 6.0);
680 // Outputting two lines (because of 3-4-5 constructions (0.3,0.4,0.5)
681 // which occur 4 times, the length is expected to be 2.0)
682 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);
685 test_one
<P
, linestring
, linestring
>("llp1", "LINESTRING(0 0,1 1)", "LINESTRING(0 1,1 0)", 1, 1, 0.0);
686 test_one
<P
, segment
, segment
>("ssp1", "LINESTRING(0 0,1 1)", "LINESTRING(0 1,1 0)", 1, 1, 0.0);
687 test_one
<P
, linestring
, linestring
>("llp2", "LINESTRING(0 0,1 1)", "LINESTRING(0 0,2 2)", 2, 2, 0.0);
689 // polygons outputing points
690 //test_one<P, polygon, polygon>("ppp1", simplex_normal[0], simplex_normal[1], 1, 7, 5.47363293);
692 test_boxes
<box
>("box(2 2,8 8)", "box(4 4,10 10)", 16, true);
693 test_boxes
<box
>("box(2 2,8 7)", "box(4 4,10 10)", 12, true);
694 test_boxes
<box
>("box(2 2,8 7)", "box(14 4,20 10)", 0, false);
695 test_boxes
<box
>("box(2 2,4 4)", "box(4 4,8 8)", 0, true);
697 test_point_output
<P
>();
701 test_one<polygon, box, polygon>(99, "box(115041.10 471900.10, 118334.60 474523.40)",
702 "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))",
708 void test_pointer_version()
710 std::vector
<test::test_point_xy
*> ln
;
711 test::test_point_xy
* p
;
712 p
= new test::test_point_xy
; p
->x
= 0; p
->y
= 0; ln
.push_back(p
);
713 p
= new test::test_point_xy
; p
->x
= 10; p
->y
= 10; ln
.push_back(p
);
715 bg::model::box
<bg::model::d2::point_xy
<double> > box
;
716 bg::assign_values(box
, 2, 2, 8, 8);
718 typedef bg::model::linestring
<bg::model::d2::point_xy
<double> > output_type
;
719 std::vector
<output_type
> clip
;
720 bg::detail::intersection::intersection_insert
<output_type
>(box
, ln
, std::back_inserter(clip
));
724 for (std::vector
<output_type
>::const_iterator it
= clip
.begin();
725 it
!= clip
.end(); ++it
)
727 length
+= bg::length(*it
);
728 n
+= bg::num_points(*it
);
731 BOOST_CHECK_EQUAL(clip
.size(), 1u);
732 BOOST_CHECK_EQUAL(n
, 2u);
733 BOOST_CHECK_CLOSE(length
, sqrt(2.0 * 6.0 * 6.0), 0.001);
735 for (std::size_t i
= 0; i
< ln
.size(); i
++)
742 template <typename P
>
743 void test_exception()
745 typedef bg::model::polygon
<P
> polygon
;
749 // Define polygon with a spike (= invalid)
750 std::string spike
= "POLYGON((0 0,0 4,2 4,2 6,2 4,4 4,4 0,0 0))";
752 test_one
<polygon
, polygon
, polygon
>("with_spike",
753 simplex_normal
[0], spike
,
756 catch(bg::overlay_invalid_input_exception
const& )
760 BOOST_CHECK_MESSAGE(false, "No exception thrown");
763 template <typename Point
>
766 typedef bg::model::polygon
<Point
> polygon
;
767 test_one
<polygon
, polygon
, polygon
>("simplex_normal",
768 simplex_normal
[0], simplex_normal
[1],
773 template <typename P
>
774 void test_boxes_per_d(P
const& min1
, P
const& max1
, P
const& min2
, P
const& max2
, bool expected_result
)
776 typedef bg::model::box
<P
> box
;
779 bool detected
= bg::intersection(box(min1
, max1
), box(min2
, max2
), box_out
);
781 BOOST_CHECK_EQUAL(detected
, expected_result
);
782 if ( detected
&& expected_result
)
784 BOOST_CHECK( bg::equals(box_out
, box(min2
,max1
)) );
788 template <typename CoordinateType
>
791 typedef bg::model::point
<CoordinateType
, 1, bg::cs::cartesian
> p1
;
792 typedef bg::model::point
<CoordinateType
, 2, bg::cs::cartesian
> p2
;
793 typedef bg::model::point
<CoordinateType
, 3, bg::cs::cartesian
> p3
;
795 test_boxes_per_d(p1(0), p1(5), p1(3), p1(6), true);
796 test_boxes_per_d(p2(0,0), p2(5,5), p2(3,3), p2(6,6), true);
797 test_boxes_per_d(p3(0,0,0), p3(5,5,5), p3(3,3,3), p3(6,6,6), true);
801 template <typename CoordinateType
>
802 void test_ticket_10868(std::string
const& wkt_out
)
804 typedef bg::model::point
<CoordinateType
, 2, bg::cs::cartesian
> point_type
;
805 typedef bg::model::polygon
807 point_type
, /*ClockWise*/false, /*Closed*/false
809 typedef bg::model::multi_polygon
<polygon_type
> multipolygon_type
;
811 polygon_type polygon1
;
812 bg::read_wkt(ticket_10868
[0], polygon1
);
813 polygon_type polygon2
;
814 bg::read_wkt(ticket_10868
[1], polygon2
);
816 multipolygon_type multipolygon_out
;
817 bg::intersection(polygon1
, polygon2
, multipolygon_out
);
818 std::stringstream stream
;
819 stream
<< bg::wkt(multipolygon_out
);
821 BOOST_CHECK_EQUAL(stream
.str(), wkt_out
);
823 test_one
<polygon_type
, polygon_type
, polygon_type
>("ticket_10868",
824 ticket_10868
[0], ticket_10868
[1],
825 1, 7, 20266195244586);
828 int test_main(int, char* [])
830 test_all
<bg::model::d2::point_xy
<double> >();
832 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
833 test_all
<bg::model::d2::point_xy
<float> >();
835 #if defined(HAVE_TTMATH)
836 std::cout
<< "Testing TTMATH" << std::endl
;
837 test_all
<bg::model::d2::point_xy
<ttmath_big
> >();
842 // Commented, because exception is now disabled:
843 // test_exception<bg::model::d2::point_xy<double> >();
845 test_pointer_version();
846 #if ! defined(BOOST_GEOMETRY_RESCALE_TO_ROBUST)
847 test_rational
<bg::model::d2::point_xy
<boost::rational
<int> > >();
850 test_boxes_nd
<double>();
852 #ifdef BOOST_GEOMETRY_TEST_INCLUDE_FAILING_TESTS
853 // ticket #10868 still fails for 32-bit integers
854 test_ticket_10868
<int32_t>("MULTIPOLYGON(((33520458 6878575,33480192 14931538,31446819 18947953,30772384 19615678,30101303 19612322,30114725 16928001,33520458 6878575)))");
856 #if !defined(BOOST_NO_INT64) || defined(BOOST_HAS_INT64_T) || defined(BOOST_HAS_MS_INT64)
857 test_ticket_10868
<int64_t>("MULTIPOLYGON(((33520458 6878575,33480192 14931538,31446819 18947953,30772384 19615678,30101303 19612322,30114725 16928001,33520458 6878575)))");
860 if (BOOST_GEOMETRY_CONDITION(sizeof(long) * CHAR_BIT
>= 64))
862 test_ticket_10868
<long>("MULTIPOLYGON(((33520458 6878575,33480192 14931538,31446819 18947953,30772384 19615678,30101303 19612322,30114725 16928001,33520458 6878575)))");
865 #if defined(BOOST_HAS_LONG_LONG)
866 test_ticket_10868
<boost::long_long_type
>("MULTIPOLYGON(((33520458 6878575,33480192 14931538,31446819 18947953,30772384 19615678,30101303 19612322,30114725 16928001,33520458 6878575)))");