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