ceph/src/boost/boost/geometry/algorithms/detail/overlay/traversal.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 2017.
   6 // Modifications copyright (c) 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_OVERLAY_TRAVERSAL_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP
  16
  17 #include <cstddef>
  18
  19 #include <boost/range.hpp>
  20
  21 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
  22 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
  23 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
  24 #include <boost/geometry/core/access.hpp>
  25 #include <boost/geometry/core/assert.hpp>
  26 #include <boost/geometry/util/condition.hpp>
  27
  28 #if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) \
  29     || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT) \
  30     || defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
  31 #  include <string>
  32 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
  33 #  include <boost/geometry/io/wkt/wkt.hpp>
  34 #endif
  35
  36 namespace boost { namespace geometry
  37 {
  38
  39 #ifndef DOXYGEN_NO_DETAIL
  40 namespace detail { namespace overlay
  41 {
  42
  43 template <typename Turn, typename Operation>
  44 #ifdef BOOST_GEOMETRY_DEBUG_TRAVERSE
  45 inline void debug_traverse(Turn const& turn, Operation op,
  46                 std::string const& header, bool condition = true)
  47 {
  48     if (! condition)
  49     {
  50         return;
  51     }
  52     std::cout << " " << header
  53         << " at " << op.seg_id
  54         << " meth: " << method_char(turn.method)
  55         << " op: " << operation_char(op.operation)
  56         << " vis: " << visited_char(op.visited)
  57         << " of:  " << operation_char(turn.operations[0].operation)
  58         << operation_char(turn.operations[1].operation)
  59         << " " << geometry::wkt(turn.point)
  60         << std::endl;
  61
  62     if (boost::contains(header, "Finished"))
  63     {
  64         std::cout << std::endl;
  65     }
  66 }
  67 #else
  68 inline void debug_traverse(Turn const& , Operation, const char*, bool = true)
  69 {
  70 }
  71 #endif
  72
  73
  74 //! Metafunction to define side_order (clockwise, ccw) by operation_type
  75 template <operation_type OpType>
  76 struct side_compare {};
  77
  78 template <>
  79 struct side_compare<operation_union>
  80 {
  81     typedef std::greater<int> type;
  82 };
  83
  84 template <>
  85 struct side_compare<operation_intersection>
  86 {
  87     typedef std::less<int> type;
  88 };
  89
  90
  91 template
  92 <
  93     bool Reverse1,
  94     bool Reverse2,
  95     overlay_type OverlayType,
  96     typename Geometry1,
  97     typename Geometry2,
  98     typename Turns,
  99     typename Clusters,
 100     typename RobustPolicy,
 101     typename SideStrategy,
 102     typename Visitor
 103 >
 104 struct traversal
 105 {
 106     static const operation_type target_operation = operation_from_overlay<OverlayType>::value;
 107
 108     typedef typename side_compare<target_operation>::type side_compare_type;
 109     typedef typename boost::range_value<Turns>::type turn_type;
 110     typedef typename turn_type::turn_operation_type turn_operation_type;
 111
 112     typedef typename geometry::point_type<Geometry1>::type point_type;
 113     typedef sort_by_side::side_sorter
 114         <
 115             Reverse1, Reverse2, OverlayType,
 116             point_type, SideStrategy, side_compare_type
 117         > sbs_type;
 118
 119     inline traversal(Geometry1 const& geometry1, Geometry2 const& geometry2,
 120             Turns& turns, Clusters const& clusters,
 121             RobustPolicy const& robust_policy, SideStrategy const& strategy,
 122             Visitor& visitor)
 123         : m_geometry1(geometry1)
 124         , m_geometry2(geometry2)
 125         , m_turns(turns)
 126         , m_clusters(clusters)
 127         , m_robust_policy(robust_policy)
 128         , m_strategy(strategy)
 129         , m_visitor(visitor)
 130     {
 131     }
 132
 133     template <typename TurnInfoMap>
 134     inline void finalize_visit_info(TurnInfoMap& turn_info_map)
 135     {
 136         for (typename boost::range_iterator<Turns>::type
 137             it = boost::begin(m_turns);
 138             it != boost::end(m_turns);
 139             ++it)
 140         {
 141             turn_type& turn = *it;
 142             for (int i = 0; i < 2; i++)
 143             {
 144                 turn_operation_type& op = turn.operations[i];
 145                 if (op.visited.visited()
 146                     || op.visited.started()
 147                     || op.visited.finished() )
 148                 {
 149                    ring_identifier const ring_id
 150                         (
 151                             op.seg_id.source_index,
 152                             op.seg_id.multi_index,
 153                             op.seg_id.ring_index
 154                         );
 155                    turn_info_map[ring_id].has_traversed_turn = true;
 156
 157                    if (op.operation == operation_continue)
 158                    {
 159                        // Continue operations should mark the other operation
 160                        // as traversed too
 161                        turn_operation_type& other_op = turn.operations[1 - i];
 162                        ring_identifier const other_ring_id
 163                             (
 164                                 other_op.seg_id.source_index,
 165                                 other_op.seg_id.multi_index,
 166                                 other_op.seg_id.ring_index
 167                             );
 168                        turn_info_map[other_ring_id].has_traversed_turn = true;
 169                    }
 170                 }
 171                 op.visited.finalize();
 172             }
 173         }
 174     }
 175
 176     //! Sets visited for ALL turns traveling to the same turn
 177     inline void set_visited_in_cluster(signed_size_type cluster_id,
 178                                        signed_size_type rank)
 179     {
 180         typename Clusters::const_iterator mit = m_clusters.find(cluster_id);
 181         BOOST_ASSERT(mit != m_clusters.end());
 182
 183         cluster_info const& cinfo = mit->second;
 184         std::set<signed_size_type> const& ids = cinfo.turn_indices;
 185
 186         for (typename std::set<signed_size_type>::const_iterator it = ids.begin();
 187              it != ids.end(); ++it)
 188         {
 189             signed_size_type const turn_index = *it;
 190             turn_type& turn = m_turns[turn_index];
 191
 192             for (int i = 0; i < 2; i++)
 193             {
 194                 turn_operation_type& op = turn.operations[i];
 195                 if (op.visited.none()
 196                     && op.enriched.rank == rank)
 197                 {
 198                     op.visited.set_visited();
 199                 }
 200             }
 201         }
 202     }
 203     inline void set_visited(turn_type& turn, turn_operation_type& op)
 204     {
 205         if (op.operation == detail::overlay::operation_continue)
 206         {
 207             // On "continue", all go in same direction so set "visited" for ALL
 208             for (int i = 0; i < 2; i++)
 209             {
 210                 turn_operation_type& turn_op = turn.operations[i];
 211                 if (turn_op.visited.none())
 212                 {
 213                     turn_op.visited.set_visited();
 214                 }
 215             }
 216         }
 217         else
 218         {
 219             op.visited.set_visited();
 220         }
 221         if (turn.is_clustered())
 222         {
 223             set_visited_in_cluster(turn.cluster_id, op.enriched.rank);
 224         }
 225     }
 226
 227     inline bool is_visited(turn_type const& , turn_operation_type const& op,
 228                          signed_size_type , int) const
 229     {
 230         return op.visited.visited();
 231     }
 232
 233     template <signed_size_type segment_identifier::*Member>
 234     inline bool select_source_generic(turn_type const& turn,
 235             segment_identifier const& current,
 236             segment_identifier const& previous) const
 237     {
 238         turn_operation_type const& op0 = turn.operations[0];
 239         turn_operation_type const& op1 = turn.operations[1];
 240
 241         bool const switch_source = op0.enriched.region_id != -1
 242                 && op0.enriched.region_id == op1.enriched.region_id;
 243
 244 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
 245         if (switch_source)
 246         {
 247             std::cout << "Switch source at " << &turn << std::endl;
 248         }
 249         else
 250         {
 251             std::cout << "DON'T SWITCH SOURCES at " << &turn << std::endl;
 252         }
 253 #endif
 254         return switch_source
 255                 ? current.*Member != previous.*Member
 256                 : current.*Member == previous.*Member;
 257     }
 258
 259     inline bool select_source(turn_type const& turn,
 260                               segment_identifier const& candidate_seg_id,
 261                               segment_identifier const& previous_seg_id) const
 262     {
 263         // For uu/ii, only switch sources if indicated
 264
 265         if (OverlayType == overlay_buffer)
 266         {
 267             // Buffer does not use source_index (always 0).
 268             return select_source_generic<&segment_identifier::multi_index>(
 269                         turn, candidate_seg_id, previous_seg_id);
 270         }
 271
 272         if (is_self_turn<OverlayType>(turn))
 273         {
 274             // Also, if it is a self-turn, stay on same ring (multi/ring)
 275             return select_source_generic<&segment_identifier::multi_index>(
 276                         turn, candidate_seg_id, previous_seg_id);
 277         }
 278
 279         // Use source_index
 280         return select_source_generic<&segment_identifier::source_index>(
 281                     turn, candidate_seg_id, previous_seg_id);
 282     }
 283
 284     inline bool traverse_possible(signed_size_type turn_index) const
 285     {
 286         if (turn_index == -1)
 287         {
 288             return false;
 289         }
 290
 291         turn_type const& turn = m_turns[turn_index];
 292
 293         // It is not a dead end if there is an operation to continue, or of
 294         // there is a cluster (assuming for now we can get out of the cluster)
 295         return turn.is_clustered()
 296             || turn.has(target_operation)
 297             || turn.has(operation_continue);
 298     }
 299
 300     inline std::size_t get_shortcut_level(turn_operation_type const& op,
 301                              signed_size_type start_turn_index,
 302                              signed_size_type origin_turn_index,
 303                              std::size_t level = 1) const
 304     {
 305         signed_size_type next_turn_index = op.enriched.get_next_turn_index();
 306         if (next_turn_index == -1)
 307         {
 308             return 0;
 309         }
 310         if (next_turn_index == start_turn_index)
 311         {
 312             // This operation finishes the ring
 313             return 0;
 314         }
 315         if (next_turn_index == origin_turn_index)
 316         {
 317             // This operation travels to itself
 318             return level;
 319         }
 320         if (level > 10)
 321         {
 322             // Avoid infinite recursion
 323             return 0;
 324         }
 325
 326         turn_type const& next_turn = m_turns[next_turn_index];
 327         for (int i = 0; i < 2; i++)
 328         {
 329             turn_operation_type const& next_op = next_turn.operations[i];
 330             if (next_op.operation == target_operation
 331                 && ! next_op.visited.finished()
 332                 && ! next_op.visited.visited())
 333             {
 334                 // Recursively continue verifying
 335                 if (get_shortcut_level(next_op, start_turn_index,
 336                                        origin_turn_index, level + 1))
 337                 {
 338                     return level + 1;
 339                 }
 340             }
 341         }
 342         return 0;
 343     }
 344
 345     inline
 346     bool select_cc_operation(turn_type const& turn,
 347                 signed_size_type start_turn_index,
 348                 int& selected_op_index) const
 349     {
 350         // For "cc", take either one, but if there is a starting one,
 351         //           take that one. If next is dead end, skip that one.
 352         // If both are valid candidates, take the one with minimal remaining
 353         // distance (important for #mysql_23023665 in buffer).
 354
 355         // Initialize with 0, automatically assigned on first result
 356         typename turn_operation_type::comparable_distance_type
 357                 min_remaining_distance = 0;
 358
 359         bool result = false;
 360
 361         for (int i = 0; i < 2; i++)
 362         {
 363             turn_operation_type const& op = turn.operations[i];
 364
 365             signed_size_type const next_turn_index = op.enriched.get_next_turn_index();
 366
 367             if (! traverse_possible(next_turn_index))
 368             {
 369                 continue;
 370             }
 371
 372             if (! result
 373                 || next_turn_index == start_turn_index
 374                 || op.remaining_distance < min_remaining_distance)
 375             {
 376                 debug_traverse(turn, op, "First candidate cc", ! result);
 377                 debug_traverse(turn, op, "Candidate cc override (start)",
 378                     result && next_turn_index == start_turn_index);
 379                 debug_traverse(turn, op, "Candidate cc override (remaining)",
 380                     result && op.remaining_distance < min_remaining_distance);
 381
 382                 selected_op_index = i;
 383                 min_remaining_distance = op.remaining_distance;
 384                 result = true;
 385             }
 386         }
 387
 388         return result;
 389     }
 390
 391     inline
 392     bool select_noncc_operation(turn_type const& turn,
 393                 segment_identifier const& previous_seg_id,
 394                 int& selected_op_index) const
 395     {
 396         bool result = false;
 397
 398         for (int i = 0; i < 2; i++)
 399         {
 400             turn_operation_type const& op = turn.operations[i];
 401
 402             if (op.operation == target_operation
 403                 && ! op.visited.finished()
 404                 && ! op.visited.visited()
 405                 && (! result || select_source(turn, op.seg_id, previous_seg_id)))
 406             {
 407                 selected_op_index = i;
 408                 debug_traverse(turn, op, "Candidate");
 409                 result = true;
 410             }
 411         }
 412
 413         return result;
 414     }
 415
 416     inline
 417     bool select_preferred_operation(turn_type const& turn,
 418                 signed_size_type turn_index,
 419                 signed_size_type start_turn_index,
 420                 int& selected_op_index) const
 421     {
 422         bool option[2] = {0};
 423         bool finishing[2] = {0};
 424         bool preferred[2] = {0};
 425         std::size_t shortcut_level[2] = {0};
 426         for (int i = 0; i < 2; i++)
 427         {
 428             turn_operation_type const& op = turn.operations[i];
 429
 430             if (op.operation == target_operation
 431                 && ! op.visited.finished()
 432                 && ! op.visited.visited())
 433             {
 434                 option[i] = true;
 435                 if (op.enriched.get_next_turn_index() == start_turn_index)
 436                 {
 437                     finishing[i] = true;
 438                 }
 439                 else
 440                 {
 441                     shortcut_level[i] = get_shortcut_level(op, start_turn_index,
 442                                                            turn_index);
 443                 }
 444
 445                 if (op.enriched.prefer_start)
 446                 {
 447                     preferred[i] = true;
 448                 }
 449             }
 450         }
 451
 452         if (option[0] != option[1])
 453         {
 454             // Only one operation is acceptable, take that one
 455             selected_op_index = option[0] ? 0 : 1;
 456             return true;
 457         }
 458
 459         if (option[0] && option[1])
 460         {
 461             // Both operations are acceptable
 462             if (finishing[0] != finishing[1])
 463             {
 464                 // Prefer operation finishing the ring
 465                 selected_op_index = finishing[0] ? 0 : 1;
 466                 return true;
 467             }
 468
 469             if (shortcut_level[0] != shortcut_level[1])
 470             {
 471                 // If a turn can travel to itself again (without closing the
 472                 // ring), take the shortest one
 473                 selected_op_index = shortcut_level[0] < shortcut_level[1] ? 0 : 1;
 474                 return true;
 475             }
 476
 477             if (preferred[0] != preferred[1])
 478             {
 479                 // Only one operation is preferred (== was not intersection)
 480                 selected_op_index = preferred[0] ? 0 : 1;
 481                 return true;
 482             }
 483         }
 484
 485         for (int i = 0; i < 2; i++)
 486         {
 487             if (option[i])
 488             {
 489                 selected_op_index = 0;
 490                 return true;
 491             }
 492         }
 493
 494         return false;
 495     }
 496
 497     inline
 498     bool select_operation(const turn_type& turn,
 499                 signed_size_type turn_index,
 500                 signed_size_type start_turn_index,
 501                 segment_identifier const& previous_seg_id,
 502                 int& selected_op_index) const
 503     {
 504         bool result = false;
 505         selected_op_index = -1;
 506         if (turn.both(operation_continue))
 507         {
 508             result = select_cc_operation(turn, start_turn_index,
 509                                          selected_op_index);
 510         }
 511         else if (OverlayType == overlay_dissolve)
 512         {
 513             result = select_preferred_operation(turn, turn_index,
 514                 start_turn_index, selected_op_index);
 515         }
 516         else
 517         {
 518             result = select_noncc_operation(turn, previous_seg_id,
 519                 selected_op_index);
 520         }
 521         if (result)
 522         {
 523            debug_traverse(turn, turn.operations[selected_op_index], "Accepted");
 524         }
 525
 526         return result;
 527     }
 528
 529     inline int starting_operation_index(const turn_type& turn) const
 530     {
 531         for (int i = 0; i < 2; i++)
 532         {
 533             if (turn.operations[i].visited.started())
 534             {
 535                 return i;
 536             }
 537         }
 538         return -1;
 539     }
 540
 541     inline bool both_finished(const turn_type& turn) const
 542     {
 543         for (int i = 0; i < 2; i++)
 544         {
 545             if (! turn.operations[i].visited.finished())
 546             {
 547                 return false;
 548             }
 549         }
 550         return true;
 551     }
 552
 553
 554     template <typename RankedPoint>
 555     inline turn_operation_type const& operation_from_rank(RankedPoint const& rp) const
 556     {
 557         return m_turns[rp.turn_index].operations[rp.operation_index];
 558     }
 559
 560     inline int select_turn_in_cluster_union(std::size_t selected_rank,
 561             typename sbs_type::rp const& ranked_point,
 562             signed_size_type start_turn_index, int start_op_index) const
 563     {
 564         // Returns 0 if it not OK
 565         // Returns 1 if it OK
 566         // Returns 2 if it OK and start turn matches
 567         // Returns 3 if it OK and start turn and start op both match
 568         if (ranked_point.rank != selected_rank
 569             || ranked_point.direction != sort_by_side::dir_to)
 570         {
 571             return 0;
 572         }
 573
 574         turn_operation_type const& op = operation_from_rank(ranked_point);
 575
 576         // Check finalized: TODO: this should be finetuned, it is not necessary
 577         if (op.visited.finalized())
 578         {
 579             return 0;
 580         }
 581
 582         if (OverlayType != overlay_dissolve
 583             && (op.enriched.count_left != 0 || op.enriched.count_right == 0))
 584         {
 585             // Check counts: in some cases interior rings might be generated with
 586             // polygons on both sides. For dissolve it can be anything.
 587             return 0;
 588         }
 589
 590         return ranked_point.turn_index == start_turn_index
 591                 && ranked_point.operation_index == start_op_index ? 3
 592             : ranked_point.turn_index == start_turn_index ? 2
 593             : 1
 594             ;
 595     }
 596
 597     inline signed_size_type select_rank(sbs_type const& sbs,
 598                                         bool skip_isolated) const
 599     {
 600         // Take the first outgoing rank corresponding to incoming region,
 601         // or take another region if it is not isolated
 602         turn_operation_type const& incoming_op
 603                 = operation_from_rank(sbs.m_ranked_points.front());
 604
 605         for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
 606         {
 607             typename sbs_type::rp const& rp = sbs.m_ranked_points[i];
 608             if (rp.rank == 0 || rp.direction == sort_by_side::dir_from)
 609             {
 610                 continue;
 611             }
 612             turn_operation_type const& op = operation_from_rank(rp);
 613
 614             if (op.operation != target_operation
 615                 && op.operation != operation_continue)
 616             {
 617                 continue;
 618             }
 619
 620             if (op.enriched.region_id == incoming_op.enriched.region_id
 621                 || (skip_isolated && ! op.enriched.isolated))
 622             {
 623                 // Region corresponds to incoming region, or (for intersection)
 624                 // there is a non-isolated other region which should be taken
 625                 return rp.rank;
 626             }
 627         }
 628         return -1;
 629     }
 630
 631     inline bool select_from_cluster_union(signed_size_type& turn_index,
 632         int& op_index, sbs_type const& sbs,
 633         signed_size_type start_turn_index, int start_op_index) const
 634     {
 635         std::size_t const selected_rank = select_rank(sbs, false);
 636
 637         int best_code = 0;
 638         bool result = false;
 639         for (std::size_t i = 1; i < sbs.m_ranked_points.size(); i++)
 640         {
 641             typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i];
 642
 643             if (ranked_point.rank > selected_rank)
 644             {
 645                 // Sorted on rank, so it makes no sense to continue
 646                 break;
 647             }
 648
 649             int const code
 650                 = select_turn_in_cluster_union(selected_rank, ranked_point,
 651                     start_turn_index, start_op_index);
 652
 653             if (code > best_code)
 654             {
 655                 // It is 1 or higher and matching better than previous
 656                 best_code = code;
 657                 turn_index = ranked_point.turn_index;
 658                 op_index = ranked_point.operation_index;
 659                 result = true;
 660             }
 661         }
 662         return result;
 663     }
 664
 665     inline bool analyze_cluster_intersection(signed_size_type& turn_index,
 666                 int& op_index, sbs_type const& sbs) const
 667     {
 668         std::size_t const selected_rank = select_rank(sbs, true);
 669
 670         if (selected_rank > 0)
 671         {
 672             typename turn_operation_type::comparable_distance_type
 673                     min_remaining_distance = 0;
 674
 675             std::size_t selected_index = sbs.m_ranked_points.size();
 676             for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
 677             {
 678                 typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i];
 679
 680                 if (ranked_point.rank == selected_rank)
 681                 {
 682                     turn_operation_type const& op = operation_from_rank(ranked_point);
 683
 684                     if (op.visited.finalized())
 685                     {
 686                         // This direction is already traveled before, the same
 687                         // cannot be traveled again
 688                         continue;
 689                     }
 690
 691                     // Take turn with the smallest remaining distance
 692                     if (selected_index == sbs.m_ranked_points.size()
 693                             || op.remaining_distance < min_remaining_distance)
 694                     {
 695                         selected_index = i;
 696                         min_remaining_distance = op.remaining_distance;
 697                     }
 698                 }
 699             }
 700
 701             if (selected_index < sbs.m_ranked_points.size())
 702             {
 703                 typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[selected_index];
 704                 turn_index = ranked_point.turn_index;
 705                 op_index = ranked_point.operation_index;
 706                 return true;
 707             }
 708         }
 709
 710         return false;
 711     }
 712
 713     inline bool select_turn_from_cluster(signed_size_type& turn_index,
 714             int& op_index,
 715             signed_size_type start_turn_index, int start_op_index,
 716             segment_identifier const& previous_seg_id) const
 717     {
 718         bool const is_union = target_operation == operation_union;
 719
 720         turn_type const& turn = m_turns[turn_index];
 721         BOOST_ASSERT(turn.is_clustered());
 722
 723         typename Clusters::const_iterator mit = m_clusters.find(turn.cluster_id);
 724         BOOST_ASSERT(mit != m_clusters.end());
 725
 726         cluster_info const& cinfo = mit->second;
 727         std::set<signed_size_type> const& ids = cinfo.turn_indices;
 728
 729         sbs_type sbs(m_strategy);
 730
 731         for (typename std::set<signed_size_type>::const_iterator sit = ids.begin();
 732              sit != ids.end(); ++sit)
 733         {
 734             signed_size_type cluster_turn_index = *sit;
 735             turn_type const& cluster_turn = m_turns[cluster_turn_index];
 736             bool const departure_turn = cluster_turn_index == turn_index;
 737             if (cluster_turn.discarded)
 738             {
 739                 // Defensive check, discarded turns should not be in cluster
 740                 continue;
 741             }
 742
 743             for (int i = 0; i < 2; i++)
 744             {
 745                 sbs.add(cluster_turn.operations[i],
 746                         cluster_turn_index, i, previous_seg_id,
 747                         m_geometry1, m_geometry2,
 748                         departure_turn);
 749             }
 750         }
 751
 752         if (! sbs.has_origin())
 753         {
 754             return false;
 755         }
 756         sbs.apply(turn.point);
 757
 758         bool result = false;
 759
 760         if (is_union)
 761         {
 762             result = select_from_cluster_union(turn_index, op_index, sbs,
 763                 start_turn_index, start_op_index);
 764         }
 765         else
 766         {
 767             result = analyze_cluster_intersection(turn_index, op_index, sbs);
 768         }
 769         return result;
 770     }
 771
 772     inline bool analyze_ii_intersection(signed_size_type& turn_index, int& op_index,
 773                     turn_type const& current_turn,
 774                     segment_identifier const& previous_seg_id)
 775     {
 776         sbs_type sbs(m_strategy);
 777
 778         // Add this turn to the sort-by-side sorter
 779         for (int i = 0; i < 2; i++)
 780         {
 781             sbs.add(current_turn.operations[i],
 782                     turn_index, i, previous_seg_id,
 783                     m_geometry1, m_geometry2,
 784                     true);
 785         }
 786
 787         if (! sbs.has_origin())
 788         {
 789             return false;
 790         }
 791
 792         sbs.apply(current_turn.point);
 793
 794         bool result = analyze_cluster_intersection(turn_index, op_index, sbs);
 795
 796         return result;
 797     }
 798
 799     inline void change_index_for_self_turn(signed_size_type& to_vertex_index,
 800                 turn_type const& start_turn,
 801                 turn_operation_type const& start_op,
 802                 int start_op_index) const
 803     {
 804         if (OverlayType != overlay_buffer && OverlayType != overlay_dissolve)
 805         {
 806             return;
 807         }
 808
 809         const bool allow_uu = OverlayType != overlay_buffer;
 810
 811         // It travels to itself, can happen. If this is a buffer, it can
 812         // sometimes travel to itself in the following configuration:
 813         //
 814         // +---->--+
 815         // |       |
 816         // |   +---*----+ *: one turn, with segment index 2/7
 817         // |   |   |    |
 818         // |   +---C    | C: closing point (start/end)
 819         // |            |
 820         // +------------+
 821         //
 822         // If it starts on segment 2 and travels to itself on segment 2, that
 823         // should be corrected to 7 because that is the shortest path
 824         //
 825         // Also a uu turn (touching with another buffered ring) might have this
 826         // apparent configuration, but there it should
 827         // always travel the whole ring
 828
 829         turn_operation_type const& other_op
 830                 = start_turn.operations[1 - start_op_index];
 831
 832         bool const correct
 833                 = (allow_uu || ! start_turn.both(operation_union))
 834                   && start_op.seg_id.source_index == other_op.seg_id.source_index
 835                   && start_op.seg_id.multi_index == other_op.seg_id.multi_index
 836                   && start_op.seg_id.ring_index == other_op.seg_id.ring_index
 837                   && start_op.seg_id.segment_index == to_vertex_index;
 838
 839 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
 840         std::cout << " WARNING: self-buffer "
 841                   << " correct=" << correct
 842                   << " turn=" << operation_char(start_turn.operations[0].operation)
 843                   << operation_char(start_turn.operations[1].operation)
 844                   << " start=" << start_op.seg_id.segment_index
 845                   << " from=" << to_vertex_index
 846                   << " to=" << other_op.enriched.travels_to_vertex_index
 847                   << std::endl;
 848 #endif
 849
 850         if (correct)
 851         {
 852             to_vertex_index = other_op.enriched.travels_to_vertex_index;
 853         }
 854     }
 855
 856     bool select_turn_from_enriched(signed_size_type& turn_index,
 857             segment_identifier& previous_seg_id,
 858             signed_size_type& to_vertex_index,
 859             signed_size_type start_turn_index,
 860             int start_op_index,
 861             turn_type const& previous_turn,
 862             turn_operation_type const& previous_op,
 863             bool is_start) const
 864     {
 865         to_vertex_index = -1;
 866
 867         if (previous_op.enriched.next_ip_index < 0)
 868         {
 869             // There is no next IP on this segment
 870             if (previous_op.enriched.travels_to_vertex_index < 0
 871                 || previous_op.enriched.travels_to_ip_index < 0)
 872             {
 873                 return false;
 874             }
 875
 876             to_vertex_index = previous_op.enriched.travels_to_vertex_index;
 877
 878             if (is_start &&
 879                     previous_op.enriched.travels_to_ip_index == start_turn_index)
 880             {
 881                 change_index_for_self_turn(to_vertex_index, previous_turn,
 882                     previous_op, start_op_index);
 883             }
 884
 885             turn_index = previous_op.enriched.travels_to_ip_index;
 886             previous_seg_id = previous_op.seg_id;
 887         }
 888         else
 889         {
 890             // Take the next IP on this segment
 891             turn_index = previous_op.enriched.next_ip_index;
 892             previous_seg_id = previous_op.seg_id;
 893         }
 894         return true;
 895     }
 896
 897     bool select_turn(signed_size_type start_turn_index, int start_op_index,
 898                      signed_size_type& turn_index,
 899                      int& op_index,
 900                      int previous_op_index,
 901                      signed_size_type previous_turn_index,
 902                      segment_identifier const& previous_seg_id,
 903                      bool is_start)
 904     {
 905         turn_type const& current_turn = m_turns[turn_index];
 906
 907         if (BOOST_GEOMETRY_CONDITION(target_operation == operation_intersection))
 908         {
 909             bool const back_at_start_cluster
 910                     = current_turn.is_clustered()
 911                     && m_turns[start_turn_index].cluster_id == current_turn.cluster_id;
 912
 913             if (turn_index == start_turn_index || back_at_start_cluster)
 914             {
 915                 // Intersection can always be finished if returning
 916                 turn_index = start_turn_index;
 917                 op_index = start_op_index;
 918                 return true;
 919             }
 920
 921             if (! current_turn.is_clustered()
 922                 && current_turn.both(operation_intersection))
 923             {
 924                 if (analyze_ii_intersection(turn_index, op_index,
 925                             current_turn, previous_seg_id))
 926                 {
 927                     return true;
 928                 }
 929             }
 930         }
 931
 932         if (current_turn.is_clustered())
 933         {
 934             if (! select_turn_from_cluster(turn_index, op_index,
 935                     start_turn_index, start_op_index, previous_seg_id))
 936             {
 937                 return false;
 938             }
 939
 940             if (is_start && turn_index == previous_turn_index)
 941             {
 942                 op_index = previous_op_index;
 943             }
 944         }
 945         else
 946         {
 947             op_index = starting_operation_index(current_turn);
 948             if (op_index == -1)
 949             {
 950                 if (both_finished(current_turn))
 951                 {
 952                     return false;
 953                 }
 954
 955                 if (! select_operation(current_turn, turn_index,
 956                                 start_turn_index,
 957                                 previous_seg_id,
 958                                 op_index))
 959                 {
 960                     return false;
 961                 }
 962             }
 963         }
 964         return true;
 965     }
 966
 967 private :
 968     Geometry1 const& m_geometry1;
 969     Geometry2 const& m_geometry2;
 970     Turns& m_turns;
 971     Clusters const& m_clusters;
 972     RobustPolicy const& m_robust_policy;
 973     SideStrategy m_strategy;
 974     Visitor& m_visitor;
 975 };
 976
 977
 978
 979 }} // namespace detail::overlay
 980 #endif // DOXYGEN_NO_DETAIL
 981
 982 }} // namespace boost::geometry
 983
 984 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP