X-Git-Url: https://git.proxmox.com/?a=blobdiff_plain;f=ceph%2Fsrc%2Fboost%2Fboost%2Fgeometry%2Falgorithms%2Fdetail%2Foverlay%2Fhandle_self_turns.hpp;h=5323c699bba1b66a2600cc66ebb8d65798fbc4cb;hb=20effc670b57271cb089376d6d0800990e5218d5;hp=9c4a3094e01ac6a8909badec44231f7df981b0a9;hpb=b32b81446b3b05102be0267e79203f59329c1d97;p=ceph.git

diff --git a/ceph/src/boost/boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp b/ceph/src/boost/boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp
index 9c4a3094e..5323c699b 100644
--- a/ceph/src/boost/boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp
+++ b/ceph/src/boost/boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp
@@ -1,6 +1,12 @@
 // Boost.Geometry (aka GGL, Generic Geometry Library)
 
 // Copyright (c) 2017 Barend Gehrels, Amsterdam, the Netherlands.
+// Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
+
+// This file was modified by Oracle on 2019-2020.
+// Modifications copyright (c) 2019-2020 Oracle and/or its affiliates.
+
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
 
 // Use, modification and distribution is subject to the Boost Software License,
 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
@@ -9,11 +15,14 @@
 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP
 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP
 
-#include <boost/range.hpp>
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+#include <boost/range/value_type.hpp>
 
 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
