ceph/src/boost/libs/geometry/test/strategies/segment_intersection_collinear.cpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2 // Unit Test
   3
   4 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   5 // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
   6 // Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
   7
   8 // Copyright (c) 2017, Oracle and/or its affiliates.
   9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  10
  11 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  12 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  13
  14 // Use, modification and distribution is subject to the Boost Software License,
  15 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  16 // http://www.boost.org/LICENSE_1_0.txt)
  17
  18 #define BOOST_GEOMETRY_DEFINE_STREAM_OPERATOR_SEGMENT_RATIO
  19
  20 #include <geometry_test_common.hpp>
  21
  22 #include <boost/geometry/algorithms/assign.hpp>
  23
  24 #include <boost/geometry/strategies/cartesian/intersection.hpp>
  25 #include <boost/geometry/strategies/intersection_result.hpp>
  26
  27 #include <boost/geometry/policies/relate/intersection_points.hpp>
  28 #include <boost/geometry/policies/relate/direction.hpp>
  29 #include <boost/geometry/policies/relate/tupled.hpp>
  30
  31 #include <boost/geometry/algorithms/intersection.hpp>
  32
  33
  34 #include <boost/geometry/geometries/point.hpp>
  35 #include <boost/geometry/geometries/segment.hpp>
  36
  37
  38 template <typename IntersectionPoints>
  39 static int check(IntersectionPoints const& is,
  40                 std::size_t index, double expected_x, double expected_y)
  41 {
  42     if (expected_x != -99 && expected_y != -99 && is.count > index)
  43     {
  44         double x = bg::get<0>(is.intersections[index]);
  45         double y = bg::get<1>(is.intersections[index]);
  46
  47         BOOST_CHECK_CLOSE(x, expected_x, 0.001);
  48         BOOST_CHECK_CLOSE(y, expected_y, 0.001);
  49         return 1;
  50     }
  51     return 0;
  52 }
  53
  54
  55 template <typename P>
  56 static void test_segment_intersection(std::string const& case_id,
  57                 int x1, int y1, int x2, int y2,
  58                 int x3, int y3, int x4, int y4,
  59                 char expected_how, bool expected_opposite,
  60                 int expected_arrival1, int expected_arrival2,
  61                 int expected_x1, int expected_y1,
  62                 int expected_x2 = -99, int expected_y2 = -99)
  63
  64 {
  65     boost::ignore_unused_variable_warning(case_id);
  66
  67     typedef bg::model::referring_segment<const P> segment_type;
  68
  69     P p1, p2, p3, p4;
  70     bg::assign_values(p1, x1, y1);
  71     bg::assign_values(p2, x2, y2);
  72     bg::assign_values(p3, x3, y3);
  73     bg::assign_values(p4, x4, y4);
  74
  75     segment_type s12(p1,p2);
  76     segment_type s34(p3,p4);
  77
  78     typedef bg::detail::no_rescale_policy rescale_policy_type;
  79     rescale_policy_type rescale_policy;
  80
  81     typedef bg::segment_intersection_points
  82     <
  83         P,
  84         typename bg::segment_ratio_type
  85         <
  86             P,
  87             rescale_policy_type
  88         >::type
  89     > result_type;
  90
  91     typedef bg::policies::relate::segments_intersection_points
  92         <
  93             result_type
  94         > points_policy_type;
  95
  96     // Get the intersection point (or two points)
  97     result_type is
  98         = bg::strategy::intersection::cartesian_segments<>
  99             ::apply(s12, s34, points_policy_type(), rescale_policy, p1, p2, p3, p4);
 100
 101     // Get just a character for Left/Right/intersects/etc, purpose is more for debugging
 102     bg::policies::relate::direction_type dir
 103         = bg::strategy::intersection::cartesian_segments<>
 104             ::apply(s12, s34, bg::policies::relate::segments_direction(),
 105                     rescale_policy, p1, p2, p3, p4);
 106
 107     std::size_t expected_count =
 108         check(is, 0, expected_x1, expected_y1)
 109         + check(is, 1, expected_x2, expected_y2);
 110
 111     BOOST_CHECK_EQUAL(is.count, expected_count);
 112     BOOST_CHECK_EQUAL(dir.how, expected_how);
 113     BOOST_CHECK_EQUAL(dir.opposite, expected_opposite);
 114     BOOST_CHECK_EQUAL(dir.arrival[0], expected_arrival1);
 115     BOOST_CHECK_EQUAL(dir.arrival[1], expected_arrival2);
 116 }
 117
 118 template <typename P, typename Pair>
 119 static void test_segment_ratio(std::string const& case_id,
 120                 int x1, int y1, int x2, int y2,
 121                 int x3, int y3, int x4, int y4,
 122                 Pair expected_pair_a1, Pair expected_pair_a2,
 123                 Pair expected_pair_b1, Pair expected_pair_b2,
 124                 int exp_ax1, int exp_ay1, int exp_ax2, int exp_ay2,
 125                 std::size_t expected_count = 2)
 126
 127 {
 128     boost::ignore_unused_variable_warning(case_id);
 129
 130     typedef bg::model::referring_segment<const P> segment_type;
 131
 132     P p1, p2, p3, p4;
 133     bg::assign_values(p1, x1, y1);
 134     bg::assign_values(p2, x2, y2);
 135     bg::assign_values(p3, x3, y3);
 136     bg::assign_values(p4, x4, y4);
 137
 138     segment_type s12(p1, p2);
 139     segment_type s34(p3, p4);
 140
 141     typedef bg::detail::no_rescale_policy rescale_policy_type;
 142     rescale_policy_type rescale_policy;
 143
 144     typedef typename bg::segment_ratio_type<P, rescale_policy_type>::type ratio_type;
 145     typedef bg::segment_intersection_points
 146     <
 147         P,
 148         ratio_type
 149     > result_type;
 150
 151     typedef bg::policies::relate::segments_intersection_points
 152         <
 153             result_type
 154         > points_policy_type;
 155
 156     // Get the intersection point (or two points)
 157     result_type is
 158         = bg::strategy::intersection::cartesian_segments<>
 159             ::apply(s12, s34, points_policy_type(), rescale_policy, p1, p2, p3, p4);
 160
 161     ratio_type expected_a1(expected_pair_a1.first, expected_pair_a1.second);
 162     ratio_type expected_a2(expected_pair_a2.first, expected_pair_a2.second);
 163     ratio_type expected_b1(expected_pair_b1.first, expected_pair_b1.second);
 164     ratio_type expected_b2(expected_pair_b2.first, expected_pair_b2.second);
 165
 166     BOOST_CHECK_EQUAL(is.count, expected_count);
 167
 168     BOOST_CHECK_EQUAL(is.fractions[0].robust_ra, expected_a1);
 169     BOOST_CHECK_EQUAL(is.fractions[0].robust_rb, expected_b1);
 170     BOOST_CHECK_EQUAL(bg::get<0>(is.intersections[0]), exp_ax1);
 171     BOOST_CHECK_EQUAL(bg::get<1>(is.intersections[0]), exp_ay1);
 172
 173     if (expected_count == 2)
 174     {
 175         BOOST_CHECK_EQUAL(bg::get<0>(is.intersections[1]), exp_ax2);
 176         BOOST_CHECK_EQUAL(bg::get<1>(is.intersections[1]), exp_ay2);
 177         BOOST_CHECK_EQUAL(is.fractions[1].robust_ra, expected_a2);
 178         BOOST_CHECK_EQUAL(is.fractions[1].robust_rb, expected_b2);
 179     }
 180 }
 181
 182
 183 template <typename P>
 184 void test_all()
 185 {
 186     // Collinear - non opposite
 187
 188     //       a1---------->a2
 189     // b1--->b2
 190     test_segment_intersection<P>("n1",
 191         2, 0, 6, 0,
 192         0, 0, 2, 0,
 193         'a', false, -1, 0,
 194         2, 0);
 195
 196     //       a1---------->a2
 197     //    b1--->b2
 198     test_segment_intersection<P>("n2",
 199         2, 0, 6, 0,
 200         1, 0, 3, 0,
 201         'c', false, -1, 1,
 202         2, 0, 3, 0);
 203
 204     //       a1---------->a2
 205     //       b1--->b2
 206     test_segment_intersection<P>("n3",
 207         2, 0, 6, 0,
 208         2, 0, 4, 0,
 209         'c', false, -1, 1,
 210         2, 0, 4, 0);
 211
 212     //       a1---------->a2
 213     //          b1--->b2
 214     test_segment_intersection<P>("n4",
 215         2, 0, 6, 0,
 216         3, 0, 5, 0,
 217         'c', false, -1, 1,
 218         3, 0, 5, 0);
 219
 220     //       a1---------->a2
 221     //              b1--->b2
 222     test_segment_intersection<P>("n5",
 223         2, 0, 6, 0,
 224         4, 0, 6, 0,
 225         'c', false, 0, 0,
 226         4, 0, 6, 0);
 227
 228     //       a1---------->a2
 229     //                 b1--->b2
 230     test_segment_intersection<P>("n6",
 231         2, 0, 6, 0,
 232         5, 0, 7, 0,
 233         'c', false, 1, -1,
 234         5, 0, 6, 0);
 235
 236     //       a1---------->a2
 237     //                    b1--->b2
 238     test_segment_intersection<P>("n7",
 239         2, 0, 6, 0,
 240         6, 0, 8, 0,
 241         'a', false, 0, -1,
 242         6, 0);
 243
 244     // Collinear - opposite
 245     //       a1---------->a2
 246     // b2<---b1
 247     test_segment_intersection<P>("o1",
 248         2, 0, 6, 0,
 249         2, 0, 0, 0,
 250         'f', true, -1, -1,
 251         2, 0);
 252
 253     //       a1---------->a2
 254     //    b2<---b1
 255     test_segment_intersection<P>("o2",
 256         2, 0, 6, 0,
 257         3, 0, 1, 0,
 258         'c', true, -1, -1,
 259         2, 0, 3, 0);
 260
 261     //       a1---------->a2
 262     //       b2<---b1
 263     test_segment_intersection<P>("o3",
 264         2, 0, 6, 0,
 265         4, 0, 2, 0,
 266         'c', true, -1, 0,
 267         2, 0, 4, 0);
 268
 269     //       a1---------->a2
 270     //           b2<---b1
 271     test_segment_intersection<P>("o4",
 272         2, 0, 6, 0,
 273         5, 0, 3, 0,
 274         'c', true, -1, 1,
 275         3, 0, 5, 0);
 276
 277     //       a1---------->a2
 278     //              b2<---b1
 279     test_segment_intersection<P>("o5",
 280         2, 0, 6, 0,
 281         6, 0, 4, 0,
 282         'c', true, 0, 1,
 283         4, 0, 6, 0);
 284
 285     //       a1---------->a2
 286     //                b2<---b1
 287     test_segment_intersection<P>("o6",
 288         2, 0, 6, 0,
 289         7, 0, 5, 0,
 290         'c', true, 1, 1,
 291         5, 0, 6, 0);
 292
 293     //       a1---------->a2
 294     //                    b2<---b1
 295     test_segment_intersection<P>("o7",
 296         2, 0, 6, 0,
 297         8, 0, 6, 0,
 298         't', true, 0, 0,
 299         6, 0);
 300
 301     //   a1---------->a2
 302     //   b1---------->b2
 303     test_segment_intersection<P>("e1",
 304         2, 0, 6, 0,
 305         2, 0, 6, 0,
 306         'e', false, 0, 0,
 307         2, 0, 6, 0);
 308
 309     //   a1---------->a2
 310     //   b2<----------b1
 311     test_segment_intersection<P>("e1",
 312         2, 0, 6, 0,
 313         6, 0, 2, 0,
 314         'e', true, 0, 0,
 315         2, 0, 6, 0);
 316
 317     // Disjoint (in vertical direction, picture still horizontal)
 318     //   a2<---a1
 319     //                      b2<---b1
 320     test_segment_intersection<P>("case_recursive_boxes_1",
 321         10, 7, 10, 6,
 322         10, 10, 10, 9,
 323         'd', false, 0, 0,
 324         -1, -1, -1, -1);
 325
 326 }
 327
 328
 329 template <typename P>
 330 void test_ratios()
 331 {
 332     // B inside A
 333     //       a1------------>a2
 334     //          b1--->b2
 335     test_segment_ratio<P>("n4",
 336         2, 0, 7, 0,
 337         3, 0, 5, 0,
 338         std::make_pair(1, 5), std::make_pair(3, 5), // IP located on 1/5, 3/5 w.r.t A
 339         std::make_pair(0, 1), std::make_pair(1, 1), // IP located on 0, 1 w.r.t. B
 340         // IP's are ordered as in A (currently)
 341         3, 0, 5, 0);
 342
 343     //       a1------------>a2
 344     //           b2<---b1
 345     test_segment_ratio<P>("o4",
 346         2, 0, 7, 0,
 347         5, 0, 3, 0,
 348         std::make_pair(1, 5), std::make_pair(3, 5),
 349         std::make_pair(1, 1), std::make_pair(0, 1),
 350         3, 0, 5, 0);
 351
 352     //       a2<------------a1
 353     //           b2<---b1
 354     test_segment_ratio<P>("o4b",
 355         7, 0, 2, 0,
 356         5, 0, 3, 0,
 357         std::make_pair(2, 5), std::make_pair(4, 5),
 358         std::make_pair(0, 1), std::make_pair(1, 1),
 359         5, 0, 3, 0);
 360
 361     //       a2<------------a1
 362     //          b1--->b2
 363     test_segment_ratio<P>("o4c",
 364         7, 0, 2, 0,
 365         3, 0, 5, 0,
 366         std::make_pair(2, 5), std::make_pair(4, 5),
 367         std::make_pair(1, 1), std::make_pair(0, 1),
 368         5, 0, 3, 0);
 369
 370     // Touch-interior
 371     //       a1---------->a2
 372     //       b1--->b2
 373     test_segment_ratio<P>("n3",
 374         2, 0, 7, 0,
 375         2, 0, 4, 0,
 376         std::make_pair(0, 1), std::make_pair(2, 5),
 377         std::make_pair(0, 1), std::make_pair(1, 1),
 378         2, 0, 4, 0);
 379
 380     //    a2<-------------a1
 381     //             b2<----b1
 382     test_segment_ratio<P>("n3b",
 383         7, 0, 2, 0,
 384         7, 0, 5, 0,
 385         std::make_pair(0, 1), std::make_pair(2, 5),
 386         std::make_pair(0, 1), std::make_pair(1, 1),
 387         7, 0, 5, 0);
 388
 389
 390     // A inside B
 391     //          a1--->a2
 392     //       b1------------>b2
 393     test_segment_ratio<P>("rn4",
 394         3, 0, 5, 0,
 395         2, 0, 7, 0,
 396         std::make_pair(0, 1), std::make_pair(1, 1),
 397         std::make_pair(1, 5), std::make_pair(3, 5),
 398         3, 0, 5, 0);
 399
 400     //           a2<---a1
 401     //       b1------------>b2
 402     test_segment_ratio<P>("ro4",
 403         5, 0, 3, 0,
 404         2, 0, 7, 0,
 405         std::make_pair(0, 1), std::make_pair(1, 1),
 406         std::make_pair(3, 5), std::make_pair(1, 5),
 407         5, 0, 3, 0);
 408
 409     //           a2<---a1
 410     //       b2<------------b1
 411     test_segment_ratio<P>("ro4b",
 412         5, 0, 3, 0,
 413         7, 0, 2, 0,
 414         std::make_pair(0, 1), std::make_pair(1, 1),
 415         std::make_pair(2, 5), std::make_pair(4, 5),
 416         5, 0, 3, 0);
 417
 418     //          a1--->a2
 419     //       b2<------------b1
 420     test_segment_ratio<P>("ro4c",
 421         3, 0, 5, 0,
 422         7, 0, 2, 0,
 423         std::make_pair(0, 1), std::make_pair(1, 1),
 424         std::make_pair(4, 5), std::make_pair(2, 5),
 425         3, 0, 5, 0);
 426
 427     // B inside A, boundaries intersect
 428     // We change the coordinates a bit (w.r.t. n3 above) to have it asymmetrical
 429     //       a1---------->a2
 430     //       b1--->b2
 431     test_segment_ratio<P>("n3",
 432         2, 0, 7, 0,
 433         2, 0, 4, 0,
 434         std::make_pair(0, 1), std::make_pair(2, 5),
 435         std::make_pair(0, 1), std::make_pair(1, 1),
 436         2, 0, 4, 0);
 437
 438     //       a1---------->a2
 439     //       b2<---b1
 440     test_segment_ratio<P>("o3",
 441         2, 0, 7, 0,
 442         4, 0, 2, 0,
 443         std::make_pair(0, 1), std::make_pair(2, 5),
 444         std::make_pair(1, 1), std::make_pair(0, 1),
 445         2, 0, 4, 0);
 446
 447     //       a1---------->a2
 448     //              b1--->b2
 449     test_segment_ratio<P>("n5",
 450         2, 0, 7, 0,
 451         5, 0, 7, 0,
 452         std::make_pair(3, 5), std::make_pair(1, 1),
 453         std::make_pair(0, 1), std::make_pair(1, 1),
 454         5, 0, 7, 0);
 455
 456     //       a1---------->a2
 457     //              b2<---b1
 458     test_segment_ratio<P>("o5",
 459         2, 0, 7, 0,
 460         7, 0, 5, 0,
 461         std::make_pair(3, 5), std::make_pair(1, 1),
 462         std::make_pair(1, 1), std::make_pair(0, 1),
 463         5, 0, 7, 0);
 464
 465     // Generic (overlaps)
 466     //       a1---------->a2
 467     //    b1----->b2
 468     test_segment_ratio<P>("n2",
 469         2, 0, 7, 0,
 470         1, 0, 4, 0,
 471         std::make_pair(0, 1), std::make_pair(2, 5),
 472         std::make_pair(1, 3), std::make_pair(1, 1),
 473         2, 0, 4, 0);
 474
 475     // Same, b reversed
 476     test_segment_ratio<P>("n2_b",
 477         2, 0, 7, 0,
 478         4, 0, 1, 0,
 479         std::make_pair(0, 1), std::make_pair(2, 5),
 480         std::make_pair(2, 3), std::make_pair(0, 1),
 481         2, 0, 4, 0);
 482
 483     // Same, both reversed
 484     test_segment_ratio<P>("n2_c",
 485         7, 0, 2, 0,
 486         4, 0, 1, 0,
 487         std::make_pair(3, 5), std::make_pair(1, 1),
 488         std::make_pair(0, 1), std::make_pair(2, 3),
 489         4, 0, 2, 0);
 490
 491     //       a1---------->a2
 492     //                 b1----->b2
 493     test_segment_ratio<P>("n6",
 494         2, 0, 6, 0,
 495         5, 0, 8, 0,
 496         std::make_pair(3, 4), std::make_pair(1, 1),
 497         std::make_pair(0, 1), std::make_pair(1, 3),
 498         5, 0, 6, 0);
 499
 500     // Degenerated one
 501     //       a1---------->a2
 502     //             b1/b2
 503     const int ignored = 99;
 504     test_segment_ratio<P>("degenerated1",
 505         2, 0, 6, 0,
 506         5, 0, 5, 0,
 507         std::make_pair(3, 4), // IP located on 3/4 w.r.t A
 508         std::make_pair(ignored, 1), // not checked
 509         std::make_pair(0, 1), // IP located at any place w.r.t B, so 0
 510         std::make_pair(ignored, 1), // not checked
 511         5, 0,
 512         ignored, ignored,
 513         1);
 514
 515     test_segment_ratio<P>("degenerated2",
 516         5, 0, 5, 0,
 517         2, 0, 6, 0,
 518         std::make_pair(0, 1), std::make_pair(ignored, 1),
 519         std::make_pair(3, 4), std::make_pair(ignored, 1),
 520         5, 0,
 521         ignored, ignored,
 522         1);
 523
 524     // Vertical one like in box_poly5 but in integer
 525     test_segment_ratio<P>("box_poly5",
 526         45, 25, 45, 15,
 527         45, 22, 45, 19,
 528         std::make_pair(3, 10), std::make_pair(6, 10),
 529         std::make_pair(0, 1), std::make_pair(1, 1),
 530         45, 22, 45, 19);
 531 }
 532
 533 int test_main(int, char* [])
 534 {
 535     // We don't rescale but use integer points as, by nature, robust points
 536     test_all<bg::model::point<int, 2, bg::cs::cartesian> >();
 537     test_ratios<bg::model::point<int, 2, bg::cs::cartesian> >();
 538     return 0;
 539 }