detail/overlay/traversal.hpp

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