detail/overlay/traversal.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // This file was modified by Oracle on 2017-2020.
0006 // Modifications copyright (c) 2017-2020 Oracle and/or its affiliates.
0007
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/condition.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 SideStrategy,
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, SideStrategy, 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, SideStrategy 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_CONDITION(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
0243         if (is_self_turn<OverlayType>(turn))
0244         {
0245             // Also, if it is a self-turn, stay on same ring (multi/ring)
0246             return select_source_generic<&segment_identifier::multi_index>(
0247                         turn, candidate_seg_id, previous_seg_id);
0248         }
0249
0250         // Use source_index
0251         return select_source_generic<&segment_identifier::source_index>(
0252                     turn, candidate_seg_id, previous_seg_id);
0253     }
0254
0255     inline bool traverse_possible(signed_size_type turn_index) const
0256     {
0257         if (turn_index == -1)
0258         {
0259             return false;
0260         }
0261
0262         turn_type const& turn = m_turns[turn_index];
0263
0264         // It is not a dead end if there is an operation to continue, or of
0265         // there is a cluster (assuming for now we can get out of the cluster)
0266         return turn.is_clustered()
0267             || turn.has(target_operation)
0268             || turn.has(operation_continue);
0269     }
0270
0271     inline std::size_t get_shortcut_level(turn_operation_type const& op,
0272                              signed_size_type start_turn_index,
0273                              signed_size_type origin_turn_index,
0274                              std::size_t level = 1) const
0275     {
0276         signed_size_type next_turn_index = op.enriched.get_next_turn_index();
0277         if (next_turn_index == -1)
0278         {
0279             return 0;
0280         }
0281         if (next_turn_index == start_turn_index)
0282         {
0283             // This operation finishes the ring
0284             return 0;
0285         }
0286         if (next_turn_index == origin_turn_index)
0287         {
0288             // This operation travels to itself
0289             return level;
0290         }
0291         if (level > 10)
0292         {
0293             // Avoid infinite recursion
0294             return 0;
0295         }
0296
0297         turn_type const& next_turn = m_turns[next_turn_index];
0298         for (int i = 0; i < 2; i++)
0299         {
0300             turn_operation_type const& next_op = next_turn.operations[i];
0301             if (next_op.operation == target_operation
0302                 && ! next_op.visited.finished()
0303                 && ! next_op.visited.visited())
0304             {
0305                 // Recursively continue verifying
0306                 if (get_shortcut_level(next_op, start_turn_index,
0307                                        origin_turn_index, level + 1))
0308                 {
0309                     return level + 1;
0310                 }
0311             }
0312         }
0313         return 0;
0314     }
0315
0316     inline
0317     bool select_cc_operation(turn_type const& turn,
0318                 signed_size_type start_turn_index,
0319                 int& selected_op_index) const
0320     {
0321         // For "cc", take either one, but if there is a starting one,
0322         //           take that one. If next is dead end, skip that one.
0323         // If both are valid candidates, take the one with minimal remaining
0324         // distance (important for #mysql_23023665 in buffer).
0325
0326         signed_size_type next[2] = {0};
0327         bool possible[2] = {0};
0328         bool close[2] = {0};
0329
0330         for (int i = 0; i < 2; i++)
0331         {
0332             next[i] = turn.operations[i].enriched.get_next_turn_index();
0333             possible[i] = traverse_possible(next[i]);
0334             close[i] = possible[i] && next[i] == start_turn_index;
0335         }
0336
0337         if (close[0] != close[1])
0338         {
0339             // One of the operations will finish the ring. Take that one.
0340             selected_op_index = close[0] ? 0 : 1;
0341             debug_traverse(turn, turn.operations[selected_op_index], "Candidate cc closing");
0342             return true;
0343         }
0344
0345         if (BOOST_GEOMETRY_CONDITION(OverlayType == overlay_buffer)
0346             && possible[0] && possible[1])
0347         {
0348             // Buffers sometimes have multiple overlapping pieces, where remaining
0349             // distance could lead to the wrong choice. Take the matching operation.
0350
0351             bool is_target[2] = {0};
0352             for (int i = 0; i < 2; i++)
0353             {
0354                 turn_operation_type const& next_op = m_turns[next[i]].operations[i];
0355                 is_target[i] = next_op.operation == target_operation;
0356             }
0357
0358             if (is_target[0] != is_target[1])
0359             {
0360                 // Take the matching operation
0361                 selected_op_index = is_target[0] ? 0 : 1;
0362                 debug_traverse(turn, turn.operations[selected_op_index], "Candidate cc target");
0363                 return true;
0364             }
0365         }
0366
0367         static bool const is_union = target_operation == operation_union;
0368
0369         typename turn_operation_type::comparable_distance_type
0370                 best_remaining_distance = 0;
0371
0372         bool result = false;
0373
0374         for (int i = 0; i < 2; i++)
0375         {
0376             if (!possible[i])
0377             {
0378                 continue;
0379             }
0380
0381             turn_operation_type const& op = turn.operations[i];
0382
0383             if (! result
0384                 || (is_union && op.remaining_distance > best_remaining_distance)
0385                 || (!is_union && op.remaining_distance < best_remaining_distance))
0386             {
0387                 debug_traverse(turn, op, "First candidate cc", ! result);
0388                 debug_traverse(turn, op, "Candidate cc override (remaining)",
0389                     result && op.remaining_distance < best_remaining_distance);
0390
0391                 selected_op_index = i;
0392                 best_remaining_distance = op.remaining_distance;
0393                 result = true;
0394             }
0395         }
0396
0397         return result;
0398     }
0399
0400     inline
0401     bool select_noncc_operation(turn_type const& turn,
0402                 segment_identifier const& previous_seg_id,
0403                 int& selected_op_index) const
0404     {
0405         bool result = false;
0406
0407         for (int i = 0; i < 2; i++)
0408         {
0409             turn_operation_type const& op = turn.operations[i];
0410
0411             if (op.operation == target_operation
0412                 && ! op.visited.finished()
0413                 && ! op.visited.visited()
0414                 && (! result || select_source(turn, op.seg_id, previous_seg_id)))
0415             {
0416                 selected_op_index = i;
0417                 debug_traverse(turn, op, "Candidate");
0418                 result = true;
0419             }
0420         }
0421
0422         return result;
0423     }
0424
0425     inline
0426     bool select_preferred_operation(turn_type const& turn,
0427                 signed_size_type turn_index,
0428                 signed_size_type start_turn_index,
0429                 int& selected_op_index) const
0430     {
0431         bool option[2] = {0};
0432         bool finishing[2] = {0};
0433         bool preferred[2] = {0};
0434         std::size_t shortcut_level[2] = {0};
0435         for (int i = 0; i < 2; i++)
0436         {
0437             turn_operation_type const& op = turn.operations[i];
0438
0439             if (op.operation == target_operation
0440                 && ! op.visited.finished()
0441                 && ! op.visited.visited())
0442             {
0443                 option[i] = true;
0444                 if (op.enriched.get_next_turn_index() == start_turn_index)
0445                 {
0446                     finishing[i] = true;
0447                 }
0448                 else
0449                 {
0450                     shortcut_level[i] = get_shortcut_level(op, start_turn_index,
0451                                                            turn_index);
0452                 }
0453
0454                 if (op.enriched.prefer_start)
0455                 {
0456                     preferred[i] = true;
0457                 }
0458             }
0459         }
0460
0461         if (option[0] != option[1])
0462         {
0463             // Only one operation is acceptable, take that one
0464             selected_op_index = option[0] ? 0 : 1;
0465             return true;
0466         }
0467
0468         if (option[0] && option[1])
0469         {
0470             // Both operations are acceptable
0471             if (finishing[0] != finishing[1])
0472             {
0473                 // Prefer operation finishing the ring
0474                 selected_op_index = finishing[0] ? 0 : 1;
0475                 return true;
0476             }
0477
0478             if (shortcut_level[0] != shortcut_level[1])
0479             {
0480                 // If a turn can travel to itself again (without closing the
0481                 // ring), take the shortest one
0482                 selected_op_index = shortcut_level[0] < shortcut_level[1] ? 0 : 1;
0483                 return true;
0484             }
0485
0486             if (preferred[0] != preferred[1])
0487             {
0488                 // Only one operation is preferred (== was not intersection)
0489                 selected_op_index = preferred[0] ? 0 : 1;
0490                 return true;
0491             }
0492         }
0493
0494         for (int i = 0; i < 2; i++)
0495         {
0496             if (option[i])
0497             {
0498                 selected_op_index = 0;
0499                 return true;
0500             }
0501         }
0502
0503         return false;
0504     }
0505
0506     inline
0507     bool select_operation(turn_type const& turn,
0508                 signed_size_type turn_index,
0509                 signed_size_type start_turn_index,
0510                 segment_identifier const& previous_seg_id,
0511                 int& selected_op_index) const
0512     {
0513         bool result = false;
0514         selected_op_index = -1;
0515         if (turn.both(operation_continue))
0516         {
0517             result = select_cc_operation(turn, start_turn_index,
0518                                          selected_op_index);
0519         }
0520         else if (BOOST_GEOMETRY_CONDITION(OverlayType == overlay_dissolve))
0521         {
0522             result = select_preferred_operation(turn, turn_index,
0523                 start_turn_index, selected_op_index);
0524         }
0525         else
0526         {
0527             result = select_noncc_operation(turn, previous_seg_id,
0528                 selected_op_index);
0529         }
0530         if (result)
0531         {
0532            debug_traverse(turn, turn.operations[selected_op_index], "Accepted");
0533         }
0534
0535         return result;
0536     }
0537
0538     inline int starting_operation_index(turn_type const& turn) const
0539     {
0540         for (int i = 0; i < 2; i++)
0541         {
0542             if (turn.operations[i].visited.started())
0543             {
0544                 return i;
0545             }
0546         }
0547         return -1;
0548     }
0549
0550     inline bool both_finished(turn_type const& turn) const
0551     {
0552         for (int i = 0; i < 2; i++)
0553         {
0554             if (! turn.operations[i].visited.finished())
0555             {
0556                 return false;
0557             }
0558         }
0559         return true;
0560     }
0561
0562     inline int priority_of_turn_in_cluster_union(sort_by_side::rank_type selected_rank,
0563             typename sbs_type::rp const& ranked_point,
0564             std::set<signed_size_type> const& cluster_indices,
0565             signed_size_type start_turn_index, int start_op_index) const
0566     {
0567         // Returns 0: not OK
0568         // Returns 1: OK but next turn is in same cluster
0569         // Returns 2: OK
0570         // Returns 3: OK and start turn matches
0571         // Returns 4: OK and start turn and start op both match
0572         if (ranked_point.rank != selected_rank
0573             || ranked_point.direction != sort_by_side::dir_to)
0574         {
0575             return 0;
0576         }
0577
0578         auto const& turn = m_turns[ranked_point.turn_index];
0579         auto const& op = turn.operations[ranked_point.operation_index];
0580
0581         // Check finalized: TODO: this should be finetuned, it is not necessary
0582         if (op.visited.finalized())
0583         {
0584             return 0;
0585         }
0586
0587         if (BOOST_GEOMETRY_CONDITION(OverlayType != overlay_dissolve)
0588             && (op.enriched.count_left != 0 || op.enriched.count_right == 0))
0589         {
0590             // Check counts: in some cases interior rings might be generated with
0591             // polygons on both sides. For dissolve it can be anything.
0592             return 0;
0593         }
0594
0595         bool const to_start = ranked_point.turn_index == start_turn_index;
0596         bool const to_start_index = ranked_point.operation_index == start_op_index;
0597
0598         bool const next_in_same_cluster
0599                 = cluster_indices.count(op.enriched.get_next_turn_index()) > 0;
0600
0601         return to_start && to_start_index ? 4
0602             : to_start ? 3
0603             : next_in_same_cluster ? 1
0604             : 2
0605             ;
0606     }
0607
0608     template <typename RankedPoint>
0609     inline turn_operation_type const& operation_from_rank(RankedPoint const& rp) const
0610     {
0611         return m_turns[rp.turn_index].operations[rp.operation_index];
0612     }
0613
0614     inline sort_by_side::rank_type select_rank(sbs_type const& sbs) const
0615     {
0616         static bool const is_intersection
0617                 = target_operation == operation_intersection;
0618
0619         // Take the first outgoing rank corresponding to incoming region,
0620         // or take another region if it is not isolated
0621         auto const& in_op = operation_from_rank(sbs.m_ranked_points.front());
0622
0623         for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
0624         {
0625             auto const& rp = sbs.m_ranked_points[i];
0626             if (rp.rank == 0 || rp.direction == sort_by_side::dir_from)
0627             {
0628                 continue;
0629             }
0630             auto const& out_op = operation_from_rank(rp);
0631
0632             if (out_op.operation != target_operation
0633                 && out_op.operation != operation_continue)
0634             {
0635                 continue;
0636             }
0637
0638             if (in_op.enriched.region_id == out_op.enriched.region_id
0639                 || (is_intersection && ! out_op.enriched.isolated))
0640             {
0641                 // Region corresponds to incoming region, or (for intersection)
0642                 // there is a non-isolated other region which should be taken
0643                 return rp.rank;
0644             }
0645         }
0646         return -1;
0647     }
0648
0649     inline bool select_from_cluster_union(signed_size_type& turn_index,
0650         std::set<signed_size_type> const& cluster_indices,
0651         int& op_index, sbs_type const& sbs,
0652         signed_size_type start_turn_index, int start_op_index) const
0653     {
0654         sort_by_side::rank_type const selected_rank = select_rank(sbs);
0655
0656         int current_priority = 0;
0657         for (std::size_t i = 1; i < sbs.m_ranked_points.size(); i++)
0658         {
0659             typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i];
0660
0661             if (ranked_point.rank > selected_rank)
0662             {
0663                 break;
0664             }
0665
0666             int const priority = priority_of_turn_in_cluster_union(selected_rank,
0667                 ranked_point, cluster_indices, start_turn_index, start_op_index);
0668
0669             if (priority > current_priority)
0670             {
0671                 current_priority = priority;
0672                 turn_index = ranked_point.turn_index;
0673                 op_index = ranked_point.operation_index;
0674             }
0675         }
0676         return current_priority > 0;
0677     }
0678
0679     inline bool analyze_cluster_intersection(signed_size_type& turn_index,
0680                 int& op_index, sbs_type const& sbs) const
0681     {
0682         // Select the rank based on regions and isolation
0683         sort_by_side::rank_type const selected_rank = select_rank(sbs);
0684
0685         if (selected_rank <= 0)
0686         {
0687             return false;
0688         }
0689
0690         // From these ranks, select the index: the first, or the one with
0691         // the smallest remaining distance
0692         typename turn_operation_type::comparable_distance_type
0693                 min_remaining_distance = 0;
0694
0695         std::size_t selected_index = sbs.m_ranked_points.size();
0696         for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
0697         {
0698             auto const& ranked_point = sbs.m_ranked_points[i];
0699
0700             if (ranked_point.rank > selected_rank)
0701             {
0702                 break;
0703             }
0704             else if (ranked_point.rank == selected_rank)
0705             {
0706                 auto const& op = operation_from_rank(ranked_point);
0707
0708                 if (op.visited.finalized())
0709                 {
0710                     // This direction is already traveled,
0711                     // it cannot be traveled again
0712                     continue;
0713                 }
0714
0715                 if (selected_index == sbs.m_ranked_points.size()
0716                         || op.remaining_distance < min_remaining_distance)
0717                 {
0718                     // It was unassigned or it is better
0719                     selected_index = i;
0720                     min_remaining_distance = op.remaining_distance;
0721                 }
0722             }
0723         }
0724
0725         if (selected_index == sbs.m_ranked_points.size())
0726         {
0727             // Should not happen, there must be points with the selected rank
0728             return false;
0729         }
0730
0731         auto const& ranked_point = sbs.m_ranked_points[selected_index];
0732         turn_index = ranked_point.turn_index;
0733         op_index = ranked_point.operation_index;
0734         return true;
0735     }
0736
0737     inline bool fill_sbs(sbs_type& sbs,
0738                          signed_size_type turn_index,
0739                          std::set<signed_size_type> const& cluster_indices,
0740                          segment_identifier const& previous_seg_id) const
0741     {
0742
0743         for (auto cluster_turn_index : cluster_indices)
0744         {
0745             turn_type const& cluster_turn = m_turns[cluster_turn_index];
0746             if (cluster_turn.discarded)
0747             {
0748                 // Defensive check, discarded turns should not be in cluster
0749                 continue;
0750             }
0751
0752             for (int i = 0; i < 2; i++)
0753             {
0754                 sbs.add(cluster_turn,
0755                         cluster_turn.operations[i],
0756                         cluster_turn_index, i, previous_seg_id,
0757                         m_geometry1, m_geometry2,
0758                         cluster_turn_index == turn_index);
0759             }
0760         }
0761
0762         if (! sbs.has_origin())
0763         {
0764             return false;
0765         }
0766         turn_type const& turn = m_turns[turn_index];
0767         sbs.apply(turn.point);
0768         return true;
0769     }
0770
0771
0772     inline bool select_turn_from_cluster(signed_size_type& turn_index,
0773             int& op_index,
0774             signed_size_type start_turn_index, int start_op_index,
0775             segment_identifier const& previous_seg_id) const
0776     {
0777         bool const is_union = target_operation == operation_union;
0778
0779         turn_type const& turn = m_turns[turn_index];
0780         BOOST_ASSERT(turn.is_clustered());
0781
0782         auto mit = m_clusters.find(turn.cluster_id);
0783         BOOST_ASSERT(mit != m_clusters.end());
0784
0785         cluster_info const& cinfo = mit->second;
0786
0787         sbs_type sbs(m_strategy);
0788
0789         if (! fill_sbs(sbs, turn_index, cinfo.turn_indices, previous_seg_id))
0790         {
0791             return false;
0792         }
0793
0794         cluster_exits<OverlayType, Turns, sbs_type> exits(m_turns, cinfo.turn_indices, sbs);
0795
0796         if (exits.apply(turn_index, op_index))
0797         {
0798             return true;
0799         }
0800
0801         bool result = false;
0802
0803         if (is_union)
0804         {
0805             result = select_from_cluster_union(turn_index, cinfo.turn_indices,
0806                                                op_index, sbs,
0807                                                start_turn_index, start_op_index);
0808             if (! result)
0809             {
0810                // There no way out found, try second pass in collected cluster exits
0811                result = exits.apply(turn_index, op_index, false);
0812             }
0813         }
0814         else
0815         {
0816             result = analyze_cluster_intersection(turn_index, op_index, sbs);
0817         }
0818         return result;
0819     }
0820
0821     // Analyzes a non-clustered "ii" intersection, as if it is clustered.
0822     inline bool analyze_ii_intersection(signed_size_type& turn_index, int& op_index,
0823                     turn_type const& current_turn,
0824                     segment_identifier const& previous_seg_id)
0825     {
0826         sbs_type sbs(m_strategy);
0827
0828         // Add this turn to the sort-by-side sorter
0829         for (int i = 0; i < 2; i++)
0830         {
0831             sbs.add(current_turn,
0832                     current_turn.operations[i],
0833                     turn_index, i, previous_seg_id,
0834                     m_geometry1, m_geometry2,
0835                     true);
0836         }
0837
0838         if (! sbs.has_origin())
0839         {
0840             return false;
0841         }
0842
0843         sbs.apply(current_turn.point);
0844
0845         bool result = analyze_cluster_intersection(turn_index, op_index, sbs);
0846
0847         return result;
0848     }
0849
0850     inline void change_index_for_self_turn(signed_size_type& to_vertex_index,
0851                 turn_type const& start_turn,
0852                 turn_operation_type const& start_op,
0853                 int start_op_index) const
0854     {
0855         if (BOOST_GEOMETRY_CONDITION(OverlayType != overlay_buffer
0856                                      && OverlayType != overlay_dissolve))
0857         {
0858             return;
0859         }
0860
0861         const bool allow_uu = OverlayType != overlay_buffer;
0862
0863         // It travels to itself, can happen. If this is a buffer, it can
0864         // sometimes travel to itself in the following configuration:
0865         //
0866         // +---->--+
0867         // |       |
0868         // |   +---*----+ *: one turn, with segment index 2/7
0869         // |   |   |    |
0870         // |   +---C    | C: closing point (start/end)
0871         // |            |
0872         // +------------+
0873         //
0874         // If it starts on segment 2 and travels to itself on segment 2, that
0875         // should be corrected to 7 because that is the shortest path
0876         //
0877         // Also a uu turn (touching with another buffered ring) might have this
0878         // apparent configuration, but there it should
0879         // always travel the whole ring
0880
0881         turn_operation_type const& other_op
0882                 = start_turn.operations[1 - start_op_index];
0883
0884         bool const correct
0885                 = (allow_uu || ! start_turn.both(operation_union))
0886                   && start_op.seg_id.source_index == other_op.seg_id.source_index
0887                   && start_op.seg_id.multi_index == other_op.seg_id.multi_index
0888                   && start_op.seg_id.ring_index == other_op.seg_id.ring_index
0889                   && start_op.seg_id.segment_index == to_vertex_index;
0890
0891 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
0892         std::cout << " WARNING: self-buffer "
0893                   << " correct=" << correct
0894                   << " turn=" << operation_char(start_turn.operations[0].operation)
0895                   << operation_char(start_turn.operations[1].operation)
0896                   << " start=" << start_op.seg_id.segment_index
0897                   << " from=" << to_vertex_index
0898                   << " to=" << other_op.enriched.travels_to_vertex_index
0899                   << std::endl;
0900 #endif
0901
0902         if (correct)
0903         {
0904             to_vertex_index = other_op.enriched.travels_to_vertex_index;
0905         }
0906     }
0907
0908     bool select_turn_from_enriched(signed_size_type& turn_index,
0909             segment_identifier& previous_seg_id,
0910             signed_size_type& to_vertex_index,
0911             signed_size_type start_turn_index,
0912             int start_op_index,
0913             turn_type const& previous_turn,
0914             turn_operation_type const& previous_op,
0915             bool is_start) const
0916     {
0917         to_vertex_index = -1;
0918
0919         if (previous_op.enriched.next_ip_index < 0)
0920         {
0921             // There is no next IP on this segment
0922             if (previous_op.enriched.travels_to_vertex_index < 0
0923                 || previous_op.enriched.travels_to_ip_index < 0)
0924             {
0925                 return false;
0926             }
0927
0928             to_vertex_index = previous_op.enriched.travels_to_vertex_index;
0929
0930             if (is_start &&
0931                     previous_op.enriched.travels_to_ip_index == start_turn_index)
0932             {
0933                 change_index_for_self_turn(to_vertex_index, previous_turn,
0934                     previous_op, start_op_index);
0935             }
0936
0937             turn_index = previous_op.enriched.travels_to_ip_index;
0938             previous_seg_id = previous_op.seg_id;
0939         }
0940         else
0941         {
0942             // Take the next IP on this segment
0943             turn_index = previous_op.enriched.next_ip_index;
0944             previous_seg_id = previous_op.seg_id;
0945         }
0946         return true;
0947     }
0948
0949     bool select_turn(signed_size_type start_turn_index, int start_op_index,
0950                      signed_size_type& turn_index,
0951                      int& op_index,
0952                      int previous_op_index,
0953                      signed_size_type previous_turn_index,
0954                      segment_identifier const& previous_seg_id,
0955                      bool is_start, bool has_points)
0956     {
0957         turn_type const& current_turn = m_turns[turn_index];
0958
0959         bool const back_at_start_cluster
0960                 = has_points
0961                 && current_turn.is_clustered()
0962                 && m_turns[start_turn_index].cluster_id == current_turn.cluster_id;
0963         if (BOOST_GEOMETRY_CONDITION(target_operation == operation_intersection))
0964         {
0965             // Intersection or difference
0966
0967             if (has_points && (turn_index == start_turn_index || back_at_start_cluster))
0968             {
0969                 // Intersection can always be finished if returning
0970                 turn_index = start_turn_index;
0971                 op_index = start_op_index;
0972                 return true;
0973             }
0974
0975             if (! current_turn.is_clustered()
0976                 && current_turn.both(operation_intersection)
0977                 && analyze_ii_intersection(turn_index, op_index,
0978                             current_turn, previous_seg_id))
0979             {
0980                 return true;
0981             }
0982         }
0983         else if (turn_index == start_turn_index || back_at_start_cluster)
0984         {
0985             // Union or buffer: cannot return immediately to starting turn, because it then
0986             // might miss a formed multi polygon with a touching point.
0987             auto const& current_op = current_turn.operations[op_index];
0988             signed_size_type const next_turn_index = current_op.enriched.get_next_turn_index();
0989             bool const to_other_turn = next_turn_index >= 0 && m_turns[next_turn_index].cluster_id != current_turn.cluster_id;
0990             if (! to_other_turn)
0991             {
0992                 // Return to starting point
0993                 turn_index = start_turn_index;
0994                 op_index = start_op_index;
0995                 return true;
0996             }
0997         }
0998
0999         if (current_turn.is_clustered())
1000         {
1001             if (! select_turn_from_cluster(turn_index, op_index,
1002                     start_turn_index, start_op_index, previous_seg_id))
1003             {
1004                 return false;
1005             }
1006
1007             if (is_start && turn_index == previous_turn_index)
1008             {
1009                 op_index = previous_op_index;
1010             }
1011         }
1012         else
1013         {
1014             op_index = starting_operation_index(current_turn);
1015             if (op_index == -1)
1016             {
1017                 if (both_finished(current_turn))
1018                 {
1019                     return false;
1020                 }
1021
1022                 if (! select_operation(current_turn, turn_index,
1023                                 start_turn_index,
1024                                 previous_seg_id,
1025                                 op_index))
1026                 {
1027                     return false;
1028                 }
1029             }
1030         }
1031         return true;
1032     }
1033
1034 private :
1035     Geometry1 const& m_geometry1;
1036     Geometry2 const& m_geometry2;
1037     Turns& m_turns;
1038     Clusters const& m_clusters;
1039     RobustPolicy const& m_robust_policy;
1040     SideStrategy m_strategy;
1041     Visitor& m_visitor;
1042 };
1043
1044
1045
1046 }} // namespace detail::overlay
1047 #endif // DOXYGEN_NO_DETAIL
1048
1049 }} // namespace boost::geometry
1050
1051 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP