Imported Upstream version 1.67.0upstream/1.67.0

1 files changed, 139 insertions, 39 deletions

diff --git a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp
index e25445651a..a35be052a0 100644
--- a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp
+++ b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp
@@ -1,6 +1,7 @@
 // Boost.Geometry (aka GGL, Generic Geometry Library)
 
 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
+// Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
 
 // This file was modified by Oracle on 2017.
 // Modifications copyright (c) 2017 Oracle and/or its affiliates.
@@ -51,6 +52,21 @@ namespace boost { namespace geometry
 namespace detail { namespace overlay
 {
 
+template <typename Turns>
+struct discarded_turn
+{
+    discarded_turn(Turns const& turns)
+        : m_turns(turns)
+    {}
+
+    template <typename IndexedTurn>
+    inline bool operator()(IndexedTurn const& indexed) const
+    {
+        return m_turns[indexed.turn_index].discarded;
+    }
+
+    Turns const& m_turns;
+};
 
 // Sorts IP-s of this ring on segment-identifier, and if on same segment,
 //  on distance.
@@ -68,7 +84,6 @@ template
 >
 inline void enrich_sort(Operations& operations,
             Turns const& turns,
-            operation_type for_operation,
             Geometry1 const& geometry1,
             Geometry2 const& geometry2,
             RobustPolicy const& robust_policy,
@@ -84,12 +99,13 @@ inline void enrich_sort(Operations& operations,
                     RobustPolicy,
                     SideStrategy,
                     Reverse1, Reverse2
-                >(turns, for_operation, geometry1, geometry2, robust_policy, strategy));
+                >(turns, geometry1, geometry2, robust_policy, strategy));
 }
 
 
 template <typename Operations, typename Turns>
-inline void enrich_assign(Operations& operations, Turns& turns)
+inline void enrich_assign(Operations& operations, Turns& turns,
+                          bool check_turns)
 {
     typedef typename boost::range_value<Turns>::type turn_type;
     typedef typename turn_type::turn_operation_type op_type;
@@ -110,14 +126,17 @@ inline void enrich_assign(Operations& operations, Turns& turns)
             turn_type& turn = turns[it->turn_index];
             op_type& op = turn.operations[it->operation_index];
 
-            // Normal behaviour: next should point at next turn:
-            if (it->turn_index == next->turn_index)
+            if (check_turns && it->turn_index == next->turn_index)
             {
+                // Normal behaviour: next points at next turn, increase next.
+                // For dissolve this should not be done, turn_index is often
+                // the same for two consecutive operations
                 ++next;
             }
 
             // Cluster behaviour: next should point after cluster, unless
             // their seg_ids are not the same
+            // (For dissolve, this is still to be examined - TODO)
             while (turn.is_clustered()
                    && it->turn_index != next->turn_index
                    && turn.cluster_id == turns[next->turn_index].cluster_id
@@ -142,6 +161,11 @@ inline void enrich_assign(Operations& operations, Turns& turns)
                 // (this is one not circular therefore fraction is considered)
                 op.enriched.next_ip_index = static_cast<signed_size_type>(next->turn_index);
             }
+
+            if (! check_turns)
+            {
+                ++next;
+            }
         }
     }
 
@@ -176,6 +200,82 @@ inline void enrich_assign(Operations& operations, Turns& turns)
 
 }
 
+template <typename Operations, typename Turns>
+inline void enrich_adapt(Operations& operations, Turns& turns)
+{
+    typedef typename boost::range_value<Turns>::type turn_type;
+    typedef typename turn_type::turn_operation_type op_type;
+    typedef typename boost::range_value<Operations>::type indexed_turn_type;
+
+    if (operations.size() < 3)
+    {
+        // If it is empty, or contains one or two turns, it makes no sense
+        return;
+    }
+
+    // Operations is a vector of indexed_turn_operation<>
+
+    // Last index:
+    std::size_t const x = operations.size() - 1;
+    bool next_phase = false;
+
+    for (std::size_t i = 0; i < operations.size(); i++)
+    {
+        indexed_turn_type const& indexed = operations[i];
+
+        turn_type& turn = turns[indexed.turn_index];
+        op_type& op = turn.operations[indexed.operation_index];
+
+        // Previous/next index
+        std::size_t const p = i > 0 ? i - 1 : x;
+        std::size_t const n = i < x ? i + 1 : 0;
+
+        turn_type const& next_turn = turns[operations[n].turn_index];
+        op_type const& next_op = next_turn.operations[operations[n].operation_index];
+
+        if (op.seg_id.segment_index == next_op.seg_id.segment_index)
+        {
+            turn_type const& prev_turn = turns[operations[p].turn_index];
+            op_type const& prev_op = prev_turn.operations[operations[p].operation_index];
+            if (op.seg_id.segment_index == prev_op.seg_id.segment_index)
+            {
+                op.enriched.startable = false;
+                next_phase = true;
+            }
+        }
+    }
+
+    if (! next_phase)
+    {
+        return;
+    }
+
+    // Discard turns which are both non-startable
+    next_phase = false;
+    for (typename boost::range_iterator<Turns>::type
+            it = boost::begin(turns);
+         it != boost::end(turns);
+         ++it)
+    {
+        turn_type& turn = *it;
+        if (! turn.operations[0].enriched.startable
+            && ! turn.operations[1].enriched.startable)
+        {
+            turn.discarded = true;
+            next_phase = true;
+        }
+    }
+
+    if (! next_phase)
+    {
+        return;
+    }
+
+    // Remove discarded turns from operations to avoid having them as next turn
+    discarded_turn<Turns> const predicate(turns);
+    operations.erase(std::remove_if(boost::begin(operations),
+        boost::end(operations), predicate), boost::end(operations));
+}
 
 template <typename Turns, typename MappedVector>
 inline void create_map(Turns const& turns, MappedVector& mapped_vector)
