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