1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. 4 5 // This file was modified by Oracle on 2013, 2014, 2015, 2017, 2018, 2019. 6 // Modifications copyright (c) 2013-2019 Oracle and/or its affiliates. 7 8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 9 10 // Use, modification and distribution is subject to the Boost Software License, 11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 12 // http://www.boost.org/LICENSE_1_0.txt) 13 14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LINEAR_LINEAR_HPP 15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LINEAR_LINEAR_HPP 16 17 #include <algorithm> 18 19 #include <boost/core/ignore_unused.hpp> 20 #include <boost/range/size.hpp> 21 22 #include <boost/geometry/core/assert.hpp> 23 24 #include <boost/geometry/util/condition.hpp> 25 #include <boost/geometry/util/range.hpp> 26 27 #include <boost/geometry/algorithms/detail/sub_range.hpp> 28 #include <boost/geometry/algorithms/detail/single_geometry.hpp> 29 30 #include <boost/geometry/algorithms/detail/relate/point_geometry.hpp> 31 #include <boost/geometry/algorithms/detail/relate/result.hpp> 32 #include <boost/geometry/algorithms/detail/relate/turns.hpp> 33 #include <boost/geometry/algorithms/detail/relate/boundary_checker.hpp> 34 #include <boost/geometry/algorithms/detail/relate/follow_helpers.hpp> 35 36 namespace boost { namespace geometry 37 { 38 39 #ifndef DOXYGEN_NO_DETAIL 40 namespace detail { namespace relate { 41 42 template <typename Result, typename BoundaryChecker, bool TransposeResult> 43 class disjoint_linestring_pred 44 { 45 public: disjoint_linestring_pred(Result & res,BoundaryChecker const & boundary_checker)46 disjoint_linestring_pred(Result & res, 47 BoundaryChecker const& boundary_checker) 48 : m_result(res) 49 , m_boundary_checker(boundary_checker) 50 , m_flags(0) 51 { 52 if ( ! may_update<interior, exterior, '1', TransposeResult>(m_result) ) 53 { 54 m_flags |= 1; 55 } 56 if ( ! may_update<boundary, exterior, '0', TransposeResult>(m_result) ) 57 { 58 m_flags |= 2; 59 } 60 } 61 62 template <typename Linestring> operator ()(Linestring const & linestring)63 bool operator()(Linestring const& linestring) 64 { 65 if ( m_flags == 3 ) 66 { 67 return false; 68 } 69 70 std::size_t const count = boost::size(linestring); 71 72 // invalid input 73 if ( count < 2 ) 74 { 75 // ignore 76 // TODO: throw an exception? 77 return true; 78 } 79 80 // point-like linestring 81 if ( count == 2 82 && equals::equals_point_point(range::front(linestring), 83 range::back(linestring), 84 m_boundary_checker.strategy()) ) 85 { 86 update<interior, exterior, '0', TransposeResult>(m_result); 87 } 88 else 89 { 90 update<interior, exterior, '1', TransposeResult>(m_result); 91 m_flags |= 1; 92 93 // check if there is a boundary 94 if ( m_flags < 2 95 && ( m_boundary_checker.template 96 is_endpoint_boundary<boundary_front>(range::front(linestring)) 97 || m_boundary_checker.template 98 is_endpoint_boundary<boundary_back>(range::back(linestring)) ) ) 99 { 100 update<boundary, exterior, '0', TransposeResult>(m_result); 101 m_flags |= 2; 102 } 103 } 104 105 return m_flags != 3 106 && ! m_result.interrupt; 107 } 108 109 private: 110 Result & m_result; 111 BoundaryChecker const& m_boundary_checker; 112 unsigned m_flags; 113 }; 114 115 template <typename Geometry1, typename Geometry2> 116 struct linear_linear 117 { 118 static const bool interruption_enabled = true; 119 120 typedef typename geometry::point_type<Geometry1>::type point1_type; 121 typedef typename geometry::point_type<Geometry2>::type point2_type; 122 123 template <typename Result, typename Strategy> applyboost::geometry::detail::relate::linear_linear124 static inline void apply(Geometry1 const& geometry1, Geometry2 const& geometry2, 125 Result & result, 126 Strategy const& strategy) 127 { 128 typedef typename Strategy::cs_tag cs_tag; 129 130 // The result should be FFFFFFFFF 131 relate::set<exterior, exterior, result_dimension<Geometry1>::value>(result);// FFFFFFFFd, d in [1,9] or T 132 if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) 133 return; 134 135 // get and analyse turns 136 typedef typename turns::get_turns 137 < 138 Geometry1, Geometry2 139 >::template turn_info_type<Strategy>::type turn_type; 140 std::vector<turn_type> turns; 141 142 interrupt_policy_linear_linear<Result> interrupt_policy(result); 143 144 turns::get_turns 145 < 146 Geometry1, 147 Geometry2, 148 detail::get_turns::get_turn_info_type<Geometry1, Geometry2, turns::assign_policy<true> > 149 >::apply(turns, geometry1, geometry2, interrupt_policy, strategy); 150 151 if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) 152 return; 153 154 typedef boundary_checker<Geometry1, Strategy> boundary_checker1_type; 155 boundary_checker1_type boundary_checker1(geometry1, strategy); 156 disjoint_linestring_pred<Result, boundary_checker1_type, false> pred1(result, boundary_checker1); 157 for_each_disjoint_geometry_if<0, Geometry1>::apply(turns.begin(), turns.end(), geometry1, pred1); 158 if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) 159 return; 160 161 typedef boundary_checker<Geometry2, Strategy> boundary_checker2_type; 162 boundary_checker2_type boundary_checker2(geometry2, strategy); 163 disjoint_linestring_pred<Result, boundary_checker2_type, true> pred2(result, boundary_checker2); 164 for_each_disjoint_geometry_if<1, Geometry2>::apply(turns.begin(), turns.end(), geometry2, pred2); 165 if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) 166 return; 167 168 if ( turns.empty() ) 169 return; 170 171 // TODO: turns must be sorted and followed only if it's possible to go out and in on the same point 172 // for linear geometries union operation must be detected which I guess would be quite often 173 174 if ( may_update<interior, interior, '1'>(result) 175 || may_update<interior, boundary, '0'>(result) 176 || may_update<interior, exterior, '1'>(result) 177 || may_update<boundary, interior, '0'>(result) 178 || may_update<boundary, boundary, '0'>(result) 179 || may_update<boundary, exterior, '0'>(result) ) 180 { 181 typedef turns::less<0, turns::less_op_linear_linear<0>, cs_tag> less; 182 std::sort(turns.begin(), turns.end(), less()); 183 184 turns_analyser<turn_type, 0> analyser; 185 analyse_each_turn(result, analyser, 186 turns.begin(), turns.end(), 187 geometry1, geometry2, 188 boundary_checker1, boundary_checker2); 189 } 190 191 if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) 192 return; 193 194 if ( may_update<interior, interior, '1', true>(result) 195 || may_update<interior, boundary, '0', true>(result) 196 || may_update<interior, exterior, '1', true>(result) 197 || may_update<boundary, interior, '0', true>(result) 198 || may_update<boundary, boundary, '0', true>(result) 199 || may_update<boundary, exterior, '0', true>(result) ) 200 { 201 typedef turns::less<1, turns::less_op_linear_linear<1>, cs_tag> less; 202 std::sort(turns.begin(), turns.end(), less()); 203 204 turns_analyser<turn_type, 1> analyser; 205 analyse_each_turn(result, analyser, 206 turns.begin(), turns.end(), 207 geometry2, geometry1, 208 boundary_checker2, boundary_checker1); 209 } 210 } 211 212 template <typename Result> 213 class interrupt_policy_linear_linear 214 { 215 public: 216 static bool const enabled = true; 217 interrupt_policy_linear_linear(Result & result)218 explicit interrupt_policy_linear_linear(Result & result) 219 : m_result(result) 220 {} 221 222 // TODO: since we update result for some operations here, we may not do it in the analyser! 223 224 template <typename Range> apply(Range const & turns)225 inline bool apply(Range const& turns) 226 { 227 typedef typename boost::range_iterator<Range const>::type iterator; 228 229 for (iterator it = boost::begin(turns) ; it != boost::end(turns) ; ++it) 230 { 231 if ( it->operations[0].operation == overlay::operation_intersection 232 || it->operations[1].operation == overlay::operation_intersection ) 233 { 234 update<interior, interior, '1'>(m_result); 235 } 236 else if ( ( it->operations[0].operation == overlay::operation_union 237 || it->operations[0].operation == overlay::operation_blocked 238 || it->operations[1].operation == overlay::operation_union 239 || it->operations[1].operation == overlay::operation_blocked ) 240 && it->operations[0].position == overlay::position_middle 241 && it->operations[1].position == overlay::position_middle ) 242 { 243 // TODO: here we could also check the boundaries and set IB,BI,BB at this point 244 update<interior, interior, '0'>(m_result); 245 } 246 } 247 248 return m_result.interrupt; 249 } 250 251 private: 252 Result & m_result; 253 }; 254 255 // This analyser should be used like Input or SinglePass Iterator 256 template <typename TurnInfo, std::size_t OpId> 257 class turns_analyser 258 { 259 typedef typename TurnInfo::point_type turn_point_type; 260 261 static const std::size_t op_id = OpId; 262 static const std::size_t other_op_id = (OpId + 1) % 2; 263 static const bool transpose_result = OpId != 0; 264 265 public: turns_analyser()266 turns_analyser() 267 : m_previous_turn_ptr(NULL) 268 , m_previous_operation(overlay::operation_none) 269 , m_degenerated_turn_ptr(NULL) 270 , m_collinear_spike_exit(false) 271 {} 272 273 template <typename Result, 274 typename TurnIt, 275 typename Geometry, 276 typename OtherGeometry, 277 typename BoundaryChecker, 278 typename OtherBoundaryChecker> apply(Result & res,TurnIt it,Geometry const & geometry,OtherGeometry const & other_geometry,BoundaryChecker const & boundary_checker,OtherBoundaryChecker const & other_boundary_checker)279 void apply(Result & res, TurnIt it, 280 Geometry const& geometry, 281 OtherGeometry const& other_geometry, 282 BoundaryChecker const& boundary_checker, 283 OtherBoundaryChecker const& other_boundary_checker) 284 { 285 overlay::operation_type const op = it->operations[op_id].operation; 286 287 segment_identifier const& seg_id = it->operations[op_id].seg_id; 288 segment_identifier const& other_id = it->operations[other_op_id].seg_id; 289 290 bool const first_in_range = m_seg_watcher.update(seg_id); 291 292 if ( op != overlay::operation_union 293 && op != overlay::operation_intersection 294 && op != overlay::operation_blocked ) 295 { 296 // degenerated turn 297 if ( op == overlay::operation_continue 298 && it->method == overlay::method_none 299 && m_exit_watcher.is_outside(*it) 300 /*&& ( m_exit_watcher.get_exit_operation() == overlay::operation_none 301 || ! turn_on_the_same_ip<op_id>(m_exit_watcher.get_exit_turn(), *it) )*/ ) 302 { 303 // TODO: rewrite the above condition 304 305 // WARNING! For spikes the above condition may be TRUE 306 // When degenerated turns are be marked in a different way than c,c/c 307 // different condition will be checked 308 309 handle_degenerated(res, *it, 310 geometry, other_geometry, 311 boundary_checker, other_boundary_checker, 312 first_in_range); 313 314 // TODO: not elegant solution! should be rewritten. 315 if ( it->operations[op_id].position == overlay::position_back ) 316 { 317 m_previous_operation = overlay::operation_blocked; 318 m_exit_watcher.reset_detected_exit(); 319 } 320 } 321 322 return; 323 } 324 325 // reset 326 m_degenerated_turn_ptr = NULL; 327 328 // handle possible exit 329 bool fake_enter_detected = false; 330 if ( m_exit_watcher.get_exit_operation() == overlay::operation_union ) 331 { 332 // real exit point - may be multiple 333 // we know that we entered and now we exit 334 if ( ! turn_on_the_same_ip<op_id>(m_exit_watcher.get_exit_turn(), 335 *it, 336 boundary_checker.strategy()) ) 337 { 338 m_exit_watcher.reset_detected_exit(); 339 340 // not the last IP 341 update<interior, exterior, '1', transpose_result>(res); 342 } 343 // fake exit point, reset state 344 else if ( op == overlay::operation_intersection ) 345 { 346 m_exit_watcher.reset_detected_exit(); 347 fake_enter_detected = true; 348 } 349 } 350 else if ( m_exit_watcher.get_exit_operation() == overlay::operation_blocked ) 351 { 352 // ignore multiple BLOCKs 353 if ( op == overlay::operation_blocked ) 354 return; 355 356 if ( op == overlay::operation_intersection 357 && turn_on_the_same_ip<op_id>(m_exit_watcher.get_exit_turn(), 358 *it, 359 boundary_checker.strategy()) ) 360 { 361 fake_enter_detected = true; 362 } 363 364 m_exit_watcher.reset_detected_exit(); 365 } 366 367 // i/i, i/x, i/u 368 if ( op == overlay::operation_intersection ) 369 { 370 bool const was_outside = m_exit_watcher.is_outside(); 371 m_exit_watcher.enter(*it); 372 373 // interiors overlaps 374 update<interior, interior, '1', transpose_result>(res); 375 376 bool const this_b = it->operations[op_id].position == overlay::position_front // ignore spikes! 377 && is_ip_on_boundary<boundary_front>(it->point, 378 it->operations[op_id], 379 boundary_checker, 380 seg_id); 381 382 // going inside on boundary point 383 // may be front only 384 if ( this_b ) 385 { 386 // may be front and back 387 bool const other_b = is_ip_on_boundary<boundary_any>(it->point, 388 it->operations[other_op_id], 389 other_boundary_checker, 390 other_id); 391 392 // it's also the boundary of the other geometry 393 if ( other_b ) 394 { 395 update<boundary, boundary, '0', transpose_result>(res); 396 } 397 else 398 { 399 update<boundary, interior, '0', transpose_result>(res); 400 } 401 } 402 // going inside on non-boundary point 403 else 404 { 405 // if we didn't enter in the past, we were outside 406 if ( was_outside 407 && ! fake_enter_detected 408 && it->operations[op_id].position != overlay::position_front 409 && ! m_collinear_spike_exit ) 410 { 411 update<interior, exterior, '1', transpose_result>(res); 412 413 // if it's the first IP then the first point is outside 414 if ( first_in_range ) 415 { 416 bool const front_b = is_endpoint_on_boundary<boundary_front>( 417 range::front(sub_range(geometry, seg_id)), 418 boundary_checker); 419 420 // if there is a boundary on the first point 421 if ( front_b ) 422 { 423 update<boundary, exterior, '0', transpose_result>(res); 424 } 425 } 426 } 427 } 428 429 m_collinear_spike_exit = false; 430 } 431 // u/i, u/u, u/x, x/i, x/u, x/x 432 else if ( op == overlay::operation_union || op == overlay::operation_blocked ) 433 { 434 // TODO: is exit watcher still needed? 435 // couldn't is_collinear and some going inside counter be used instead? 436 437 bool const is_collinear = it->operations[op_id].is_collinear; 438 bool const was_outside = m_exit_watcher.is_outside() 439 && m_exit_watcher.get_exit_operation() == overlay::operation_none; 440 // TODO: move the above condition into the exit_watcher? 441 442 // to exit we must be currently inside and the current segment must be collinear 443 if ( !was_outside && is_collinear ) 444 { 445 m_exit_watcher.exit(*it, false); 446 // if the position is not set to back it must be a spike 447 if ( it->operations[op_id].position != overlay::position_back ) 448 { 449 m_collinear_spike_exit = true; 450 } 451 } 452 453 bool const op_blocked = op == overlay::operation_blocked; 454 455 // we're inside and going out from inside 456 // possibly going out right now 457 if ( ! was_outside && is_collinear ) 458 { 459 if ( op_blocked 460 && it->operations[op_id].position == overlay::position_back ) // ignore spikes! 461 { 462 // check if this is indeed the boundary point 463 // NOTE: is_ip_on_boundary<>() should be called here but the result will be the same 464 if ( is_endpoint_on_boundary<boundary_back>(it->point, boundary_checker) ) 465 { 466 // may be front and back 467 bool const other_b = is_ip_on_boundary<boundary_any>(it->point, 468 it->operations[other_op_id], 469 other_boundary_checker, 470 other_id); 471 // it's also the boundary of the other geometry 472 if ( other_b ) 473 { 474 update<boundary, boundary, '0', transpose_result>(res); 475 } 476 else 477 { 478 update<boundary, interior, '0', transpose_result>(res); 479 } 480 } 481 } 482 } 483 // we're outside or intersects some segment from the outside 484 else 485 { 486 // if we are truly outside 487 if ( was_outside 488 && it->operations[op_id].position != overlay::position_front 489 && ! m_collinear_spike_exit 490 /*&& !is_collinear*/ ) 491 { 492 update<interior, exterior, '1', transpose_result>(res); 493 } 494 495 // boundaries don't overlap - just an optimization 496 if ( it->method == overlay::method_crosses ) 497 { 498 // the L1 is going from one side of the L2 to the other through the point 499 update<interior, interior, '0', transpose_result>(res); 500 501 // it's the first point in range 502 if ( first_in_range ) 503 { 504 bool const front_b = is_endpoint_on_boundary<boundary_front>( 505 range::front(sub_range(geometry, seg_id)), 506 boundary_checker); 507 508 // if there is a boundary on the first point 509 if ( front_b ) 510 { 511 update<boundary, exterior, '0', transpose_result>(res); 512 } 513 } 514 } 515 // method other than crosses, check more conditions 516 else 517 { 518 bool const this_b = is_ip_on_boundary<boundary_any>(it->point, 519 it->operations[op_id], 520 boundary_checker, 521 seg_id); 522 523 bool const other_b = is_ip_on_boundary<boundary_any>(it->point, 524 it->operations[other_op_id], 525 other_boundary_checker, 526 other_id); 527 528 // if current IP is on boundary of the geometry 529 if ( this_b ) 530 { 531 // it's also the boundary of the other geometry 532 if ( other_b ) 533 { 534 update<boundary, boundary, '0', transpose_result>(res); 535 } 536 else 537 { 538 update<boundary, interior, '0', transpose_result>(res); 539 } 540 } 541 // if current IP is not on boundary of the geometry 542 else 543 { 544 // it's also the boundary of the other geometry 545 if ( other_b ) 546 { 547 update<interior, boundary, '0', transpose_result>(res); 548 } 549 else 550 { 551 update<interior, interior, '0', transpose_result>(res); 552 } 553 } 554 555 // first IP on the last segment point - this means that the first point is outside 556 if ( first_in_range 557 && ( !this_b || op_blocked ) 558 && was_outside 559 && it->operations[op_id].position != overlay::position_front 560 && ! m_collinear_spike_exit 561 /*&& !is_collinear*/ ) 562 { 563 bool const front_b = is_endpoint_on_boundary<boundary_front>( 564 range::front(sub_range(geometry, seg_id)), 565 boundary_checker); 566 567 // if there is a boundary on the first point 568 if ( front_b ) 569 { 570 update<boundary, exterior, '0', transpose_result>(res); 571 } 572 } 573 574 } 575 } 576 } 577 578 // store ref to previously analysed (valid) turn 579 m_previous_turn_ptr = boost::addressof(*it); 580 // and previously analysed (valid) operation 581 m_previous_operation = op; 582 } 583 584 // Called for last 585 template <typename Result, 586 typename TurnIt, 587 typename Geometry, 588 typename OtherGeometry, 589 typename BoundaryChecker, 590 typename OtherBoundaryChecker> apply(Result & res,TurnIt first,TurnIt last,Geometry const & geometry,OtherGeometry const &,BoundaryChecker const & boundary_checker,OtherBoundaryChecker const &)591 void apply(Result & res, 592 TurnIt first, TurnIt last, 593 Geometry const& geometry, 594 OtherGeometry const& /*other_geometry*/, 595 BoundaryChecker const& boundary_checker, 596 OtherBoundaryChecker const& /*other_boundary_checker*/) 597 { 598 boost::ignore_unused(first, last); 599 //BOOST_GEOMETRY_ASSERT( first != last ); 600 601 // here, the possible exit is the real one 602 // we know that we entered and now we exit 603 if ( /*m_exit_watcher.get_exit_operation() == overlay::operation_union // THIS CHECK IS REDUNDANT 604 ||*/ m_previous_operation == overlay::operation_union 605 || m_degenerated_turn_ptr ) 606 { 607 update<interior, exterior, '1', transpose_result>(res); 608 609 BOOST_GEOMETRY_ASSERT(first != last); 610 611 const TurnInfo * turn_ptr = NULL; 612 if ( m_degenerated_turn_ptr ) 613 turn_ptr = m_degenerated_turn_ptr; 614 else if ( m_previous_turn_ptr ) 615 turn_ptr = m_previous_turn_ptr; 616 617 if ( turn_ptr ) 618 { 619 segment_identifier const& prev_seg_id = turn_ptr->operations[op_id].seg_id; 620 621 //BOOST_GEOMETRY_ASSERT(!boost::empty(sub_range(geometry, prev_seg_id))); 622 bool const prev_back_b = is_endpoint_on_boundary<boundary_back>( 623 range::back(sub_range(geometry, prev_seg_id)), 624 boundary_checker); 625 626 // if there is a boundary on the last point 627 if ( prev_back_b ) 628 { 629 update<boundary, exterior, '0', transpose_result>(res); 630 } 631 } 632 } 633 634 // Just in case, 635 // reset exit watcher before the analysis of the next Linestring 636 // note that if there are some enters stored there may be some error above 637 m_exit_watcher.reset(); 638 639 m_previous_turn_ptr = NULL; 640 m_previous_operation = overlay::operation_none; 641 m_degenerated_turn_ptr = NULL; 642 643 // actually if this is set to true here there is some error 644 // in get_turns_ll or relate_ll, an assert could be checked here 645 m_collinear_spike_exit = false; 646 } 647 648 template <typename Result, 649 typename Turn, 650 typename Geometry, 651 typename OtherGeometry, 652 typename BoundaryChecker, 653 typename OtherBoundaryChecker> handle_degenerated(Result & res,Turn const & turn,Geometry const & geometry,OtherGeometry const & other_geometry,BoundaryChecker const & boundary_checker,OtherBoundaryChecker const & other_boundary_checker,bool first_in_range)654 void handle_degenerated(Result & res, 655 Turn const& turn, 656 Geometry const& geometry, 657 OtherGeometry const& other_geometry, 658 BoundaryChecker const& boundary_checker, 659 OtherBoundaryChecker const& other_boundary_checker, 660 bool first_in_range) 661 { 662 typename detail::single_geometry_return_type<Geometry const>::type 663 ls1_ref = detail::single_geometry(geometry, turn.operations[op_id].seg_id); 664 typename detail::single_geometry_return_type<OtherGeometry const>::type 665 ls2_ref = detail::single_geometry(other_geometry, turn.operations[other_op_id].seg_id); 666 667 // only one of those should be true: 668 669 if ( turn.operations[op_id].position == overlay::position_front ) 670 { 671 // valid, point-sized 672 if ( boost::size(ls2_ref) == 2 ) 673 { 674 bool const front_b = is_endpoint_on_boundary<boundary_front>(turn.point, boundary_checker); 675 676 if ( front_b ) 677 { 678 update<boundary, interior, '0', transpose_result>(res); 679 } 680 else 681 { 682 update<interior, interior, '0', transpose_result>(res); 683 } 684 685 // operation 'c' should be last for the same IP so we know that the next point won't be the same 686 update<interior, exterior, '1', transpose_result>(res); 687 688 m_degenerated_turn_ptr = boost::addressof(turn); 689 } 690 } 691 else if ( turn.operations[op_id].position == overlay::position_back ) 692 { 693 // valid, point-sized 694 if ( boost::size(ls2_ref) == 2 ) 695 { 696 update<interior, exterior, '1', transpose_result>(res); 697 698 bool const back_b = is_endpoint_on_boundary<boundary_back>(turn.point, boundary_checker); 699 700 if ( back_b ) 701 { 702 update<boundary, interior, '0', transpose_result>(res); 703 } 704 else 705 { 706 update<interior, interior, '0', transpose_result>(res); 707 } 708 709 if ( first_in_range ) 710 { 711 //BOOST_GEOMETRY_ASSERT(!boost::empty(ls1_ref)); 712 bool const front_b = is_endpoint_on_boundary<boundary_front>( 713 range::front(ls1_ref), boundary_checker); 714 if ( front_b ) 715 { 716 update<boundary, exterior, '0', transpose_result>(res); 717 } 718 } 719 } 720 } 721 else if ( turn.operations[op_id].position == overlay::position_middle 722 && turn.operations[other_op_id].position == overlay::position_middle ) 723 { 724 update<interior, interior, '0', transpose_result>(res); 725 726 // here we don't know which one is degenerated 727 728 bool const is_point1 = boost::size(ls1_ref) == 2 729 && equals::equals_point_point(range::front(ls1_ref), 730 range::back(ls1_ref), 731 boundary_checker.strategy()); 732 bool const is_point2 = boost::size(ls2_ref) == 2 733 && equals::equals_point_point(range::front(ls2_ref), 734 range::back(ls2_ref), 735 other_boundary_checker.strategy()); 736 737 // if the second one is degenerated 738 if ( !is_point1 && is_point2 ) 739 { 740 update<interior, exterior, '1', transpose_result>(res); 741 742 if ( first_in_range ) 743 { 744 //BOOST_GEOMETRY_ASSERT(!boost::empty(ls1_ref)); 745 bool const front_b = is_endpoint_on_boundary<boundary_front>( 746 range::front(ls1_ref), boundary_checker); 747 if ( front_b ) 748 { 749 update<boundary, exterior, '0', transpose_result>(res); 750 } 751 } 752 753 m_degenerated_turn_ptr = boost::addressof(turn); 754 } 755 } 756 757 // NOTE: other.position == front and other.position == back 758 // will be handled later, for the other geometry 759 } 760 761 private: 762 exit_watcher<TurnInfo, OpId> m_exit_watcher; 763 segment_watcher<same_single> m_seg_watcher; 764 const TurnInfo * m_previous_turn_ptr; 765 overlay::operation_type m_previous_operation; 766 const TurnInfo * m_degenerated_turn_ptr; 767 bool m_collinear_spike_exit; 768 }; 769 770 template <typename Result, 771 typename TurnIt, 772 typename Analyser, 773 typename Geometry, 774 typename OtherGeometry, 775 typename BoundaryChecker, 776 typename OtherBoundaryChecker> analyse_each_turnboost::geometry::detail::relate::linear_linear777 static inline void analyse_each_turn(Result & res, 778 Analyser & analyser, 779 TurnIt first, TurnIt last, 780 Geometry const& geometry, 781 OtherGeometry const& other_geometry, 782 BoundaryChecker const& boundary_checker, 783 OtherBoundaryChecker const& other_boundary_checker) 784 { 785 if ( first == last ) 786 return; 787 788 for ( TurnIt it = first ; it != last ; ++it ) 789 { 790 analyser.apply(res, it, 791 geometry, other_geometry, 792 boundary_checker, other_boundary_checker); 793 794 if ( BOOST_GEOMETRY_CONDITION( res.interrupt ) ) 795 return; 796 } 797 798 analyser.apply(res, first, last, 799 geometry, other_geometry, 800 boundary_checker, other_boundary_checker); 801 } 802 }; 803 804 }} // namespace detail::relate 805 #endif // DOXYGEN_NO_DETAIL 806 807 }} // namespace boost::geometry 808 809 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LINEAR_LINEAR_HPP 810