@@ -255,8 +355,8 @@ inline void calculate_remaining_distance(Turns& turns)
             continue;
         }
 
-        int const to_index0 = op0.enriched.get_next_turn_index();
-        int const to_index1 = op1.enriched.get_next_turn_index();
+        signed_size_type const to_index0 = op0.enriched.get_next_turn_index();
+        signed_size_type const to_index1 = op1.enriched.get_next_turn_index();
         if (to_index0 >= 0
                 && to_index1 >= 0
                 && to_index0 != to_index1)
@@ -311,6 +411,7 @@ inline void enrich_intersection_points(Turns& turns,
             = target_operation == detail::overlay::operation_union
             ? detail::overlay::operation_intersection
             : detail::overlay::operation_union;
+    static const bool is_dissolve = OverlayType == overlay_dissolve;
 
     typedef typename boost::range_value<Turns>::type turn_type;
     typedef typename turn_type::turn_operation_type op_type;
@@ -338,31 +439,25 @@ inline void enrich_intersection_points(Turns& turns,
     {
         turn_type& turn = *it;
 
-        if (turn.both(detail::overlay::operation_none))
-        {
-            turn.discarded = true;
-            continue;
-        }
-
-        if (turn.both(opposite_operation))
+        if (turn.both(detail::overlay::operation_none)
+            || turn.both(opposite_operation)
+            || (detail::overlay::is_self_turn<OverlayType>(turn)
+                && ! turn.is_clustered()
+                && ! turn.both(target_operation)))
         {
             // For intersections, remove uu to avoid the need to travel
             // a union (during intersection) in uu/cc clusters (e.g. #31,#32,#33)
-            // Also, for union, discard ii
+
+            // Similarly, for union, discard ii
+
+            // Only keep self-uu-turns or self-ii-turns
+
+            // Blocked (or combination with blocked is still needed for difference)
             turn.discarded = true;
             turn.cluster_id = -1;
             continue;
         }
 
-        if (detail::overlay::is_self_turn<OverlayType>(turn)
-            && ! turn.is_clustered()
-            && ! turn.both(target_operation))
-        {
-            // Only keep self-uu-turns or self-ii-turns
-           turn.discarded = true;
-           continue;
-        }
-
         if (! turn.discarded
             && turn.both(detail::overlay::operation_continue))
         {
@@ -370,16 +465,19 @@ inline void enrich_intersection_points(Turns& turns,
         }
     }
 
-    detail::overlay::discard_closed_turns
-        <
-            OverlayType,
-            target_operation
-        >::apply(turns, clusters, geometry1, geometry2);
-    detail::overlay::discard_open_turns
-        <
-            OverlayType,
-            target_operation
-        >::apply(turns, clusters, geometry1, geometry2);
+    if (! is_dissolve)
+    {
+        detail::overlay::discard_closed_turns
+            <
+                OverlayType,
+                target_operation
+            >::apply(turns, clusters, geometry1, geometry2);
+        detail::overlay::discard_open_turns
+            <
+                OverlayType,
+                target_operation
+            >::apply(turns, clusters, geometry1, geometry2);
+    }
 
     // Create a map of vectors of indexed operation-types to be able
     // to sort intersection points PER RING
@@ -399,7 +497,7 @@ inline void enrich_intersection_points(Turns& turns,
         << mit->first << std::endl;
 #endif
         detail::overlay::enrich_sort<Reverse1, Reverse2>(
-                    mit->second, turns, target_operation,
+                    mit->second, turns,
                     geometry1, geometry2,
                     robust_policy, strategy);
     }
@@ -413,11 +511,13 @@ inline void enrich_intersection_points(Turns& turns,
     std::cout << "ENRICH-assign Ring "
         << mit->first << std::endl;
 #endif
-        detail::overlay::enrich_assign(mit->second, turns);
-    }
+        if (is_dissolve)
+        {
+            detail::overlay::enrich_adapt(mit->second, turns);
+        }
 
-    // Check some specific type of self-turns (after getting enriched info)
-    detail::overlay::discard_self_turns_which_loop<OverlayType>(turns);
+        detail::overlay::enrich_assign(mit->second, turns, ! is_dissolve);
+    }
 
     if (has_colocations)
     {