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