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
  36 template
  37 <
  38     typename Point, typename Geometry,
  39     typename Tag2 = typename geometry::tag<Geometry>::type
  40 >
  41 struct check_within_strategy
  42 {
  43     template <typename Strategy>
  44     static inline typename Strategy::template point_in_geometry_strategy<Point, Geometry>::type
  45         within(Strategy const& strategy)
  46     {
  47         return strategy.template get_point_in_geometry_strategy<Point, Geometry>();
  48     }
  49
  50     template <typename Strategy>
  51     static inline typename Strategy::template point_in_geometry_strategy<Point, Geometry>::type
  52         covered_by(Strategy const& strategy)
  53     {
  54         return strategy.template get_point_in_geometry_strategy<Point, Geometry>();
  55     }
  56 };
  57
  58 template <typename Point, typename Geometry>
  59 struct check_within_strategy<Point, Geometry, box_tag>
  60 {
  61     template <typename Strategy>
  62     static inline typename Strategy::within_point_box_strategy_type
  63         within(Strategy const& )
  64     {
  65         return typename Strategy::within_point_box_strategy_type();
  66     }
  67
  68     template <typename Strategy>
  69     static inline typename Strategy::covered_by_point_box_strategy_type
  70         covered_by(Strategy const&)
  71     {
  72         return typename Strategy::covered_by_point_box_strategy_type();
  73     }
  74 };
  75
  76
  77 template <overlay_type OverlayType>
  78 struct check_within
  79 {
  80     template
  81     <
  82         typename Turn, typename Geometry0, typename Geometry1,
  83         typename UmbrellaStrategy
  84     >
  85     static inline
  86     bool apply(Turn const& turn, Geometry0 const& geometry0,
  87                Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
  88     {
  89         typedef typename Turn::point_type point_type;
  90
  91         // Operations 0 and 1 have the same source index in self-turns
  92         return turn.operations[0].seg_id.source_index == 0
  93             ? geometry::within(turn.point, geometry1,
  94                 check_within_strategy<point_type, Geometry1>::within(strategy))
  95             : geometry::within(turn.point, geometry0,
  96                 check_within_strategy<point_type, Geometry0>::within(strategy));
  97     }
  98
  99 };
 100
 101 template <>
 102 struct check_within<overlay_difference>
 103 {
 104     template
 105     <
 106         typename Turn, typename Geometry0, typename Geometry1,
 107         typename UmbrellaStrategy
 108     >
 109     static inline
 110     bool apply(Turn const& turn, Geometry0 const& geometry0,
 111                Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
 112     {
 113         typedef typename Turn::point_type point_type;
 114
 115         // difference = intersection(a, reverse(b))
 116         // therefore we should reverse the meaning of within for geometry1
 117         return turn.operations[0].seg_id.source_index == 0
 118             ? ! geometry::covered_by(turn.point, geometry1,
 119                   check_within_strategy<point_type, Geometry1>::covered_by(strategy))
 120             : geometry::within(turn.point, geometry0,
 121                 check_within_strategy<point_type, Geometry0>::within(strategy));
 122     }
 123 };
 124
 125 struct discard_turns
 126 {
 127     template
 128     <
 129         typename Turns, typename Clusters,
 130         typename Geometry0, typename Geometry1,
 131         typename Strategy
 132     >
 133     static inline
 134     void apply(Turns& , Clusters const& ,
 135                Geometry0 const& , Geometry1 const& ,
 136                Strategy const& )
 137     {}
 138 };
 139
 140 template <overlay_type OverlayType, operation_type OperationType>
 141 struct discard_closed_turns : discard_turns {};
 142
 143 // It is only implemented for operation_union, not in buffer
 144 template <>
 145 struct discard_closed_turns<overlay_union, operation_union>
 146 {
 147     // Point in Geometry Strategy
 148     template
 149     <
 150         typename Turns, typename Clusters,
 151         typename Geometry0, typename Geometry1,
 152         typename Strategy
 153     >
 154     static inline
 155     void apply(Turns& turns, Clusters const& /*clusters*/,
 156                Geometry0 const& geometry0, Geometry1 const& geometry1,
 157                Strategy const& strategy)
 158     {
 159         typedef typename boost::range_value<Turns>::type turn_type;
 160
 161         for (typename boost::range_iterator<Turns>::type
 162                 it = boost::begin(turns);
 163              it != boost::end(turns);
 164              ++it)
 165         {
 166             turn_type& turn = *it;
 167
 168             if (! turn.discarded
 169                 && is_self_turn<overlay_union>(turn)
 170                 && check_within<overlay_union>::apply(turn, geometry0,
 171                                                       geometry1, strategy))
 172             {
 173                 // Turn is in the interior of other geometry
 174                 turn.discarded = true;
 175             }
 176         }
 177     }
 178 };
 179
 180 template <overlay_type OverlayType>
 181 struct discard_self_intersection_turns
 182 {
 183 private :
 184
 185     template <typename Turns, typename Clusters>
 186     static inline
 187     bool is_self_cluster(signed_size_type cluster_id,
 188             const Turns& turns, Clusters const& clusters)
 189     {
 190         typename Clusters::const_iterator cit = clusters.find(cluster_id);
 191         if (cit == clusters.end())
 192         {
 193             return false;
 194         }
 195
 196         cluster_info const& cinfo = cit->second;
 197         for (std::set<signed_size_type>::const_iterator it
 198              = cinfo.turn_indices.begin();
 199              it != cinfo.turn_indices.end(); ++it)
 200         {
 201             if (! is_self_turn<OverlayType>(turns[*it]))
 202             {
 203                 return false;
 204             }
 205         }
 206
 207         return true;
 208     }
 209
 210     template <typename Turns, typename Clusters,
 211               typename Geometry0, typename Geometry1, typename Strategy>
 212     static inline
 213     void discard_clusters(Turns& turns, Clusters const& clusters,
 214             Geometry0 const& geometry0, Geometry1 const& geometry1,
 215             Strategy const& strategy)
 216     {
 217         for (typename Clusters::const_iterator cit = clusters.begin();
 218              cit != clusters.end(); ++cit)
 219         {
 220             signed_size_type const cluster_id = cit->first;
 221
 222             // If there are only self-turns in the cluster, the cluster should
 223             // be located within the other geometry, for intersection
 224             if (! cit->second.turn_indices.empty()
 225                 && is_self_cluster(cluster_id, turns, clusters))
 226             {
 227                 cluster_info const& cinfo = cit->second;
 228                 signed_size_type const index = *cinfo.turn_indices.begin();
 229                 if (! check_within<OverlayType>::apply(turns[index],
 230                                                        geometry0, geometry1,
 231                                                        strategy))
 232                 {
 233                     // Discard all turns in cluster
 234                     for (std::set<signed_size_type>::const_iterator sit
 235                          = cinfo.turn_indices.begin();
 236                          sit != cinfo.turn_indices.end(); ++sit)
 237                     {
 238                         turns[*sit].discarded = true;
 239                     }
 240                 }
 241             }
 242         }
 243     }
 244
 245 public :
 246
 247     template <typename Turns, typename Clusters,
 248               typename Geometry0, typename Geometry1, typename Strategy>
 249     static inline
 250     void apply(Turns& turns, Clusters const& clusters,
 251             Geometry0 const& geometry0, Geometry1 const& geometry1,
 252             Strategy const& strategy)
 253     {
 254         discard_clusters(turns, clusters, geometry0, geometry1, strategy);
 255
 256         typedef typename boost::range_value<Turns>::type turn_type;
 257
 258         for (typename boost::range_iterator<Turns>::type
 259                 it = boost::begin(turns);
 260              it != boost::end(turns);
 261              ++it)
 262         {
 263             turn_type& turn = *it;
 264
 265             // It is a ii self-turn
 266             // Check if it is within the other geometry
 267             if (! turn.discarded
 268                 && is_self_turn<overlay_intersection>(turn)
 269                 && ! check_within<OverlayType>::apply(turn, geometry0,
 270                                                       geometry1, strategy))
 271             {
 272                 // It is not within another geometry, set it as non startable.
 273                 // It still might be traveled (#case_recursive_boxes_70)
 274                 turn.operations[0].enriched.startable = false;
 275                 turn.operations[1].enriched.startable = false;
 276             }
 277         }
 278     }
 279 };
 280
 281
 282 template <overlay_type OverlayType, operation_type OperationType>
 283 struct discard_open_turns : discard_turns {};
 284
 285 // Handler for intersection
 286 template <>
 287 struct discard_open_turns<overlay_intersection, operation_intersection>
 288         : discard_self_intersection_turns<overlay_intersection> {};
 289
 290 // Handler for difference, with different meaning of 'within'
 291 template <>
 292 struct discard_open_turns<overlay_difference, operation_intersection>
 293         : discard_self_intersection_turns<overlay_difference> {};
 294
 295 }} // namespace detail::overlay
 296 #endif //DOXYGEN_NO_DETAIL
 297
 298
 299 }} // namespace boost::geometry
 300
 301 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP