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