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