ceph/src/boost/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 // This file was modified by Oracle on 2017.
   6 // Modifications copyright (c) 2017 Oracle and/or its affiliates.
   7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   8
   9 // Use, modification and distribution is subject to the Boost Software License,
  10 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  11 // http://www.boost.org/LICENSE_1_0.txt)
  12
  13 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP
  14 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP
  15
  16 #include <boost/range.hpp>
  17
  18 #include <boost/geometry/algorithms/area.hpp>
  19 #include <boost/geometry/algorithms/envelope.hpp>
  20 #include <boost/geometry/algorithms/expand.hpp>
  21 #include <boost/geometry/algorithms/detail/partition.hpp>
  22 #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
  23 #include <boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp>
  24 #include <boost/geometry/algorithms/covered_by.hpp>
  25
  26 #include <boost/geometry/geometries/box.hpp>
  27
  28 namespace boost { namespace geometry
  29 {
  30
  31
  32 #ifndef DOXYGEN_NO_DETAIL
  33 namespace detail { namespace overlay
  34 {
  35
  36
  37
  38 template
  39 <
  40     typename Item,
  41     typename InnerGeometry,
  42     typename Geometry1, typename Geometry2,
  43     typename RingCollection,
  44     typename Strategy
  45 >
  46 static inline bool within_selected_input(Item const& item2,
  47         InnerGeometry const& inner_geometry,
  48         ring_identifier const& outer_id,
  49         Geometry1 const& geometry1, Geometry2 const& geometry2,
  50         RingCollection const& collection,
  51         Strategy const& strategy)
  52 {
  53     typedef typename geometry::tag<Geometry1>::type tag1;
  54     typedef typename geometry::tag<Geometry2>::type tag2;
  55
  56     // NOTE: range_in_geometry first checks the item2.point and then
  57     // if this point is on boundary it checks points of inner_geometry
  58     // ring until a point inside/outside other geometry ring is found
  59     switch (outer_id.source_index)
  60     {
  61         // covered_by
  62         case 0 :
  63             return range_in_geometry(item2.point, inner_geometry,
  64                 get_ring<tag1>::apply(outer_id, geometry1), strategy) >= 0;
  65         case 1 :
  66             return range_in_geometry(item2.point, inner_geometry,
  67                 get_ring<tag2>::apply(outer_id, geometry2), strategy) >= 0;
  68         case 2 :
  69             return range_in_geometry(item2.point, inner_geometry,
  70                 get_ring<void>::apply(outer_id, collection), strategy) >= 0;
  71     }
  72     return false;
  73 }
  74
  75 template
  76 <
  77     typename Item,
  78     typename Geometry1, typename Geometry2,
  79     typename RingCollection,
  80     typename Strategy
  81 >
  82 static inline bool within_selected_input(Item const& item2,
  83         ring_identifier const& inner_id, ring_identifier const& outer_id,
  84         Geometry1 const& geometry1, Geometry2 const& geometry2,
  85         RingCollection const& collection,
  86         Strategy const& strategy)
  87 {
  88     typedef typename geometry::tag<Geometry1>::type tag1;
  89     typedef typename geometry::tag<Geometry2>::type tag2;
  90
  91     switch (inner_id.source_index)
  92     {
  93         case 0 :
  94             return within_selected_input(item2,
  95                get_ring<tag1>::apply(inner_id, geometry1),
  96                outer_id, geometry1, geometry2, collection, strategy);
  97         case 1 :
  98             return within_selected_input(item2,
  99                get_ring<tag2>::apply(inner_id, geometry2),
 100                outer_id, geometry1, geometry2, collection, strategy);
 101         case 2 :
 102             return within_selected_input(item2,
 103                 get_ring<void>::apply(inner_id, collection),
 104                 outer_id, geometry1, geometry2, collection, strategy);
 105     }
 106     return false;
 107 }
 108
 109
 110 template <typename Point, typename AreaType>
 111 struct ring_info_helper
 112 {
 113     ring_identifier id;
 114     AreaType real_area;
 115     AreaType abs_area;
 116     model::box<Point> envelope;
 117
 118     inline ring_info_helper()
 119         : real_area(0), abs_area(0)
 120     {}
 121
 122     inline ring_info_helper(ring_identifier i, AreaType const& a)
 123         : id(i), real_area(a), abs_area(geometry::math::abs(a))
 124     {}
 125 };
 126
 127
 128 struct ring_info_helper_get_box
 129 {
 130     template <typename Box, typename InputItem>
 131     static inline void apply(Box& total, InputItem const& item)
 132     {
 133         geometry::expand(total, item.envelope);
 134     }
 135 };
 136
 137 struct ring_info_helper_ovelaps_box
 138 {
 139     template <typename Box, typename InputItem>
 140     static inline bool apply(Box const& box, InputItem const& item)
 141     {
 142         return ! geometry::detail::disjoint::disjoint_box_box(box, item.envelope);
 143     }
 144 };
 145
 146 template
 147 <
 148     typename Geometry1,
 149     typename Geometry2,
 150     typename Collection,
 151     typename RingMap,
 152     typename Strategy
 153 >
 154 struct assign_visitor
 155 {
 156     typedef typename RingMap::mapped_type ring_info_type;
 157
 158     Geometry1 const& m_geometry1;
 159     Geometry2 const& m_geometry2;
 160     Collection const& m_collection;
 161     RingMap& m_ring_map;
 162     Strategy const& m_strategy;
 163     bool m_check_for_orientation;
 164
 165     inline assign_visitor(Geometry1 const& g1, Geometry2 const& g2, Collection const& c,
 166                           RingMap& map, Strategy const& strategy, bool check)
 167         : m_geometry1(g1)
 168         , m_geometry2(g2)
 169         , m_collection(c)
 170         , m_ring_map(map)
 171         , m_strategy(strategy)
 172         , m_check_for_orientation(check)
 173     {}
 174
 175     template <typename Item>
 176     inline bool apply(Item const& outer, Item const& inner, bool first = true)
 177     {
 178         if (first && outer.abs_area < inner.abs_area)
 179         {
 180             // Apply with reversed arguments
 181             apply(inner, outer, false);
 182             return true;
 183         }
 184
 185         if (m_check_for_orientation
 186          || (math::larger(outer.real_area, 0)
 187           && math::smaller(inner.real_area, 0)))
 188         {
 189             ring_info_type& inner_in_map = m_ring_map[inner.id];
 190
 191             if (geometry::covered_by(inner_in_map.point, outer.envelope)
 192                && within_selected_input(inner_in_map, inner.id, outer.id,
 193                                         m_geometry1, m_geometry2, m_collection,
 194                                         m_strategy)
 195                )
 196             {
 197                 // Assign a parent if there was no earlier parent, or the newly
 198                 // found parent is smaller than the previous one
 199                 if (inner_in_map.parent.source_index == -1
 200                     || outer.abs_area < inner_in_map.parent_area)
 201                 {
 202                     inner_in_map.parent = outer.id;
 203                     inner_in_map.parent_area = outer.abs_area;
 204                 }
 205             }
 206         }
 207
 208         return true;
 209     }
 210 };
 211
 212
 213
 214
 215 template
 216 <
 217     typename Geometry1, typename Geometry2,
 218     typename RingCollection,
 219     typename RingMap,
 220     typename Strategy
 221 >
 222 inline void assign_parents(Geometry1 const& geometry1,
 223             Geometry2 const& geometry2,
 224             RingCollection const& collection,
 225             RingMap& ring_map,
 226             Strategy const& strategy,
 227             bool check_for_orientation = false,
 228             bool discard_double_negative = false)
 229 {
 230     typedef typename geometry::tag<Geometry1>::type tag1;
 231     typedef typename geometry::tag<Geometry2>::type tag2;
 232
 233     typedef typename RingMap::mapped_type ring_info_type;
 234     typedef typename ring_info_type::point_type point_type;
 235     typedef model::box<point_type> box_type;
 236     typedef typename Strategy::template area_strategy
 237         <
 238             point_type
 239         >::type::return_type area_result_type;
 240
 241     typedef typename RingMap::iterator map_iterator_type;
 242
 243     {
 244         typedef ring_info_helper<point_type, area_result_type> helper;
 245         typedef std::vector<helper> vector_type;
 246         typedef typename boost::range_iterator<vector_type const>::type vector_iterator_type;
 247
 248         std::size_t count_total = ring_map.size();
 249         std::size_t count_positive = 0;
 250         std::size_t index_positive = 0; // only used if count_positive>0
 251         std::size_t index = 0;
 252
 253         // Copy to vector (with new approach this might be obsolete as well, using the map directly)
 254         vector_type vector(count_total);
 255
 256         for (map_iterator_type it = boost::begin(ring_map);
 257             it != boost::end(ring_map); ++it, ++index)
 258         {
 259             vector[index] = helper(it->first, it->second.get_area());
 260             helper& item = vector[index];
 261             switch(it->first.source_index)
 262             {
 263                 case 0 :
 264                     geometry::envelope(get_ring<tag1>::apply(it->first, geometry1),
 265                                        item.envelope, strategy.get_envelope_strategy());
 266                     break;
 267                 case 1 :
 268                     geometry::envelope(get_ring<tag2>::apply(it->first, geometry2),
 269                                        item.envelope, strategy.get_envelope_strategy());
 270                     break;
 271                 case 2 :
 272                     geometry::envelope(get_ring<void>::apply(it->first, collection),
 273                                        item.envelope, strategy.get_envelope_strategy());
 274                     break;
 275             }
 276
 277             // Expand envelope slightly
 278             expand_by_epsilon(item.envelope);
 279
 280             if (item.real_area > 0)
 281             {
 282                 count_positive++;
 283                 index_positive = index;
 284             }
 285         }
 286
 287         if (! check_for_orientation)
 288         {
 289             if (count_positive == count_total)
 290             {
 291                 // Optimization for only positive rings
 292                 // -> no assignment of parents or reversal necessary, ready here.
 293                 return;
 294             }
 295
 296             if (count_positive == 1)
 297             {
 298                 // Optimization for one outer ring
 299                 // -> assign this as parent to all others (all interior rings)
 300                 // In unions, this is probably the most occuring case and gives
 301                 //    a dramatic improvement (factor 5 for star_comb testcase)
 302                 ring_identifier id_of_positive = vector[index_positive].id;
 303                 ring_info_type& outer = ring_map[id_of_positive];
 304                 index = 0;
 305                 for (vector_iterator_type it = boost::begin(vector);
 306                     it != boost::end(vector); ++it, ++index)
 307                 {
 308                     if (index != index_positive)
 309                     {
 310                         ring_info_type& inner = ring_map[it->id];
 311                         inner.parent = id_of_positive;
 312                         outer.children.push_back(it->id);
 313                     }
 314                 }
 315                 return;
 316             }
 317         }
 318
 319         assign_visitor
 320             <
 321                 Geometry1, Geometry2,
 322                 RingCollection, RingMap,
 323                 Strategy
 324             > visitor(geometry1, geometry2, collection, ring_map, strategy, check_for_orientation);
 325
 326         geometry::partition
 327             <
 328                 box_type
 329             >::apply(vector, visitor, ring_info_helper_get_box(),
 330                      ring_info_helper_ovelaps_box());
 331     }
 332
 333     if (check_for_orientation)
 334     {
 335         for (map_iterator_type it = boost::begin(ring_map);
 336             it != boost::end(ring_map); ++it)
 337         {
 338             ring_info_type& info = it->second;
 339             if (geometry::math::equals(info.get_area(), 0))
 340             {
 341                 info.discarded = true;
 342             }
 343             else if (info.parent.source_index >= 0)
 344             {
 345                 const ring_info_type& parent = ring_map[info.parent];
 346                 bool const pos = math::larger(info.get_area(), 0);
 347                 bool const parent_pos = math::larger(parent.area, 0);
 348
 349                 bool const double_neg = discard_double_negative && ! pos && ! parent_pos;
 350
 351                 if ((pos && parent_pos) || double_neg)
 352                 {
 353                     // Discard positive inner ring with positive parent
 354                     // Also, for some cases (dissolve), negative inner ring
 355                     // with negative parent shouild be discarded
 356                     info.discarded = true;
 357                 }
 358
 359                 if (pos || info.discarded)
 360                 {
 361                     // Remove parent ID from any positive or discarded inner rings
 362                     info.parent.source_index = -1;
 363                 }
 364             }
 365             else if (info.parent.source_index < 0
 366                     && math::smaller(info.get_area(), 0))
 367             {
 368                 // Reverse negative ring without parent
 369                 info.reversed = true;
 370             }
 371         }
 372     }
 373
 374     // Assign childlist
 375     for (map_iterator_type it = boost::begin(ring_map);
 376         it != boost::end(ring_map); ++it)
 377     {
 378         if (it->second.parent.source_index >= 0)
 379         {
 380             ring_map[it->second.parent].children.push_back(it->first);
 381         }
 382     }
 383 }
 384
 385
 386 // Version for one geometry (called by buffer/dissolve)
 387 template
 388 <
 389     typename Geometry,
 390     typename RingCollection,
 391     typename RingMap,
 392     typename Strategy
 393 >
 394 inline void assign_parents(Geometry const& geometry,
 395             RingCollection const& collection,
 396             RingMap& ring_map,
 397             Strategy const& strategy,
 398             bool check_for_orientation,
 399             bool discard_double_negative)
 400 {
 401     // Call it with an empty geometry as second geometry (source_id == 1)
 402     // (ring_map should be empty for source_id==1)
 403
 404     Geometry empty;
 405     assign_parents(geometry, empty, collection, ring_map, strategy,
 406                    check_for_orientation, discard_double_negative);
 407 }
 408
 409
 410 }} // namespace detail::overlay
 411 #endif // DOXYGEN_NO_DETAIL
 412
 413
 414 }} // namespace geometry
 415
 416
 417 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP