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
   5 // Use, modification and distribution is subject to the Boost Software License,
   6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP
  10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP
  11
  12 #include <boost/range.hpp>
  13
  14 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
  15 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
  16 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
  17 #include <boost/geometry/algorithms/within.hpp>
  18
  19 namespace boost { namespace geometry
  20 {
  21
  22 #ifndef DOXYGEN_NO_DETAIL
  23 namespace detail { namespace overlay
  24 {
  25
  26 struct discard_turns
  27 {
  28     template <typename Turns, typename Clusters, typename Geometry0, typename Geometry1>
  29     static inline
  30     void apply(Turns& , Clusters const& , Geometry0 const& , Geometry1 const& )
  31     {}
  32 };
  33
  34 template <overlay_type OverlayType, operation_type OperationType>
  35 struct discard_closed_turns : discard_turns {};
  36
  37 // It is only implemented for operation_union, not in buffer
  38 template <>
  39 struct discard_closed_turns<overlay_union, operation_union>
  40 {
  41
  42     template <typename Turns, typename Clusters, typename Geometry0, typename Geometry1>
  43     static inline
  44     void apply(Turns& turns, Clusters const& clusters,
  45             Geometry0 const& geometry0, Geometry1 const& geometry1)
  46     {
  47         typedef typename boost::range_value<Turns>::type turn_type;
  48
  49         for (typename boost::range_iterator<Turns>::type
  50                 it = boost::begin(turns);
  51              it != boost::end(turns);
  52              ++it)
  53         {
  54             turn_type& turn = *it;
  55
  56             if (turn.discarded || ! is_self_turn<overlay_union>(turn))
  57             {
  58                 continue;
  59             }
  60
  61             bool const within =
  62                     turn.operations[0].seg_id.source_index == 0
  63                     ? geometry::within(turn.point, geometry1)
  64                     : geometry::within(turn.point, geometry0);
  65
  66             if (within)
  67             {
  68                 // It is in the interior of the other geometry
  69                 turn.discarded = true;
  70             }
  71         }
  72     }
  73 };
  74
  75 struct discard_self_intersection_turns
  76 {
  77 private :
  78
  79     template <typename Turns, typename Clusters>
  80     static inline
  81     bool any_blocked(signed_size_type cluster_id,
  82             const Turns& turns, Clusters const& clusters)
  83     {
  84         typename Clusters::const_iterator cit = clusters.find(cluster_id);
  85         if (cit == clusters.end())
  86         {
  87             return false;
  88         }
  89         cluster_info const& cinfo = cit->second;
  90         for (std::set<signed_size_type>::const_iterator it
  91              = cinfo.turn_indices.begin();
  92              it != cinfo.turn_indices.end(); ++it)
  93         {
  94             typename boost::range_value<Turns>::type const& turn = turns[*it];
  95             if (turn.any_blocked())
  96             {
  97                 return true;
  98             }
  99         }
 100         return false;
 101     }
 102
 103     template <typename Turns, typename Clusters>
 104     static inline
 105     bool is_self_cluster(signed_size_type cluster_id,
 106             const Turns& turns, Clusters const& clusters)
 107     {
 108         typename Clusters::const_iterator cit = clusters.find(cluster_id);
 109         if (cit == clusters.end())
 110         {
 111             return false;
 112         }
 113
 114         cluster_info const& cinfo = cit->second;
 115         for (std::set<signed_size_type>::const_iterator it
 116              = cinfo.turn_indices.begin();
 117              it != cinfo.turn_indices.end(); ++it)
 118         {
 119             if (! is_self_turn<overlay_intersection>(turns[*it]))
 120             {
 121                 return false;
 122             }
 123         }
 124
 125         return true;
 126     }
 127
 128     template <typename Turn, typename Geometry0, typename Geometry1>
 129     static inline
 130     bool within(Turn const& turn, Geometry0 const& geometry0,
 131                 Geometry1 const& geometry1)
 132     {
 133         return turn.operations[0].seg_id.source_index == 0
 134             ? geometry::within(turn.point, geometry1)
 135             : geometry::within(turn.point, geometry0);
 136     }
 137
 138     template <typename Turns, typename Clusters,
 139               typename Geometry0, typename Geometry1>
 140     static inline
 141     void discard_clusters(Turns& turns, Clusters const& clusters,
 142             Geometry0 const& geometry0, Geometry1 const& geometry1)
 143     {
 144         for (typename Clusters::const_iterator cit = clusters.begin();
 145              cit != clusters.end(); ++cit)
 146         {
 147             signed_size_type cluster_id = cit->first;
 148
 149             // If there are only self-turns in the cluster, the cluster should
 150             // be located within the other geometry, for intersection
 151             if (is_self_cluster(cluster_id, turns, clusters))
 152             {
 153                 cluster_info const& cinfo = cit->second;
 154                 if (! within(turns[*cinfo.turn_indices.begin()], geometry0, geometry1))
 155                 {
 156                     // Discard all turns in cluster
 157                     for (std::set<signed_size_type>::const_iterator sit = cinfo.turn_indices.begin();
 158                          sit != cinfo.turn_indices.end(); ++sit)
 159                     {
 160                         turns[*sit].discarded = true;
 161                     }
 162                 }
 163             }
 164         }
 165     }
 166
 167 public :
 168
 169     template <typename Turns, typename Clusters,
 170               typename Geometry0, typename Geometry1>
 171     static inline
 172     void apply(Turns& turns, Clusters const& clusters,
 173             Geometry0 const& geometry0, Geometry1 const& geometry1)
 174     {
 175         discard_clusters(turns, clusters, geometry0, geometry1);
 176
 177         typedef typename boost::range_value<Turns>::type turn_type;
 178
 179         for (typename boost::range_iterator<Turns>::type
 180                 it = boost::begin(turns);
 181              it != boost::end(turns);
 182              ++it)
 183         {
 184             turn_type& turn = *it;
 185
 186             if (turn.discarded || ! is_self_turn<overlay_intersection>(turn))
 187             {
 188                 continue;
 189             }
 190
 191             segment_identifier const& id0 = turn.operations[0].seg_id;
 192             segment_identifier const& id1 = turn.operations[1].seg_id;
 193             if (id0.multi_index != id1.multi_index
 194                     || (id0.ring_index == -1 && id1.ring_index == -1)
 195                     || (id0.ring_index >= 0 && id1.ring_index >= 0))
 196             {
 197                 // Not an ii ring (int/ext) on same ring
 198                 continue;
 199             }
 200
 201             if (turn.is_clustered() && turn.has_colocated_both)
 202             {
 203                 // Don't delete a self-ii-turn colocated with another ii-turn
 204                 // (for example #case_recursive_boxes_70)
 205                 // But for some cases (#case_58_iet) they should be deleted,
 206                 // there are many self-turns there and also blocked turns there
 207                 if (! any_blocked(turn.cluster_id, turns, clusters))
 208                 {
 209                     continue;
 210                 }
 211             }
 212
 213             // It is a ii self-turn
 214             // Check if it is within the other geometry
 215             // If not, it can be ignored
 216             if (! within(turn, geometry0, geometry1))
 217             {
 218                 // It is not within another geometry, discard the turn
 219                 turn.discarded = true;
 220             }
 221         }
 222     }
 223 };
 224
 225 template <overlay_type OverlayType, operation_type OperationType>
 226 struct discard_open_turns : discard_turns {};
 227
 228 // Handler it for intersection
 229 template <>
 230 struct discard_open_turns<overlay_intersection, operation_intersection>
 231         : discard_self_intersection_turns {};
 232
 233 // For difference, it should be done in a different way (TODO)
 234
 235
 236 template <overlay_type OverlayType, typename Turns>
 237 inline void discard_self_turns_which_loop(Turns& turns)
 238 {
 239     if (operation_from_overlay<OverlayType>::value == operation_union)
 240     {
 241         // For union, self-turn i/u traveling to itself are allowed to form
 242         // holes. #case_recursive_boxes_37
 243         // TODO: this can be finetuned by inspecting the cluster too,
 244         // and if there are non-self-turns the polygons on their sides can
 245         // be checked
 246         return;
 247     }
 248
 249     typedef typename boost::range_value<Turns>::type turn_type;
 250     typedef typename turn_type::turn_operation_type op_type;
 251
 252     signed_size_type turn_index = 0;
 253     for (typename boost::range_iterator<Turns>::type
 254             it = boost::begin(turns);
 255          it != boost::end(turns);
 256          ++it, ++turn_index)
 257     {
 258         turn_type& turn = *it;
 259
 260         if (! is_self_turn<OverlayType>(turn))
 261         {
 262             continue;
 263         }
 264         if (! turn.combination(operation_intersection, operation_union))
 265         {
 266             // ii may travel to itself
 267             continue;
 268         }
 269
 270         for (int i = 0; i < 2; i++)
 271         {
 272             op_type& op = turn.operations[i];
 273
 274             if (op.enriched.startable
 275                 && op.operation == operation_intersection
 276                 && op.enriched.get_next_turn_index() == turn_index)
 277             {
 278                 // Self-turn i/u, i part traveling to itself. Discard it.
 279                 // (alternatively it might be made unstartable - but the
 280                 // intersection-operation may not be traveled anyway, and the
 281                 // union-operation is not traveled at all in intersections
 282                 // #case_recursive_boxes_77
 283                 turn.discarded = true;
 284             }
 285         }
 286     }
 287
 288 }
 289
 290 }} // namespace detail::overlay
 291 #endif //DOXYGEN_NO_DETAIL
 292
 293
 294 }} // namespace boost::geometry
 295
 296 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP