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