boost/geometry/algorithms/detail/overlay/get_turn_info.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // Use, modification and distribution is subject to the Boost Software License,
   6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP
  10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP
  11
  12
  13 #include <boost/assert.hpp>
  14 #include <boost/geometry/core/access.hpp>
  15 #include <boost/geometry/strategies/intersection.hpp>
  16
  17 #include <boost/geometry/algorithms/convert.hpp>
  18 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
  19 #include <boost/geometry/algorithms/detail/recalculate.hpp>
  20
  21 #include <boost/geometry/geometries/segment.hpp>
  22
  23 #include <boost/geometry/policies/robustness/robust_point_type.hpp>
  24 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp>
  25
  26 // Silence warning C4127: conditional expression is constant
  27 #if defined(_MSC_VER)
  28 #pragma warning(push)
  29 #pragma warning(disable : 4127)
  30 #endif
  31
  32
  33 namespace boost { namespace geometry
  34 {
  35
  36 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
  37 class turn_info_exception : public geometry::exception
  38 {
  39     std::string message;
  40 public:
  41
  42     // NOTE: "char" will be replaced by enum in future version
  43     inline turn_info_exception(char const method)
  44     {
  45         message = "Boost.Geometry Turn exception: ";
  46         message += method;
  47     }
  48
  49     virtual ~turn_info_exception() throw()
  50     {}
  51
  52     virtual char const* what() const throw()
  53     {
  54         return message.c_str();
  55     }
  56 };
  57 #endif
  58
  59 #ifndef DOXYGEN_NO_DETAIL
  60 namespace detail { namespace overlay
  61 {
  62
  63 struct base_turn_handler
  64 {
  65     // Returns true if both sides are opposite
  66     static inline bool opposite(int side1, int side2)
  67     {
  68         // We cannot state side1 == -side2, because 0 == -0
  69         // So either side1*side2==-1 or side1==-side2 && side1 != 0
  70         return side1 * side2 == -1;
  71     }
  72
  73     // Same side of a segment (not being 0)
  74     static inline bool same(int side1, int side2)
  75     {
  76         return side1 * side2 == 1;
  77     }
  78
  79     // Both continue
  80     template <typename TurnInfo>
  81     static inline void both(TurnInfo& ti, operation_type const op)
  82     {
  83         ti.operations[0].operation = op;
  84         ti.operations[1].operation = op;
  85     }
  86
  87     // If condition, first union/second intersection, else vice versa
  88     template <typename TurnInfo>
  89     static inline void ui_else_iu(bool condition, TurnInfo& ti)
  90     {
  91         ti.operations[0].operation = condition
  92                     ? operation_union : operation_intersection;
  93         ti.operations[1].operation = condition
  94                     ? operation_intersection : operation_union;
  95     }
  96
  97     // If condition, both union, else both intersection
  98     template <typename TurnInfo>
  99     static inline void uu_else_ii(bool condition, TurnInfo& ti)
 100     {
 101         both(ti, condition ? operation_union : operation_intersection);
 102     }
 103
 104     template <typename TurnInfo, typename IntersectionInfo>
 105     static inline void assign_point(TurnInfo& ti,
 106                 method_type method,
 107                 IntersectionInfo const& info, int index)
 108     {
 109         ti.method = method;
 110         BOOST_ASSERT(index >= 0 && unsigned(index) < info.count); // TODO  remove this
 111         geometry::convert(info.intersections[index], ti.point);
 112         ti.operations[0].fraction = info.fractions[index].robust_ra;
 113         ti.operations[1].fraction = info.fractions[index].robust_rb;
 114     }
 115
 116     template <typename IntersectionInfo>
 117     static inline int non_opposite_to_index(IntersectionInfo const& info)
 118     {
 119         return info.fractions[0].robust_rb < info.fractions[1].robust_rb
 120             ? 1 : 0;
 121     }
 122
 123 };
 124
 125
 126 template
 127 <
 128     typename TurnInfo
 129 >
 130 struct touch_interior : public base_turn_handler
 131 {
 132     // Index: 0, P is the interior, Q is touching and vice versa
 133     template
 134     <
 135         int Index,
 136         typename Point1,
 137         typename Point2,
 138         typename IntersectionInfo,
 139         typename DirInfo,
 140         typename SidePolicy
 141     >
 142     static inline void apply(
 143                 Point1 const& , Point1 const& , Point1 const& ,
 144                 Point2 const& , Point2 const& , Point2 const& ,
 145                 TurnInfo& ti,
 146                 IntersectionInfo const& intersection_info,
 147                 DirInfo const& dir_info,
 148                 SidePolicy const& side)
 149     {
 150         assign_point(ti, method_touch_interior, intersection_info, 0);
 151
 152         // Both segments of q touch segment p somewhere in its interior
 153         // 1) We know: if q comes from LEFT or RIGHT
 154         // (i.e. dir_info.sides.get<Index,0>() == 1 or -1)
 155         // 2) Important is: if q_k goes to LEFT, RIGHT, COLLINEAR
 156         //    and, if LEFT/COLL, if it is lying LEFT or RIGHT w.r.t. q_i
 157
 158         static int const index_p = Index;
 159         static int const index_q = 1 - Index;
 160
 161         int const side_qi_p = dir_info.sides.template get<index_q, 0>();
 162         int const side_qk_p = side.qk_wrt_p1();
 163
 164         if (side_qi_p == -side_qk_p)
 165         {
 166             // Q crosses P from left->right or from right->left (test "ML1")
 167             // Union: folow P (left->right) or Q (right->left)
 168             // Intersection: other turn
 169             int index = side_qk_p == -1 ? index_p : index_q;
 170             ti.operations[index].operation = operation_union;
 171             ti.operations[1 - index].operation = operation_intersection;
 172             return;
 173         }
 174
 175         int const side_qk_q = side.qk_wrt_q1();
 176
 177         if (side_qi_p == -1 && side_qk_p == -1 && side_qk_q == 1)
 178         {
 179             // Q turns left on the right side of P (test "MR3")
 180             // Both directions for "intersection"
 181             both(ti, operation_intersection);
 182         }
 183         else if (side_qi_p == 1 && side_qk_p == 1 && side_qk_q == -1)
 184         {
 185             // Q turns right on the left side of P (test "ML3")
 186             // Union: take both operation
 187             // Intersection: skip
 188             both(ti, operation_union);
 189         }
 190         else if (side_qi_p == side_qk_p && side_qi_p == side_qk_q)
 191         {
 192             // Q turns left on the left side of P (test "ML2")
 193             // or Q turns right on the right side of P (test "MR2")
 194             // Union: take left turn (Q if Q turns left, P if Q turns right)
 195             // Intersection: other turn
 196             int index = side_qk_q == 1 ? index_q : index_p;
 197             ti.operations[index].operation = operation_union;
 198             ti.operations[1 - index].operation = operation_intersection;
 199         }
 200         else if (side_qk_p == 0)
 201         {
 202             // Q intersects on interior of P and continues collinearly
 203             if (side_qk_q == side_qi_p)
 204             {
 205                 // Collinearly in the same direction
 206                 // (Q comes from left of P and turns left,
 207                 //  OR Q comes from right of P and turns right)
 208                 // Omit intersection point.
 209                 // Union: just continue
 210                 // Intersection: just continue
 211                 both(ti, operation_continue);
 212             }
 213             else
 214             {
 215                 // Opposite direction, which is never travelled.
 216                 // If Q turns left, P continues for intersection
 217                 // If Q turns right, P continues for union
 218                 ti.operations[Index].operation = side_qk_q == 1
 219                     ? operation_intersection
 220                     : operation_union;
 221                 ti.operations[1 - Index].operation = operation_blocked;
 222             }
 223         }
 224         else
 225         {
 226             // Should not occur!
 227             ti.method = method_error;
 228         }
 229     }
 230 };
 231
 232
 233 template
 234 <
 235     typename TurnInfo
 236 >
 237 struct touch : public base_turn_handler
 238 {
 239     static inline bool between(int side1, int side2, int turn)
 240     {
 241         return side1 == side2 && ! opposite(side1, turn);
 242     }
 243
 244     /*static inline void block_second(bool block, TurnInfo& ti)
 245     {
 246         if (block)
 247         {
 248             ti.operations[1].operation = operation_blocked;
 249         }
 250     }*/
 251
 252
 253     template
 254     <
 255         typename Point1,
 256         typename Point2,
 257         typename IntersectionInfo,
 258         typename DirInfo,
 259         typename SidePolicy
 260     >
 261     static inline void apply(
 262                 Point1 const& , Point1 const& , Point1 const& ,
 263                 Point2 const& , Point2 const& , Point2 const& ,
 264                 TurnInfo& ti,
 265                 IntersectionInfo const& intersection_info,
 266                 DirInfo const& dir_info,
 267                 SidePolicy const& side)
 268     {
 269         assign_point(ti, method_touch, intersection_info, 0);
 270
 271         int const side_qi_p1 = dir_info.sides.template get<1, 0>();
 272         int const side_qk_p1 = side.qk_wrt_p1();
 273
 274
 275         // If Qi and Qk are both at same side of Pi-Pj,
 276         // or collinear (so: not opposite sides)
 277         if (! opposite(side_qi_p1, side_qk_p1))
 278         {
 279             int const side_pk_q2 = side.pk_wrt_q2();
 280             int const side_pk_p  = side.pk_wrt_p1();
 281             int const side_qk_q  = side.qk_wrt_q1();
 282
 283             bool const q_turns_left = side_qk_q == 1;
 284             bool const block_q = side_qk_p1 == 0
 285                         && ! same(side_qi_p1, side_qk_q)
 286                         ;
 287
 288             // If Pk at same side as Qi/Qk
 289             // (the "or" is for collinear case)
 290             // or Q is fully collinear && P turns not to left
 291             if (side_pk_p == side_qi_p1
 292                 || side_pk_p == side_qk_p1
 293                 || (side_qi_p1 == 0 && side_qk_p1 == 0 && side_pk_p != -1)
 294                 )
 295             {
 296                 // Collinear -> lines join, continue
 297                 // (#BRL2)
 298                 if (side_pk_q2 == 0 && ! block_q)
 299                 {
 300                     both(ti, operation_continue);
 301                     return;
 302                 }
 303
 304                 int const side_pk_q1 = side.pk_wrt_q1();
 305
 306
 307                 // Collinear opposite case -> block P
 308                 // (#BRL4, #BLR8)
 309                 if (side_pk_q1 == 0)
 310                 {
 311                     ti.operations[0].operation = operation_blocked;
 312                     // Q turns right -> union (both independent),
 313                     // Q turns left -> intersection
 314                     ti.operations[1].operation = block_q ? operation_blocked
 315                         : q_turns_left ? operation_intersection
 316                         : operation_union;
 317                     return;
 318                 }
 319
 320                 // Pk between Qi and Qk
 321                 // (#BRL3, #BRL7)
 322                 if (between(side_pk_q1, side_pk_q2, side_qk_q))
 323                 {
 324                     ui_else_iu(q_turns_left, ti);
 325                     if (block_q)
 326                     {
 327                         ti.operations[1].operation = operation_blocked;
 328                     }
 329                     //block_second(block_q, ti);
 330                     return;
 331                 }
 332
 333                 // Pk between Qk and P, so left of Qk (if Q turns right) and vv
 334                 // (#BRL1)
 335                 if (side_pk_q2 == -side_qk_q)
 336                 {
 337                     ui_else_iu(! q_turns_left, ti);
 338                     return;
 339                 }
 340
 341                 //
 342                 // (#BRL5, #BRL9)
 343                 if (side_pk_q1 == -side_qk_q)
 344                 {
 345                     uu_else_ii(! q_turns_left, ti);
 346                     if (block_q)
 347                     {
 348                         ti.operations[1].operation = operation_blocked;
 349                     }
 350                     //block_second(block_q, ti);
 351                     return;
 352                 }
 353             }
 354             else
 355             {
 356                 // Pk at other side than Qi/Pk
 357                 ti.operations[0].operation = q_turns_left
 358                             ? operation_intersection
 359                             : operation_union;
 360                 ti.operations[1].operation = block_q
 361                             ? operation_blocked
 362                             : side_qi_p1 == 1 || side_qk_p1 == 1
 363                             ? operation_union
 364                             : operation_intersection;
 365
 366                 return;
 367             }
 368         }
 369         else
 370         {
 371             // From left to right or from right to left
 372             int const side_pk_p = side.pk_wrt_p1();
 373             bool const right_to_left = side_qk_p1 == 1;
 374
 375             // If p turns into direction of qi (1,2)
 376             if (side_pk_p == side_qi_p1)
 377             {
 378                 int const side_pk_q1 = side.pk_wrt_q1();
 379
 380                 // Collinear opposite case -> block P
 381                 if (side_pk_q1 == 0)
 382                 {
 383                     ti.operations[0].operation = operation_blocked;
 384                     ti.operations[1].operation = right_to_left
 385                                 ? operation_union : operation_intersection;
 386                     return;
 387                 }
 388
 389                 if (side_pk_q1 == side_qk_p1)
 390                 {
 391                     uu_else_ii(right_to_left, ti);
 392                     return;
 393                 }
 394             }
 395
 396             // If p turns into direction of qk (4,5)
 397             if (side_pk_p == side_qk_p1)
 398             {
 399                 int const side_pk_q2 = side.pk_wrt_q2();
 400
 401                 // Collinear case -> lines join, continue
 402                 if (side_pk_q2 == 0)
 403                 {
 404                     both(ti, operation_continue);
 405                     return;
 406                 }
 407                 if (side_pk_q2 == side_qk_p1)
 408                 {
 409                     ui_else_iu(right_to_left, ti);
 410                     return;
 411                 }
 412             }
 413             // otherwise (3)
 414             ui_else_iu(! right_to_left, ti);
 415             return;
 416         }
 417
 418 #ifdef BOOST_GEOMETRY_DEBUG_GET_TURNS
 419         // Normally a robustness issue.
 420         // TODO: more research if still occuring
 421         std::cout << "Not yet handled" << std::endl
 422             << "pi " << get<0>(pi) << " , " << get<1>(pi)
 423             << " pj " << get<0>(pj) << " , " << get<1>(pj)
 424             << " pk " << get<0>(pk) << " , " << get<1>(pk)
 425             << std::endl
 426             << "qi " << get<0>(qi) << " , " << get<1>(qi)
 427             << " qj " << get<0>(qj) << " , " << get<1>(qj)
 428             << " qk " << get<0>(qk) << " , " << get<1>(qk)
 429             << std::endl;
 430 #endif
 431
 432     }
 433 };
 434
 435
 436 template
 437 <
 438     typename TurnInfo
 439 >
 440 struct equal : public base_turn_handler
 441 {
 442     template
 443     <
 444         typename Point1,
 445         typename Point2,
 446         typename IntersectionInfo,
 447         typename DirInfo,
 448         typename SidePolicy
 449     >
 450     static inline void apply(
 451                 Point1 const& , Point1 const& , Point1 const& ,
 452                 Point2 const& , Point2 const& , Point2 const& ,
 453                 TurnInfo& ti,
 454                 IntersectionInfo const& info,
 455                 DirInfo const&  ,
 456                 SidePolicy const& side)
 457     {
 458         // Copy the intersection point in TO direction
 459         assign_point(ti, method_equal, info, non_opposite_to_index(info));
 460
 461         int const side_pk_q2 = side.pk_wrt_q2();
 462         int const side_pk_p = side.pk_wrt_p1();
 463         int const side_qk_p = side.qk_wrt_p1();
 464
 465
 466         // If pk is collinear with qj-qk, they continue collinearly.
 467         // This can be on either side of p1 (== q1), or collinear
 468         // The second condition checks if they do not continue
 469         // oppositely
 470         if (side_pk_q2 == 0 && side_pk_p == side_qk_p)
 471         {
 472             both(ti, operation_continue);
 473
 474             return;
 475         }
 476
 477
 478         // If they turn to same side (not opposite sides)
 479         if (! opposite(side_pk_p, side_qk_p))
 480         {
 481             // If pk is left of q2 or collinear: p: union, q: intersection
 482             ui_else_iu(side_pk_q2 != -1, ti);
 483         }
 484         else
 485         {
 486             // They turn opposite sides. If p turns left (or collinear),
 487             // p: union, q: intersection
 488             ui_else_iu(side_pk_p != -1, ti);
 489         }
 490     }
 491 };
 492
 493
 494 template
 495 <
 496     typename TurnInfo,
 497     typename AssignPolicy
 498 >
 499 struct equal_opposite : public base_turn_handler
 500 {
 501     template
 502     <
 503         typename Point1,
 504         typename Point2,
 505         typename OutputIterator,
 506         typename IntersectionInfo,
 507         typename DirInfo
 508     >
 509     static inline void apply(Point1 const& pi, Point2 const& qi,
 510                 /* by value: */ TurnInfo tp,
 511                 OutputIterator& out,
 512                 IntersectionInfo const& intersection_info,
 513                 DirInfo const& dir_info)
 514     {
 515         // For equal-opposite segments, normally don't do anything.
 516         if (AssignPolicy::include_opposite)
 517         {
 518             tp.method = method_equal;
 519             for (int i = 0; i < 2; i++)
 520             {
 521                 tp.operations[i].operation = operation_opposite;
 522             }
 523             for (unsigned int i = 0; i < intersection_info.count; i++)
 524             {
 525                 assign_point(tp, method_none, intersection_info, i);
 526                 AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info);
 527                 *out++ = tp;
 528             }
 529         }
 530     }
 531 };
 532
 533 template
 534 <
 535     typename TurnInfo
 536 >
 537 struct collinear : public base_turn_handler
 538 {
 539     /*
 540         arrival P   pk//p1  qk//q1   product*  case    result
 541          1           1                1        CLL1    ui
 542         -1                   1       -1        CLL2    iu
 543          1           1                1        CLR1    ui
 544         -1                  -1        1        CLR2    ui
 545
 546          1          -1               -1        CRL1    iu
 547         -1                   1       -1        CRL2    iu
 548          1          -1               -1        CRR1    iu
 549         -1                  -1        1        CRR2    ui
 550
 551          1           0                0        CC1     cc
 552         -1                   0        0        CC2     cc
 553
 554          *product = arrival * (pk//p1 or qk//q1)
 555
 556          Stated otherwise:
 557          - if P arrives: look at turn P
 558          - if Q arrives: look at turn Q
 559          - if P arrives and P turns left: union for P
 560          - if P arrives and P turns right: intersection for P
 561          - if Q arrives and Q turns left: union for Q (=intersection for P)
 562          - if Q arrives and Q turns right: intersection for Q (=union for P)
 563
 564          ROBUSTNESS: p and q are collinear, so you would expect
 565          that side qk//p1 == pk//q1. But that is not always the case
 566          in near-epsilon ranges. Then decision logic is different.
 567          If p arrives, q is further, so the angle qk//p1 is (normally)
 568          more precise than pk//p1
 569
 570     */
 571     template
 572     <
 573         typename Point1,
 574         typename Point2,
 575         typename IntersectionInfo,
 576         typename DirInfo,
 577         typename SidePolicy
 578     >
 579     static inline void apply(
 580                 Point1 const& , Point1 const& , Point1 const& ,
 581                 Point2 const& , Point2 const& , Point2 const& ,
 582                 TurnInfo& ti,
 583                 IntersectionInfo const& info,
 584                 DirInfo const& dir_info,
 585                 SidePolicy const& side)
 586     {
 587         // Copy the intersection point in TO direction
 588         assign_point(ti, method_collinear, info, non_opposite_to_index(info));
 589
 590         int const arrival = dir_info.arrival[0];
 591         // Should not be 0, this is checked before
 592         BOOST_ASSERT(arrival != 0);
 593
 594         int const side_p = side.pk_wrt_p1();
 595         int const side_q = side.qk_wrt_q1();
 596
 597         // If p arrives, use p, else use q
 598         int const side_p_or_q = arrival == 1
 599             ? side_p
 600             : side_q
 601             ;
 602
 603         // See comments above,
 604         // resulting in a strange sort of mathematic rule here:
 605         // The arrival-info multiplied by the relevant side
 606         // delivers a consistent result.
 607
 608         int const product = arrival * side_p_or_q;
 609
 610         if(product == 0)
 611         {
 612             both(ti, operation_continue);
 613         }
 614         else
 615         {
 616             ui_else_iu(product == 1, ti);
 617         }
 618     }
 619
 620 };
 621
 622 template
 623 <
 624     typename TurnInfo,
 625     typename AssignPolicy
 626 >
 627 struct collinear_opposite : public base_turn_handler
 628 {
 629 private :
 630     /*
 631         arrival P  arrival Q  pk//p1   qk//q1  case  result2  result
 632         --------------------------------------------------------------
 633          1          1          1       -1      CLO1    ix      xu
 634          1          1          1        0      CLO2    ix      (xx)
 635          1          1          1        1      CLO3    ix      xi
 636
 637          1          1          0       -1      CCO1    (xx)    xu
 638          1          1          0        0      CCO2    (xx)    (xx)
 639          1          1          0        1      CCO3    (xx)    xi
 640
 641          1          1         -1       -1      CRO1    ux      xu
 642          1          1         -1        0      CRO2    ux      (xx)
 643          1          1         -1        1      CRO3    ux      xi
 644
 645         -1          1                  -1      CXO1    xu
 646         -1          1                   0      CXO2    (xx)
 647         -1          1                   1      CXO3    xi
 648
 649          1         -1          1               CXO1    ix
 650          1         -1          0               CXO2    (xx)
 651          1         -1         -1               CXO3    ux
 652     */
 653
 654     template
 655     <
 656         int Index,
 657         typename Point1,
 658         typename Point2,
 659         typename IntersectionInfo
 660     >
 661     static inline bool set_tp(Point1 const& , Point1 const& , Point1 const& , int side_rk_r,
 662                 bool const handle_robustness,
 663                 Point2 const& , Point2 const& , int side_rk_s,
 664                 TurnInfo& tp, IntersectionInfo const& intersection_info)
 665     {
 666         boost::ignore_unused_variable_warning(handle_robustness);
 667         boost::ignore_unused_variable_warning(side_rk_s);
 668
 669         operation_type blocked = operation_blocked;
 670         switch(side_rk_r)
 671         {
 672
 673             case 1 :
 674                 // Turning left on opposite collinear: intersection
 675                 tp.operations[Index].operation = operation_intersection;
 676                 break;
 677             case -1 :
 678                 // Turning right on opposite collinear: union
 679                 tp.operations[Index].operation = operation_union;
 680                 break;
 681             case 0 :
 682                 // No turn on opposite collinear: block, do not traverse
 683                 // But this "xx" is usually ignored, it is useless to include
 684                 // two operations blocked, so the whole point does not need
 685                 // to be generated.
 686                 // So return false to indicate nothing is to be done.
 687                 if (AssignPolicy::include_opposite)
 688                 {
 689                     tp.operations[Index].operation = operation_opposite;
 690                     blocked = operation_opposite;
 691                 }
 692                 else
 693                 {
 694                     return false;
 695                 }
 696                 break;
 697         }
 698
 699         // The other direction is always blocked when collinear opposite
 700         tp.operations[1 - Index].operation = blocked;
 701
 702         // If P arrives within Q, set info on P (which is done above, index=0),
 703         // this turn-info belongs to the second intersection point, index=1
 704         // (see e.g. figure CLO1)
 705         assign_point(tp, method_collinear, intersection_info, 1 - Index);
 706         return true;
 707     }
 708
 709 public:
 710     static inline void empty_transformer(TurnInfo &) {}
 711
 712     template
 713     <
 714         typename Point1,
 715         typename Point2,
 716         typename OutputIterator,
 717         typename IntersectionInfo,
 718         typename DirInfo,
 719         typename SidePolicy
 720     >
 721     static inline void apply(
 722                 Point1 const& pi, Point1 const& pj, Point1 const& pk,
 723                 Point2 const& qi, Point2 const& qj, Point2 const& qk,
 724
 725                 // Opposite collinear can deliver 2 intersection points,
 726                 TurnInfo const& tp_model,
 727                 OutputIterator& out,
 728
 729                 IntersectionInfo const& intersection_info,
 730                 DirInfo const& dir_info,
 731                 SidePolicy const& side)
 732     {
 733         apply(pi, pj, pk, qi, qj, qk, tp_model, out, intersection_info, dir_info, side, empty_transformer);
 734     }
 735
 736 public:
 737     template
 738     <
 739         typename Point1,
 740         typename Point2,
 741         typename OutputIterator,
 742         typename IntersectionInfo,
 743         typename DirInfo,
 744         typename SidePolicy,
 745         typename TurnTransformer
 746     >
 747     static inline void apply(
 748                 Point1 const& pi, Point1 const& pj, Point1 const& pk,
 749                 Point2 const& qi, Point2 const& qj, Point2 const& qk,
 750
 751                 // Opposite collinear can deliver 2 intersection points,
 752                 TurnInfo const& tp_model,
 753                 OutputIterator& out,
 754
 755                 IntersectionInfo const& intersection_info,
 756                 DirInfo const& dir_info,
 757                 SidePolicy const& side,
 758                 TurnTransformer turn_transformer,
 759                 bool const is_pk_valid = true, bool const is_qk_valid = true)
 760     {
 761         TurnInfo tp = tp_model;
 762
 763         // If P arrives within Q, there is a turn dependent on P
 764         if ( dir_info.arrival[0] == 1
 765           && is_pk_valid
 766           && set_tp<0>(pi, pj, pk, side.pk_wrt_p1(), true, qi, qj, side.pk_wrt_q1(), tp, intersection_info) )
 767         {
 768             turn_transformer(tp);
 769
 770             AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info);
 771             *out++ = tp;
 772         }
 773
 774         // If Q arrives within P, there is a turn dependent on Q
 775         if ( dir_info.arrival[1] == 1
 776           && is_qk_valid
 777           && set_tp<1>(qi, qj, qk, side.qk_wrt_q1(), false, pi, pj, side.qk_wrt_p1(), tp, intersection_info) )
 778         {
 779             turn_transformer(tp);
 780
 781             AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info);
 782             *out++ = tp;
 783         }
 784
 785         if (AssignPolicy::include_opposite)
 786         {
 787             // Handle cases not yet handled above
 788             if ((dir_info.arrival[1] == -1 && dir_info.arrival[0] == 0)
 789                 || (dir_info.arrival[0] == -1 && dir_info.arrival[1] == 0))
 790             {
 791                 for (int i = 0; i < 2; i++)
 792                 {
 793                     tp.operations[i].operation = operation_opposite;
 794                 }
 795                 for (unsigned int i = 0; i < intersection_info.count; i++)
 796                 {
 797                     assign_point(tp, method_collinear, intersection_info, i);
 798                     AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info);
 799                     *out++ = tp;
 800                 }
 801             }
 802         }
 803
 804     }
 805 };
 806
 807
 808 template
 809 <
 810     typename TurnInfo
 811 >
 812 struct crosses : public base_turn_handler
 813 {
 814     template
 815     <
 816         typename Point1,
 817         typename Point2,
 818         typename IntersectionInfo,
 819         typename DirInfo
 820     >
 821     static inline void apply(
 822                 Point1 const& , Point1 const& , Point1 const& ,
 823                 Point2 const& , Point2 const& , Point2 const& ,
 824                 TurnInfo& ti,
 825                 IntersectionInfo const& intersection_info,
 826                 DirInfo const& dir_info)
 827     {
 828         assign_point(ti, method_crosses, intersection_info, 0);
 829
 830         // In all casees:
 831         // If Q crosses P from left to right
 832         // Union: take P
 833         // Intersection: take Q
 834         // Otherwise: vice versa
 835         int const side_qi_p1 = dir_info.sides.template get<1, 0>();
 836         int const index = side_qi_p1 == 1 ? 0 : 1;
 837         ti.operations[index].operation = operation_union;
 838         ti.operations[1 - index].operation = operation_intersection;
 839     }
 840 };
 841
 842 struct only_convert : public base_turn_handler
 843 {
 844     template<typename TurnInfo, typename IntersectionInfo>
 845     static inline void apply(TurnInfo& ti, IntersectionInfo const& intersection_info)
 846     {
 847         assign_point(ti, method_none, intersection_info, 0); // was collinear
 848         ti.operations[0].operation = operation_continue;
 849         ti.operations[1].operation = operation_continue;
 850     }
 851 };
 852
 853 /*!
 854 \brief Policy doing nothing
 855 \details get_turn_info can have an optional policy to get/assign some
 856     extra information. By default it does not, and this class
 857     is that default.
 858  */
 859 struct assign_null_policy
 860 {
 861     static bool const include_no_turn = false;
 862     static bool const include_degenerate = false;
 863     static bool const include_opposite = false;
 864
 865     template
 866     <
 867         typename Info,
 868         typename Point1,
 869         typename Point2,
 870         typename IntersectionInfo,
 871         typename DirInfo
 872     >
 873     static inline void apply(Info& , Point1 const& , Point2 const&, IntersectionInfo const&, DirInfo const&)
 874     {}
 875
 876 };
 877
 878
 879 /*!
 880     \brief Turn information: intersection point, method, and turn information
 881     \details Information necessary for traversal phase (a phase
 882         of the overlay process). The information is gathered during the
 883         get_turns (segment intersection) phase.
 884     \tparam Point1 point type of first segment
 885     \tparam Point2 point type of second segment
 886     \tparam TurnInfo type of class getting intersection and turn info
 887     \tparam AssignPolicy policy to assign extra info,
 888         e.g. to calculate distance from segment's first points
 889         to intersection points.
 890         It also defines if a certain class of points
 891         (degenerate, non-turns) should be included.
 892  */
 893 template<typename AssignPolicy>
 894 struct get_turn_info
 895 {
 896     // Intersect pi-pj with qi-qj
 897     // The points pk and qk are used do determine more information
 898     // about the turn (turn left/right)
 899     template
 900     <
 901         typename Point1,
 902         typename Point2,
 903         typename TurnInfo,
 904         typename RobustPolicy,
 905         typename OutputIterator
 906     >
 907     static inline OutputIterator apply(
 908                 Point1 const& pi, Point1 const& pj, Point1 const& pk,
 909                 Point2 const& qi, Point2 const& qj, Point2 const& qk,
 910                 bool /*is_p_first*/, bool /*is_p_last*/,
 911                 bool /*is_q_first*/, bool /*is_q_last*/,
 912                 TurnInfo const& tp_model,
 913                 RobustPolicy const& robust_policy,
 914                 OutputIterator out)
 915     {
 916         typedef intersection_info<Point1, Point2, typename TurnInfo::point_type, RobustPolicy>
 917             inters_info;
 918
 919         inters_info inters(pi, pj, pk, qi, qj, qk, robust_policy);
 920
 921         char const method = inters.d_info().how;
 922
 923         // Copy, to copy possibly extended fields
 924         TurnInfo tp = tp_model;
 925
 926         // Select method and apply
 927         switch(method)
 928         {
 929             case 'a' : // collinear, "at"
 930             case 'f' : // collinear, "from"
 931             case 's' : // starts from the middle
 932                 if (AssignPolicy::include_no_turn
 933                     && inters.i_info().count > 0)
 934                 {
 935                     only_convert::apply(tp, inters.i_info());
 936                     AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
 937                     *out++ = tp;
 938                 }
 939                 break;
 940
 941             case 'd' : // disjoint: never do anything
 942                 break;
 943
 944             case 'm' :
 945             {
 946                 typedef touch_interior
 947                     <
 948                         TurnInfo
 949                     > policy;
 950
 951                 // If Q (1) arrives (1)
 952                 if ( inters.d_info().arrival[1] == 1 )
 953                 {
 954                     policy::template apply<0>(pi, pj, pk, qi, qj, qk,
 955                                 tp, inters.i_info(), inters.d_info(),
 956                                 inters.sides());
 957                 }
 958                 else
 959                 {
 960                     // Swap p/q
 961                     side_calculator
 962                         <
 963                             typename inters_info::robust_point2_type,
 964                             typename inters_info::robust_point1_type
 965                         > swapped_side_calc(inters.rqi(), inters.rqj(), inters.rqk(),
 966                                             inters.rpi(), inters.rpj(), inters.rpk());
 967                     policy::template apply<1>(qi, qj, qk, pi, pj, pk,
 968                                 tp, inters.i_info(), inters.d_info(),
 969                                 swapped_side_calc);
 970                 }
 971                 AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
 972                 *out++ = tp;
 973             }
 974             break;
 975             case 'i' :
 976             {
 977                 crosses<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
 978                     tp, inters.i_info(), inters.d_info());
 979                 AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
 980                 *out++ = tp;
 981             }
 982             break;
 983             case 't' :
 984             {
 985                 // Both touch (both arrive there)
 986                 touch<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
 987                     tp, inters.i_info(), inters.d_info(), inters.sides());
 988                 AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
 989                 *out++ = tp;
 990             }
 991             break;
 992             case 'e':
 993             {
 994                 if ( ! inters.d_info().opposite )
 995                 {
 996                     // Both equal
 997                     // or collinear-and-ending at intersection point
 998                     equal<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
 999                         tp, inters.i_info(), inters.d_info(), inters.sides());
1000                     AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
1001                     *out++ = tp;
1002                 }
1003                 else
1004                 {
1005                     equal_opposite
1006                         <
1007                             TurnInfo,
1008                             AssignPolicy
1009                         >::apply(pi, qi,
1010                             tp, out, inters.i_info(), inters.d_info());
1011                 }
1012             }
1013             break;
1014             case 'c' :
1015             {
1016                 // Collinear
1017                 if ( ! inters.d_info().opposite )
1018                 {
1019
1020                     if ( inters.d_info().arrival[0] == 0 )
1021                     {
1022                         // Collinear, but similar thus handled as equal
1023                         equal<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
1024                                 tp, inters.i_info(), inters.d_info(), inters.sides());
1025
1026                         // override assigned method
1027                         tp.method = method_collinear;
1028                     }
1029                     else
1030                     {
1031                         collinear<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
1032                                 tp, inters.i_info(), inters.d_info(), inters.sides());
1033                     }
1034
1035                     AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
1036                     *out++ = tp;
1037                 }
1038                 else
1039                 {
1040                     collinear_opposite
1041                         <
1042                             TurnInfo,
1043                             AssignPolicy
1044                         >::apply(pi, pj, pk, qi, qj, qk,
1045                             tp, out, inters.i_info(), inters.d_info(), inters.sides());
1046                 }
1047             }
1048             break;
1049             case '0' :
1050             {
1051                 // degenerate points
1052                 if (AssignPolicy::include_degenerate)
1053                 {
1054                     only_convert::apply(tp, inters.i_info());
1055                     AssignPolicy::apply(tp, pi, qi, inters.i_info(), inters.d_info());
1056                     *out++ = tp;
1057                 }
1058             }
1059             break;
1060             default :
1061             {
1062 #if defined(BOOST_GEOMETRY_DEBUG_ROBUSTNESS)
1063                 std::cout << "TURN: Unknown method: " << method << std::endl;
1064 #endif
1065 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
1066                 throw turn_info_exception(method);
1067 #endif
1068             }
1069             break;
1070         }
1071
1072         return out;
1073     }
1074 };
1075
1076
1077 }} // namespace detail::overlay
1078 #endif //DOXYGEN_NO_DETAIL
1079
1080
1081 }} // namespace boost::geometry
1082
1083
1084 #if defined(_MSC_VER)
1085 #pragma warning(pop)
1086 #endif
1087
1088 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP