ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/overlay/assign_parents.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_ASSIGN_PARENTS_HPP
  10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP
  11
  12 #include <boost/range.hpp>
  13
  14 #include <boost/geometry/algorithms/area.hpp>
  15 #include <boost/geometry/algorithms/envelope.hpp>
  16 #include <boost/geometry/algorithms/expand.hpp>
  17 #include <boost/geometry/algorithms/detail/partition.hpp>
  18 #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
  19 #include <boost/geometry/algorithms/within.hpp>
  20
  21 #include <boost/geometry/geometries/box.hpp>
  22
  23 namespace boost { namespace geometry
  24 {
  25
  26
  27 #ifndef DOXYGEN_NO_DETAIL
  28 namespace detail { namespace overlay
  29 {
  30
  31
  32
  33 template
  34 <
  35     typename Item,
  36     typename Geometry1, typename Geometry2,
  37     typename RingCollection
  38 >
  39 static inline bool within_selected_input(Item const& item2, ring_identifier const& ring_id,
  40         Geometry1 const& geometry1, Geometry2 const& geometry2,
  41         RingCollection const& collection)
  42 {
  43     typedef typename geometry::tag<Geometry1>::type tag1;
  44     typedef typename geometry::tag<Geometry2>::type tag2;
  45
  46     switch (ring_id.source_index)
  47     {
  48         case 0 :
  49             return geometry::within(item2.point,
  50                 get_ring<tag1>::apply(ring_id, geometry1));
  51             break;
  52         case 1 :
  53             return geometry::within(item2.point,
  54                 get_ring<tag2>::apply(ring_id, geometry2));
  55             break;
  56         case 2 :
  57             return geometry::within(item2.point,
  58                 get_ring<void>::apply(ring_id, collection));
  59             break;
  60     }
  61     return false;
  62 }
  63
  64
  65 template <typename Point>
  66 struct ring_info_helper
  67 {
  68     typedef typename geometry::default_area_result<Point>::type area_type;
  69
  70     ring_identifier id;
  71     area_type real_area;
  72     area_type abs_area;
  73     model::box<Point> envelope;
  74
  75     inline ring_info_helper()
  76         : real_area(0), abs_area(0)
  77     {}
  78
  79     inline ring_info_helper(ring_identifier i, area_type a)
  80         : id(i), real_area(a), abs_area(geometry::math::abs(a))
  81     {}
  82 };
  83
  84
  85 struct ring_info_helper_get_box
  86 {
  87     template <typename Box, typename InputItem>
  88     static inline void apply(Box& total, InputItem const& item)
  89     {
  90         geometry::expand(total, item.envelope);
  91     }
  92 };
  93
  94 struct ring_info_helper_ovelaps_box
  95 {
  96     template <typename Box, typename InputItem>
  97     static inline bool apply(Box const& box, InputItem const& item)
  98     {
  99         return ! geometry::detail::disjoint::disjoint_box_box(box, item.envelope);
 100     }
 101 };
 102
 103 template <typename Geometry1, typename Geometry2, typename Collection, typename RingMap>
 104 struct assign_visitor
 105 {
 106     typedef typename RingMap::mapped_type ring_info_type;
 107
 108     Geometry1 const& m_geometry1;
 109     Geometry2 const& m_geometry2;
 110     Collection const& m_collection;
 111     RingMap& m_ring_map;
 112     bool m_check_for_orientation;
 113
 114
 115     inline assign_visitor(Geometry1 const& g1, Geometry2 const& g2, Collection const& c,
 116                 RingMap& map, bool check)
 117         : m_geometry1(g1)
 118         , m_geometry2(g2)
 119         , m_collection(c)
 120         , m_ring_map(map)
 121         , m_check_for_orientation(check)
 122     {}
 123
 124     template <typename Item>
 125     inline void apply(Item const& outer, Item const& inner, bool first = true)
 126     {
 127         if (first && outer.abs_area < inner.abs_area)
 128         {
 129             // Apply with reversed arguments
 130             apply(inner, outer, false);
 131             return;
 132         }
 133
 134         if (m_check_for_orientation
 135          || (math::larger(outer.real_area, 0)
 136           && math::smaller(inner.real_area, 0)))
 137         {
 138             ring_info_type& inner_in_map = m_ring_map[inner.id];
 139
 140             if (geometry::within(inner_in_map.point, outer.envelope)
 141                && within_selected_input(inner_in_map, outer.id, m_geometry1, m_geometry2, m_collection)
 142                )
 143             {
 144                 // Assign a parent if there was no earlier parent, or the newly
 145                 // found parent is smaller than the previous one
 146                 if (inner_in_map.parent.source_index == -1
 147                     || outer.abs_area < inner_in_map.parent_area)
 148                 {
 149                     inner_in_map.parent = outer.id;
 150                     inner_in_map.parent_area = outer.abs_area;
 151                 }
 152             }
 153         }
 154     }
 155 };
 156
 157
 158
 159
 160 template
 161 <
 162     typename Geometry1, typename Geometry2,
 163     typename RingCollection,
 164     typename RingMap
 165 >
 166 inline void assign_parents(Geometry1 const& geometry1,
 167             Geometry2 const& geometry2,
 168             RingCollection const& collection,
 169             RingMap& ring_map,
 170             bool check_for_orientation = false)
 171 {
 172     typedef typename geometry::tag<Geometry1>::type tag1;
 173     typedef typename geometry::tag<Geometry2>::type tag2;
 174
 175     typedef typename RingMap::mapped_type ring_info_type;
 176     typedef typename ring_info_type::point_type point_type;
 177     typedef model::box<point_type> box_type;
 178
 179     typedef typename RingMap::iterator map_iterator_type;
 180
 181     {
 182         typedef ring_info_helper<point_type> helper;
 183         typedef std::vector<helper> vector_type;
 184         typedef typename boost::range_iterator<vector_type const>::type vector_iterator_type;
 185
 186         std::size_t count_total = ring_map.size();
 187         std::size_t count_positive = 0;
 188         std::size_t index_positive = 0; // only used if count_positive>0
 189         std::size_t index = 0;
 190
 191         // Copy to vector (with new approach this might be obsolete as well, using the map directly)
 192         vector_type vector(count_total);
 193
 194         for (map_iterator_type it = boost::begin(ring_map);
 195             it != boost::end(ring_map); ++it, ++index)
 196         {
 197             vector[index] = helper(it->first, it->second.get_area());
 198             helper& item = vector[index];
 199             switch(it->first.source_index)
 200             {
 201                 case 0 :
 202                     geometry::envelope(get_ring<tag1>::apply(it->first, geometry1),
 203                             item.envelope);
 204                     break;
 205                 case 1 :
 206                     geometry::envelope(get_ring<tag2>::apply(it->first, geometry2),
 207                             item.envelope);
 208                     break;
 209                 case 2 :
 210                     geometry::envelope(get_ring<void>::apply(it->first, collection),
 211                             item.envelope);
 212                     break;
 213             }
 214             if (item.real_area > 0)
 215             {
 216                 count_positive++;
 217                 index_positive = index;
 218             }
 219         }
 220
 221         if (! check_for_orientation)
 222         {
 223             if (count_positive == count_total)
 224             {
 225                 // Optimization for only positive rings
 226                 // -> no assignment of parents or reversal necessary, ready here.
 227                 return;
 228             }
 229
 230             if (count_positive == 1)
 231             {
 232                 // Optimization for one outer ring
 233                 // -> assign this as parent to all others (all interior rings)
 234                 // In unions, this is probably the most occuring case and gives
 235                 //    a dramatic improvement (factor 5 for star_comb testcase)
 236                 ring_identifier id_of_positive = vector[index_positive].id;
 237                 ring_info_type& outer = ring_map[id_of_positive];
 238                 index = 0;
 239                 for (vector_iterator_type it = boost::begin(vector);
 240                     it != boost::end(vector); ++it, ++index)
 241                 {
 242                     if (index != index_positive)
 243                     {
 244                         ring_info_type& inner = ring_map[it->id];
 245                         inner.parent = id_of_positive;
 246                         outer.children.push_back(it->id);
 247                     }
 248                 }
 249                 return;
 250             }
 251         }
 252
 253         assign_visitor
 254             <
 255                 Geometry1, Geometry2,
 256                 RingCollection, RingMap
 257             > visitor(geometry1, geometry2, collection, ring_map, check_for_orientation);
 258
 259         geometry::partition
 260             <
 261                 box_type, ring_info_helper_get_box, ring_info_helper_ovelaps_box
 262             >::apply(vector, visitor);
 263     }
 264
 265     if (check_for_orientation)
 266     {
 267         for (map_iterator_type it = boost::begin(ring_map);
 268             it != boost::end(ring_map); ++it)
 269         {
 270             if (geometry::math::equals(it->second.get_area(), 0))
 271             {
 272                 it->second.discarded = true;
 273             }
 274             else if (it->second.parent.source_index >= 0
 275                     && math::larger(it->second.get_area(), 0))
 276             {
 277                 const ring_info_type& parent = ring_map[it->second.parent];
 278
 279                 if (math::larger(parent.area, 0))
 280                 {
 281                     // Discard positive inner ring with positive parent
 282                     it->second.discarded = true;
 283                 }
 284                 // Remove parent ID from any positive inner ring
 285                 it->second.parent.source_index = -1;
 286             }
 287             else if (it->second.parent.source_index < 0
 288                     && math::smaller(it->second.get_area(), 0))
 289             {
 290                 // Reverse negative ring without parent
 291                 it->second.reversed = true;
 292             }
 293         }
 294     }
 295
 296     // Assign childlist
 297     for (map_iterator_type it = boost::begin(ring_map);
 298         it != boost::end(ring_map); ++it)
 299     {
 300         if (it->second.parent.source_index >= 0)
 301         {
 302             ring_map[it->second.parent].children.push_back(it->first);
 303         }
 304     }
 305 }
 306
 307
 308 // Version for one geometry (called by buffer)
 309 template
 310 <
 311     typename Geometry,
 312     typename RingCollection,
 313     typename RingMap
 314 >
 315 inline void assign_parents(Geometry const& geometry,
 316             RingCollection const& collection,
 317             RingMap& ring_map,
 318             bool check_for_orientation)
 319 {
 320     // Call it with an empty geometry as second geometry (source_id == 1)
 321     // (ring_map should be empty for source_id==1)
 322
 323     Geometry empty;
 324     assign_parents(geometry, empty, collection, ring_map, check_for_orientation);
 325 }
 326
 327
 328 }} // namespace detail::overlay
 329 #endif // DOXYGEN_NO_DETAIL
 330
 331
 332 }} // namespace geometry
 333
 334
 335 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP