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, 2021, 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& pj, Point1 const& pk, 589 Point2 const& , Point2 const& qj, Point2 const& qk, 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 // Calculate remaining distance. If it continues collinearly it is 628 // measured until the end of the next segment 629 ti.operations[0].remaining_distance 630 = side_p == 0 631 ? distance_measure(ti.point, pk) 632 : distance_measure(ti.point, pj); 633 ti.operations[1].remaining_distance 634 = side_q == 0 635 ? distance_measure(ti.point, qk) 636 : distance_measure(ti.point, qj); 637 } 638 639 template <typename Point1, typename Point2> 640 static inline typename geometry::coordinate_type<Point1>::type distance_measureboost::geometry::detail::overlay::collinear641 distance_measure(Point1 const& a, Point2 const& b) 642 { 643 // TODO: use comparable distance for point-point instead - but that 644 // causes currently cycling include problems 645 typedef typename geometry::coordinate_type<Point1>::type ctype; 646 ctype const dx = get<0>(a) - get<0>(b); 647 ctype const dy = get<1>(b) - get<1>(b); 648 return dx * dx + dy * dy; 649 } 650 }; 651 652 template 653 < 654 typename TurnInfo, 655 typename AssignPolicy 656 > 657 struct collinear_opposite : public base_turn_handler 658 { 659 private : 660 /* 661 arrival P arrival Q pk//p1 qk//q1 case result2 result 662 -------------------------------------------------------------- 663 1 1 1 -1 CLO1 ix xu 664 1 1 1 0 CLO2 ix (xx) 665 1 1 1 1 CLO3 ix xi 666 667 1 1 0 -1 CCO1 (xx) xu 668 1 1 0 0 CCO2 (xx) (xx) 669 1 1 0 1 CCO3 (xx) xi 670 671 1 1 -1 -1 CRO1 ux xu 672 1 1 -1 0 CRO2 ux (xx) 673 1 1 -1 1 CRO3 ux xi 674 675 -1 1 -1 CXO1 xu 676 -1 1 0 CXO2 (xx) 677 -1 1 1 CXO3 xi 678 679 1 -1 1 CXO1 ix 680 1 -1 0 CXO2 (xx) 681 1 -1 -1 CXO3 ux 682 */ 683 684 template 685 < 686 unsigned int Index, 687 typename Point1, 688 typename Point2, 689 typename IntersectionInfo 690 > set_tpboost::geometry::detail::overlay::collinear_opposite691 static inline bool set_tp(Point1 const& , Point1 const& , Point1 const& , int side_rk_r, 692 bool const handle_robustness, 693 Point2 const& , Point2 const& , int side_rk_s, 694 TurnInfo& tp, IntersectionInfo const& intersection_info) 695 { 696 BOOST_STATIC_ASSERT(Index <= 1); 697 698 boost::ignore_unused(handle_robustness, side_rk_s); 699 700 operation_type blocked = operation_blocked; 701 switch(side_rk_r) 702 { 703 704 case 1 : 705 // Turning left on opposite collinear: intersection 706 tp.operations[Index].operation = operation_intersection; 707 break; 708 case -1 : 709 // Turning right on opposite collinear: union 710 tp.operations[Index].operation = operation_union; 711 break; 712 case 0 : 713 // No turn on opposite collinear: block, do not traverse 714 // But this "xx" is usually ignored, it is useless to include 715 // two operations blocked, so the whole point does not need 716 // to be generated. 717 // So return false to indicate nothing is to be done. 718 if (AssignPolicy::include_opposite) 719 { 720 tp.operations[Index].operation = operation_opposite; 721 blocked = operation_opposite; 722 } 723 else 724 { 725 return false; 726 } 727 break; 728 } 729 730 // The other direction is always blocked when collinear opposite 731 tp.operations[1 - Index].operation = blocked; 732 733 // If P arrives within Q, set info on P (which is done above, index=0), 734 // this turn-info belongs to the second intersection point, index=1 735 // (see e.g. figure CLO1) 736 assign_point(tp, method_collinear, intersection_info, 1 - Index); 737 return true; 738 } 739 740 public: empty_transformerboost::geometry::detail::overlay::collinear_opposite741 static inline void empty_transformer(TurnInfo &) {} 742 743 template 744 < 745 typename Point1, 746 typename Point2, 747 typename OutputIterator, 748 typename IntersectionInfo, 749 typename SidePolicy 750 > applyboost::geometry::detail::overlay::collinear_opposite751 static inline void apply( 752 Point1 const& pi, Point1 const& pj, Point1 const& pk, 753 Point2 const& qi, Point2 const& qj, Point2 const& qk, 754 755 // Opposite collinear can deliver 2 intersection points, 756 TurnInfo const& tp_model, 757 OutputIterator& out, 758 759 IntersectionInfo const& intersection_info, 760 SidePolicy const& side) 761 { 762 apply(pi, pj, pk, qi, qj, qk, tp_model, out, intersection_info, side, empty_transformer); 763 } 764 765 public: 766 template 767 < 768 typename Point1, 769 typename Point2, 770 typename OutputIterator, 771 typename IntersectionInfo, 772 typename SidePolicy, 773 typename TurnTransformer 774 > applyboost::geometry::detail::overlay::collinear_opposite775 static inline void apply( 776 Point1 const& pi, Point1 const& pj, Point1 const& pk, 777 Point2 const& qi, Point2 const& qj, Point2 const& qk, 778 779 // Opposite collinear can deliver 2 intersection points, 780 TurnInfo const& tp_model, 781 OutputIterator& out, 782 783 IntersectionInfo const& info, 784 SidePolicy const& side, 785 TurnTransformer turn_transformer, 786 bool const is_pk_valid = true, bool const is_qk_valid = true) 787 { 788 TurnInfo tp = tp_model; 789 790 int const p_arrival = info.d_info().arrival[0]; 791 int const q_arrival = info.d_info().arrival[1]; 792 793 // If P arrives within Q, there is a turn dependent on P 794 if ( p_arrival == 1 795 && is_pk_valid 796 && set_tp<0>(pi, pj, pk, side.pk_wrt_p1(), true, qi, qj, side.pk_wrt_q1(), tp, info.i_info()) ) 797 { 798 turn_transformer(tp); 799 800 AssignPolicy::apply(tp, pi, qi, info); 801 *out++ = tp; 802 } 803 804 // If Q arrives within P, there is a turn dependent on Q 805 if ( q_arrival == 1 806 && is_qk_valid 807 && set_tp<1>(qi, qj, qk, side.qk_wrt_q1(), false, pi, pj, side.qk_wrt_p1(), tp, info.i_info()) ) 808 { 809 turn_transformer(tp); 810 811 AssignPolicy::apply(tp, pi, qi, info); 812 *out++ = tp; 813 } 814 815 if (AssignPolicy::include_opposite) 816 { 817 // Handle cases not yet handled above 818 if ((q_arrival == -1 && p_arrival == 0) 819 || (p_arrival == -1 && q_arrival == 0)) 820 { 821 for (unsigned int i = 0; i < 2; i++) 822 { 823 tp.operations[i].operation = operation_opposite; 824 } 825 for (unsigned int i = 0; i < info.i_info().count; i++) 826 { 827 assign_point(tp, method_collinear, info.i_info(), i); 828 AssignPolicy::apply(tp, pi, qi, info); 829 *out++ = tp; 830 } 831 } 832 } 833 834 } 835 }; 836 837 838 template 839 < 840 typename TurnInfo 841 > 842 struct crosses : public base_turn_handler 843 { 844 template 845 < 846 typename Point1, 847 typename Point2, 848 typename IntersectionInfo, 849 typename DirInfo 850 > applyboost::geometry::detail::overlay::crosses851 static inline void apply( 852 Point1 const& , Point1 const& , Point1 const& , 853 Point2 const& , Point2 const& , Point2 const& , 854 TurnInfo& ti, 855 IntersectionInfo const& intersection_info, 856 DirInfo const& dir_info) 857 { 858 assign_point(ti, method_crosses, intersection_info, 0); 859 860 // In all casees: 861 // If Q crosses P from left to right 862 // Union: take P 863 // Intersection: take Q 864 // Otherwise: vice versa 865 int const side_qi_p1 = dir_info.sides.template get<1, 0>(); 866 unsigned int const index = side_qi_p1 == 1 ? 0 : 1; 867 ti.operations[index].operation = operation_union; 868 ti.operations[1 - index].operation = operation_intersection; 869 } 870 }; 871 872 struct only_convert : public base_turn_handler 873 { 874 template<typename TurnInfo, typename IntersectionInfo> applyboost::geometry::detail::overlay::only_convert875 static inline void apply(TurnInfo& ti, IntersectionInfo const& intersection_info) 876 { 877 assign_point(ti, method_none, intersection_info, 0); // was collinear 878 ti.operations[0].operation = operation_continue; 879 ti.operations[1].operation = operation_continue; 880 } 881 }; 882 883 /*! 884 \brief Policy doing nothing 885 \details get_turn_info can have an optional policy to get/assign some 886 extra information. By default it does not, and this class 887 is that default. 888 */ 889 struct assign_null_policy 890 { 891 static bool const include_no_turn = false; 892 static bool const include_degenerate = false; 893 static bool const include_opposite = false; 894 895 template 896 < 897 typename Info, 898 typename Point1, 899 typename Point2, 900 typename IntersectionInfo 901 > applyboost::geometry::detail::overlay::assign_null_policy902 static inline void apply(Info& , Point1 const& , Point2 const&, IntersectionInfo const&) 903 {} 904 905 }; 906 907 908 /*! 909 \brief Turn information: intersection point, method, and turn information 910 \details Information necessary for traversal phase (a phase 911 of the overlay process). The information is gathered during the 912 get_turns (segment intersection) phase. 913 \tparam Point1 point type of first segment 914 \tparam Point2 point type of second segment 915 \tparam TurnInfo type of class getting intersection and turn info 916 \tparam AssignPolicy policy to assign extra info, 917 e.g. to calculate distance from segment's first points 918 to intersection points. 919 It also defines if a certain class of points 920 (degenerate, non-turns) should be included. 921 */ 922 template<typename AssignPolicy> 923 struct get_turn_info 924 { 925 // Intersect pi-pj with qi-qj 926 // The points pk and qk are used do determine more information 927 // about the turn (turn left/right) 928 template 929 < 930 typename Point1, 931 typename Point2, 932 typename TurnInfo, 933 typename RobustPolicy, 934 typename OutputIterator 935 > applyboost::geometry::detail::overlay::get_turn_info936 static inline OutputIterator apply( 937 Point1 const& pi, Point1 const& pj, Point1 const& pk, 938 Point2 const& qi, Point2 const& qj, Point2 const& qk, 939 bool /*is_p_first*/, bool /*is_p_last*/, 940 bool /*is_q_first*/, bool /*is_q_last*/, 941 TurnInfo const& tp_model, 942 RobustPolicy const& robust_policy, 943 OutputIterator out) 944 { 945 typedef intersection_info<Point1, Point2, typename TurnInfo::point_type, RobustPolicy> 946 inters_info; 947 948 inters_info inters(pi, pj, pk, qi, qj, qk, robust_policy); 949 950 char const method = inters.d_info().how; 951 952 // Copy, to copy possibly extended fields 953 TurnInfo tp = tp_model; 954 955 // Select method and apply 956 switch(method) 957 { 958 case 'a' : // collinear, "at" 959 case 'f' : // collinear, "from" 960 case 's' : // starts from the middle 961 if (AssignPolicy::include_no_turn 962 && inters.i_info().count > 0) 963 { 964 only_convert::apply(tp, inters.i_info()); 965 AssignPolicy::apply(tp, pi, qi, inters); 966 *out++ = tp; 967 } 968 break; 969 970 case 'd' : // disjoint: never do anything 971 break; 972 973 case 'm' : 974 { 975 typedef touch_interior 976 < 977 TurnInfo 978 > policy; 979 980 // If Q (1) arrives (1) 981 if ( inters.d_info().arrival[1] == 1 ) 982 { 983 policy::template apply<0>(pi, pj, pk, qi, qj, qk, 984 tp, inters.i_info(), inters.d_info(), 985 inters.sides()); 986 } 987 else 988 { 989 // Swap p/q 990 side_calculator 991 < 992 typename inters_info::robust_point2_type, 993 typename inters_info::robust_point1_type 994 > swapped_side_calc(inters.rqi(), inters.rqj(), inters.rqk(), 995 inters.rpi(), inters.rpj(), inters.rpk()); 996 policy::template apply<1>(qi, qj, qk, pi, pj, pk, 997 tp, inters.i_info(), inters.d_info(), 998 swapped_side_calc); 999 } 1000 AssignPolicy::apply(tp, pi, qi, inters); 1001 *out++ = tp; 1002 } 1003 break; 1004 case 'i' : 1005 { 1006 crosses<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, 1007 tp, inters.i_info(), inters.d_info()); 1008 AssignPolicy::apply(tp, pi, qi, inters); 1009 *out++ = tp; 1010 } 1011 break; 1012 case 't' : 1013 { 1014 // Both touch (both arrive there) 1015 touch<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, 1016 tp, inters.i_info(), inters.d_info(), inters.sides()); 1017 AssignPolicy::apply(tp, pi, qi, inters); 1018 *out++ = tp; 1019 } 1020 break; 1021 case 'e': 1022 { 1023 if ( ! inters.d_info().opposite ) 1024 { 1025 // Both equal 1026 // or collinear-and-ending at intersection point 1027 equal<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, 1028 tp, inters.i_info(), inters.d_info(), inters.sides()); 1029 AssignPolicy::apply(tp, pi, qi, inters); 1030 *out++ = tp; 1031 } 1032 else 1033 { 1034 equal_opposite 1035 < 1036 TurnInfo, 1037 AssignPolicy 1038 >::apply(pi, qi, 1039 tp, out, inters); 1040 } 1041 } 1042 break; 1043 case 'c' : 1044 { 1045 // Collinear 1046 if ( ! inters.d_info().opposite ) 1047 { 1048 1049 if ( inters.d_info().arrival[0] == 0 ) 1050 { 1051 // Collinear, but similar thus handled as equal 1052 equal<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, 1053 tp, inters.i_info(), inters.d_info(), inters.sides()); 1054 1055 // override assigned method 1056 tp.method = method_collinear; 1057 } 1058 else 1059 { 1060 collinear<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, 1061 tp, inters.i_info(), inters.d_info(), inters.sides()); 1062 } 1063 1064 AssignPolicy::apply(tp, pi, qi, inters); 1065 *out++ = tp; 1066 } 1067 else 1068 { 1069 collinear_opposite 1070 < 1071 TurnInfo, 1072 AssignPolicy 1073 >::apply(pi, pj, pk, qi, qj, qk, 1074 tp, out, inters, inters.sides()); 1075 } 1076 } 1077 break; 1078 case '0' : 1079 { 1080 // degenerate points 1081 if (AssignPolicy::include_degenerate) 1082 { 1083 only_convert::apply(tp, inters.i_info()); 1084 AssignPolicy::apply(tp, pi, qi, inters); 1085 *out++ = tp; 1086 } 1087 } 1088 break; 1089 default : 1090 { 1091 #if defined(BOOST_GEOMETRY_DEBUG_ROBUSTNESS) 1092 std::cout << "TURN: Unknown method: " << method << std::endl; 1093 #endif 1094 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW) 1095 throw turn_info_exception(method); 1096 #endif 1097 } 1098 break; 1099 } 1100 1101 return out; 1102 } 1103 }; 1104 1105 1106 }} // namespace detail::overlay 1107 #endif //DOXYGEN_NO_DETAIL 1108 1109 1110 }} // namespace boost::geometry 1111 1112 1113 #if defined(_MSC_VER) 1114 #pragma warning(pop) 1115 #endif 1116 1117 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP 1118