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