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 2013, 2014, 2015, 2017. 7 // Modifications copyright (c) 2013-2017 Oracle and/or its affiliates. 8 9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 10 11 // Use, modification and distribution is subject to the Boost Software License, 12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 13 // http://www.boost.org/LICENSE_1_0.txt) 14 15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_LL_HPP 16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_LL_HPP 17 18 #include <boost/throw_exception.hpp> 19 20 #include <boost/geometry/core/assert.hpp> 21 22 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp> 23 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp> 24 25 #include <boost/geometry/util/condition.hpp> 26 27 namespace boost { namespace geometry { 28 29 #ifndef DOXYGEN_NO_DETAIL 30 namespace detail { namespace overlay { 31 32 template<typename AssignPolicy> 33 struct get_turn_info_linear_linear 34 { 35 static const bool handle_spikes = true; 36 37 template 38 < 39 typename Point1, 40 typename Point2, 41 typename TurnInfo, 42 typename IntersectionStrategy, 43 typename RobustPolicy, 44 typename OutputIterator 45 > applyboost::geometry::detail::overlay::get_turn_info_linear_linear46 static inline OutputIterator apply( 47 Point1 const& pi, Point1 const& pj, Point1 const& pk, 48 Point2 const& qi, Point2 const& qj, Point2 const& qk, 49 bool is_p_first, bool is_p_last, 50 bool is_q_first, bool is_q_last, 51 TurnInfo const& tp_model, 52 IntersectionStrategy const& strategy, 53 RobustPolicy const& robust_policy, 54 OutputIterator out) 55 { 56 typedef intersection_info 57 < 58 Point1, Point2, 59 typename TurnInfo::point_type, 60 IntersectionStrategy, 61 RobustPolicy 62 > inters_info; 63 64 inters_info inters(pi, pj, pk, qi, qj, qk, strategy, robust_policy); 65 66 char const method = inters.d_info().how; 67 68 // Copy, to copy possibly extended fields 69 TurnInfo tp = tp_model; 70 71 // Select method and apply 72 switch(method) 73 { 74 case 'a' : // collinear, "at" 75 case 'f' : // collinear, "from" 76 case 's' : // starts from the middle 77 get_turn_info_for_endpoint<AssignPolicy, true, true> 78 ::apply(pi, pj, pk, qi, qj, qk, 79 is_p_first, is_p_last, is_q_first, is_q_last, 80 tp_model, inters, method_none, out); 81 break; 82 83 case 'd' : // disjoint: never do anything 84 break; 85 86 case 'm' : 87 { 88 if ( get_turn_info_for_endpoint<AssignPolicy, false, true> 89 ::apply(pi, pj, pk, qi, qj, qk, 90 is_p_first, is_p_last, is_q_first, is_q_last, 91 tp_model, inters, method_touch_interior, out) ) 92 { 93 // do nothing 94 } 95 else 96 { 97 typedef touch_interior 98 < 99 TurnInfo 100 > policy; 101 102 // If Q (1) arrives (1) 103 if ( inters.d_info().arrival[1] == 1) 104 { 105 policy::template apply<0>(pi, pj, pk, qi, qj, qk, 106 tp, inters.i_info(), inters.d_info(), 107 inters.sides()); 108 } 109 else 110 { 111 // Swap p/q 112 side_calculator 113 < 114 typename inters_info::cs_tag, 115 typename inters_info::robust_point2_type, 116 typename inters_info::robust_point1_type, 117 typename inters_info::side_strategy_type 118 > swapped_side_calc(inters.rqi(), inters.rqj(), inters.rqk(), 119 inters.rpi(), inters.rpj(), inters.rpk(), 120 inters.get_side_strategy()); 121 122 policy::template apply<1>(qi, qj, qk, pi, pj, pk, 123 tp, inters.i_info(), inters.d_info(), 124 swapped_side_calc); 125 } 126 127 if ( tp.operations[0].operation == operation_blocked ) 128 { 129 tp.operations[1].is_collinear = true; 130 } 131 if ( tp.operations[1].operation == operation_blocked ) 132 { 133 tp.operations[0].is_collinear = true; 134 } 135 136 replace_method_and_operations_tm(tp.method, 137 tp.operations[0].operation, 138 tp.operations[1].operation); 139 140 AssignPolicy::apply(tp, pi, qi, inters); 141 *out++ = tp; 142 } 143 } 144 break; 145 case 'i' : 146 { 147 crosses<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, 148 tp, inters.i_info(), inters.d_info()); 149 150 replace_operations_i(tp.operations[0].operation, tp.operations[1].operation); 151 152 AssignPolicy::apply(tp, pi, qi, inters); 153 *out++ = tp; 154 } 155 break; 156 case 't' : 157 { 158 // Both touch (both arrive there) 159 if ( get_turn_info_for_endpoint<AssignPolicy, false, true> 160 ::apply(pi, pj, pk, qi, qj, qk, 161 is_p_first, is_p_last, is_q_first, is_q_last, 162 tp_model, inters, method_touch, out) ) 163 { 164 // do nothing 165 } 166 else 167 { 168 touch<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, 169 tp, inters.i_info(), inters.d_info(), inters.sides()); 170 171 // workarounds for touch<> not taking spikes into account starts here 172 // those was discovered empirically 173 // touch<> is not symmetrical! 174 // P spikes and Q spikes may produce various operations! 175 // TODO: this is not optimal solution - think about rewriting touch<> 176 177 if ( tp.operations[0].operation == operation_blocked 178 && tp.operations[1].operation == operation_blocked ) 179 { 180 // two touching spikes on the same line 181 if ( inters.is_spike_p() && inters.is_spike_q() ) 182 { 183 tp.operations[0].operation = operation_union; 184 tp.operations[1].operation = operation_union; 185 } 186 else 187 { 188 tp.operations[0].is_collinear = true; 189 tp.operations[1].is_collinear = true; 190 } 191 } 192 else if ( tp.operations[0].operation == operation_blocked ) 193 { 194 // a spike on P on the same line with Q1 195 if ( inters.is_spike_p() ) 196 { 197 if ( inters.sides().qk_wrt_p1() == 0 ) 198 { 199 tp.operations[0].is_collinear = true; 200 } 201 else 202 { 203 tp.operations[0].operation = operation_union; 204 } 205 } 206 else 207 { 208 tp.operations[1].is_collinear = true; 209 } 210 } 211 else if ( tp.operations[1].operation == operation_blocked ) 212 { 213 // a spike on Q on the same line with P1 214 if ( inters.is_spike_q() ) 215 { 216 if ( inters.sides().pk_wrt_q1() == 0 ) 217 { 218 tp.operations[1].is_collinear = true; 219 } 220 else 221 { 222 tp.operations[1].operation = operation_union; 223 } 224 } 225 else 226 { 227 tp.operations[0].is_collinear = true; 228 } 229 } 230 else if ( tp.operations[0].operation == operation_continue 231 && tp.operations[1].operation == operation_continue ) 232 { 233 // P spike on the same line with Q2 (opposite) 234 if ( inters.sides().pk_wrt_q1() == -inters.sides().qk_wrt_q1() 235 && inters.is_spike_p() ) 236 { 237 tp.operations[0].operation = operation_union; 238 tp.operations[1].operation = operation_union; 239 } 240 } 241 else if ( tp.operations[0].operation == operation_none 242 && tp.operations[1].operation == operation_none ) 243 { 244 // spike not handled by touch<> 245 bool const is_p = inters.is_spike_p(); 246 bool const is_q = inters.is_spike_q(); 247 248 if ( is_p || is_q ) 249 { 250 tp.operations[0].operation = operation_union; 251 tp.operations[1].operation = operation_union; 252 253 if ( inters.sides().pk_wrt_q2() == 0 ) 254 { 255 tp.operations[0].operation = operation_continue; // will be converted to i 256 if ( is_p ) 257 { 258 tp.operations[0].is_collinear = true; 259 } 260 } 261 262 if ( inters.sides().qk_wrt_p2() == 0 ) 263 { 264 tp.operations[1].operation = operation_continue; // will be converted to i 265 if ( is_q ) 266 { 267 tp.operations[1].is_collinear = true; 268 } 269 } 270 } 271 } 272 273 // workarounds for touch<> not taking spikes into account ends here 274 275 replace_method_and_operations_tm(tp.method, 276 tp.operations[0].operation, 277 tp.operations[1].operation); 278 279 // TODO: move this into the append_xxx and call for each turn? 280 AssignPolicy::apply(tp, pi, qi, inters); 281 282 if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes) 283 || ! append_opposite_spikes<append_touches>(tp, inters, 284 is_p_last, is_q_last, 285 out) ) 286 { 287 *out++ = tp; 288 } 289 } 290 } 291 break; 292 case 'e': 293 { 294 if ( get_turn_info_for_endpoint<AssignPolicy, true, true> 295 ::apply(pi, pj, pk, qi, qj, qk, 296 is_p_first, is_p_last, is_q_first, is_q_last, 297 tp_model, inters, method_equal, out) ) 298 { 299 // do nothing 300 } 301 else 302 { 303 tp.operations[0].is_collinear = true; 304 tp.operations[1].is_collinear = true; 305 306 if ( ! inters.d_info().opposite ) 307 { 308 // Both equal 309 // or collinear-and-ending at intersection point 310 equal<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, 311 tp, inters.i_info(), inters.d_info(), inters.sides()); 312 313 operation_type spike_op 314 = ( tp.operations[0].operation != operation_continue 315 || tp.operations[1].operation != operation_continue ) ? 316 operation_union : 317 operation_continue; 318 319 // transform turn 320 turn_transformer_ec transformer(method_touch); 321 transformer(tp); 322 323 // TODO: move this into the append_xxx and call for each turn? 324 AssignPolicy::apply(tp, pi, qi, inters); 325 326 // conditionally handle spikes 327 if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes) 328 || ! append_collinear_spikes(tp, inters, 329 is_p_last, is_q_last, 330 method_touch, spike_op, 331 out) ) 332 { 333 *out++ = tp; // no spikes 334 } 335 } 336 else 337 { 338 // TODO: ignore for spikes or generate something else than opposite? 339 340 equal_opposite 341 < 342 TurnInfo, 343 AssignPolicy 344 >::apply(pi, qi, tp, out, inters); 345 } 346 } 347 } 348 break; 349 case 'c' : 350 { 351 // Collinear 352 if ( get_turn_info_for_endpoint<AssignPolicy, true, true> 353 ::apply(pi, pj, pk, qi, qj, qk, 354 is_p_first, is_p_last, is_q_first, is_q_last, 355 tp_model, inters, method_collinear, out) ) 356 { 357 // do nothing 358 } 359 else 360 { 361 // NOTE: this is for spikes since those are set in the turn_transformer_ec 362 tp.operations[0].is_collinear = true; 363 tp.operations[1].is_collinear = true; 364 365 if ( ! inters.d_info().opposite ) 366 { 367 method_type method_replace = method_touch_interior; 368 operation_type spike_op = operation_continue; 369 370 if ( inters.d_info().arrival[0] == 0 ) 371 { 372 // Collinear, but similar thus handled as equal 373 equal<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, 374 tp, inters.i_info(), inters.d_info(), inters.sides()); 375 376 method_replace = method_touch; 377 if ( tp.operations[0].operation != operation_continue 378 || tp.operations[1].operation != operation_continue ) 379 { 380 spike_op = operation_union; 381 } 382 } 383 else 384 { 385 collinear<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, 386 tp, inters.i_info(), inters.d_info(), inters.sides()); 387 388 //method_replace = method_touch_interior; 389 //spike_op = operation_continue; 390 } 391 392 // transform turn 393 turn_transformer_ec transformer(method_replace); 394 transformer(tp); 395 396 // TODO: move this into the append_xxx and call for each turn? 397 AssignPolicy::apply(tp, pi, qi, inters); 398 399 // conditionally handle spikes 400 if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes) 401 || ! append_collinear_spikes(tp, inters, 402 is_p_last, is_q_last, 403 method_replace, spike_op, 404 out) ) 405 { 406 // no spikes 407 *out++ = tp; 408 } 409 } 410 else 411 { 412 // If this always 'm' ? 413 turn_transformer_ec transformer(method_touch_interior); 414 415 // conditionally handle spikes 416 if ( BOOST_GEOMETRY_CONDITION(handle_spikes) ) 417 { 418 append_opposite_spikes<append_collinear_opposite>(tp, inters, 419 is_p_last, is_q_last, 420 out); 421 } 422 423 // TODO: ignore for spikes? 424 // E.g. pass is_p_valid = !is_p_last && !is_pj_spike, 425 // the same with is_q_valid 426 427 collinear_opposite 428 < 429 TurnInfo, 430 AssignPolicy 431 >::apply(pi, pj, pk, qi, qj, qk, 432 tp, out, inters, inters.sides(), 433 transformer, !is_p_last, !is_q_last); 434 } 435 } 436 } 437 break; 438 case '0' : 439 { 440 // degenerate points 441 if ( BOOST_GEOMETRY_CONDITION(AssignPolicy::include_degenerate) ) 442 { 443 only_convert::apply(tp, inters.i_info()); 444 445 // if any, only one of those should be true 446 if ( is_p_first 447 && equals::equals_point_point(pi, tp.point) ) 448 { 449 tp.operations[0].position = position_front; 450 } 451 else if ( is_p_last 452 && equals::equals_point_point(pj, tp.point) ) 453 { 454 tp.operations[0].position = position_back; 455 } 456 else if ( is_q_first 457 && equals::equals_point_point(qi, tp.point) ) 458 { 459 tp.operations[1].position = position_front; 460 } 461 else if ( is_q_last 462 && equals::equals_point_point(qj, tp.point) ) 463 { 464 tp.operations[1].position = position_back; 465 } 466 467 AssignPolicy::apply(tp, pi, qi, inters); 468 *out++ = tp; 469 } 470 } 471 break; 472 default : 473 { 474 #if defined(BOOST_GEOMETRY_DEBUG_ROBUSTNESS) 475 std::cout << "TURN: Unknown method: " << method << std::endl; 476 #endif 477 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW) 478 BOOST_THROW_EXCEPTION(turn_info_exception(method)); 479 #endif 480 } 481 break; 482 } 483 484 return out; 485 } 486 487 template <typename TurnInfo, 488 typename IntersectionInfo, 489 typename OutIt> append_collinear_spikesboost::geometry::detail::overlay::get_turn_info_linear_linear490 static inline bool append_collinear_spikes(TurnInfo & tp, 491 IntersectionInfo const& inters_info, 492 bool is_p_last, bool is_q_last, 493 method_type method, operation_type spike_op, 494 OutIt out) 495 { 496 // method == touch || touch_interior 497 // both position == middle 498 499 bool is_p_spike = tp.operations[0].operation == spike_op 500 && ! is_p_last 501 && inters_info.is_spike_p(); 502 bool is_q_spike = tp.operations[1].operation == spike_op 503 && ! is_q_last 504 && inters_info.is_spike_q(); 505 506 if ( is_p_spike && is_q_spike ) 507 { 508 if ( tp.method == method_equal 509 && tp.operations[0].operation == operation_continue 510 && tp.operations[1].operation == operation_continue ) 511 { 512 // treat both non-opposite collinear spikes as no-spikes 513 return false; 514 } 515 516 tp.method = method; 517 tp.operations[0].operation = operation_blocked; 518 tp.operations[1].operation = operation_blocked; 519 *out++ = tp; 520 tp.operations[0].operation = operation_intersection; 521 tp.operations[1].operation = operation_intersection; 522 *out++ = tp; 523 524 return true; 525 } 526 else if ( is_p_spike ) 527 { 528 tp.method = method; 529 tp.operations[0].operation = operation_blocked; 530 tp.operations[1].operation = operation_union; 531 *out++ = tp; 532 tp.operations[0].operation = operation_intersection; 533 //tp.operations[1].operation = operation_union; 534 *out++ = tp; 535 536 return true; 537 } 538 else if ( is_q_spike ) 539 { 540 tp.method = method; 541 tp.operations[0].operation = operation_union; 542 tp.operations[1].operation = operation_blocked; 543 *out++ = tp; 544 //tp.operations[0].operation = operation_union; 545 tp.operations[1].operation = operation_intersection; 546 *out++ = tp; 547 548 return true; 549 } 550 551 return false; 552 } 553 554 enum append_version { append_touches, append_collinear_opposite }; 555 556 template <append_version Version, 557 typename TurnInfo, 558 typename IntersectionInfo, 559 typename OutIt> append_opposite_spikesboost::geometry::detail::overlay::get_turn_info_linear_linear560 static inline bool append_opposite_spikes(TurnInfo & tp, 561 IntersectionInfo const& inters, 562 bool is_p_last, bool is_q_last, 563 OutIt out) 564 { 565 static const bool is_version_touches = (Version == append_touches); 566 567 bool is_p_spike = ( is_version_touches ? 568 ( tp.operations[0].operation == operation_continue 569 || tp.operations[0].operation == operation_intersection ) : 570 true ) 571 && ! is_p_last 572 && inters.is_spike_p(); 573 bool is_q_spike = ( is_version_touches ? 574 ( tp.operations[1].operation == operation_continue 575 || tp.operations[1].operation == operation_intersection ) : 576 true ) 577 && ! is_q_last 578 && inters.is_spike_q(); 579 580 bool res = false; 581 582 if ( is_p_spike 583 && ( BOOST_GEOMETRY_CONDITION(is_version_touches) 584 || inters.d_info().arrival[0] == 1 ) ) 585 { 586 if ( BOOST_GEOMETRY_CONDITION(is_version_touches) ) 587 { 588 tp.operations[0].is_collinear = true; 589 tp.operations[1].is_collinear = false; 590 tp.method = method_touch; 591 } 592 else // Version == append_collinear_opposite 593 { 594 tp.operations[0].is_collinear = true; 595 tp.operations[1].is_collinear = false; 596 597 BOOST_GEOMETRY_ASSERT(inters.i_info().count > 1); 598 599 base_turn_handler::assign_point(tp, method_touch_interior, 600 inters.i_info(), 1); 601 602 AssignPolicy::apply(tp, inters.pi(), inters.qi(), inters); 603 } 604 605 tp.operations[0].operation = operation_blocked; 606 tp.operations[1].operation = operation_intersection; 607 *out++ = tp; 608 tp.operations[0].operation = operation_intersection; 609 //tp.operations[1].operation = operation_intersection; 610 *out++ = tp; 611 612 res = true; 613 } 614 615 if ( is_q_spike 616 && ( BOOST_GEOMETRY_CONDITION(is_version_touches) 617 || inters.d_info().arrival[1] == 1 ) ) 618 { 619 if ( BOOST_GEOMETRY_CONDITION(is_version_touches) ) 620 { 621 tp.operations[0].is_collinear = false; 622 tp.operations[1].is_collinear = true; 623 tp.method = method_touch; 624 } 625 else // Version == append_collinear_opposite 626 { 627 tp.operations[0].is_collinear = false; 628 tp.operations[1].is_collinear = true; 629 630 BOOST_GEOMETRY_ASSERT(inters.i_info().count > 0); 631 632 base_turn_handler::assign_point(tp, method_touch_interior, inters.i_info(), 0); 633 634 AssignPolicy::apply(tp, inters.pi(), inters.qi(), inters); 635 } 636 637 tp.operations[0].operation = operation_intersection; 638 tp.operations[1].operation = operation_blocked; 639 *out++ = tp; 640 //tp.operations[0].operation = operation_intersection; 641 tp.operations[1].operation = operation_intersection; 642 *out++ = tp; 643 644 res = true; 645 } 646 647 return res; 648 } 649 replace_method_and_operations_tmboost::geometry::detail::overlay::get_turn_info_linear_linear650 static inline void replace_method_and_operations_tm(method_type & method, 651 operation_type & op0, 652 operation_type & op1) 653 { 654 if ( op0 == operation_blocked && op1 == operation_blocked ) 655 { 656 // NOTE: probably only if methods are WRT IPs, not segments! 657 method = (method == method_touch ? method_equal : method_collinear); 658 op0 = operation_continue; 659 op1 = operation_continue; 660 } 661 else 662 { 663 if ( op0 == operation_continue || op0 == operation_blocked ) 664 { 665 op0 = operation_intersection; 666 } 667 else if ( op0 == operation_intersection ) 668 { 669 op0 = operation_union; 670 } 671 672 if ( op1 == operation_continue || op1 == operation_blocked ) 673 { 674 op1 = operation_intersection; 675 } 676 else if ( op1 == operation_intersection ) 677 { 678 op1 = operation_union; 679 } 680 681 // spikes in 'm' 682 if ( method == method_error ) 683 { 684 method = method_touch_interior; 685 op0 = operation_union; 686 op1 = operation_union; 687 } 688 } 689 } 690 691 class turn_transformer_ec 692 { 693 public: turn_transformer_ec(method_type method_t_or_m)694 explicit turn_transformer_ec(method_type method_t_or_m) 695 : m_method(method_t_or_m) 696 {} 697 698 template <typename Turn> operator ()(Turn & turn) const699 void operator()(Turn & turn) const 700 { 701 operation_type & op0 = turn.operations[0].operation; 702 operation_type & op1 = turn.operations[1].operation; 703 704 BOOST_GEOMETRY_ASSERT(op0 != operation_blocked || op1 != operation_blocked ); 705 706 if ( op0 == operation_blocked ) 707 { 708 op0 = operation_intersection; 709 } 710 else if ( op0 == operation_intersection ) 711 { 712 op0 = operation_union; 713 } 714 715 if ( op1 == operation_blocked ) 716 { 717 op1 = operation_intersection; 718 } 719 else if ( op1 == operation_intersection ) 720 { 721 op1 = operation_union; 722 } 723 724 if ( op0 == operation_intersection || op0 == operation_union 725 || op1 == operation_intersection || op1 == operation_union ) 726 { 727 turn.method = m_method; 728 } 729 730 // TODO: is this correct? 731 // it's equivalent to comparing to operation_blocked at the beginning of the function 732 turn.operations[0].is_collinear = op0 != operation_intersection; 733 turn.operations[1].is_collinear = op1 != operation_intersection; 734 } 735 736 private: 737 method_type m_method; 738 }; 739 replace_operations_iboost::geometry::detail::overlay::get_turn_info_linear_linear740 static inline void replace_operations_i(operation_type & op0, operation_type & op1) 741 { 742 if ( op0 == operation_intersection ) 743 { 744 op0 = operation_union; 745 } 746 747 if ( op1 == operation_intersection ) 748 { 749 op1 = operation_union; 750 } 751 } 752 }; 753 754 }} // namespace detail::overlay 755 #endif // DOXYGEN_NO_DETAIL 756 757 }} // namespace boost::geometry 758 759 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_LL_HPP 760