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-2020. 7 // Modifications copyright (c) 2015-2020 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 #include <boost/core/ignore_unused.hpp> 19 #include <boost/throw_exception.hpp> 20 21 #include <boost/geometry/core/access.hpp> 22 #include <boost/geometry/core/assert.hpp> 23 #include <boost/geometry/core/config.hpp> 24 #include <boost/geometry/core/exception.hpp> 25 26 #include <boost/geometry/algorithms/convert.hpp> 27 #include <boost/geometry/algorithms/detail/overlay/get_distance_measure.hpp> 28 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> 29 30 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp> 31 32 // Silence warning C4127: conditional expression is constant 33 #if defined(_MSC_VER) 34 #pragma warning(push) 35 #pragma warning(disable : 4127) 36 #endif 37 38 39 namespace boost { namespace geometry 40 { 41 42 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW) 43 class turn_info_exception : public geometry::exception 44 { 45 std::string message; 46 public: 47 48 // NOTE: "char" will be replaced by enum in future version turn_info_exception(char const method)49 inline turn_info_exception(char const method) 50 { 51 message = "Boost.Geometry Turn exception: "; 52 message += method; 53 } 54 ~turn_info_exception()55 virtual ~turn_info_exception() throw() 56 {} 57 what() const58 virtual char const* what() const throw() 59 { 60 return message.c_str(); 61 } 62 }; 63 #endif 64 65 #ifndef DOXYGEN_NO_DETAIL 66 namespace detail { namespace overlay 67 { 68 69 struct base_turn_handler 70 { 71 // Returns true if both sides are opposite oppositeboost::geometry::detail::overlay::base_turn_handler72 static inline bool opposite(int side1, int side2) 73 { 74 // We cannot state side1 == -side2, because 0 == -0 75 // So either side1*side2==-1 or side1==-side2 && side1 != 0 76 return side1 * side2 == -1; 77 } 78 79 // Same side of a segment (not being 0) sameboost::geometry::detail::overlay::base_turn_handler80 static inline bool same(int side1, int side2) 81 { 82 return side1 * side2 == 1; 83 } 84 85 // Both get the same operation 86 template <typename TurnInfo> bothboost::geometry::detail::overlay::base_turn_handler87 static inline void both(TurnInfo& ti, operation_type const op) 88 { 89 ti.operations[0].operation = op; 90 ti.operations[1].operation = op; 91 } 92 93 // If condition, first union/second intersection, else vice versa 94 template <typename TurnInfo> ui_else_iuboost::geometry::detail::overlay::base_turn_handler95 static inline void ui_else_iu(bool condition, TurnInfo& ti) 96 { 97 ti.operations[0].operation = condition 98 ? operation_union : operation_intersection; 99 ti.operations[1].operation = condition 100 ? operation_intersection : operation_union; 101 } 102 103 // If condition, both union, else both intersection 104 template <typename TurnInfo> uu_else_iiboost::geometry::detail::overlay::base_turn_handler105 static inline void uu_else_ii(bool condition, TurnInfo& ti) 106 { 107 both(ti, condition ? operation_union : operation_intersection); 108 } 109 110 111 #if ! defined(BOOST_GEOMETRY_USE_RESCALING) 112 template 113 < 114 typename UniqueSubRange1, 115 typename UniqueSubRange2 116 > side_with_distance_measureboost::geometry::detail::overlay::base_turn_handler117 static inline int side_with_distance_measure(UniqueSubRange1 const& range_p, 118 UniqueSubRange2 const& range_q, 119 int range_index, int point_index) 120 { 121 if (range_index >= 1 && range_p.is_last_segment()) 122 { 123 return 0; 124 } 125 if (point_index >= 2 && range_q.is_last_segment()) 126 { 127 return 0; 128 } 129 130 auto const dm = get_distance_measure(range_p.at(range_index), range_p.at(range_index + 1), range_q.at(point_index)); 131 static decltype(dm.measure) const zero = 0; 132 return dm.measure == zero ? 0 : dm.measure > zero ? 1 : -1; 133 } 134 135 template 136 < 137 typename UniqueSubRange1, 138 typename UniqueSubRange2 139 > verified_sideboost::geometry::detail::overlay::base_turn_handler140 static inline int verified_side(int side, 141 UniqueSubRange1 const& range_p, 142 UniqueSubRange2 const& range_q, 143 int range_index, 144 int point_index) 145 { 146 return side == 0 ? side_with_distance_measure(range_p, range_q, range_index, point_index) : side; 147 } 148 #else 149 template <typename T1, typename T2> verified_sideboost::geometry::detail::overlay::base_turn_handler150 static inline int verified_side(int side, T1 const& , T2 const& , int , int) 151 { 152 return side; 153 } 154 #endif 155 156 157 template <typename TurnInfo, typename IntersectionInfo> assign_pointboost::geometry::detail::overlay::base_turn_handler158 static inline void assign_point(TurnInfo& ti, 159 method_type method, 160 IntersectionInfo const& info, unsigned int index) 161 { 162 ti.method = method; 163 164 BOOST_GEOMETRY_ASSERT(index < info.count); 165 166 geometry::convert(info.intersections[index], ti.point); 167 ti.operations[0].fraction = info.fractions[index].robust_ra; 168 ti.operations[1].fraction = info.fractions[index].robust_rb; 169 } 170 171 template <typename TurnInfo, typename IntersectionInfo, typename DirInfo> assign_point_and_correctboost::geometry::detail::overlay::base_turn_handler172 static inline void assign_point_and_correct(TurnInfo& ti, 173 method_type method, 174 IntersectionInfo const& info, DirInfo const& dir_info) 175 { 176 ti.method = method; 177 178 // For touch/touch interior always take the intersection point 0 179 // (usually there is only one - but if collinear is handled as touch, both could be taken). 180 static int const index = 0; 181 182 geometry::convert(info.intersections[index], ti.point); 183 184 for (int i = 0; i < 2; i++) 185 { 186 if (dir_info.arrival[i] == 1) 187 { 188 // The segment arrives at the intersection point, its fraction should be 1 189 // (due to precision it might be nearly so, but not completely, in rare cases) 190 ti.operations[i].fraction = {1, 1}; 191 } 192 else if (dir_info.arrival[i] == -1) 193 { 194 // The segment leaves from the intersection point, likewise its fraction should be 0 195 ti.operations[i].fraction = {0, 1}; 196 } 197 else 198 { 199 ti.operations[i].fraction = i == 0 ? info.fractions[index].robust_ra 200 : info.fractions[index].robust_rb; 201 } 202 } 203 } 204 205 template <typename IntersectionInfo> non_opposite_to_indexboost::geometry::detail::overlay::base_turn_handler206 static inline unsigned int non_opposite_to_index(IntersectionInfo const& info) 207 { 208 return info.fractions[0].robust_rb < info.fractions[1].robust_rb 209 ? 1 : 0; 210 } 211 212 template <typename Point1, typename Point2> 213 static inline typename geometry::coordinate_type<Point1>::type distance_measureboost::geometry::detail::overlay::base_turn_handler214 distance_measure(Point1 const& a, Point2 const& b) 215 { 216 // TODO: use comparable distance for point-point instead - but that 217 // causes currently cycling include problems 218 auto const dx = get<0>(a) - get<0>(b); 219 auto const dy = get<1>(a) - get<1>(b); 220 return dx * dx + dy * dy; 221 } 222 223 template 224 < 225 std::size_t IndexP, 226 std::size_t IndexQ, 227 typename UniqueSubRange1, 228 typename UniqueSubRange2, 229 typename UmbrellaStrategy, 230 typename TurnInfo 231 > both_collinearboost::geometry::detail::overlay::base_turn_handler232 static inline void both_collinear( 233 UniqueSubRange1 const& range_p, 234 UniqueSubRange2 const& range_q, 235 UmbrellaStrategy const&, 236 std::size_t index_p, std::size_t index_q, 237 TurnInfo& ti) 238 { 239 boost::ignore_unused(range_p, range_q); 240 BOOST_GEOMETRY_ASSERT(IndexP + IndexQ == 1); 241 BOOST_GEOMETRY_ASSERT(index_p > 0 && index_p <= 2); 242 BOOST_GEOMETRY_ASSERT(index_q > 0 && index_q <= 2); 243 244 #if ! defined(BOOST_GEOMETRY_USE_RESCALING) 245 bool const p_in_range = index_p < range_p.size(); 246 bool const q_in_range = index_q < range_q.size(); 247 ti.operations[IndexP].remaining_distance 248 = p_in_range 249 ? distance_measure(ti.point, range_p.at(index_p)) 250 : 0; 251 ti.operations[IndexQ].remaining_distance 252 = q_in_range 253 ? distance_measure(ti.point, range_q.at(index_q)) 254 : 0; 255 256 if (p_in_range && q_in_range) 257 { 258 // pk/q2 is considered as collinear, but there might be 259 // a tiny measurable difference. If so, use that. 260 // Calculate pk // qj-qk 261 bool const p_closer 262 = ti.operations[IndexP].remaining_distance 263 < ti.operations[IndexQ].remaining_distance; 264 auto const dm 265 = p_closer 266 ? get_distance_measure(range_q.at(index_q - 1), 267 range_q.at(index_q), range_p.at(index_p)) 268 : get_distance_measure(range_p.at(index_p - 1), 269 range_p.at(index_p), range_q.at(index_q)); 270 271 if (! dm.is_zero()) 272 { 273 // Not truely collinear, distinguish for union/intersection 274 // If p goes left (positive), take that for a union 275 bool const p_left 276 = p_closer ? dm.is_positive() : dm.is_negative(); 277 278 ti.operations[IndexP].operation = p_left 279 ? operation_union : operation_intersection; 280 ti.operations[IndexQ].operation = p_left 281 ? operation_intersection : operation_union; 282 return; 283 } 284 } 285 #endif 286 287 both(ti, operation_continue); 288 } 289 290 }; 291 292 293 template 294 < 295 typename TurnInfo 296 > 297 struct touch_interior : public base_turn_handler 298 { 299 300 template 301 < 302 typename IntersectionInfo, 303 typename UniqueSubRange 304 > handle_as_touchboost::geometry::detail::overlay::touch_interior305 static bool handle_as_touch(IntersectionInfo const& info, 306 UniqueSubRange const& non_touching_range) 307 { 308 #if defined(BOOST_GEOMETRY_USE_RESCALING) 309 return false; 310 #endif 311 // 312 // 313 // ^ Q(i) ^ P(i) 314 // \ / 315 // \ / 316 // \ / 317 // \ / 318 // \ / 319 // \ / 320 // \ / 321 // \ / 322 // \ / 323 // \ / it is about buffer_rt_r 324 // P(k) v/ they touch here "in the middle", but at the intersection... 325 // <---------------->v there is no follow up IP 326 // / 327 // / 328 // / 329 // / 330 // / 331 // / 332 // v Q(k) 333 // 334 335 // Measure where the IP is located. If it is really close to the end, 336 // then there is no space for the next IP (on P(1)/Q(2). A "from" 337 // intersection will be generated, but those are never handled. 338 // Therefore handle it as a normal touch (two segments arrive at the 339 // intersection point). It currently checks for zero, but even a 340 // distance a little bit larger would do. 341 auto const dm = distance_measure(info.intersections[0], non_touching_range.at(1)); 342 decltype(dm) const zero = 0; 343 bool const result = math::equals(dm, zero); 344 return result; 345 } 346 347 // Index: 0, P is the interior, Q is touching and vice versa 348 template 349 < 350 unsigned int Index, 351 typename UniqueSubRange1, 352 typename UniqueSubRange2, 353 typename IntersectionInfo, 354 typename DirInfo, 355 typename SidePolicy, 356 typename UmbrellaStrategy 357 > applyboost::geometry::detail::overlay::touch_interior358 static inline void apply(UniqueSubRange1 const& range_p, 359 UniqueSubRange2 const& range_q, 360 TurnInfo& ti, 361 IntersectionInfo const& intersection_info, 362 DirInfo const& dir_info, 363 SidePolicy const& side, 364 UmbrellaStrategy const& umbrella_strategy) 365 { 366 assign_point_and_correct(ti, method_touch_interior, intersection_info, dir_info); 367 368 // Both segments of q touch segment p somewhere in its interior 369 // 1) We know: if q comes from LEFT or RIGHT 370 // (i.e. dir_info.sides.get<Index,0>() == 1 or -1) 371 // 2) Important is: if q_k goes to LEFT, RIGHT, COLLINEAR 372 // and, if LEFT/COLL, if it is lying LEFT or RIGHT w.r.t. q_i 373 374 BOOST_STATIC_ASSERT(Index <= 1); 375 static unsigned int const index_p = Index; 376 static unsigned int const index_q = 1 - Index; 377 378 bool const has_pk = ! range_p.is_last_segment(); 379 bool const has_qk = ! range_q.is_last_segment(); 380 int const side_qi_p = dir_info.sides.template get<index_q, 0>(); 381 int const side_qk_p = has_qk ? side.qk_wrt_p1() : 0; 382 383 if (side_qi_p == -side_qk_p) 384 { 385 // Q crosses P from left->right or from right->left (test "ML1") 386 // Union: folow P (left->right) or Q (right->left) 387 // Intersection: other turn 388 unsigned int index = side_qk_p == -1 ? index_p : index_q; 389 ti.operations[index].operation = operation_union; 390 ti.operations[1 - index].operation = operation_intersection; 391 return; 392 } 393 394 int const side_qk_q = has_qk ? side.qk_wrt_q1() : 0; 395 396 // Only necessary if rescaling is turned off: 397 int const side_pj_q2 = has_qk ? side.pj_wrt_q2() : 0; 398 399 if (side_qi_p == -1 && side_qk_p == -1 && side_qk_q == 1) 400 { 401 // Q turns left on the right side of P (test "MR3") 402 // Both directions for "intersection" 403 both(ti, operation_intersection); 404 ti.touch_only = true; 405 } 406 else if (side_qi_p == 1 && side_qk_p == 1 && side_qk_q == -1) 407 { 408 if (has_qk && side_pj_q2 == -1) 409 { 410 // Q turns right on the left side of P (test "ML3") 411 // Union: take both operations 412 // Intersection: skip 413 both(ti, operation_union); 414 } 415 else 416 { 417 // q2 is collinear with p1, so it does not turn back. This 418 // can happen in floating point precision. In this case, 419 // block one of the operations to avoid taking that path. 420 ti.operations[index_p].operation = operation_union; 421 ti.operations[index_q].operation = operation_blocked; 422 } 423 ti.touch_only = true; 424 } 425 else if (side_qi_p == side_qk_p && side_qi_p == side_qk_q) 426 { 427 // Q turns left on the left side of P (test "ML2") 428 // or Q turns right on the right side of P (test "MR2") 429 // Union: take left turn (Q if Q turns left, P if Q turns right) 430 // Intersection: other turn 431 unsigned int index = side_qk_q == 1 ? index_q : index_p; 432 if (has_qk && side_pj_q2 == 0) 433 { 434 // Even though sides xk w.r.t. 1 are distinct, pj is collinear 435 // with q. Therefore swap the path 436 index = 1 - index; 437 } 438 439 if (has_pk && has_qk && opposite(side_pj_q2, side_qi_p)) 440 { 441 // Without rescaling, floating point requires extra measures 442 int const side_qj_p1 = side.qj_wrt_p1(); 443 int const side_qj_p2 = side.qj_wrt_p2(); 444 445 if (same(side_qj_p1, side_qj_p2)) 446 { 447 int const side_pj_q1 = side.pj_wrt_q1(); 448 if (opposite(side_pj_q1, side_pj_q2)) 449 { 450 index = 1 - index; 451 } 452 } 453 } 454 455 ti.operations[index].operation = operation_union; 456 ti.operations[1 - index].operation = operation_intersection; 457 ti.touch_only = true; 458 } 459 else if (side_qk_p == 0) 460 { 461 // Q intersects on interior of P and continues collinearly 462 if (side_qk_q == side_qi_p) 463 { 464 both_collinear<index_p, index_q>(range_p, range_q, umbrella_strategy, 1, 2, ti); 465 } 466 else 467 { 468 // Opposite direction, which is never travelled. 469 // If Q turns left, P continues for intersection 470 // If Q turns right, P continues for union 471 ti.operations[index_p].operation = side_qk_q == 1 472 ? operation_intersection 473 : operation_union; 474 ti.operations[index_q].operation = operation_blocked; 475 } 476 } 477 else 478 { 479 // Should not occur! 480 ti.method = method_error; 481 } 482 } 483 }; 484 485 486 template 487 < 488 typename TurnInfo 489 > 490 struct touch : public base_turn_handler 491 { betweenboost::geometry::detail::overlay::touch492 static inline bool between(int side1, int side2, int turn) 493 { 494 return side1 == side2 && ! opposite(side1, turn); 495 } 496 497 #if ! defined(BOOST_GEOMETRY_USE_RESCALING) 498 template 499 < 500 typename UniqueSubRange1, 501 typename UniqueSubRange2 502 > handle_imperfect_touchboost::geometry::detail::overlay::touch503 static inline bool handle_imperfect_touch(UniqueSubRange1 const& range_p, 504 UniqueSubRange2 const& range_q, TurnInfo& ti) 505 { 506 // Q 507 // ^ 508 // || 509 // || 510 // |^---- 511 // >----->P 512 // * * they touch here (P/Q are (nearly) on top) 513 // 514 // Q continues from where P comes. 515 // P continues from where Q comes 516 // This is often a blocking situation, 517 // unless there are FP issues: there might be a distance 518 // between Pj and Qj, in that case handle it as a union. 519 // 520 // Exaggerated: 521 // Q 522 // ^ Q is nearly vertical 523 // \ but not completely - and still ends above P 524 // | \qj In this case it should block P and 525 // | ^------ set Q to Union 526 // >----->P qj is LEFT of P1 and pi is LEFT of Q2 527 // (the other way round is also possible) 528 529 auto const dm_qj_p1 = get_distance_measure(range_p.at(0), range_p.at(1), range_q.at(1)); 530 auto const dm_pi_q2 = get_distance_measure(range_q.at(1), range_q.at(2), range_p.at(0)); 531 532 if (dm_qj_p1.measure > 0 && dm_pi_q2.measure > 0) 533 { 534 // Even though there is a touch, Q(j) is left of P1 535 // and P(i) is still left from Q2. 536 // It can continue. 537 ti.operations[0].operation = operation_blocked; 538 // Q turns right -> union (both independent), 539 // Q turns left -> intersection 540 ti.operations[1].operation = operation_union; 541 ti.touch_only = true; 542 return true; 543 } 544 545 auto const dm_pj_q1 = get_distance_measure(range_q.at(0), range_q.at(1), range_p.at(1)); 546 auto const dm_qi_p2 = get_distance_measure(range_p.at(1), range_p.at(2), range_q.at(0)); 547 548 if (dm_pj_q1.measure > 0 && dm_qi_p2.measure > 0) 549 { 550 // Even though there is a touch, Q(j) is left of P1 551 // and P(i) is still left from Q2. 552 // It can continue. 553 ti.operations[0].operation = operation_union; 554 // Q turns right -> union (both independent), 555 // Q turns left -> intersection 556 ti.operations[1].operation = operation_blocked; 557 ti.touch_only = true; 558 return true; 559 } 560 return false; 561 } 562 #endif 563 564 template 565 < 566 typename UniqueSubRange1, 567 typename UniqueSubRange2, 568 typename IntersectionInfo, 569 typename DirInfo, 570 typename SideCalculator, 571 typename UmbrellaStrategy 572 > applyboost::geometry::detail::overlay::touch573 static inline void apply(UniqueSubRange1 const& range_p, 574 UniqueSubRange2 const& range_q, 575 TurnInfo& ti, 576 IntersectionInfo const& intersection_info, 577 DirInfo const& dir_info, 578 SideCalculator const& side, 579 UmbrellaStrategy const& umbrella_strategy) 580 { 581 assign_point_and_correct(ti, method_touch, intersection_info, dir_info); 582 583 bool const has_pk = ! range_p.is_last_segment(); 584 bool const has_qk = ! range_q.is_last_segment(); 585 586 int const side_pk_q1 = has_pk ? side.pk_wrt_q1() : 0; 587 588 int const side_qi_p1 = verified_side(dir_info.sides.template get<1, 0>(), range_p, range_q, 0, 0); 589 int const side_qk_p1 = has_qk ? verified_side(side.qk_wrt_p1(), range_p, range_q, 0, 2) : 0; 590 591 // If Qi and Qk are both at same side of Pi-Pj, 592 // or collinear (so: not opposite sides) 593 if (! opposite(side_qi_p1, side_qk_p1)) 594 { 595 int const side_pk_q2 = has_pk && has_qk ? side.pk_wrt_q2() : 0; 596 int const side_pk_p = has_pk ? side.pk_wrt_p1() : 0; 597 int const side_qk_q = has_qk ? side.qk_wrt_q1() : 0; 598 599 bool const q_turns_left = side_qk_q == 1; 600 601 bool const block_q = side_qk_p1 == 0 602 && ! same(side_qi_p1, side_qk_q) 603 ; 604 605 // If Pk at same side as Qi/Qk 606 // (the "or" is for collinear case) 607 // or Q is fully collinear && P turns not to left 608 if (side_pk_p == side_qi_p1 609 || side_pk_p == side_qk_p1 610 || (side_qi_p1 == 0 && side_qk_p1 == 0 && side_pk_p != -1)) 611 { 612 #if ! defined(BOOST_GEOMETRY_USE_RESCALING) 613 if (side_qk_p1 == 0 && side_pk_q1 == 0 614 && has_qk && has_qk 615 && handle_imperfect_touch(range_p, range_q, ti)) 616 { 617 // If q continues collinearly (opposite) with p, it should be blocked 618 // but (FP) not if there is just a tiny space in between 619 return; 620 } 621 #endif 622 // Collinear -> lines join, continue 623 // (#BRL2) 624 if (side_pk_q2 == 0 && ! block_q) 625 { 626 both_collinear<0, 1>(range_p, range_q, umbrella_strategy, 2, 2, ti); 627 return; 628 } 629 630 // Collinear opposite case -> block P 631 // (#BRL4, #BLR8) 632 if (side_pk_q1 == 0) 633 { 634 ti.operations[0].operation = operation_blocked; 635 // Q turns right -> union (both independent), 636 // Q turns left -> intersection 637 ti.operations[1].operation = block_q ? operation_blocked 638 : q_turns_left ? operation_intersection 639 : operation_union; 640 return; 641 } 642 643 // Pk between Qi and Qk 644 // (#BRL3, #BRL7) 645 if (between(side_pk_q1, side_pk_q2, side_qk_q)) 646 { 647 ui_else_iu(q_turns_left, ti); 648 if (block_q) 649 { 650 ti.operations[1].operation = operation_blocked; 651 } 652 return; 653 } 654 655 // Pk between Qk and P, so left of Qk (if Q turns right) and vv 656 // (#BRL1) 657 if (side_pk_q2 == -side_qk_q) 658 { 659 ui_else_iu(! q_turns_left, ti); 660 ti.touch_only = true; 661 return; 662 } 663 664 // 665 // (#BRL5, #BRL9) 666 if (side_pk_q1 == -side_qk_q) 667 { 668 uu_else_ii(! q_turns_left, ti); 669 if (block_q) 670 { 671 ti.operations[1].operation = operation_blocked; 672 } 673 else 674 { 675 ti.touch_only = true; 676 } 677 return; 678 } 679 } 680 else 681 { 682 // Pk at other side than Qi/Pk 683 ti.operations[0].operation = q_turns_left 684 ? operation_intersection 685 : operation_union; 686 ti.operations[1].operation = block_q 687 ? operation_blocked 688 : side_qi_p1 == 1 || side_qk_p1 == 1 689 ? operation_union 690 : operation_intersection; 691 if (! block_q) 692 { 693 ti.touch_only = true; 694 } 695 696 return; 697 } 698 } 699 else 700 { 701 // The qi/qk are opposite to each other, w.r.t. p1 702 // From left to right or from right to left 703 int const side_pk_p = has_pk ? verified_side(side.pk_wrt_p1(), range_p, range_p, 0, 2) : 0; 704 bool const right_to_left = side_qk_p1 == 1; 705 706 // If p turns into direction of qi (1,2) 707 if (side_pk_p == side_qi_p1) 708 { 709 // Collinear opposite case -> block P 710 if (side_pk_q1 == 0) 711 { 712 ti.operations[0].operation = operation_blocked; 713 ti.operations[1].operation = right_to_left 714 ? operation_union : operation_intersection; 715 return; 716 } 717 718 if (side_pk_q1 == side_qk_p1) 719 { 720 uu_else_ii(right_to_left, ti); 721 ti.touch_only = true; 722 return; 723 } 724 } 725 726 // If p turns into direction of qk (4,5) 727 if (side_pk_p == side_qk_p1) 728 { 729 int const side_pk_q2 = has_pk ? side.pk_wrt_q2() : 0; 730 731 // Collinear case -> lines join, continue 732 if (side_pk_q2 == 0) 733 { 734 both(ti, operation_continue); 735 return; 736 } 737 if (side_pk_q2 == side_qk_p1) 738 { 739 ui_else_iu(right_to_left, ti); 740 ti.touch_only = true; 741 return; 742 } 743 } 744 // otherwise (3) 745 ui_else_iu(! right_to_left, ti); 746 return; 747 } 748 } 749 }; 750 751 752 template 753 < 754 typename TurnInfo 755 > 756 struct equal : public base_turn_handler 757 { 758 template 759 < 760 typename UniqueSubRange1, 761 typename UniqueSubRange2, 762 typename IntersectionInfo, 763 typename DirInfo, 764 typename SideCalculator, 765 typename UmbrellaStrategy 766 > applyboost::geometry::detail::overlay::equal767 static inline void apply(UniqueSubRange1 const& range_p, 768 UniqueSubRange2 const& range_q, 769 TurnInfo& ti, 770 IntersectionInfo const& info, 771 DirInfo const& , 772 SideCalculator const& side, 773 UmbrellaStrategy const& umbrella_strategy) 774 { 775 // Copy the intersection point in TO direction 776 assign_point(ti, method_equal, info, non_opposite_to_index(info)); 777 778 bool const has_pk = ! range_p.is_last_segment(); 779 bool const has_qk = ! range_q.is_last_segment(); 780 781 int const side_pk_q2 = has_pk && has_qk ? side.pk_wrt_q2() : 0; 782 int const side_pk_p = has_pk ? side.pk_wrt_p1() : 0; 783 int const side_qk_p = has_qk ? side.qk_wrt_p1() : 0; 784 785 #if ! defined(BOOST_GEOMETRY_USE_RESCALING) 786 787 if (has_pk && has_qk && side_pk_p == side_qk_p) 788 { 789 // They turn to the same side, or continue both collinearly 790 // Without rescaling, to check for union/intersection, 791 // try to check side values (without any thresholds) 792 auto const dm_pk_q2 793 = get_distance_measure(range_q.at(1), range_q.at(2), range_p.at(2)); 794 auto const dm_qk_p2 795 = get_distance_measure(range_p.at(1), range_p.at(2), range_q.at(2)); 796 797 if (dm_qk_p2.measure != dm_pk_q2.measure) 798 { 799 // A (possibly very small) difference is detected, which 800 // can be used to distinguish between union/intersection 801 ui_else_iu(dm_qk_p2.measure < dm_pk_q2.measure, ti); 802 return; 803 } 804 } 805 #endif 806 807 // If pk is collinear with qj-qk, they continue collinearly. 808 // This can be on either side of p1 (== q1), or collinear 809 // The second condition checks if they do not continue 810 // oppositely 811 if (side_pk_q2 == 0 && side_pk_p == side_qk_p) 812 { 813 both_collinear<0, 1>(range_p, range_q, umbrella_strategy, 2, 2, ti); 814 return; 815 } 816 817 818 // If they turn to same side (not opposite sides) 819 if (! opposite(side_pk_p, side_qk_p)) 820 { 821 // If pk is left of q2 or collinear: p: union, q: intersection 822 ui_else_iu(side_pk_q2 != -1, ti); 823 } 824 else 825 { 826 // They turn opposite sides. If p turns left (or collinear), 827 // p: union, q: intersection 828 ui_else_iu(side_pk_p != -1, ti); 829 } 830 } 831 }; 832 833 template 834 < 835 typename TurnInfo 836 > 837 struct start : public base_turn_handler 838 { 839 template 840 < 841 typename UniqueSubRange1, 842 typename UniqueSubRange2, 843 typename IntersectionInfo, 844 typename DirInfo, 845 typename SideCalculator, 846 typename UmbrellaStrategy 847 > applyboost::geometry::detail::overlay::start848 static inline bool apply(UniqueSubRange1 const& /*range_p*/, 849 UniqueSubRange2 const& /*range_q*/, 850 TurnInfo& ti, 851 IntersectionInfo const& info, 852 DirInfo const& dir_info, 853 SideCalculator const& side, 854 UmbrellaStrategy const& ) 855 { 856 #if defined(BOOST_GEOMETRY_USE_RESCALING) 857 // With rescaling, start turns are not needed. 858 return false; 859 #endif 860 861 // Start turns have either how_a = -1, or how_b = -1 (either p leaves or q leaves) 862 BOOST_GEOMETRY_ASSERT(dir_info.how_a != dir_info.how_b); 863 BOOST_GEOMETRY_ASSERT(dir_info.how_a == -1 || dir_info.how_b == -1); 864 BOOST_GEOMETRY_ASSERT(dir_info.how_a == 0 || dir_info.how_b == 0); 865 866 if (dir_info.how_b == -1) 867 { 868 // p ---------------> 869 // | 870 // | q q leaves 871 // v 872 // 873 874 int const side_qj_p1 = side.qj_wrt_p1(); 875 ui_else_iu(side_qj_p1 == -1, ti); 876 } 877 else if (dir_info.how_a == -1) 878 { 879 // p leaves 880 int const side_pj_q1 = side.pj_wrt_q1(); 881 ui_else_iu(side_pj_q1 == 1, ti); 882 } 883 884 // Copy intersection point 885 assign_point_and_correct(ti, method_start, info, dir_info); 886 return true; 887 } 888 889 }; 890 891 892 template 893 < 894 typename TurnInfo, 895 typename AssignPolicy 896 > 897 struct equal_opposite : public base_turn_handler 898 { 899 template 900 < 901 typename UniqueSubRange1, 902 typename UniqueSubRange2, 903 typename OutputIterator, 904 typename IntersectionInfo 905 > applyboost::geometry::detail::overlay::equal_opposite906 static inline void apply( 907 UniqueSubRange1 const& /*range_p*/, 908 UniqueSubRange2 const& /*range_q*/, 909 /* by value: */ TurnInfo tp, 910 OutputIterator& out, 911 IntersectionInfo const& intersection_info) 912 { 913 // For equal-opposite segments, normally don't do anything. 914 if (AssignPolicy::include_opposite) 915 { 916 tp.method = method_equal; 917 for (unsigned int i = 0; i < 2; i++) 918 { 919 tp.operations[i].operation = operation_opposite; 920 } 921 for (unsigned int i = 0; i < intersection_info.i_info().count; i++) 922 { 923 assign_point(tp, method_none, intersection_info.i_info(), i); 924 *out++ = tp; 925 } 926 } 927 } 928 }; 929 930 template 931 < 932 typename TurnInfo 933 > 934 struct collinear : public base_turn_handler 935 { 936 template 937 < 938 typename IntersectionInfo, 939 typename UniqueSubRange1, 940 typename UniqueSubRange2, 941 typename DirInfo 942 > handle_as_equalboost::geometry::detail::overlay::collinear943 static bool handle_as_equal(IntersectionInfo const& info, 944 UniqueSubRange1 const& range_p, 945 UniqueSubRange2 const& range_q, 946 DirInfo const& dir_info) 947 { 948 #if defined(BOOST_GEOMETRY_USE_RESCALING) 949 return false; 950 #endif 951 int const arrival_p = dir_info.arrival[0]; 952 int const arrival_q = dir_info.arrival[1]; 953 if (arrival_p * arrival_q != -1 || info.count != 2) 954 { 955 // Code below assumes that either p or q arrives in the other segment 956 return false; 957 } 958 959 auto const dm = distance_measure(info.intersections[1], 960 arrival_p == 1 ? range_q.at(1) : range_p.at(1)); 961 decltype(dm) const zero = 0; 962 return math::equals(dm, zero); 963 } 964 965 /* 966 Either P arrives within Q (arrival_p == -1) or Q arrives within P. 967 968 Typical situation: 969 ^q2 970 / 971 ^q1 972 / ____ ip[1] 973 //|p1 } this section of p/q is colllinear 974 q0// | } ____ ip[0] 975 / | 976 / v 977 p0 p2 978 979 P arrives (at p1) in segment Q (between q0 and q1). 980 Therefore arrival_p == 1 981 P (p2) goes to the right (-1). Follow P for intersection, or follow Q for union. 982 Therefore if (arrival_p==1) and side_p==-1, result = iu 983 984 Complete table: 985 986 arrival P pk//p1 qk//q1 product case result 987 1 1 1 CLL1 ui 988 -1 1 -1 CLL2 iu 989 1 1 1 CLR1 ui 990 -1 -1 1 CLR2 ui 991 992 1 -1 -1 CRL1 iu 993 -1 1 -1 CRL2 iu 994 1 -1 -1 CRR1 iu 995 -1 -1 1 CRR2 ui 996 997 1 0 0 CC1 cc 998 -1 0 0 CC2 cc 999 1000 Resulting in the rule: 1001 The arrival-info multiplied by the relevant side delivers the result. 1002 product = arrival * (pk//p1 or qk//q1) 1003 1004 Stated otherwise: 1005 - if P arrives: look at turn P 1006 - if Q arrives: look at turn Q 1007 - if P arrives and P turns left: union for P 1008 - if P arrives and P turns right: intersection for P 1009 - if Q arrives and Q turns left: union for Q (=intersection for P) 1010 - if Q arrives and Q turns right: intersection for Q (=union for P) 1011 */ 1012 template 1013 < 1014 typename UniqueSubRange1, 1015 typename UniqueSubRange2, 1016 typename IntersectionInfo, 1017 typename DirInfo, 1018 typename SidePolicy 1019 > applyboost::geometry::detail::overlay::collinear1020 static inline void apply( 1021 UniqueSubRange1 const& range_p, 1022 UniqueSubRange2 const& range_q, 1023 TurnInfo& ti, 1024 IntersectionInfo const& info, 1025 DirInfo const& dir_info, 1026 SidePolicy const& side) 1027 { 1028 // Copy the intersection point in TO direction 1029 assign_point(ti, method_collinear, info, non_opposite_to_index(info)); 1030 1031 int const arrival_p = dir_info.arrival[0]; 1032 // Should not be 0, this is checked before 1033 BOOST_GEOMETRY_ASSERT(arrival_p != 0); 1034 1035 bool const has_pk = ! range_p.is_last_segment(); 1036 bool const has_qk = ! range_q.is_last_segment(); 1037 int const side_p = has_pk ? side.pk_wrt_p1() : 0; 1038 int const side_q = has_qk ? side.qk_wrt_q1() : 0; 1039 1040 // If p arrives, use p, else use q 1041 int const side_p_or_q = arrival_p == 1 1042 ? side_p 1043 : side_q 1044 ; 1045 1046 // Calculate product according to comments above. 1047 int const product = arrival_p * side_p_or_q; 1048 1049 if (product == 0) 1050 { 1051 both(ti, operation_continue); 1052 } 1053 else 1054 { 1055 ui_else_iu(product == 1, ti); 1056 } 1057 1058 // Calculate remaining distance. If it continues collinearly it is 1059 // measured until the end of the next segment 1060 ti.operations[0].remaining_distance 1061 = side_p == 0 && has_pk 1062 ? distance_measure(ti.point, range_p.at(2)) 1063 : distance_measure(ti.point, range_p.at(1)); 1064 ti.operations[1].remaining_distance 1065 = side_q == 0 && has_qk 1066 ? distance_measure(ti.point, range_q.at(2)) 1067 : distance_measure(ti.point, range_q.at(1)); 1068 } 1069 }; 1070 1071 template 1072 < 1073 typename TurnInfo, 1074 typename AssignPolicy 1075 > 1076 struct collinear_opposite : public base_turn_handler 1077 { 1078 private : 1079 /* 1080 arrival P arrival Q pk//p1 qk//q1 case result2 result 1081 -------------------------------------------------------------- 1082 1 1 1 -1 CLO1 ix xu 1083 1 1 1 0 CLO2 ix (xx) 1084 1 1 1 1 CLO3 ix xi 1085 1086 1 1 0 -1 CCO1 (xx) xu 1087 1 1 0 0 CCO2 (xx) (xx) 1088 1 1 0 1 CCO3 (xx) xi 1089 1090 1 1 -1 -1 CRO1 ux xu 1091 1 1 -1 0 CRO2 ux (xx) 1092 1 1 -1 1 CRO3 ux xi 1093 1094 -1 1 -1 CXO1 xu 1095 -1 1 0 CXO2 (xx) 1096 -1 1 1 CXO3 xi 1097 1098 1 -1 1 CXO1 ix 1099 1 -1 0 CXO2 (xx) 1100 1 -1 -1 CXO3 ux 1101 */ 1102 1103 template <unsigned int Index, typename IntersectionInfo> set_tpboost::geometry::detail::overlay::collinear_opposite1104 static inline bool set_tp(int side_rk_r, TurnInfo& tp, 1105 IntersectionInfo const& intersection_info) 1106 { 1107 BOOST_STATIC_ASSERT(Index <= 1); 1108 1109 operation_type blocked = operation_blocked; 1110 switch(side_rk_r) 1111 { 1112 case 1 : 1113 // Turning left on opposite collinear: intersection 1114 tp.operations[Index].operation = operation_intersection; 1115 break; 1116 case -1 : 1117 // Turning right on opposite collinear: union 1118 tp.operations[Index].operation = operation_union; 1119 break; 1120 case 0 : 1121 // No turn on opposite collinear: block, do not traverse 1122 // But this "xx" is usually ignored, it is useless to include 1123 // two operations blocked, so the whole point does not need 1124 // to be generated. 1125 // So return false to indicate nothing is to be done. 1126 if (AssignPolicy::include_opposite) 1127 { 1128 tp.operations[Index].operation = operation_opposite; 1129 blocked = operation_opposite; 1130 } 1131 else 1132 { 1133 return false; 1134 } 1135 break; 1136 } 1137 1138 // The other direction is always blocked when collinear opposite 1139 tp.operations[1 - Index].operation = blocked; 1140 1141 // If P arrives within Q, set info on P (which is done above, index=0), 1142 // this turn-info belongs to the second intersection point, index=1 1143 // (see e.g. figure CLO1) 1144 assign_point(tp, method_collinear, intersection_info, 1 - Index); 1145 return true; 1146 } 1147 1148 public: empty_transformerboost::geometry::detail::overlay::collinear_opposite1149 static inline void empty_transformer(TurnInfo &) {} 1150 1151 template 1152 < 1153 typename UniqueSubRange1, 1154 typename UniqueSubRange2, 1155 typename OutputIterator, 1156 typename IntersectionInfo, 1157 typename SidePolicy 1158 > applyboost::geometry::detail::overlay::collinear_opposite1159 static inline void apply( 1160 UniqueSubRange1 const& range_p, 1161 UniqueSubRange2 const& range_q, 1162 1163 // Opposite collinear can deliver 2 intersection points, 1164 TurnInfo const& tp_model, 1165 OutputIterator& out, 1166 1167 IntersectionInfo const& intersection_info, 1168 SidePolicy const& side) 1169 { 1170 apply(range_p, range_q, 1171 tp_model, out, intersection_info, side, empty_transformer); 1172 } 1173 1174 template 1175 < 1176 typename UniqueSubRange1, 1177 typename UniqueSubRange2, 1178 typename OutputIterator, 1179 typename IntersectionInfo, 1180 typename SidePolicy, 1181 typename TurnTransformer 1182 > applyboost::geometry::detail::overlay::collinear_opposite1183 static inline void apply( 1184 UniqueSubRange1 const& range_p, 1185 UniqueSubRange2 const& range_q, 1186 1187 // Opposite collinear can deliver 2 intersection points, 1188 TurnInfo const& tp_model, 1189 OutputIterator& out, 1190 1191 IntersectionInfo const& info, 1192 SidePolicy const& side, 1193 TurnTransformer turn_transformer) 1194 { 1195 TurnInfo tp = tp_model; 1196 1197 int const arrival_p = info.d_info().arrival[0]; 1198 int const arrival_q = info.d_info().arrival[1]; 1199 1200 // If P arrives within Q, there is a turn dependent on P 1201 if ( arrival_p == 1 1202 && ! range_p.is_last_segment() 1203 && set_tp<0>(side.pk_wrt_p1(), tp, info.i_info()) ) 1204 { 1205 turn_transformer(tp); 1206 1207 *out++ = tp; 1208 } 1209 1210 // If Q arrives within P, there is a turn dependent on Q 1211 if ( arrival_q == 1 1212 && ! range_q.is_last_segment() 1213 && set_tp<1>(side.qk_wrt_q1(), tp, info.i_info()) ) 1214 { 1215 turn_transformer(tp); 1216 1217 *out++ = tp; 1218 } 1219 1220 if (AssignPolicy::include_opposite) 1221 { 1222 // Handle cases not yet handled above 1223 if ((arrival_q == -1 && arrival_p == 0) 1224 || (arrival_p == -1 && arrival_q == 0)) 1225 { 1226 for (unsigned int i = 0; i < 2; i++) 1227 { 1228 tp.operations[i].operation = operation_opposite; 1229 } 1230 for (unsigned int i = 0; i < info.i_info().count; i++) 1231 { 1232 assign_point(tp, method_collinear, info.i_info(), i); 1233 *out++ = tp; 1234 } 1235 } 1236 } 1237 1238 } 1239 }; 1240 1241 1242 template 1243 < 1244 typename TurnInfo 1245 > 1246 struct crosses : public base_turn_handler 1247 { 1248 template <typename IntersectionInfo, typename DirInfo> applyboost::geometry::detail::overlay::crosses1249 static inline void apply(TurnInfo& ti, 1250 IntersectionInfo const& intersection_info, 1251 DirInfo const& dir_info) 1252 { 1253 assign_point(ti, method_crosses, intersection_info, 0); 1254 1255 // In all cases: 1256 // If Q crosses P from left to right 1257 // Union: take P 1258 // Intersection: take Q 1259 // Otherwise: vice versa 1260 int const side_qi_p1 = dir_info.sides.template get<1, 0>(); 1261 unsigned int const index = side_qi_p1 == 1 ? 0 : 1; 1262 ti.operations[index].operation = operation_union; 1263 ti.operations[1 - index].operation = operation_intersection; 1264 } 1265 }; 1266 1267 struct only_convert : public base_turn_handler 1268 { 1269 template<typename TurnInfo, typename IntersectionInfo> applyboost::geometry::detail::overlay::only_convert1270 static inline void apply(TurnInfo& ti, IntersectionInfo const& intersection_info) 1271 { 1272 assign_point(ti, method_none, intersection_info, 0); 1273 ti.operations[0].operation = operation_continue; 1274 ti.operations[1].operation = operation_continue; 1275 } 1276 }; 1277 1278 /*! 1279 \brief Policy doing nothing 1280 \details get_turn_info can have an optional policy include extra 1281 truns. By default it does not, and this class is that default. 1282 */ 1283 struct assign_null_policy 1284 { 1285 static bool const include_no_turn = false; 1286 static bool const include_degenerate = false; 1287 static bool const include_opposite = false; 1288 static bool const include_start_turn = false; 1289 }; 1290 1291 struct assign_policy_only_start_turns 1292 { 1293 static bool const include_no_turn = false; 1294 static bool const include_degenerate = false; 1295 static bool const include_opposite = false; 1296 static bool const include_start_turn = true; 1297 }; 1298 1299 /*! 1300 \brief Turn information: intersection point, method, and turn information 1301 \details Information necessary for traversal phase (a phase 1302 of the overlay process). The information is gathered during the 1303 get_turns (segment intersection) phase. 1304 \tparam AssignPolicy policy to assign extra info, 1305 e.g. to calculate distance from segment's first points 1306 to intersection points. 1307 It also defines if a certain class of points 1308 (degenerate, non-turns) should be included. 1309 */ 1310 template<typename AssignPolicy> 1311 struct get_turn_info 1312 { 1313 // Intersect a segment p with a segment q 1314 // Both p and q are modelled as sub_ranges to provide more points 1315 // to be able to give more information about the turn (left/right) 1316 template 1317 < 1318 typename UniqueSubRange1, 1319 typename UniqueSubRange2, 1320 typename TurnInfo, 1321 typename UmbrellaStrategy, 1322 typename RobustPolicy, 1323 typename OutputIterator 1324 > applyboost::geometry::detail::overlay::get_turn_info1325 static inline OutputIterator apply( 1326 UniqueSubRange1 const& range_p, 1327 UniqueSubRange2 const& range_q, 1328 TurnInfo const& tp_model, 1329 UmbrellaStrategy const& umbrella_strategy, 1330 RobustPolicy const& robust_policy, 1331 OutputIterator out) 1332 { 1333 typedef intersection_info 1334 < 1335 UniqueSubRange1, UniqueSubRange2, 1336 typename TurnInfo::point_type, 1337 UmbrellaStrategy, 1338 RobustPolicy 1339 > inters_info; 1340 1341 inters_info inters(range_p, range_q, umbrella_strategy, robust_policy); 1342 1343 char const method = inters.d_info().how; 1344 1345 if (method == 'd') 1346 { 1347 // Disjoint 1348 return out; 1349 } 1350 1351 // Copy, to copy possibly extended fields 1352 TurnInfo tp = tp_model; 1353 1354 bool const handle_as_touch_interior = method == 'm'; 1355 bool const handle_as_cross = method == 'i'; 1356 bool handle_as_touch = method == 't'; 1357 bool handle_as_equal = method == 'e'; 1358 bool const handle_as_collinear = method == 'c'; 1359 bool const handle_as_degenerate = method == '0'; 1360 bool const handle_as_start = method == 's'; 1361 1362 // (angle, from) 1363 bool do_only_convert = method == 'a' || method == 'f'; 1364 1365 if (handle_as_start) 1366 { 1367 // It is in some cases necessary to handle a start turn 1368 if (AssignPolicy::include_start_turn 1369 && start<TurnInfo>::apply(range_p, range_q, tp, inters.i_info(), inters.d_info(), inters.sides(), umbrella_strategy)) 1370 { 1371 *out++ = tp; 1372 } 1373 else 1374 { 1375 do_only_convert = true; 1376 } 1377 } 1378 1379 if (handle_as_touch_interior) 1380 { 1381 typedef touch_interior<TurnInfo> handler; 1382 1383 if ( inters.d_info().arrival[1] == 1 ) 1384 { 1385 // Q arrives 1386 if (handler::handle_as_touch(inters.i_info(), range_p)) 1387 { 1388 handle_as_touch = true; 1389 } 1390 else 1391 { 1392 handler::template apply<0>(range_p, range_q, tp, inters.i_info(), inters.d_info(), 1393 inters.sides(), umbrella_strategy); 1394 *out++ = tp; 1395 } 1396 } 1397 else 1398 { 1399 // P arrives, swap p/q 1400 if (handler::handle_as_touch(inters.i_info(), range_q)) 1401 { 1402 handle_as_touch = true; 1403 } 1404 else 1405 { 1406 handler::template apply<1>(range_q, range_p, tp, inters.i_info(), inters.d_info(), 1407 inters.swapped_sides(), umbrella_strategy); 1408 *out++ = tp; 1409 } 1410 } 1411 } 1412 1413 if (handle_as_cross) 1414 { 1415 crosses<TurnInfo>::apply(tp, inters.i_info(), inters.d_info()); 1416 *out++ = tp; 1417 } 1418 1419 if (handle_as_touch) 1420 { 1421 // Touch: both segments arrive at the intersection point 1422 touch<TurnInfo>::apply(range_p, range_q, tp, inters.i_info(), inters.d_info(), inters.sides(), umbrella_strategy); 1423 *out++ = tp; 1424 } 1425 1426 if (handle_as_collinear) 1427 { 1428 // Collinear 1429 if ( ! inters.d_info().opposite ) 1430 { 1431 if (inters.d_info().arrival[0] == 0 1432 || collinear<TurnInfo>::handle_as_equal(inters.i_info(), range_p, range_q, inters.d_info())) 1433 { 1434 // Both segments arrive at the second intersection point 1435 handle_as_equal = true; 1436 } 1437 else 1438 { 1439 collinear<TurnInfo>::apply(range_p, range_q, tp, 1440 inters.i_info(), inters.d_info(), inters.sides()); 1441 *out++ = tp; 1442 } 1443 } 1444 else 1445 { 1446 collinear_opposite 1447 < 1448 TurnInfo, 1449 AssignPolicy 1450 >::apply(range_p, range_q, tp, out, inters, inters.sides()); 1451 // Zero, or two, turn points are assigned to *out++ 1452 } 1453 } 1454 1455 if (handle_as_equal) 1456 { 1457 if ( ! inters.d_info().opposite ) 1458 { 1459 // Both equal 1460 // or collinear-and-ending at intersection point 1461 equal<TurnInfo>::apply(range_p, range_q, tp, 1462 inters.i_info(), inters.d_info(), inters.sides(), 1463 umbrella_strategy); 1464 if (handle_as_collinear) 1465 { 1466 // Keep info as collinear, 1467 // so override already assigned method 1468 tp.method = method_collinear; 1469 } 1470 *out++ = tp; 1471 } 1472 else 1473 { 1474 equal_opposite 1475 < 1476 TurnInfo, 1477 AssignPolicy 1478 >::apply(range_p, range_q, tp, out, inters); 1479 // Zero, or two, turn points are assigned to *out++ 1480 } 1481 } 1482 1483 if ((handle_as_degenerate && AssignPolicy::include_degenerate) 1484 || (do_only_convert && AssignPolicy::include_no_turn)) 1485 { 1486 if (inters.i_info().count > 0) 1487 { 1488 only_convert::apply(tp, inters.i_info()); 1489 *out++ = tp; 1490 } 1491 } 1492 1493 return out; 1494 } 1495 }; 1496 1497 1498 }} // namespace detail::overlay 1499 #endif //DOXYGEN_NO_DETAIL 1500 1501 1502 }} // namespace boost::geometry 1503 1504 1505 #if defined(_MSC_VER) 1506 #pragma warning(pop) 1507 #endif 1508 1509 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP 1510