Imported Upstream version 1.67.0upstream/1.67.0

1 files changed, 56 insertions, 2 deletions

diff --git a/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp b/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp
index 4df3f6e7ac..7f80c8313a 100644
--- a/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp
+++ b/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp
@@ -162,7 +162,7 @@ struct traversal_ring_creator
         // Update registration and append point
         turn_type& current_turn = m_turns[turn_index];
         turn_operation_type& op = current_turn.operations[op_index];
-        detail::overlay::append_no_dups_or_spikes(current_ring, current_turn.point,
+        detail::overlay::append_no_collinear(current_ring, current_turn.point,
             m_intersection_strategy.get_side_strategy(),
             m_robust_policy);
 
@@ -180,7 +180,7 @@ struct traversal_ring_creator
         turn_type const& start_turn = m_turns[start_turn_index];
         turn_operation_type& start_op = m_turns[start_turn_index].operations[start_op_index];
 
-        detail::overlay::append_no_dups_or_spikes(ring, start_turn.point,
+        detail::overlay::append_no_collinear(ring, start_turn.point,
             m_intersection_strategy.get_side_strategy(),
             m_robust_policy);
 
@@ -344,6 +344,60 @@ struct traversal_ring_creator
         }
     }
 
+    template <typename Rings>
+    void iterate_with_preference(std::size_t phase,
+                 Rings& rings, std::size_t& finalized_ring_size,
+                 typename Backtrack::state_type& state)
+    {
+        for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
+        {
+            turn_type const& turn = m_turns[turn_index];
+
+            if (turn.discarded || turn.blocked())
+            {
+                // Skip discarded and blocked turns
+                continue;
+            }
+
+            turn_operation_type const& op0 = turn.operations[0];
+            turn_operation_type const& op1 = turn.operations[1];
+
+            if (phase == 0)
+            {
+                if (! op0.enriched.prefer_start && ! op1.enriched.prefer_start)
+                {
+                    // Not preferred, take next one
+                    continue;
+                }
+            }
+
+            if (turn.both(operation_continue))
+            {
+                // Traverse only one turn, the one with the SMALLEST remaining distance
+                // to avoid skipping a turn in between, which can happen in rare cases
+                // (e.g. #130)
+                int const op_index
+                        = op0.remaining_distance <= op1.remaining_distance ? 0 : 1;
+
+                traverse_with_operation(turn, turn_index, op_index,
+                        rings, finalized_ring_size, state);
+            }
+            else
+            {
+                bool const forward = op0.enriched.prefer_start;
+
+                int op_index = forward ? 0 : 1;
+                int const increment = forward ? 1 : -1;
+
+                for (int i = 0; i < 2; i++, op_index += increment)
+                {
+                    traverse_with_operation(turn, turn_index, op_index,
+                            rings, finalized_ring_size, state);
+                }
+            }
+        }
+    }
+
 private:
     traversal_type m_trav;