+#include <boost/geometry/algorithms/covered_by.hpp>
 #include <boost/geometry/algorithms/within.hpp>
 
 namespace boost { namespace geometry
@@ -23,11 +32,108 @@ namespace boost { namespace geometry
 namespace detail { namespace overlay
 {
 
+
+template
+<
+    typename Point, typename Geometry,
+    typename Tag2 = typename geometry::tag<Geometry>::type
+>
+struct check_within_strategy
+{
+    template <typename Strategy>
+    static inline typename Strategy::template point_in_geometry_strategy<Point, Geometry>::type
+        within(Strategy const& strategy)
+    {
+        return strategy.template get_point_in_geometry_strategy<Point, Geometry>();
+    }
+
+    template <typename Strategy>
+    static inline typename Strategy::template point_in_geometry_strategy<Point, Geometry>::type
+        covered_by(Strategy const& strategy)
+    {
+        return strategy.template get_point_in_geometry_strategy<Point, Geometry>();
+    }
+};
+
+template <typename Point, typename Geometry>
+struct check_within_strategy<Point, Geometry, box_tag>
+{
+    template <typename Strategy>
+    static inline typename Strategy::within_point_box_strategy_type
+        within(Strategy const& )
+    {
+        return typename Strategy::within_point_box_strategy_type();
+    }
+
+    template <typename Strategy>
+    static inline typename Strategy::covered_by_point_box_strategy_type
+        covered_by(Strategy const&)
+    {
+        return typename Strategy::covered_by_point_box_strategy_type();
+    }
+};
+
+
+template <overlay_type OverlayType>
+struct check_within
+{
+    template
+    <
+        typename Turn, typename Geometry0, typename Geometry1,
+        typename UmbrellaStrategy
+    >
+    static inline
+    bool apply(Turn const& turn, Geometry0 const& geometry0,
+               Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
+    {
+        typedef typename Turn::point_type point_type;
+
+        // Operations 0 and 1 have the same source index in self-turns
+        return turn.operations[0].seg_id.source_index == 0
+            ? geometry::within(turn.point, geometry1,
+                check_within_strategy<point_type, Geometry1>::within(strategy))
+            : geometry::within(turn.point, geometry0,
+                check_within_strategy<point_type, Geometry0>::within(strategy));
+    }
+
+};
+
+template <>
+struct check_within<overlay_difference>
+{
+    template
+    <
+        typename Turn, typename Geometry0, typename Geometry1,
+        typename UmbrellaStrategy
+    >
+    static inline
+    bool apply(Turn const& turn, Geometry0 const& geometry0,
+               Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
+    {
+        typedef typename Turn::point_type point_type;
+
+        // difference = intersection(a, reverse(b))
+        // therefore we should reverse the meaning of within for geometry1
+        return turn.operations[0].seg_id.source_index == 0
+            ? ! geometry::covered_by(turn.point, geometry1,
+                  check_within_strategy<point_type, Geometry1>::covered_by(strategy))
+            : geometry::within(turn.point, geometry0,
+                check_within_strategy<point_type, Geometry0>::within(strategy));
+    }
+};
+
 struct discard_turns
 {
-    template <typename Turns, typename Clusters, typename Geometry0, typename Geometry1>
+    template
+    <
+        typename Turns, typename Clusters,
+        typename Geometry0, typename Geometry1,
+        typename Strategy
+    >
     static inline
-    void apply(Turns& , Clusters const& , Geometry0 const& , Geometry1 const& )
+    void apply(Turns& , Clusters const& ,
+               Geometry0 const& , Geometry1 const& ,
+               Strategy const& )
     {}
 };
 
@@ -38,11 +144,17 @@ struct discard_closed_turns : discard_turns {};
 template <>
 struct discard_closed_turns<overlay_union, operation_union>
 {
-
-    template <typename Turns, typename Clusters, typename Geometry0, typename Geometry1>
+    // Point in Geometry Strategy
+    template
+    <
+        typename Turns, typename Clusters,
+        typename Geometry0, typename Geometry1,
+        typename Strategy
+    >
     static inline
-    void apply(Turns& turns, Clusters const& clusters,
-            Geometry0 const& geometry0, Geometry1 const& geometry1)
+    void apply(Turns& turns, Clusters const& /*clusters*/,
+               Geometry0 const& geometry0, Geometry1 const& geometry1,
+               Strategy const& strategy)
     {
         typedef typename boost::range_value<Turns>::type turn_type;
 
@@ -53,53 +165,23 @@ struct discard_closed_turns<overlay_union, operation_union>
         {
             turn_type& turn = *it;
 
-            if (turn.discarded || ! is_self_turn<overlay_union>(turn))
+            if (! turn.discarded
+                && is_self_turn<overlay_union>(turn)
+                && check_within<overlay_union>::apply(turn, geometry0,
+                                                      geometry1, strategy))
             {
-                continue;
-            }
-
-            bool const within =
-                    turn.operations[0].seg_id.source_index == 0
-                    ? geometry::within(turn.point, geometry1)
-                    : geometry::within(turn.point, geometry0);
-
-            if (within)
-            {
-                // It is in the interior of the other geometry
+                // Turn is in the interior of other geometry
                 turn.discarded = true;
             }
         }
     }
 };
 
+template <overlay_type OverlayType>
 struct discard_self_intersection_turns
 {
 private :
 
-    template <typename Turns, typename Clusters>
-    static inline
-    bool any_blocked(signed_size_type cluster_id,
-            const Turns& turns, Clusters const& clusters)
-    {
-        typename Clusters::const_iterator cit = clusters.find(cluster_id);
-        if (cit == clusters.end())
-        {
-            return false;
-        }
-        cluster_info const& cinfo = cit->second;
-        for (std::set<signed_size_type>::const_iterator it
-             = cinfo.turn_indices.begin();
-             it != cinfo.turn_indices.end(); ++it)
-        {
-            typename boost::range_value<Turns>::type const& turn = turns[*it];
-            if (turn.any_blocked())
-            {
-                return true;
-            }
-        }
-        return false;
-    }
-
     template <typename Turns, typename Clusters>
     static inline
     bool is_self_cluster(signed_size_type cluster_id,
@@ -116,7 +198,7 @@ private :
              = cinfo.turn_indices.begin();
              it != cinfo.turn_indices.end(); ++it)
         {
-            if (! is_self_turn<overlay_intersection>(turns[*it]))
+            if (! is_self_turn<OverlayType>(turns[*it]))
             {
                 return false;
             }
@@ -125,36 +207,32 @@ private :
         return true;
     }
 
-    template <typename Turn, typename Geometry0, typename Geometry1>
-    static inline
-    bool within(Turn const& turn, Geometry0 const& geometry0,
-                Geometry1 const& geometry1)
-    {
-        return turn.operations[0].seg_id.source_index == 0
-            ? geometry::within(turn.point, geometry1)
-            : geometry::within(turn.point, geometry0);
-    }
-
     template <typename Turns, typename Clusters,
-              typename Geometry0, typename Geometry1>
+              typename Geometry0, typename Geometry1, typename Strategy>
     static inline
     void discard_clusters(Turns& turns, Clusters const& clusters,
-            Geometry0 const& geometry0, Geometry1 const& geometry1)
+            Geometry0 const& geometry0, Geometry1 const& geometry1,
+            Strategy const& strategy)
     {
         for (typename Clusters::const_iterator cit = clusters.begin();
              cit != clusters.end(); ++cit)
         {
-            signed_size_type cluster_id = cit->first;
+            signed_size_type const cluster_id = cit->first;
 
             // If there are only self-turns in the cluster, the cluster should
             // be located within the other geometry, for intersection
-            if (is_self_cluster(cluster_id, turns, clusters))
+            if (! cit->second.turn_indices.empty()
+                && is_self_cluster(cluster_id, turns, clusters))
             {
                 cluster_info const& cinfo = cit->second;
-                if (! within(turns[*cinfo.turn_indices.begin()], geometry0, geometry1))
+                signed_size_type const index = *cinfo.turn_indices.begin();
+                if (! check_within<OverlayType>::apply(turns[index],
+                                                       geometry0, geometry1,
+                                                       strategy))
                 {
                     // Discard all turns in cluster
-                    for (std::set<signed_size_type>::const_iterator sit = cinfo.turn_indices.begin();
+                    for (std::set<signed_size_type>::const_iterator sit
+                         = cinfo.turn_indices.begin();
                          sit != cinfo.turn_indices.end(); ++sit)
                     {
                         turns[*sit].discarded = true;
@@ -167,12 +245,13 @@ private :
 public :
 
     template <typename Turns, typename Clusters,
-              typename Geometry0, typename Geometry1>
+              typename Geometry0, typename Geometry1, typename Strategy>
     static inline
     void apply(Turns& turns, Clusters const& clusters,
-            Geometry0 const& geometry0, Geometry1 const& geometry1)
+            Geometry0 const& geometry0, Geometry1 const& geometry1,
+            Strategy const& strategy)
     {
-        discard_clusters(turns, clusters, geometry0, geometry1);
+        discard_clusters(turns, clusters, geometry0, geometry1, strategy);
 
         typedef typename boost::range_value<Turns>::type turn_type;
 
@@ -183,109 +262,35 @@ public :
         {
             turn_type& turn = *it;
 
-            if (turn.discarded || ! is_self_turn<overlay_intersection>(turn))
-            {
-                continue;
-            }
-
-            segment_identifier const& id0 = turn.operations[0].seg_id;
-            segment_identifier const& id1 = turn.operations[1].seg_id;
-            if (id0.multi_index != id1.multi_index
-                    || (id0.ring_index == -1 && id1.ring_index == -1)
-                    || (id0.ring_index >= 0 && id1.ring_index >= 0))
-            {
-                // Not an ii ring (int/ext) on same ring
-                continue;
-            }
-
-            if (turn.is_clustered() && turn.has_colocated_both)
-            {
-                // Don't delete a self-ii-turn colocated with another ii-turn
-                // (for example #case_recursive_boxes_70)
-                // But for some cases (#case_58_iet) they should be deleted,
-                // there are many self-turns there and also blocked turns there
-                if (! any_blocked(turn.cluster_id, turns, clusters))
-                {
-                    continue;
-                }
-            }
-
             // It is a ii self-turn
             // Check if it is within the other geometry
-            // If not, it can be ignored
-            if (! within(turn, geometry0, geometry1))
+            if (! turn.discarded
+                && is_self_turn<overlay_intersection>(turn)
+                && ! check_within<OverlayType>::apply(turn, geometry0,
+                                                      geometry1, strategy))
             {
-                // It is not within another geometry, discard the turn
-                turn.discarded = true;
+                // It is not within another geometry, set it as non startable.
+                // It still might be traveled (#case_recursive_boxes_70)
+                turn.operations[0].enriched.startable = false;
+                turn.operations[1].enriched.startable = false;
             }
         }
     }
 };
 
+
 template <overlay_type OverlayType, operation_type OperationType>
 struct discard_open_turns : discard_turns {};
 
-// Handler it for intersection
+// Handler for intersection
 template <>
 struct discard_open_turns<overlay_intersection, operation_intersection>
-        : discard_self_intersection_turns {};
-
-// For difference, it should be done in a different way (TODO)
-
-
-template <overlay_type OverlayType, typename Turns>
-inline void discard_self_turns_which_loop(Turns& turns)
-{
-    if (operation_from_overlay<OverlayType>::value == operation_union)
-    {
-        // For union, self-turn i/u traveling to itself are allowed to form
-        // holes. #case_recursive_boxes_37
-        // TODO: this can be finetuned by inspecting the cluster too,
-        // and if there are non-self-turns the polygons on their sides can
-        // be checked
-        return;
-    }
-
-    typedef typename boost::range_value<Turns>::type turn_type;
-    typedef typename turn_type::turn_operation_type op_type;
-
-    signed_size_type turn_index = 0;
-    for (typename boost::range_iterator<Turns>::type
-            it = boost::begin(turns);
-         it != boost::end(turns);
-         ++it, ++turn_index)
-    {
-        turn_type& turn = *it;
-
-        if (! is_self_turn<OverlayType>(turn))
-        {
-            continue;
-        }
-        if (! turn.combination(operation_intersection, operation_union))
-        {
-            // ii may travel to itself
-            continue;
-        }
+        : discard_self_intersection_turns<overlay_intersection> {};
 
-        for (int i = 0; i < 2; i++)
-        {
-            op_type& op = turn.operations[i];
-
-            if (op.enriched.startable
-                && op.operation == operation_intersection
-                && op.enriched.get_next_turn_index() == turn_index)
-            {
-                // Self-turn i/u, i part traveling to itself. Discard it.
-                // (alternatively it might be made unstartable - but the
-                // intersection-operation may not be traveled anyway, and the
-                // union-operation is not traveled at all in intersections
-                // #case_recursive_boxes_77
-                turn.discarded = true;
-            }
-        }
-    }
-
-}
+// Handler for difference, with different meaning of 'within'
+template <>
+struct discard_open_turns<overlay_difference, operation_intersection>
+        : discard_self_intersection_turns<overlay_difference> {};
 
 }} // namespace detail::overlay
 #endif //DOXYGEN_NO_DETAIL