boost/geometry/algorithms/detail/relate/linear_linear.hpp

   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:
  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>
  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>
 126     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
 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>
 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:
 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>
 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>
 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>
 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>
 794     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