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