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