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