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