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