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