ceph/src/boost/boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2017 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   5
   6 // This file was modified by Oracle on 2019-2020.
   7 // Modifications copyright (c) 2019-2020 Oracle and/or its affiliates.
   8
   9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  10
  11 // Use, modification and distribution is subject to the Boost Software License,
  12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  13 // http://www.boost.org/LICENSE_1_0.txt)
  14
  15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP
  16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP
  17
  18 #include <boost/range/begin.hpp>
  19 #include <boost/range/end.hpp>
  20 #include <boost/range/value_type.hpp>
  21
  22 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
  23 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
  24 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
  25 #include <boost/geometry/algorithms/covered_by.hpp>
  26 #include <boost/geometry/algorithms/within.hpp>
  27
  28 namespace boost { namespace geometry
  29 {
  30
  31 #ifndef DOXYGEN_NO_DETAIL
  32 namespace detail { namespace overlay
  33 {
  34
  35 template <overlay_type OverlayType>
  36 struct check_within
  37 {
  38     template
  39     <
  40         typename Turn, typename Geometry0, typename Geometry1,
  41         typename UmbrellaStrategy
  42     >
  43     static inline
  44     bool apply(Turn const& turn, Geometry0 const& geometry0,
  45                Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
  46     {
  47         // Operations 0 and 1 have the same source index in self-turns
  48         return turn.operations[0].seg_id.source_index == 0
  49             ? geometry::within(turn.point, geometry1, strategy)
  50             : geometry::within(turn.point, geometry0, strategy);
  51     }
  52
  53 };
  54
  55 template <>
  56 struct check_within<overlay_difference>
  57 {
  58     template
  59     <
  60         typename Turn, typename Geometry0, typename Geometry1,
  61         typename UmbrellaStrategy
  62     >
  63     static inline
  64     bool apply(Turn const& turn, Geometry0 const& geometry0,
  65                Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
  66     {
  67         // difference = intersection(a, reverse(b))
  68         // therefore we should reverse the meaning of within for geometry1
  69         return turn.operations[0].seg_id.source_index == 0
  70             ? ! geometry::covered_by(turn.point, geometry1, strategy)
  71             : geometry::within(turn.point, geometry0, strategy);
  72     }
  73 };
  74
  75 struct discard_turns
  76 {
  77     template
  78     <
  79         typename Turns, typename Clusters,
  80         typename Geometry0, typename Geometry1,
  81         typename Strategy
  82     >
  83     static inline
  84     void apply(Turns& , Clusters const& ,
  85                Geometry0 const& , Geometry1 const& ,
  86                Strategy const& )
  87     {}
  88 };
  89
  90 template <overlay_type OverlayType, operation_type OperationType>
  91 struct discard_closed_turns : discard_turns {};
  92
  93 // It is only implemented for operation_union, not in buffer
  94 template <>
  95 struct discard_closed_turns<overlay_union, operation_union>
  96 {
  97     // Point in Geometry Strategy
  98     template
  99     <
 100         typename Turns, typename Clusters,
 101         typename Geometry0, typename Geometry1,
 102         typename Strategy
 103     >
 104     static inline
 105     void apply(Turns& turns, Clusters const& /*clusters*/,
 106                Geometry0 const& geometry0, Geometry1 const& geometry1,
 107                Strategy const& strategy)
 108     {
 109         typedef typename boost::range_value<Turns>::type turn_type;
 110
 111         for (typename boost::range_iterator<Turns>::type
 112                 it = boost::begin(turns);
 113              it != boost::end(turns);
 114              ++it)
 115         {
 116             turn_type& turn = *it;
 117
 118             if (! turn.discarded
 119                 && is_self_turn<overlay_union>(turn)
 120                 && check_within<overlay_union>::apply(turn, geometry0,
 121                                                       geometry1, strategy))
 122             {
 123                 // Turn is in the interior of other geometry
 124                 turn.discarded = true;
 125             }
 126         }
 127     }
 128 };
 129
 130 template <overlay_type OverlayType>
 131 struct discard_self_intersection_turns
 132 {
 133 private :
 134
 135     template <typename Turns, typename Clusters>
 136     static inline
 137     bool is_self_cluster(signed_size_type cluster_id,
 138             const Turns& turns, Clusters const& clusters)
 139     {
 140         typename Clusters::const_iterator cit = clusters.find(cluster_id);
 141         if (cit == clusters.end())
 142         {
 143             return false;
 144         }
 145
 146         cluster_info const& cinfo = cit->second;
 147         for (std::set<signed_size_type>::const_iterator it
 148              = cinfo.turn_indices.begin();
 149              it != cinfo.turn_indices.end(); ++it)
 150         {
 151             if (! is_self_turn<OverlayType>(turns[*it]))
 152             {
 153                 return false;
 154             }
 155         }
 156
 157         return true;
 158     }
 159
 160     template <typename Turns, typename Clusters,
 161               typename Geometry0, typename Geometry1, typename Strategy>
 162     static inline
 163     void discard_clusters(Turns& turns, Clusters const& clusters,
 164             Geometry0 const& geometry0, Geometry1 const& geometry1,
 165             Strategy const& strategy)
 166     {
 167         for (typename Clusters::const_iterator cit = clusters.begin();
 168              cit != clusters.end(); ++cit)
 169         {
 170             signed_size_type const cluster_id = cit->first;
 171
 172             // If there are only self-turns in the cluster, the cluster should
 173             // be located within the other geometry, for intersection
 174             if (! cit->second.turn_indices.empty()
 175                 && is_self_cluster(cluster_id, turns, clusters))
 176             {
 177                 cluster_info const& cinfo = cit->second;
 178                 signed_size_type const index = *cinfo.turn_indices.begin();
 179                 if (! check_within<OverlayType>::apply(turns[index],
 180                                                        geometry0, geometry1,
 181                                                        strategy))
 182                 {
 183                     // Discard all turns in cluster
 184                     for (std::set<signed_size_type>::const_iterator sit
 185                          = cinfo.turn_indices.begin();
 186                          sit != cinfo.turn_indices.end(); ++sit)
 187                     {
 188                         turns[*sit].discarded = true;
 189                     }
 190                 }
 191             }
 192         }
 193     }
 194
 195 public :
 196
 197     template <typename Turns, typename Clusters,
 198               typename Geometry0, typename Geometry1, typename Strategy>
 199     static inline
 200     void apply(Turns& turns, Clusters const& clusters,
 201             Geometry0 const& geometry0, Geometry1 const& geometry1,
 202             Strategy const& strategy)
 203     {
 204         discard_clusters(turns, clusters, geometry0, geometry1, strategy);
 205
 206         typedef typename boost::range_value<Turns>::type turn_type;
 207
 208         for (typename boost::range_iterator<Turns>::type
 209                 it = boost::begin(turns);
 210              it != boost::end(turns);
 211              ++it)
 212         {
 213             turn_type& turn = *it;
 214
 215             // It is a ii self-turn
 216             // Check if it is within the other geometry
 217             if (! turn.discarded
 218                 && is_self_turn<overlay_intersection>(turn)
 219                 && ! check_within<OverlayType>::apply(turn, geometry0,
 220                                                       geometry1, strategy))
 221             {
 222                 // It is not within another geometry, set it as non startable.
 223                 // It still might be traveled (#case_recursive_boxes_70)
 224                 turn.operations[0].enriched.startable = false;
 225                 turn.operations[1].enriched.startable = false;
 226             }
 227         }
 228     }
 229 };
 230
 231
 232 template <overlay_type OverlayType, operation_type OperationType>
 233 struct discard_open_turns : discard_turns {};
 234
 235 // Handler for intersection
 236 template <>
 237 struct discard_open_turns<overlay_intersection, operation_intersection>
 238         : discard_self_intersection_turns<overlay_intersection> {};
 239
 240 // Handler for difference, with different meaning of 'within'
 241 template <>
 242 struct discard_open_turns<overlay_difference, operation_intersection>
 243         : discard_self_intersection_turns<overlay_difference> {};
 244
 245 }} // namespace detail::overlay
 246 #endif //DOXYGEN_NO_DETAIL
 247
 248
 249 }} // namespace boost::geometry
 250
 251 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP