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