ceph/src/boost/libs/geometry/test/algorithms/set_operations/intersection/intersection.cpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2 // Unit Test
   3
   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.
   7
   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
  12
  13 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  14 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  15
  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)
  19
  20 #include <climits>
  21 #include <iostream>
  22 #include <string>
  23
  24 #include <boost/config.hpp>
  25 #include <boost/core/ignore_unused.hpp>
  26
  27 #include <boost/geometry/geometries/point_xy.hpp>
  28 #include <boost/geometry/geometries/register/linestring.hpp>
  29
  30 #include <boost/geometry/util/condition.hpp>
  31 #include <boost/geometry/util/rational.hpp>
  32
  33 #include "test_intersection.hpp"
  34 #include <algorithms/test_overlay.hpp>
  35
  36 #include <algorithms/overlay/overlay_cases.hpp>
  37
  38 #include <test_common/test_point.hpp>
  39 #include <test_common/with_pointer.hpp>
  40 #include <test_geometries/custom_segment.hpp>
  41
  42
  43 BOOST_GEOMETRY_REGISTER_LINESTRING_TEMPLATED(std::vector)
  44
  45
  46 template <typename Polygon>
  47 void test_areal()
  48 {
  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;
  52
  53     ut_settings ignore_validity;
  54     ignore_validity.test_validity = false;
  55
  56
  57     test_one<Polygon, Polygon, Polygon>("simplex_with_empty_1",
  58         simplex_normal[0], polygon_empty,
  59         0, 0, 0.0);
  60     test_one<Polygon, Polygon, Polygon>("simplex_with_empty_2",
  61         polygon_empty, simplex_normal[0],
  62         0, 0, 0.0);
  63
  64     test_one<Polygon, Polygon, Polygon>("simplex_normal",
  65         simplex_normal[0], simplex_normal[1],
  66         1, 7, 5.47363293);
  67     test_one<Polygon, Polygon, Polygon>("star_ring", example_star, example_ring,
  68         1, 18, 2.80983);
  69
  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)
  72         2.5020508);
  73     test_one<Polygon, Polygon, Polygon>("first_within_second1",
  74         first_within_second[0], first_within_second[1],
  75         1, 5, 1.0);
  76
  77     test_one<Polygon, Polygon, Polygon>("first_within_second2",
  78         first_within_second[1], first_within_second[0],
  79         1, 5, 1.0);
  80
  81     test_one<Polygon, Polygon, Polygon>("first_within_hole_of_second",
  82             first_within_hole_of_second[0], first_within_hole_of_second[1],
  83             0, 0, 0.0);
  84
  85     // Two forming new hole
  86     test_one<Polygon, Polygon, Polygon>("new_hole",
  87         new_hole[0], new_hole[1],
  88         2, 10, 2.0);
  89
  90     // Two identical
  91     test_one<Polygon, Polygon, Polygon>("identical",
  92         identical[0], identical[1],
  93         1, 5, 1.0);
  94
  95     test_one<Polygon, Polygon, Polygon>("intersect_exterior_and_interiors_winded",
  96         intersect_exterior_and_interiors_winded[0], intersect_exterior_and_interiors_winded[1],
  97         1, 14, 25.2166667);
  98
  99     test_one<Polygon, Polygon, Polygon>("intersect_holes_disjoint",
 100         intersect_holes_disjoint[0], intersect_holes_disjoint[1],
 101         1, 15, 18.0);
 102
 103     test_one<Polygon, Polygon, Polygon>("intersect_holes_intersect",
 104         intersect_holes_intersect[0], intersect_holes_intersect[1],
 105         1, 14, 18.25);
 106
 107     test_one<Polygon, Polygon, Polygon>("intersect_holes_intersect_and_disjoint",
 108         intersect_holes_intersect_and_disjoint[0], intersect_holes_intersect_and_disjoint[1],
 109         1, 19, 17.25);
 110
 111     test_one<Polygon, Polygon, Polygon>("intersect_holes_intersect_and_touch",
 112         intersect_holes_intersect_and_touch[0], intersect_holes_intersect_and_touch[1],
 113         1, 23, 17.25);
 114
 115     test_one<Polygon, Polygon, Polygon>("intersect_holes_new_ring",
 116         intersect_holes_new_ring[0], intersect_holes_new_ring[1],
 117         2, 23, 122.1039);
 118
 119     test_one<Polygon, Polygon, Polygon>("winded",
 120         winded[0], winded[1],
 121         1, 22, 40.0);
 122
 123     test_one<Polygon, Polygon, Polygon>("within_holes_disjoint",
 124         within_holes_disjoint[0], within_holes_disjoint[1],
 125         1, 15, 23.0);
 126
 127     test_one<Polygon, Polygon, Polygon>("side_side",
 128         side_side[0], side_side[1],
 129         0, 0, 0.0);
 130
 131     test_one<Polygon, Polygon, Polygon>("two_bends",
 132         two_bends[0], two_bends[1],
 133         1, 7, 24.0);
 134
 135     test_one<Polygon, Polygon, Polygon>("star_comb_15",
 136         star_comb_15[0], star_comb_15[1],
 137         28, 150, 189.952883);
 138
 139     test_one<Polygon, Polygon, Polygon>("simplex_normal",
 140         simplex_normal[0], simplex_normal[1],
 141         1, 7, 5.47363293);
 142
 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));
 146
 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);
 150
 151     test_one<Polygon, Polygon, Polygon>("only_hole_intersections1",
 152         only_hole_intersections[0], only_hole_intersections[1],
 153         1, 21, 178.090909);
 154     test_one<Polygon, Polygon, Polygon>("only_hole_intersection2",
 155         only_hole_intersections[0], only_hole_intersections[2],
 156         1, 21, 149.090909);
 157
 158     test_one<Polygon, Polygon, Polygon>("fitting",
 159         fitting[0], fitting[1],
 160         0, 0, 0.0);
 161
 162     test_one<Polygon, Polygon, Polygon>("crossed",
 163         crossed[0], crossed[1],
 164         3, 0, 1.5);
 165
 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));
 169
 170 #if defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
 171     test_one<Polygon, Polygon, Polygon>("isovist",
 172         isovist1[0], isovist1[1],
 173         1, 19, 88.4178,
 174         ignore_validity);
 175 #else
 176     // SQL Server gives: 88.1920416352664
 177     // PostGIS gives:    88.19203677911
 178     test_one<Polygon, Polygon, Polygon>("isovist",
 179         isovist1[0], isovist1[1],
 180         1, 19, 88.19203,
 181         ut_settings(if_typed_tt<ct>(0.01, 0.1)));
 182 #endif
 183
 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));
 188
 189     // Expectations:
 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 <=
 196
 197 #if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
 198     test_one<Polygon, Polygon, Polygon>("geos_3",
 199         geos_3[0], geos_3[1],
 200             0, 0, 0.0);
 201 #endif
 202     test_one<Polygon, Polygon, Polygon>("geos_4",
 203         geos_4[0], geos_4[1],
 204             1, -1, 0.08368849);
 205
 206
 207     if ( BOOST_GEOMETRY_CONDITION(! ccw && open) )
 208     {
 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),
 216             0.6649875,
 217             ut_settings(if_typed<ct, float>(1.0, 0.01)));
 218     }
 219
 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],
 226         1, 4,
 227         #if defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
 228             0.40
 229         #else
 230             0.397162651, ut_settings(0.01)
 231         #endif
 232             );
 233
 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);
 238 #endif
 239
 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);
 243
 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));
 247
 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));
 251
 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));
 256
 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));
 260
 261     test_one<Polygon, Polygon, Polygon>("buffer_rt_g", buffer_rt_g[0], buffer_rt_g[1],
 262                 1, 0, 2.914213562373);
 263 #endif
 264
 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],
 270                 1, 4, 0.0003);
 271
 272     test_one<Polygon, Polygon, Polygon>("ticket_8310a", ticket_8310a[0], ticket_8310a[1],
 273                 1, 5, 0.3843747);
 274     test_one<Polygon, Polygon, Polygon>("ticket_8310b", ticket_8310b[0], ticket_8310b[1],
 275                 1, 5, 0.3734379);
 276     test_one<Polygon, Polygon, Polygon>("ticket_8310c", ticket_8310c[0], ticket_8310c[1],
 277                 1, 5, 0.4689541);
 278
 279     test_one<Polygon, Polygon, Polygon>("ticket_9081_15",
 280                 ticket_9081_15[0], ticket_9081_15[1],
 281                 1, 4, 0.0068895780745301394);
 282
 283     test_one<Polygon, Polygon, Polygon>("ticket_10108_a",
 284                 ticket_10108_a[0], ticket_10108_a[1],
 285                 0, 0, 0.0);
 286
 287 #if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS)
 288     // msvc  5.6023011e-5
 289     // mingw 5.6022954e-5
 290     test_one<Polygon, Polygon, Polygon>("ticket_10108_b",
 291                 ticket_10108_b[0], ticket_10108_b[1],
 292                 0, 0, 5.6022983e-5);
 293 #endif
 294
 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],
 306                 1, 4, 703687777321);
 307     test_one<Polygon, Polygon, Polygon>("ticket_10747_e",
 308                 ticket_10747_e[0], ticket_10747_e[1],
 309                 1, 4, 7.0368748575710959e-15);
 310
 311     test_one<Polygon, Polygon, Polygon>("ticket_11576",
 312                 ticket_11576[0], ticket_11576[1],
 313                 1, 0, 5.585617332907136e-07);
 314
 315     test_one<Polygon, Polygon, Polygon>("ticket_9563", ticket_9563[0], ticket_9563[1],
 316                 1, 8, 129.90381);
 317
 318     test_one<Polygon, Polygon, Polygon>("buffer_mp1", buffer_mp1[0], buffer_mp1[1],
 319                 1, 31, 2.271707796);
 320     test_one<Polygon, Polygon, Polygon>("buffer_mp2", buffer_mp2[0], buffer_mp2[1],
 321                 1, 29, 0.457126);
 322
 323     test_one<Polygon, Polygon, Polygon>("case_58_iet",
 324         case_58[0], case_58[2],
 325         2, -1, 1.0 / 3.0);
 326
 327     test_one<Polygon, Polygon, Polygon>("case_80",
 328         case_80[0], case_80[1],
 329         0, -1, 0.0);
 330
 331     test_one<Polygon, Polygon, Polygon>("case_81",
 332         case_81[0], case_81[1],
 333         0, -1, 0.0);
 334
 335     test_one<Polygon, Polygon, Polygon>("mysql_21964049",
 336         mysql_21964049[0], mysql_21964049[1],
 337         0, -1, 0.0);
 338
 339     test_one<Polygon, Polygon, Polygon>("mysql_21964465",
 340         mysql_21964465[0], mysql_21964465[1],
 341         0, -1, 0.0);
 342
 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);
 347
 348     test_one<Polygon, Polygon, Polygon>("mysql_23023665_6",
 349         mysql_23023665_6[0], mysql_23023665_6[1],
 350         1, -1, 11.812440191387557,
 351         ignore_validity);
 352
 353     test_one<Polygon, Polygon, Polygon>("mysql_23023665_10",
 354         mysql_23023665_10[0], mysql_23023665_10[1],
 355         1, 0, -1, 54.701340543162523,
 356         ignore_validity);
 357
 358     test_one<Polygon, Polygon, Polygon>("mysql_23023665_11",
 359         mysql_23023665_11[0], mysql_23023665_11[1],
 360         1, 0, -1, 35.933385462482065,
 361         ignore_validity);
 362
 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);
 368 }
 369
 370 template <typename Polygon, typename Box>
 371 void test_areal_clip()
 372 {
 373     test_one<Polygon, Box, Polygon>("boxring", example_box, example_ring,
 374         2, 12, 1.09125);
 375     test_one<Polygon, Polygon, Box>("boxring2", example_ring,example_box,
 376         2, 12, 1.09125);
 377
 378     test_one<Polygon, Box, Polygon>("boxpoly", example_box, example_polygon,
 379         3, 19, 0.840166);
 380
 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))",
 383         2, 12, 1.09125);
 384
 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))",
 387         2, 12, 1.00375);
 388
 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))",
 391         2, 12, 1.00375);
 392
 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))",
 395         2, 16, 0.860892);
 396
 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))",
 399         2, 11, 0.7575961);
 400
 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))",
 403         2, 13, 1.0744456);
 404
 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))",
 407         1, 4, 0.75);
 408 }
 409
 410
 411 template <typename Box>
 412 void test_boxes(std::string const& wkt1, std::string const& wkt2, double expected_area, bool expected_result)
 413 {
 414     Box box1, box2;
 415     bg::read_wkt(wkt1, box1);
 416     bg::read_wkt(wkt2, box2);
 417
 418     Box box_out;
 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);
 422
 423     BOOST_CHECK_EQUAL(detected, expected_result);
 424     if (detected && expected_result)
 425     {
 426         BOOST_CHECK_CLOSE(area, expected_area, 0.01);
 427     }
 428 }
 429
 430 template <typename P>
 431 void test_point_output()
 432 {
 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;
 437
 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);
 445 }
 446
 447
 448 template <typename Polygon, typename LineString>
 449 void test_areal_linear()
 450 {
 451     std::string const poly_simplex = "POLYGON((1 1,1 3,3 3,3 1,1 1))";
 452
 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));
 457
 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);
 464
 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));
 470
 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);
 475
 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);
 482
 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)",
 486          0, 0, 0);
 487
 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)",
 491          2, 4, 10);
 492
 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)",
 496          2, 6, 17.071068);
 497
 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)",
 501          1, 3, 10);
 502
 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)",
 506          1, 3, 10);
 507
 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)",
 511          1, 3, 10);
 512
 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)",
 516          1, 6, 29.313708);
 517
 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)",
 521          1, 3, 10);
 522
 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)",
 526          1, 4, 20.540925);
 527
 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)",
 531          1, 4, 18.540925);
 532
 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)",
 536          2, 6, 20.540925);
 537
 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)",
 541          0, 0, 0);
 542
 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)",
 546          0, 0, 0);
 547
 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)",
 551          1, 6, 21.0);
 552
 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)",
 556          1, 6, 21.099019);
 557
 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));
 562
 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);
 565
 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);
 569
 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);
 572
 573 }
 574
 575
 576 template <typename Linestring, typename Box>
 577 void test_linear_box()
 578 {
 579     typedef bg::model::multi_linestring<Linestring> multi_linestring_type;
 580
 581     test_one_lp<Linestring, Box, Linestring>
 582         ("case-l-b-01",
 583          "BOX(-10 -10,10 10)",
 584          "LINESTRING(-20 -20, 0 0,20 20)",
 585          1, 3, 20 * sqrt(2.0));
 586
 587     test_one_lp<Linestring, Box, Linestring>
 588         ("case-l-b-02",
 589          "BOX(-10 -10,10 10)",
 590          "LINESTRING(-20 -20, 20 20)",
 591          1, 2, 20.0 * sqrt(2.0));
 592
 593     test_one_lp<Linestring, Box, Linestring>
 594         ("case-l-b-02",
 595          "BOX(-10 -10,10 10)",
 596          "LINESTRING(-20 -20, 20 20,15 0,0 -15)",
 597          2, 4, 25.0 * sqrt(2.0));
 598
 599     test_one_lp<Linestring, Box, multi_linestring_type>
 600         ("case-ml-b-01",
 601          "BOX(-10 -10,10 10)",
 602          "MULTILINESTRING((-20 -20, 20 20),(0 -15,15 0))",
 603          2, 4, 25.0 * sqrt(2.0));
 604 }
 605
 606
 607 template <typename P>
 608 void test_all()
 609 {
 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;
 614
 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>();
 619
 620     ut_settings ignore_validity;
 621     ignore_validity.test_validity = false;
 622
 623     std::string clip = "box(2 2,8 8)";
 624
 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>();
 630 #endif
 631
 632     test_linear_box<linestring, box>();
 633
 634     // Test polygons clockwise and counter clockwise
 635     test_areal<polygon>();
 636
 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>();
 641 #endif
 642
 643     test_areal_clip<polygon, box>();
 644 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
 645     test_areal_clip<polygon_ccw, box>();
 646 #endif
 647
 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],
 653         1, 7, 5.47363293);
 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],
 657         1, 7, 5.47363293);
 658 #endif
 659
 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));
 663
 664     // Box/segment
 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));
 667
 668     // Completely inside
 669     test_one<linestring, linestring, box>("llbi", "LINESTRING(3 3,7 7)", clip, 1, 2, sqrt(2.0 * 4.0 * 4.0));
 670
 671     // Completely outside
 672     test_one<linestring, linestring, box>("llbo", "LINESTRING(9 9,10 10)", clip, 0, 0, 0.0);
 673
 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);
 676
 677     // Along border
 678     test_one<linestring, linestring, box>("llb_along", "LINESTRING(2 2,2 8)", clip, 1, 2, 6.0);
 679
 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);
 683
 684     // linear
 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);
 688
 689     // polygons outputing points
 690     //test_one<P, polygon, polygon>("ppp1", simplex_normal[0], simplex_normal[1], 1, 7, 5.47363293);
 691
 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);
 696
 697     test_point_output<P>();
 698
 699
 700     /*
 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))",
 703                 1, 26, 3727690.74);
 704     */
 705
 706 }
 707
 708 void test_pointer_version()
 709 {
 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);
 714
 715     bg::model::box<bg::model::d2::point_xy<double> > box;
 716     bg::assign_values(box, 2, 2, 8, 8);
 717
 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));
 721
 722     double length = 0;
 723     std::size_t n = 0;
 724     for (std::vector<output_type>::const_iterator it = clip.begin();
 725             it != clip.end(); ++it)
 726     {
 727         length += bg::length(*it);
 728         n += bg::num_points(*it);
 729     }
 730
 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);
 734
 735     for (std::size_t i = 0; i < ln.size(); i++)
 736     {
 737         delete ln[i];
 738     }
 739 }
 740
 741
 742 template <typename P>
 743 void test_exception()
 744 {
 745     typedef bg::model::polygon<P> polygon;
 746
 747     try
 748     {
 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))";
 751
 752         test_one<polygon, polygon, polygon>("with_spike",
 753             simplex_normal[0], spike,
 754             0, 0, 0);
 755     }
 756     catch(bg::overlay_invalid_input_exception const& )
 757     {
 758         return;
 759     }
 760     BOOST_CHECK_MESSAGE(false, "No exception thrown");
 761 }
 762
 763 template <typename Point>
 764 void test_rational()
 765 {
 766     typedef bg::model::polygon<Point> polygon;
 767     test_one<polygon, polygon, polygon>("simplex_normal",
 768         simplex_normal[0], simplex_normal[1],
 769         1, 7, 5.47363293);
 770 }
 771
 772
 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)
 775 {
 776     typedef bg::model::box<P> box;
 777
 778     box box_out;
 779     bool detected = bg::intersection(box(min1, max1), box(min2, max2), box_out);
 780
 781     BOOST_CHECK_EQUAL(detected, expected_result);
 782     if ( detected && expected_result )
 783     {
 784         BOOST_CHECK( bg::equals(box_out, box(min2,max1)) );
 785     }
 786 }
 787
 788 template <typename CoordinateType>
 789 void test_boxes_nd()
 790 {
 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;
 794
 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);
 798 }
 799
 800
 801 template <typename CoordinateType>
 802 void test_ticket_10868(std::string const& wkt_out)
 803 {
 804     typedef bg::model::point<CoordinateType, 2, bg::cs::cartesian> point_type;
 805     typedef bg::model::polygon
 806         <
 807             point_type, /*ClockWise*/false, /*Closed*/false
 808         > polygon_type;
 809     typedef bg::model::multi_polygon<polygon_type> multipolygon_type;
 810
 811     polygon_type polygon1;
 812     bg::read_wkt(ticket_10868[0], polygon1);
 813     polygon_type polygon2;
 814     bg::read_wkt(ticket_10868[1], polygon2);
 815
 816     multipolygon_type multipolygon_out;
 817     bg::intersection(polygon1, polygon2, multipolygon_out);
 818     std::stringstream stream;
 819     stream << bg::wkt(multipolygon_out);
 820
 821     BOOST_CHECK_EQUAL(stream.str(), wkt_out);
 822
 823     test_one<polygon_type, polygon_type, polygon_type>("ticket_10868",
 824         ticket_10868[0], ticket_10868[1],
 825         1, 7, 20266195244586);
 826 }
 827
 828 int test_main(int, char* [])
 829 {
 830     test_all<bg::model::d2::point_xy<double> >();
 831
 832 #if ! defined(BOOST_GEOMETRY_TEST_ONLY_ONE_TYPE)
 833     test_all<bg::model::d2::point_xy<float> >();
 834
 835 #if defined(HAVE_TTMATH)
 836     std::cout << "Testing TTMATH" << std::endl;
 837     test_all<bg::model::d2::point_xy<ttmath_big> >();
 838 #endif
 839
 840 #endif
 841
 842     // Commented, because exception is now disabled:
 843     // test_exception<bg::model::d2::point_xy<double> >();
 844
 845     test_pointer_version();
 846 #if ! defined(BOOST_GEOMETRY_RESCALE_TO_ROBUST)
 847     test_rational<bg::model::d2::point_xy<boost::rational<int> > >();
 848 #endif
 849
 850     test_boxes_nd<double>();
 851
 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)))");
 855
 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)))");
 858 #endif
 859
 860     if (BOOST_GEOMETRY_CONDITION(sizeof(long) * CHAR_BIT >= 64))
 861     {
 862         test_ticket_10868<long>("MULTIPOLYGON(((33520458 6878575,33480192 14931538,31446819 18947953,30772384 19615678,30101303 19612322,30114725 16928001,33520458 6878575)))");
 863     }
 864
 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)))");
 867 #endif
 868 #endif
 869
 870     return 0;
 871 }