detail/overlay/traversal.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2023-2024 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2017-2020.
0007 // Modifications copyright (c) 2017-2020 Oracle and/or its affiliates.
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Use, modification and distribution is subject to the Boost Software License,
0011 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0012 // http://www.boost.org/LICENSE_1_0.txt)
0013
0014 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP
0016
0017 #include <cstddef>
0018 #include <set>
0019
0020 #include <boost/range/begin.hpp>
0021 #include <boost/range/end.hpp>
0022 #include <boost/range/value_type.hpp>
0023
0024 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
0025 #include <boost/geometry/algorithms/detail/overlay/cluster_exits.hpp>
0026 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
0027 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
0028 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
0029 #include <boost/geometry/core/assert.hpp>
0030 #include <boost/geometry/util/constexpr.hpp>
0031
0032 #if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) \
0033     || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT) \
0034     || defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
0035 #  include <string>
0036 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
0037 #  include <boost/geometry/io/wkt/wkt.hpp>
0038 #endif
0039
0040 namespace boost { namespace geometry
0041 {
0042
0043 #ifndef DOXYGEN_NO_DETAIL
0044 namespace detail { namespace overlay
0045 {
0046
0047 template <typename Turn, typename Operation>
0048 #ifdef BOOST_GEOMETRY_DEBUG_TRAVERSE
0049 inline void debug_traverse(Turn const& turn, Operation op,
0050                 std::string const& header, bool condition = true)
0051 {
0052     if (! condition)
0053     {
0054         return;
0055     }
0056     std::cout << " " << header
0057         << " at " << op.seg_id
0058         << " meth: " << method_char(turn.method)
0059         << " op: " << operation_char(op.operation)
0060         << " vis: " << visited_char(op.visited)
0061         << " of:  " << operation_char(turn.operations[0].operation)
0062         << operation_char(turn.operations[1].operation)
0063         << " " << geometry::wkt(turn.point)
0064         << std::endl;
0065
0066     if (boost::contains(header, "Finished"))
0067     {
0068         std::cout << std::endl;
0069     }
0070 }
0071 #else
0072 inline void debug_traverse(Turn const& , Operation, const char*, bool = true)
0073 {
0074 }
0075 #endif
0076
0077 template
0078 <
0079     bool Reverse1,
0080     bool Reverse2,
0081     overlay_type OverlayType,
0082     typename Geometry1,
0083     typename Geometry2,
0084     typename Turns,
0085     typename Clusters,
0086     typename RobustPolicy,
0087     typename Strategy,
0088     typename Visitor
0089 >
0090 struct traversal
0091 {
0092 private :
0093
0094     static const operation_type target_operation = operation_from_overlay<OverlayType>::value;
0095
0096     typedef typename sort_by_side::side_compare<target_operation>::type side_compare_type;
0097     typedef typename boost::range_value<Turns>::type turn_type;
0098     typedef typename turn_type::turn_operation_type turn_operation_type;
0099
0100     typedef typename geometry::point_type<Geometry1>::type point_type;
0101     typedef sort_by_side::side_sorter
0102         <
0103             Reverse1, Reverse2, OverlayType,
0104             point_type, Strategy, side_compare_type
0105         > sbs_type;
0106
0107 public :
0108     inline traversal(Geometry1 const& geometry1, Geometry2 const& geometry2,
0109             Turns& turns, Clusters const& clusters,
0110             RobustPolicy const& robust_policy, Strategy const& strategy,
0111             Visitor& visitor)
0112         : m_geometry1(geometry1)
0113         , m_geometry2(geometry2)
0114         , m_turns(turns)
0115         , m_clusters(clusters)
0116         , m_robust_policy(robust_policy)
0117         , m_strategy(strategy)
0118         , m_visitor(visitor)
0119     {
0120     }
0121
0122     template <typename TurnInfoMap>
0123     inline void finalize_visit_info(TurnInfoMap& turn_info_map)
0124     {
0125         for (auto& turn : m_turns)
0126         {
0127             for (int i = 0; i < 2; i++)
0128             {
0129                 turn_operation_type& op = turn.operations[i];
0130                 if (op.visited.visited()
0131                     || op.visited.started()
0132                     || op.visited.finished() )
0133                 {
0134                    ring_identifier const ring_id = ring_id_by_seg_id(op.seg_id);
0135                    turn_info_map[ring_id].has_traversed_turn = true;
0136
0137                    if (op.operation == operation_continue)
0138                    {
0139                        // Continue operations should mark the other operation
0140                        // as traversed too
0141                        turn_operation_type& other_op = turn.operations[1 - i];
0142                        ring_identifier const other_ring_id
0143                                = ring_id_by_seg_id(other_op.seg_id);
0144                        turn_info_map[other_ring_id].has_traversed_turn = true;
0145                    }
0146                 }
0147                 op.visited.finalize();
0148             }
0149         }
0150     }
0151
0152     //! Sets visited for ALL turns traveling to the same turn
0153     inline void set_visited_in_cluster(signed_size_type cluster_id,
0154                                        signed_size_type rank)
0155     {
0156         auto mit = m_clusters.find(cluster_id);
0157         BOOST_ASSERT(mit != m_clusters.end());
0158
0159         cluster_info const& cinfo = mit->second;
0160
0161         for (auto turn_index : cinfo.turn_indices)
0162         {
0163             turn_type& turn = m_turns[turn_index];
0164
0165             for (auto& op : turn.operations)
0166             {
0167                 if (op.visited.none() && op.enriched.rank == rank)
0168                 {
0169                     op.visited.set_visited();
0170                 }
0171             }
0172         }
0173     }
0174     inline void set_visited(turn_type& turn, turn_operation_type& op)
0175     {
0176         if (op.operation == detail::overlay::operation_continue)
0177         {
0178             // On "continue", all go in same direction so set "visited" for ALL
0179             for (int i = 0; i < 2; i++)
0180             {
0181                 turn_operation_type& turn_op = turn.operations[i];
0182                 if (turn_op.visited.none())
0183                 {
0184                     turn_op.visited.set_visited();
0185                 }
0186             }
0187         }
0188         else
0189         {
0190             op.visited.set_visited();
0191         }
0192         if (turn.is_clustered())
0193         {
0194             set_visited_in_cluster(turn.cluster_id, op.enriched.rank);
0195         }
0196     }
0197
0198     inline bool is_visited(turn_type const& , turn_operation_type const& op,
0199                          signed_size_type , int) const
0200     {
0201         return op.visited.visited();
0202     }
0203
0204     template <signed_size_type segment_identifier::*Member>
0205     inline bool select_source_generic(turn_type const& turn,
0206             segment_identifier const& current,
0207             segment_identifier const& previous) const
0208     {
0209         turn_operation_type const& op0 = turn.operations[0];
0210         turn_operation_type const& op1 = turn.operations[1];
0211
0212         bool const switch_source = op0.enriched.region_id != -1
0213                 && op0.enriched.region_id == op1.enriched.region_id;
0214
0215 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
0216         if (switch_source)
0217         {
0218             std::cout << "Switch source at " << &turn << std::endl;
0219         }
0220         else
0221         {
0222             std::cout << "DON'T SWITCH SOURCES at " << &turn << std::endl;
0223         }
0224 #endif
0225         return switch_source
0226                 ? current.*Member != previous.*Member
0227                 : current.*Member == previous.*Member;
0228     }
0229
0230     inline bool select_source(turn_type const& turn,
0231                               segment_identifier const& candidate_seg_id,
0232                               segment_identifier const& previous_seg_id) const
0233     {
0234         // For uu/ii, only switch sources if indicated
0235
0236         if BOOST_GEOMETRY_CONSTEXPR (OverlayType == overlay_buffer)
0237         {
0238             // Buffer does not use source_index (always 0).
0239             return select_source_generic<&segment_identifier::multi_index>(
0240                         turn, candidate_seg_id, previous_seg_id);
0241         }
0242         else // else prevents unreachable code warning
0243         {
0244             if (is_self_turn<OverlayType>(turn))
0245             {
0246                 // Also, if it is a self-turn, stay on same ring (multi/ring)
0247                 return select_source_generic<&segment_identifier::multi_index>(
0248                             turn, candidate_seg_id, previous_seg_id);
0249             }
0250
0251             // Use source_index
0252             return select_source_generic<&segment_identifier::source_index>(
0253                         turn, candidate_seg_id, previous_seg_id);
0254         }
0255     }
0256
0257     inline bool traverse_possible(signed_size_type turn_index) const
0258     {
0259         if (turn_index == -1)
0260         {
0261             return false;
0262         }
0263
0264         turn_type const& turn = m_turns[turn_index];
0265
0266         // It is not a dead end if there is an operation to continue, or of
0267         // there is a cluster (assuming for now we can get out of the cluster)
0268         return turn.is_clustered()
0269             || turn.has(target_operation)
0270             || turn.has(operation_continue);
0271     }
0272
0273     inline std::size_t get_shortcut_level(turn_operation_type const& op,
0274                              signed_size_type start_turn_index,
0275                              signed_size_type origin_turn_index,
0276                              std::size_t level = 1) const
0277     {
0278         signed_size_type next_turn_index = op.enriched.get_next_turn_index();
0279         if (next_turn_index == -1)
0280         {
0281             return 0;
0282         }
0283         if (next_turn_index == start_turn_index)
0284         {
0285             // This operation finishes the ring
0286             return 0;
0287         }
0288         if (next_turn_index == origin_turn_index)
0289         {
0290             // This operation travels to itself
0291             return level;
0292         }
0293         if (level > 10)
0294         {
0295             // Avoid infinite recursion
0296             return 0;
0297         }
0298
0299         turn_type const& next_turn = m_turns[next_turn_index];
0300         for (int i = 0; i < 2; i++)
0301         {
0302             turn_operation_type const& next_op = next_turn.operations[i];
0303             if (next_op.operation == target_operation
0304                 && ! next_op.visited.finished()
0305                 && ! next_op.visited.visited())
0306             {
0307                 // Recursively continue verifying
0308                 if (get_shortcut_level(next_op, start_turn_index,
0309                                        origin_turn_index, level + 1))
0310                 {
0311                     return level + 1;
0312                 }
0313             }
0314         }
0315         return 0;
0316     }
0317
0318     inline
0319     bool select_cc_operation(turn_type const& turn,
0320                 signed_size_type start_turn_index,
0321                 int& selected_op_index) const
0322     {
0323         // For "cc", take either one, but if there is a starting one,
0324         //           take that one. If next is dead end, skip that one.
0325         // If both are valid candidates, take the one with minimal remaining
0326         // distance (important for #mysql_23023665 in buffer).
0327
0328         signed_size_type next[2] = {0};
0329         bool possible[2] = {0};
0330         bool close[2] = {0};
0331
0332         for (int i = 0; i < 2; i++)
0333         {
0334             next[i] = turn.operations[i].enriched.get_next_turn_index();
0335             possible[i] = traverse_possible(next[i]);
0336             close[i] = possible[i] && next[i] == start_turn_index;
0337         }
0338
0339         if (close[0] != close[1])
0340         {
0341             // One of the operations will finish the ring. Take that one.
0342             selected_op_index = close[0] ? 0 : 1;
0343             debug_traverse(turn, turn.operations[selected_op_index], "Candidate cc closing");
0344             return true;
0345         }
0346
0347         if BOOST_GEOMETRY_CONSTEXPR (OverlayType == overlay_buffer)
0348         {
0349             if (possible[0] && possible[1])
0350             {
0351                 // Buffers sometimes have multiple overlapping pieces, where remaining
0352                 // distance could lead to the wrong choice. Take the matching operation.
0353
0354                 bool is_target[2] = {0};
0355                 for (int i = 0; i < 2; i++)
0356                 {
0357                     turn_operation_type const& next_op = m_turns[next[i]].operations[i];
0358                     is_target[i] = next_op.operation == target_operation;
0359                 }
0360
0361                 if (is_target[0] != is_target[1])
0362                 {
0363                     // Take the matching operation
0364                     selected_op_index = is_target[0] ? 0 : 1;
0365                     debug_traverse(turn, turn.operations[selected_op_index], "Candidate cc target");
0366                     return true;
0367                 }
0368             }
0369         }
0370
0371         static bool const is_union = target_operation == operation_union;
0372
0373         typename turn_operation_type::comparable_distance_type
0374                 best_remaining_distance = 0;
0375
0376         bool result = false;
0377
0378         for (int i = 0; i < 2; i++)
0379         {
0380             if (!possible[i])
0381             {
0382                 continue;
0383             }
0384
0385             turn_operation_type const& op = turn.operations[i];
0386
0387             if (! result
0388                 || (is_union && op.remaining_distance > best_remaining_distance)
0389                 || (!is_union && op.remaining_distance < best_remaining_distance))
0390             {
0391                 debug_traverse(turn, op, "First candidate cc", ! result);
0392                 debug_traverse(turn, op, "Candidate cc override (remaining)",
0393                     result && op.remaining_distance < best_remaining_distance);
0394
0395                 selected_op_index = i;
0396                 best_remaining_distance = op.remaining_distance;
0397                 result = true;
0398             }
0399         }
0400
0401         return result;
0402     }
0403
0404     inline
0405     bool select_noncc_operation(turn_type const& turn,
0406                 segment_identifier const& previous_seg_id,
0407                 int& selected_op_index) const
0408     {
0409         bool result = false;
0410
0411         for (int i = 0; i < 2; i++)
0412         {
0413             turn_operation_type const& op = turn.operations[i];
0414
0415             if (op.operation == target_operation
0416                 && ! op.visited.finished()
0417                 && ! op.visited.visited()
0418                 && (! result || select_source(turn, op.seg_id, previous_seg_id)))
0419             {
0420                 selected_op_index = i;
0421                 debug_traverse(turn, op, "Candidate");
0422                 result = true;
0423             }
0424         }
0425
0426         return result;
0427     }
0428
0429     inline
0430     bool select_preferred_operation(turn_type const& turn,
0431                 signed_size_type turn_index,
0432                 signed_size_type start_turn_index,
0433                 int& selected_op_index) const
0434     {
0435         bool option[2] = {0};
0436         bool finishing[2] = {0};
0437         bool preferred[2] = {0};
0438         std::size_t shortcut_level[2] = {0};
0439         for (int i = 0; i < 2; i++)
0440         {
0441             turn_operation_type const& op = turn.operations[i];
0442
0443             if (op.operation == target_operation
0444                 && ! op.visited.finished()
0445                 && ! op.visited.visited())
0446             {
0447                 option[i] = true;
0448                 if (op.enriched.get_next_turn_index() == start_turn_index)
0449                 {
0450                     finishing[i] = true;
0451                 }
0452                 else
0453                 {
0454                     shortcut_level[i] = get_shortcut_level(op, start_turn_index,
0455                                                            turn_index);
0456                 }
0457
0458                 if (op.enriched.prefer_start)
0459                 {
0460                     preferred[i] = true;
0461                 }
0462             }
0463         }
0464
0465         if (option[0] != option[1])
0466         {
0467             // Only one operation is acceptable, take that one
0468             selected_op_index = option[0] ? 0 : 1;
0469             return true;
0470         }
0471
0472         if (option[0] && option[1])
0473         {
0474             // Both operations are acceptable
0475             if (finishing[0] != finishing[1])
0476             {
0477                 // Prefer operation finishing the ring
0478                 selected_op_index = finishing[0] ? 0 : 1;
0479                 return true;
0480             }
0481
0482             if (shortcut_level[0] != shortcut_level[1])
0483             {
0484                 // If a turn can travel to itself again (without closing the
0485                 // ring), take the shortest one
0486                 selected_op_index = shortcut_level[0] < shortcut_level[1] ? 0 : 1;
0487                 return true;
0488             }
0489
0490             if (preferred[0] != preferred[1])
0491             {
0492                 // Only one operation is preferred (== was not intersection)
0493                 selected_op_index = preferred[0] ? 0 : 1;
0494                 return true;
0495             }
0496         }
0497
0498         for (int i = 0; i < 2; i++)
0499         {
0500             if (option[i])
0501             {
0502                 selected_op_index = 0;
0503                 return true;
0504             }
0505         }
0506
0507         return false;
0508     }
0509
0510     inline
0511     bool select_operation(turn_type const& turn,
0512                 signed_size_type turn_index,
0513                 signed_size_type start_turn_index,
0514                 segment_identifier const& previous_seg_id,
0515                 int& selected_op_index) const
0516     {
0517         bool result = false;
0518         selected_op_index = -1;
0519         if (turn.both(operation_continue))
0520         {
0521             result = select_cc_operation(turn, start_turn_index,
0522                                          selected_op_index);
0523         }
0524         else if BOOST_GEOMETRY_CONSTEXPR (OverlayType == overlay_dissolve)
0525         {
0526             result = select_preferred_operation(turn, turn_index,
0527                 start_turn_index, selected_op_index);
0528         }
0529         else
0530         {
0531             result = select_noncc_operation(turn, previous_seg_id,
0532                 selected_op_index);
0533         }
0534         if (result)
0535         {
0536            debug_traverse(turn, turn.operations[selected_op_index], "Accepted");
0537         }
0538
0539         return result;
0540     }
0541
0542     inline int starting_operation_index(turn_type const& turn) const
0543     {
0544         for (int i = 0; i < 2; i++)
0545         {
0546             if (turn.operations[i].visited.started())
0547             {
0548                 return i;
0549             }
0550         }
0551         return -1;
0552     }
0553
0554     inline bool both_finished(turn_type const& turn) const
0555     {
0556         for (int i = 0; i < 2; i++)
0557         {
0558             if (! turn.operations[i].visited.finished())
0559             {
0560                 return false;
0561             }
0562         }
0563         return true;
0564     }
0565
0566     // Returns a priority, the one with the highst priority will be selected
0567     //   0: not OK
0568     //   1: OK following spike out
0569     //   2: OK but next turn is in same cluster
0570     //   3: OK
0571     //   4: OK and start turn matches
0572     //   5: OK and start turn and start operation both match, this is the best
0573     inline int priority_of_turn_in_cluster_union(sort_by_side::rank_type selected_rank,
0574             typename sbs_type::rp const& ranked_point,
0575             cluster_info const& cinfo,
0576             signed_size_type start_turn_index, int start_op_index) const
0577     {
0578         if (ranked_point.rank != selected_rank
0579             || ranked_point.direction != sort_by_side::dir_to)
0580         {
0581             return 0;
0582         }
0583
0584         auto const& turn = m_turns[ranked_point.turn_index];
0585         auto const& op = turn.operations[ranked_point.operation_index];
0586
0587         // Check finalized: TODO: this should be finetuned, it is not necessary
0588         if (op.visited.finalized())
0589         {
0590             return 0;
0591         }
0592
0593         if BOOST_GEOMETRY_CONSTEXPR (OverlayType != overlay_dissolve)
0594         {
0595             if (op.enriched.count_left != 0 || op.enriched.count_right == 0)
0596             {
0597                 // Check counts: in some cases interior rings might be generated with
0598                 // polygons on both sides. For dissolve it can be anything.
0599
0600                 // If this forms a spike, going to/from the cluster point in the same
0601                 // (opposite) direction, it can still be used.
0602                 return cinfo.spike_count > 0 ? 1 : 0;
0603             }
0604         }
0605
0606         bool const to_start = ranked_point.turn_index == start_turn_index;
0607         bool const to_start_index = ranked_point.operation_index == start_op_index;
0608
0609         bool const next_in_same_cluster
0610                 = cinfo.turn_indices.count(op.enriched.get_next_turn_index()) > 0;
0611
0612         // Return the priority as described above
0613         return to_start && to_start_index ? 5
0614             : to_start ? 4
0615             : next_in_same_cluster ? 2
0616             : 3
0617             ;
0618     }
0619
0620     template <typename RankedPoint>
0621     inline turn_operation_type const& operation_from_rank(RankedPoint const& rp) const
0622     {
0623         return m_turns[rp.turn_index].operations[rp.operation_index];
0624     }
0625
0626     inline sort_by_side::rank_type select_rank(sbs_type const& sbs) const
0627     {
0628         static bool const is_intersection
0629                 = target_operation == operation_intersection;
0630
0631         // Take the first outgoing rank corresponding to incoming region,
0632         // or take another region if it is not isolated
0633         auto const& in_op = operation_from_rank(sbs.m_ranked_points.front());
0634
0635         for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
0636         {
0637             auto const& rp = sbs.m_ranked_points[i];
0638             if (rp.rank == 0 || rp.direction == sort_by_side::dir_from)
0639             {
0640                 continue;
0641             }
0642             auto const& out_op = operation_from_rank(rp);
0643
0644             if (out_op.operation != target_operation
0645                 && out_op.operation != operation_continue)
0646             {
0647                 continue;
0648             }
0649
0650             if (in_op.enriched.region_id == out_op.enriched.region_id
0651                 || (is_intersection && ! out_op.enriched.isolated))
0652             {
0653                 // Region corresponds to incoming region, or (for intersection)
0654                 // there is a non-isolated other region which should be taken
0655                 return rp.rank;
0656             }
0657         }
0658         return -1;
0659     }
0660
0661     inline bool select_from_cluster_union(signed_size_type& turn_index,
0662         cluster_info const& cinfo,
0663         int& op_index, sbs_type const& sbs,
0664         signed_size_type start_turn_index, int start_op_index) const
0665     {
0666         sort_by_side::rank_type const selected_rank = select_rank(sbs);
0667
0668         int current_priority = 0;
0669         for (std::size_t i = 1; i < sbs.m_ranked_points.size(); i++)
0670         {
0671             auto const& ranked_point = sbs.m_ranked_points[i];
0672
0673             if (ranked_point.rank > selected_rank)
0674             {
0675                 break;
0676             }
0677
0678             int const priority = priority_of_turn_in_cluster_union(selected_rank,
0679                 ranked_point, cinfo, start_turn_index, start_op_index);
0680
0681             if (priority > current_priority)
0682             {
0683                 current_priority = priority;
0684                 turn_index = ranked_point.turn_index;
0685                 op_index = ranked_point.operation_index;
0686             }
0687         }
0688         return current_priority > 0;
0689     }
0690
0691     inline bool analyze_cluster_intersection(signed_size_type& turn_index,
0692                 int& op_index, sbs_type const& sbs) const
0693     {
0694         // Select the rank based on regions and isolation
0695         sort_by_side::rank_type const selected_rank = select_rank(sbs);
0696
0697         if (selected_rank <= 0)
0698         {
0699             return false;
0700         }
0701
0702         // From these ranks, select the index: the first, or the one with
0703         // the smallest remaining distance
0704         typename turn_operation_type::comparable_distance_type
0705                 min_remaining_distance = 0;
0706
0707         std::size_t selected_index = sbs.m_ranked_points.size();
0708         for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
0709         {
0710             auto const& ranked_point = sbs.m_ranked_points[i];
0711
0712             if (ranked_point.rank > selected_rank)
0713             {
0714                 break;
0715             }
0716             else if (ranked_point.rank == selected_rank)
0717             {
0718                 auto const& op = operation_from_rank(ranked_point);
0719
0720                 if (op.visited.finalized())
0721                 {
0722                     // This direction is already traveled,
0723                     // it cannot be traveled again
0724                     continue;
0725                 }
0726
0727                 if (selected_index == sbs.m_ranked_points.size()
0728                         || op.remaining_distance < min_remaining_distance)
0729                 {
0730                     // It was unassigned or it is better
0731                     selected_index = i;
0732                     min_remaining_distance = op.remaining_distance;
0733                 }
0734             }
0735         }
0736
0737         if (selected_index == sbs.m_ranked_points.size())
0738         {
0739             // Should not happen, there must be points with the selected rank
0740             return false;
0741         }
0742
0743         auto const& ranked_point = sbs.m_ranked_points[selected_index];
0744         turn_index = ranked_point.turn_index;
0745         op_index = ranked_point.operation_index;
0746         return true;
0747     }
0748
0749     inline bool fill_sbs(sbs_type& sbs,
0750                          signed_size_type turn_index,
0751                          std::set<signed_size_type> const& cluster_indices,
0752                          segment_identifier const& previous_seg_id) const
0753     {
0754
0755         for (auto cluster_turn_index : cluster_indices)
0756         {
0757             turn_type const& cluster_turn = m_turns[cluster_turn_index];
0758             if (cluster_turn.discarded)
0759             {
0760                 // Defensive check, discarded turns should not be in cluster
0761                 continue;
0762             }
0763
0764             for (int i = 0; i < 2; i++)
0765             {
0766                 sbs.add(cluster_turn,
0767                         cluster_turn.operations[i],
0768                         cluster_turn_index, i, previous_seg_id,
0769                         m_geometry1, m_geometry2,
0770                         cluster_turn_index == turn_index);
0771             }
0772         }
0773
0774         if (! sbs.has_origin())
0775         {
0776             return false;
0777         }
0778         turn_type const& turn = m_turns[turn_index];
0779         sbs.apply(turn.point);
0780         return true;
0781     }
0782
0783
0784     inline bool select_turn_from_cluster(signed_size_type& turn_index,
0785             int& op_index,
0786             signed_size_type start_turn_index, int start_op_index,
0787             segment_identifier const& previous_seg_id) const
0788     {
0789         bool const is_union = target_operation == operation_union;
0790
0791         turn_type const& turn = m_turns[turn_index];
0792         BOOST_ASSERT(turn.is_clustered());
0793
0794         auto mit = m_clusters.find(turn.cluster_id);
0795         BOOST_ASSERT(mit != m_clusters.end());
0796
0797         cluster_info const& cinfo = mit->second;
0798
0799         sbs_type sbs(m_strategy);
0800
0801         if (! fill_sbs(sbs, turn_index, cinfo.turn_indices, previous_seg_id))
0802         {
0803             return false;
0804         }
0805
0806         if BOOST_GEOMETRY_CONSTEXPR (is_union)
0807         {
0808             if (cinfo.open_count == 0 && cinfo.spike_count > 0)
0809             {
0810                 // Leave the cluster from the spike.
0811                 for (std::size_t i = 0; i + 1 < sbs.m_ranked_points.size(); i++)
0812                 {
0813                     auto const& current = sbs.m_ranked_points[i];
0814                     auto const& next = sbs.m_ranked_points[i + 1];
0815                     if (current.rank == next.rank
0816                         && current.direction == detail::overlay::sort_by_side::dir_from
0817                         && next.direction == detail::overlay::sort_by_side::dir_to)
0818                     {
0819                         turn_index = next.turn_index;
0820                         op_index = next.operation_index;
0821                         return true;
0822                     }
0823                 }
0824             }
0825         }
0826
0827         cluster_exits<OverlayType, Turns, sbs_type> exits(m_turns, cinfo.turn_indices, sbs);
0828
0829         if (exits.apply(turn_index, op_index))
0830         {
0831             return true;
0832         }
0833
0834         bool result = false;
0835
0836         if BOOST_GEOMETRY_CONSTEXPR (is_union)
0837         {
0838             result = select_from_cluster_union(turn_index, cinfo,
0839                                                op_index, sbs,
0840                                                start_turn_index, start_op_index);
0841             if (! result)
0842             {
0843                // There no way out found, try second pass in collected cluster exits
0844                result = exits.apply(turn_index, op_index, false);
0845             }
0846         }
0847         else
0848         {
0849             result = analyze_cluster_intersection(turn_index, op_index, sbs);
0850         }
0851         return result;
0852     }
0853
0854     // Analyzes a non-clustered "ii" intersection, as if it is clustered.
0855     inline bool analyze_ii_intersection(signed_size_type& turn_index, int& op_index,
0856                     turn_type const& current_turn,
0857                     segment_identifier const& previous_seg_id)
0858     {
0859         sbs_type sbs(m_strategy);
0860
0861         // Add this turn to the sort-by-side sorter
0862         for (int i = 0; i < 2; i++)
0863         {
0864             sbs.add(current_turn,
0865                     current_turn.operations[i],
0866                     turn_index, i, previous_seg_id,
0867                     m_geometry1, m_geometry2,
0868                     true);
0869         }
0870
0871         if (! sbs.has_origin())
0872         {
0873             return false;
0874         }
0875
0876         sbs.apply(current_turn.point);
0877
0878         bool result = analyze_cluster_intersection(turn_index, op_index, sbs);
0879
0880         return result;
0881     }
0882
0883     inline void change_index_for_self_turn(signed_size_type& to_vertex_index,
0884                 turn_type const& start_turn,
0885                 turn_operation_type const& start_op,
0886                 int start_op_index) const
0887     {
0888         if BOOST_GEOMETRY_CONSTEXPR (OverlayType != overlay_buffer
0889                                   && OverlayType != overlay_dissolve)
0890         {
0891             return;
0892         }
0893         else // else prevents unreachable code warning
0894         {
0895             const bool allow_uu = OverlayType != overlay_buffer;
0896
0897             // It travels to itself, can happen. If this is a buffer, it can
0898             // sometimes travel to itself in the following configuration:
0899             //
0900             // +---->--+
0901             // |       |
0902             // |   +---*----+ *: one turn, with segment index 2/7
0903             // |   |   |    |
0904             // |   +---C    | C: closing point (start/end)
0905             // |            |
0906             // +------------+
0907             //
0908             // If it starts on segment 2 and travels to itself on segment 2, that
0909             // should be corrected to 7 because that is the shortest path
0910             //
0911             // Also a uu turn (touching with another buffered ring) might have this
0912             // apparent configuration, but there it should
0913             // always travel the whole ring
0914
0915             turn_operation_type const& other_op
0916                     = start_turn.operations[1 - start_op_index];
0917
0918             bool const correct
0919                     = (allow_uu || ! start_turn.both(operation_union))
0920                       && start_op.seg_id.source_index == other_op.seg_id.source_index
0921                       && start_op.seg_id.multi_index == other_op.seg_id.multi_index
0922                       && start_op.seg_id.ring_index == other_op.seg_id.ring_index
0923                       && start_op.seg_id.segment_index == to_vertex_index;
0924
0925 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
0926             std::cout << " WARNING: self-buffer "
0927                       << " correct=" << correct
0928                       << " turn=" << operation_char(start_turn.operations[0].operation)
0929                       << operation_char(start_turn.operations[1].operation)
0930                       << " start=" << start_op.seg_id.segment_index
0931                       << " from=" << to_vertex_index
0932                       << " to=" << other_op.enriched.travels_to_vertex_index
0933                       << std::endl;
0934 #endif
0935
0936             if (correct)
0937             {
0938                 to_vertex_index = other_op.enriched.travels_to_vertex_index;
0939             }
0940         }
0941     }
0942
0943     bool select_turn_from_enriched(signed_size_type& turn_index,
0944             segment_identifier& previous_seg_id,
0945             signed_size_type& to_vertex_index,
0946             signed_size_type start_turn_index,
0947             int start_op_index,
0948             turn_type const& previous_turn,
0949             turn_operation_type const& previous_op,
0950             bool is_start) const
0951     {
0952         to_vertex_index = -1;
0953
0954         if (previous_op.enriched.next_ip_index < 0)
0955         {
0956             // There is no next IP on this segment
0957             if (previous_op.enriched.travels_to_vertex_index < 0
0958                 || previous_op.enriched.travels_to_ip_index < 0)
0959             {
0960                 return false;
0961             }
0962
0963             to_vertex_index = previous_op.enriched.travels_to_vertex_index;
0964
0965             if (is_start &&
0966                     previous_op.enriched.travels_to_ip_index == start_turn_index)
0967             {
0968                 change_index_for_self_turn(to_vertex_index, previous_turn,
0969                     previous_op, start_op_index);
0970             }
0971
0972             turn_index = previous_op.enriched.travels_to_ip_index;
0973             previous_seg_id = previous_op.seg_id;
0974         }
0975         else
0976         {
0977             // Take the next IP on this segment
0978             turn_index = previous_op.enriched.next_ip_index;
0979             previous_seg_id = previous_op.seg_id;
0980         }
0981         return true;
0982     }
0983
0984     bool select_turn(signed_size_type start_turn_index, int start_op_index,
0985                      signed_size_type& turn_index,
0986                      int& op_index,
0987                      int previous_op_index,
0988                      signed_size_type previous_turn_index,
0989                      segment_identifier const& previous_seg_id,
0990                      bool is_start, bool has_points)
0991     {
0992         turn_type const& current_turn = m_turns[turn_index];
0993
0994         bool const back_at_start_cluster
0995                 = has_points
0996                 && current_turn.is_clustered()
0997                 && m_turns[start_turn_index].cluster_id == current_turn.cluster_id;
0998         if BOOST_GEOMETRY_CONSTEXPR (target_operation == operation_intersection)
0999         {
1000             // Intersection or difference
1001
1002             if (has_points && (turn_index == start_turn_index || back_at_start_cluster))
1003             {
1004                 // Intersection can always be finished if returning
1005                 turn_index = start_turn_index;
1006                 op_index = start_op_index;
1007                 return true;
1008             }
1009
1010             if (! current_turn.is_clustered()
1011                 && current_turn.both(operation_intersection)
1012                 && analyze_ii_intersection(turn_index, op_index,
1013                             current_turn, previous_seg_id))
1014             {
1015                 return true;
1016             }
1017         }
1018         else if (turn_index == start_turn_index || back_at_start_cluster)
1019         {
1020             // Union or buffer: cannot return immediately to starting turn, because it then
1021             // might miss a formed multi polygon with a touching point.
1022             auto const& current_op = current_turn.operations[op_index];
1023             signed_size_type const next_turn_index = current_op.enriched.get_next_turn_index();
1024             bool const to_other_turn = next_turn_index >= 0 && m_turns[next_turn_index].cluster_id != current_turn.cluster_id;
1025             if (! to_other_turn)
1026             {
1027                 // Return to starting point
1028                 turn_index = start_turn_index;
1029                 op_index = start_op_index;
1030                 return true;
1031             }
1032         }
1033
1034         if (current_turn.is_clustered())
1035         {
1036             if (! select_turn_from_cluster(turn_index, op_index,
1037                     start_turn_index, start_op_index, previous_seg_id))
1038             {
1039                 return false;
1040             }
1041
1042             if (is_start && turn_index == previous_turn_index)
1043             {
1044                 op_index = previous_op_index;
1045             }
1046         }
1047         else
1048         {
1049             op_index = starting_operation_index(current_turn);
1050             if (op_index == -1)
1051             {
1052                 if (both_finished(current_turn))
1053                 {
1054                     return false;
1055                 }
1056
1057                 if (! select_operation(current_turn, turn_index,
1058                                 start_turn_index,
1059                                 previous_seg_id,
1060                                 op_index))
1061                 {
1062                     return false;
1063                 }
1064             }
1065         }
1066         return true;
1067     }
1068
1069 private :
1070     Geometry1 const& m_geometry1;
1071     Geometry2 const& m_geometry2;
1072     Turns& m_turns;
1073     Clusters const& m_clusters;
1074     RobustPolicy const& m_robust_policy;
1075     Strategy m_strategy;
1076     Visitor& m_visitor;
1077 };
1078
1079
1080
1081 }} // namespace detail::overlay
1082 #endif // DOXYGEN_NO_DETAIL
1083
1084 }} // namespace boost::geometry
1085
1086 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP