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