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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland.
   5
   6 // This file was modified by Oracle on 2017-2021.
   7 // Modifications copyright (c) 2017-2021 Oracle and/or its affiliates.
   8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   9
  10 // Use, modification and distribution is subject to the Boost Software License,
  11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  12 // http://www.boost.org/LICENSE_1_0.txt)
  13
  14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP
  16
  17
  18 #include <map>
  19
  20 #include <boost/range/begin.hpp>
  21 #include <boost/range/end.hpp>
  22 #include <boost/range/size.hpp>
  23
  24 #include <boost/geometry/core/tags.hpp>
  25
  26 #include <boost/geometry/algorithms/covered_by.hpp>
  27 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
  28 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
  29 #include <boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp>
  30 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
  31 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
  32
  33
  34 namespace boost { namespace geometry
  35 {
  36
  37
  38 #ifndef DOXYGEN_NO_DETAIL
  39 namespace detail { namespace overlay
  40 {
  41
  42 struct ring_turn_info
  43 {
  44     bool has_traversed_turn;
  45     bool has_blocked_turn;
  46     bool within_other;
  47
  48     ring_turn_info()
  49         : has_traversed_turn(false)
  50         , has_blocked_turn(false)
  51         , within_other(false)
  52     {}
  53 };
  54
  55 namespace dispatch
  56 {
  57
  58     template <typename Tag, typename Geometry>
  59     struct select_rings
  60     {};
  61
  62     template <typename Box>
  63     struct select_rings<box_tag, Box>
  64     {
  65         template <typename Geometry, typename RingPropertyMap, typename Strategy>
  66         static inline void apply(Box const& box, Geometry const& ,
  67                 ring_identifier const& id, RingPropertyMap& ring_properties,
  68                 Strategy const& strategy)
  69         {
  70             ring_properties[id] = typename RingPropertyMap::mapped_type(box, strategy);
  71         }
  72
  73         template <typename RingPropertyMap, typename Strategy>
  74         static inline void apply(Box const& box,
  75                 ring_identifier const& id, RingPropertyMap& ring_properties,
  76                 Strategy const& strategy)
  77         {
  78             ring_properties[id] = typename RingPropertyMap::mapped_type(box, strategy);
  79         }
  80     };
  81
  82     template <typename Ring>
  83     struct select_rings<ring_tag, Ring>
  84     {
  85         template <typename Geometry, typename RingPropertyMap, typename Strategy>
  86         static inline void apply(Ring const& ring, Geometry const& ,
  87                     ring_identifier const& id, RingPropertyMap& ring_properties,
  88                     Strategy const& strategy)
  89         {
  90             if (boost::size(ring) > 0)
  91             {
  92                 ring_properties[id] = typename RingPropertyMap::mapped_type(ring, strategy);
  93             }
  94         }
  95
  96         template <typename RingPropertyMap, typename Strategy>
  97         static inline void apply(Ring const& ring,
  98                     ring_identifier const& id, RingPropertyMap& ring_properties,
  99                     Strategy const& strategy)
 100         {
 101             if (boost::size(ring) > 0)
 102             {
 103                 ring_properties[id] = typename RingPropertyMap::mapped_type(ring, strategy);
 104             }
 105         }
 106     };
 107
 108
 109     template <typename Polygon>
 110     struct select_rings<polygon_tag, Polygon>
 111     {
 112         template <typename Geometry, typename RingPropertyMap, typename Strategy>
 113         static inline void apply(Polygon const& polygon, Geometry const& geometry,
 114                     ring_identifier id, RingPropertyMap& ring_properties,
 115                     Strategy const& strategy)
 116         {
 117             typedef typename geometry::ring_type<Polygon>::type ring_type;
 118             typedef select_rings<ring_tag, ring_type> per_ring;
 119
 120             per_ring::apply(exterior_ring(polygon), geometry, id, ring_properties, strategy);
 121
 122             typename interior_return_type<Polygon const>::type
 123                 rings = interior_rings(polygon);
 124             for (typename detail::interior_iterator<Polygon const>::type
 125                     it = boost::begin(rings); it != boost::end(rings); ++it)
 126             {
 127                 id.ring_index++;
 128                 per_ring::apply(*it, geometry, id, ring_properties, strategy);
 129             }
 130         }
 131
 132         template <typename RingPropertyMap, typename Strategy>
 133         static inline void apply(Polygon const& polygon,
 134                 ring_identifier id, RingPropertyMap& ring_properties,
 135                 Strategy const& strategy)
 136         {
 137             typedef typename geometry::ring_type<Polygon>::type ring_type;
 138             typedef select_rings<ring_tag, ring_type> per_ring;
 139
 140             per_ring::apply(exterior_ring(polygon), id, ring_properties, strategy);
 141
 142             typename interior_return_type<Polygon const>::type
 143                 rings = interior_rings(polygon);
 144             for (typename detail::interior_iterator<Polygon const>::type
 145                     it = boost::begin(rings); it != boost::end(rings); ++it)
 146             {
 147                 id.ring_index++;
 148                 per_ring::apply(*it, id, ring_properties, strategy);
 149             }
 150         }
 151     };
 152
 153     template <typename Multi>
 154     struct select_rings<multi_polygon_tag, Multi>
 155     {
 156         template <typename Geometry, typename RingPropertyMap, typename Strategy>
 157         static inline void apply(Multi const& multi, Geometry const& geometry,
 158                     ring_identifier id, RingPropertyMap& ring_properties,
 159                     Strategy const& strategy)
 160         {
 161             typedef typename boost::range_iterator
 162                 <
 163                     Multi const
 164                 >::type iterator_type;
 165
 166             typedef select_rings<polygon_tag, typename boost::range_value<Multi>::type> per_polygon;
 167
 168             id.multi_index = 0;
 169             for (iterator_type it = boost::begin(multi); it != boost::end(multi); ++it)
 170             {
 171                 id.ring_index = -1;
 172                 per_polygon::apply(*it, geometry, id, ring_properties, strategy);
 173                 id.multi_index++;
 174             }
 175         }
 176     };
 177
 178 } // namespace dispatch
 179
 180
 181 template<overlay_type OverlayType>
 182 struct decide
 183 {
 184     // Default implementation (union, inflate, deflate, dissolve)
 185     static bool include(ring_identifier const& , ring_turn_info const& info)
 186     {
 187         return ! info.within_other;
 188     }
 189
 190     static bool reversed(ring_identifier const& , ring_turn_info const& )
 191     {
 192         return false;
 193     }
 194
 195 };
 196
 197 template<>
 198 struct decide<overlay_difference>
 199 {
 200     static bool include(ring_identifier const& id, ring_turn_info const& info)
 201     {
 202         // Difference: A - B
 203
 204         // If this is A (source_index=0), then the ring is inside B
 205         // If this is B (source_index=1), then the ring is NOT inside A
 206
 207         // If this is A and the ring is within the other geometry,
 208         // then we should NOT include it.
 209         // If this is B then we SHOULD include it.
 210
 211         return id.source_index == 0
 212             ? ! info.within_other
 213             : info.within_other;
 214     }
 215
 216     static bool reversed(ring_identifier const& id, ring_turn_info const& info)
 217     {
 218         // Difference: A - B
 219         // If this is B, and the ring is included, it should be reversed afterwards
 220
 221         return id.source_index == 1 && include(id, info);
 222     }
 223 };
 224
 225 template<>
 226 struct decide<overlay_intersection>
 227 {
 228     static bool include(ring_identifier const& , ring_turn_info const& info)
 229     {
 230         return info.within_other;
 231     }
 232
 233     static bool reversed(ring_identifier const& , ring_turn_info const& )
 234     {
 235         return false;
 236     }
 237 };
 238
 239 template
 240 <
 241     overlay_type OverlayType,
 242     typename Geometry1,
 243     typename Geometry2,
 244     typename TurnInfoMap,
 245     typename RingPropertyMap,
 246     typename Strategy
 247 >
 248 inline void update_ring_selection(Geometry1 const& geometry1,
 249             Geometry2 const& geometry2,
 250             TurnInfoMap const& turn_info_map,
 251             RingPropertyMap const& all_ring_properties,
 252             RingPropertyMap& selected_ring_properties,
 253             Strategy const& strategy)
 254 {
 255     selected_ring_properties.clear();
 256
 257     for (typename RingPropertyMap::const_iterator it = boost::begin(all_ring_properties);
 258         it != boost::end(all_ring_properties);
 259         ++it)
 260     {
 261         ring_identifier const& id = it->first;
 262
 263         ring_turn_info info;
 264
 265         typename TurnInfoMap::const_iterator tcit = turn_info_map.find(id);
 266         if (tcit != turn_info_map.end())
 267         {
 268             info = tcit->second; // Copy by value
 269         }
 270
 271         if (info.has_traversed_turn || info.has_blocked_turn)
 272         {
 273             // This turn is traversed or blocked,
 274             // don't include the original ring
 275             continue;
 276         }
 277
 278         // Check if the ring is within the other geometry, by taking
 279         // a point lying on the ring
 280         switch(id.source_index)
 281         {
 282             // within
 283             case 0 :
 284                 info.within_other = range_in_geometry(it->second.point,
 285                                                       geometry1, geometry2,
 286                                                       strategy) > 0;
 287                 break;
 288             case 1 :
 289                 info.within_other = range_in_geometry(it->second.point,
 290                                                       geometry2, geometry1,
 291                                                       strategy) > 0;
 292                 break;
 293         }
 294
 295         if (decide<OverlayType>::include(id, info))
 296         {
 297             typename RingPropertyMap::mapped_type properties = it->second; // Copy by value
 298             properties.reversed = decide<OverlayType>::reversed(id, info);
 299             selected_ring_properties[id] = properties;
 300         }
 301     }
 302 }
 303
 304
 305 /*!
 306 \brief The function select_rings select rings based on the overlay-type (union,intersection)
 307 */
 308 template
 309 <
 310     overlay_type OverlayType,
 311     typename Geometry1,
 312     typename Geometry2,
 313     typename RingTurnInfoMap,
 314     typename RingPropertyMap,
 315     typename Strategy
 316 >
 317 inline void select_rings(Geometry1 const& geometry1, Geometry2 const& geometry2,
 318             RingTurnInfoMap const& turn_info_per_ring,
 319             RingPropertyMap& selected_ring_properties,
 320             Strategy const& strategy)
 321 {
 322     typedef typename geometry::tag<Geometry1>::type tag1;
 323     typedef typename geometry::tag<Geometry2>::type tag2;
 324
 325     RingPropertyMap all_ring_properties;
 326     dispatch::select_rings<tag1, Geometry1>::apply(geometry1, geometry2,
 327                 ring_identifier(0, -1, -1), all_ring_properties,
 328                 strategy);
 329     dispatch::select_rings<tag2, Geometry2>::apply(geometry2, geometry1,
 330                 ring_identifier(1, -1, -1), all_ring_properties,
 331                 strategy);
 332
 333     update_ring_selection<OverlayType>(geometry1, geometry2, turn_info_per_ring,
 334                 all_ring_properties, selected_ring_properties,
 335                 strategy);
 336 }
 337
 338 template
 339 <
 340     overlay_type OverlayType,
 341     typename Geometry,
 342     typename RingTurnInfoMap,
 343     typename RingPropertyMap,
 344     typename Strategy
 345 >
 346 inline void select_rings(Geometry const& geometry,
 347             RingTurnInfoMap const& turn_info_per_ring,
 348             RingPropertyMap& selected_ring_properties,
 349             Strategy const& strategy)
 350 {
 351     typedef typename geometry::tag<Geometry>::type tag;
 352
 353     RingPropertyMap all_ring_properties;
 354     dispatch::select_rings<tag, Geometry>::apply(geometry,
 355                 ring_identifier(0, -1, -1), all_ring_properties,
 356                 strategy);
 357
 358     update_ring_selection<OverlayType>(geometry, geometry, turn_info_per_ring,
 359                 all_ring_properties, selected_ring_properties,
 360                 strategy);
 361 }
 362
 363
 364 }} // namespace detail::overlay
 365 #endif // DOXYGEN_NO_DETAIL
 366
 367
 368 }} // namespace boost::geometry
 369
 370
 371 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP