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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 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/point_on_border.hpp>
  24 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
  25 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
  26 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
  27
  28
  29 namespace boost { namespace geometry
  30 {
  31
  32
  33 #ifndef DOXYGEN_NO_DETAIL
  34 namespace detail { namespace overlay
  35 {
  36
  37
  38 namespace dispatch
  39 {
  40
  41     template <typename Tag, typename Geometry>
  42     struct select_rings
  43     {};
  44
  45     template <typename Box>
  46     struct select_rings<box_tag, Box>
  47     {
  48         template <typename Geometry, typename Map>
  49         static inline void apply(Box const& box, Geometry const& ,
  50                 ring_identifier const& id, Map& map, bool midpoint)
  51         {
  52             map[id] = typename Map::mapped_type(box, midpoint);
  53         }
  54
  55         template <typename Map>
  56         static inline void apply(Box const& box,
  57                 ring_identifier const& id, Map& map, bool midpoint)
  58         {
  59             map[id] = typename Map::mapped_type(box, midpoint);
  60         }
  61     };
  62
  63     template <typename Ring>
  64     struct select_rings<ring_tag, Ring>
  65     {
  66         template <typename Geometry, typename Map>
  67         static inline void apply(Ring const& ring, Geometry const& ,
  68                     ring_identifier const& id, Map& map, bool midpoint)
  69         {
  70             if (boost::size(ring) > 0)
  71             {
  72                 map[id] = typename Map::mapped_type(ring, midpoint);
  73             }
  74         }
  75
  76         template <typename Map>
  77         static inline void apply(Ring const& ring,
  78                     ring_identifier const& id, Map& map, bool midpoint)
  79         {
  80             if (boost::size(ring) > 0)
  81             {
  82                 map[id] = typename Map::mapped_type(ring, midpoint);
  83             }
  84         }
  85     };
  86
  87
  88     template <typename Polygon>
  89     struct select_rings<polygon_tag, Polygon>
  90     {
  91         template <typename Geometry, typename Map>
  92         static inline void apply(Polygon const& polygon, Geometry const& geometry,
  93                     ring_identifier id, Map& map, bool midpoint)
  94         {
  95             typedef typename geometry::ring_type<Polygon>::type ring_type;
  96             typedef select_rings<ring_tag, ring_type> per_ring;
  97
  98             per_ring::apply(exterior_ring(polygon), geometry, id, map, midpoint);
  99
 100             typename interior_return_type<Polygon const>::type
 101                 rings = interior_rings(polygon);
 102             for (typename detail::interior_iterator<Polygon const>::type
 103                     it = boost::begin(rings); it != boost::end(rings); ++it)
 104             {
 105                 id.ring_index++;
 106                 per_ring::apply(*it, geometry, id, map, midpoint);
 107             }
 108         }
 109
 110         template <typename Map>
 111         static inline void apply(Polygon const& polygon,
 112                 ring_identifier id, Map& map, bool midpoint)
 113         {
 114             typedef typename geometry::ring_type<Polygon>::type ring_type;
 115             typedef select_rings<ring_tag, ring_type> per_ring;
 116
 117             per_ring::apply(exterior_ring(polygon), id, map, midpoint);
 118
 119             typename interior_return_type<Polygon const>::type
 120                 rings = interior_rings(polygon);
 121             for (typename detail::interior_iterator<Polygon const>::type
 122                     it = boost::begin(rings); it != boost::end(rings); ++it)
 123             {
 124                 id.ring_index++;
 125                 per_ring::apply(*it, id, map, midpoint);
 126             }
 127         }
 128     };
 129
 130     template <typename Multi>
 131     struct select_rings<multi_polygon_tag, Multi>
 132     {
 133         template <typename Geometry, typename Map>
 134         static inline void apply(Multi const& multi, Geometry const& geometry,
 135                     ring_identifier id, Map& map, bool midpoint)
 136         {
 137             typedef typename boost::range_iterator
 138                 <
 139                     Multi const
 140                 >::type iterator_type;
 141
 142             typedef select_rings<polygon_tag, typename boost::range_value<Multi>::type> per_polygon;
 143
 144             id.multi_index = 0;
 145             for (iterator_type it = boost::begin(multi); it != boost::end(multi); ++it)
 146             {
 147                 id.ring_index = -1;
 148                 per_polygon::apply(*it, geometry, id, map, midpoint);
 149                 id.multi_index++;
 150             }
 151         }
 152     };
 153
 154 } // namespace dispatch
 155
 156
 157 template<overlay_type OverlayType>
 158 struct decide
 159 {};
 160
 161 template<>
 162 struct decide<overlay_union>
 163 {
 164     template <typename Code>
 165     static bool include(ring_identifier const& , Code const& code)
 166     {
 167         return code.within_code * -1 == 1;
 168     }
 169
 170     template <typename Code>
 171     static bool reversed(ring_identifier const& , Code const& )
 172     {
 173         return false;
 174     }
 175 };
 176
 177 template<>
 178 struct decide<overlay_difference>
 179 {
 180     template <typename Code>
 181     static bool include(ring_identifier const& id, Code const& code)
 182     {
 183         bool is_first = id.source_index == 0;
 184         return code.within_code * -1 * (is_first ? 1 : -1) == 1;
 185     }
 186
 187     template <typename Code>
 188     static bool reversed(ring_identifier const& id, Code const& code)
 189     {
 190         return include(id, code) && id.source_index == 1;
 191     }
 192 };
 193
 194 template<>
 195 struct decide<overlay_intersection>
 196 {
 197     template <typename Code>
 198     static bool include(ring_identifier const& , Code const& code)
 199     {
 200         return code.within_code * 1 == 1;
 201     }
 202
 203     template <typename Code>
 204     static bool reversed(ring_identifier const& , Code const& )
 205     {
 206         return false;
 207     }
 208 };
 209
 210
 211 template
 212 <
 213     overlay_type OverlayType,
 214     typename Geometry1, typename Geometry2,
 215     typename IntersectionMap, typename SelectionMap
 216 >
 217 inline void update_selection_map(Geometry1 const& geometry1,
 218             Geometry2 const& geometry2,
 219             IntersectionMap const& intersection_map,
 220             SelectionMap const& map_with_all, SelectionMap& selection_map)
 221 {
 222     selection_map.clear();
 223
 224     for (typename SelectionMap::const_iterator it = boost::begin(map_with_all);
 225         it != boost::end(map_with_all);
 226         ++it)
 227     {
 228         /*
 229         int union_code = it->second.within_code * -1;
 230         bool is_first = it->first.source_index == 0;
 231         std::cout << it->first << " " << it->second.area
 232             << ": " << it->second.within_code
 233             << " union: " << union_code
 234             << " intersection: " << (it->second.within_code * 1)
 235             << " G1-G2: " << (union_code * (is_first ? 1 : -1))
 236             << " G2-G1: " << (union_code * (is_first ? -1 : 1))
 237             << " -> " << (decide<OverlayType>::include(it->first, it->second) ? "INC" : "")
 238             << decide<OverlayType>::reverse(it->first, it->second)
 239             << std::endl;
 240         */
 241
 242         bool found = intersection_map.find(it->first) != intersection_map.end();
 243         if (! found)
 244         {
 245             ring_identifier const id = it->first;
 246             typename SelectionMap::mapped_type properties = it->second; // Copy by value
 247
 248             // Calculate the "within code" (previously this was done earlier but is
 249             // much efficienter here - it can be even more efficient doing it all at once,
 250             // using partition, TODO)
 251             // So though this is less elegant than before, it avoids many unused point-in-poly calculations
 252             switch(id.source_index)
 253             {
 254                 case 0 :
 255                     properties.within_code
 256                         = geometry::within(properties.point, geometry2) ? 1 : -1;
 257                     break;
 258                 case 1 :
 259                     properties.within_code
 260                         = geometry::within(properties.point, geometry1) ? 1 : -1;
 261                     break;
 262             }
 263
 264             if (decide<OverlayType>::include(id, properties))
 265             {
 266                 properties.reversed = decide<OverlayType>::reversed(id, properties);
 267                 selection_map[id] = properties;
 268             }
 269         }
 270     }
 271 }
 272
 273
 274 /*!
 275 \brief The function select_rings select rings based on the overlay-type (union,intersection)
 276 */
 277 template
 278 <
 279     overlay_type OverlayType,
 280     typename Geometry1, typename Geometry2,
 281     typename IntersectionMap, typename SelectionMap
 282 >
 283 inline void select_rings(Geometry1 const& geometry1, Geometry2 const& geometry2,
 284             IntersectionMap const& intersection_map,
 285             SelectionMap& selection_map, bool midpoint)
 286 {
 287     typedef typename geometry::tag<Geometry1>::type tag1;
 288     typedef typename geometry::tag<Geometry2>::type tag2;
 289
 290     SelectionMap map_with_all;
 291     dispatch::select_rings<tag1, Geometry1>::apply(geometry1, geometry2,
 292                 ring_identifier(0, -1, -1), map_with_all, midpoint);
 293     dispatch::select_rings<tag2, Geometry2>::apply(geometry2, geometry1,
 294                 ring_identifier(1, -1, -1), map_with_all, midpoint);
 295
 296     update_selection_map<OverlayType>(geometry1, geometry2, intersection_map,
 297                 map_with_all, selection_map);
 298 }
 299
 300 template
 301 <
 302     overlay_type OverlayType,
 303     typename Geometry,
 304     typename IntersectionMap, typename SelectionMap
 305 >
 306 inline void select_rings(Geometry const& geometry,
 307             IntersectionMap const& intersection_map,
 308             SelectionMap& selection_map, bool midpoint)
 309 {
 310     typedef typename geometry::tag<Geometry>::type tag;
 311
 312     SelectionMap map_with_all;
 313     dispatch::select_rings<tag, Geometry>::apply(geometry,
 314                 ring_identifier(0, -1, -1), map_with_all, midpoint);
 315
 316     update_selection_map<OverlayType>(geometry, geometry, intersection_map,
 317                 map_with_all, selection_map);
 318 }
 319
 320
 321 }} // namespace detail::overlay
 322 #endif // DOXYGEN_NO_DETAIL
 323
 324
 325 }} // namespace boost::geometry
 326
 327
 328 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP