detail/overlay/assign_parents.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2017-2023.
0007 // Modifications copyright (c) 2017-2023 Oracle and/or its affiliates.
0008 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010
0011 // Use, modification and distribution is subject to the Boost Software License,
0012 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0013 // http://www.boost.org/LICENSE_1_0.txt)
0014
0015 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP
0016 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP
0017
0018 #include <boost/range/begin.hpp>
0019 #include <boost/range/end.hpp>
0020
0021 #include <boost/geometry/core/coordinate_type.hpp>
0022
0023 #include <boost/geometry/algorithms/area_result.hpp>
0024 #include <boost/geometry/algorithms/envelope.hpp>
0025 #include <boost/geometry/algorithms/expand.hpp>
0026 #include <boost/geometry/algorithms/detail/covered_by/implementation.hpp>
0027 #include <boost/geometry/algorithms/detail/partition.hpp>
0028 #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
0029 #include <boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp>
0030 #include <boost/geometry/views/enumerate_view.hpp>
0031
0032 #include <boost/geometry/geometries/box.hpp>
0033
0034
0035 namespace boost { namespace geometry
0036 {
0037
0038
0039 #ifndef DOXYGEN_NO_DETAIL
0040 namespace detail { namespace overlay
0041 {
0042
0043
0044
0045 template
0046 <
0047     typename Item,
0048     typename InnerGeometry,
0049     typename Geometry1, typename Geometry2,
0050     typename RingCollection,
0051     typename Strategy
0052 >
0053 static inline bool within_selected_input(Item const& item2,
0054         InnerGeometry const& inner_geometry,
0055         ring_identifier const& outer_id,
0056         Geometry1 const& geometry1, Geometry2 const& geometry2,
0057         RingCollection const& collection,
0058         Strategy const& strategy)
0059 {
0060     using tag1 = geometry::tag_t<Geometry1>;
0061     using tag2 = geometry::tag_t<Geometry2>;
0062
0063     // NOTE: range_in_geometry first checks the item2.point and then
0064     // if this point is on boundary it checks points of inner_geometry
0065     // ring until a point inside/outside other geometry ring is found
0066     switch (outer_id.source_index)
0067     {
0068         // covered_by
0069         case 0 :
0070             return range_in_geometry(item2.point, inner_geometry,
0071                 get_ring<tag1>::apply(outer_id, geometry1), strategy) >= 0;
0072         case 1 :
0073             return range_in_geometry(item2.point, inner_geometry,
0074                 get_ring<tag2>::apply(outer_id, geometry2), strategy) >= 0;
0075         case 2 :
0076             return range_in_geometry(item2.point, inner_geometry,
0077                 get_ring<void>::apply(outer_id, collection), strategy) >= 0;
0078     }
0079     return false;
0080 }
0081
0082 template
0083 <
0084     typename Item,
0085     typename Geometry1, typename Geometry2,
0086     typename RingCollection,
0087     typename Strategy
0088 >
0089 static inline bool within_selected_input(Item const& item2,
0090         ring_identifier const& inner_id, ring_identifier const& outer_id,
0091         Geometry1 const& geometry1, Geometry2 const& geometry2,
0092         RingCollection const& collection,
0093         Strategy const& strategy)
0094 {
0095     using tag1 = geometry::tag_t<Geometry1>;
0096     using tag2 = geometry::tag_t<Geometry2>;
0097
0098     switch (inner_id.source_index)
0099     {
0100         case 0 :
0101             return within_selected_input(item2,
0102                get_ring<tag1>::apply(inner_id, geometry1),
0103                outer_id, geometry1, geometry2, collection, strategy);
0104         case 1 :
0105             return within_selected_input(item2,
0106                get_ring<tag2>::apply(inner_id, geometry2),
0107                outer_id, geometry1, geometry2, collection, strategy);
0108         case 2 :
0109             return within_selected_input(item2,
0110                 get_ring<void>::apply(inner_id, collection),
0111                 outer_id, geometry1, geometry2, collection, strategy);
0112     }
0113     return false;
0114 }
0115
0116
0117 template <typename Point, typename AreaType>
0118 struct ring_info_helper
0119 {
0120     ring_identifier id;
0121     AreaType real_area;
0122     AreaType abs_area;
0123     model::box<Point> envelope;
0124
0125     inline ring_info_helper()
0126         : real_area(0), abs_area(0)
0127     {}
0128
0129     inline ring_info_helper(ring_identifier i, AreaType const& a)
0130         : id(i), real_area(a), abs_area(geometry::math::abs(a))
0131     {}
0132 };
0133
0134
0135 template <typename Strategy>
0136 struct ring_info_helper_get_box
0137 {
0138     ring_info_helper_get_box(Strategy const& strategy)
0139         : m_strategy(strategy)
0140     {}
0141
0142     template <typename Box, typename InputItem>
0143     inline void apply(Box& total, InputItem const& item) const
0144     {
0145         assert_coordinate_type_equal(total, item.envelope);
0146         geometry::expand(total, item.envelope, m_strategy);
0147     }
0148
0149     Strategy const& m_strategy;
0150 };
0151
0152 template <typename Strategy>
0153 struct ring_info_helper_overlaps_box
0154 {
0155     ring_info_helper_overlaps_box(Strategy const& strategy)
0156         : m_strategy(strategy)
0157     {}
0158
0159     template <typename Box, typename InputItem>
0160     inline bool apply(Box const& box, InputItem const& item) const
0161     {
0162         assert_coordinate_type_equal(box, item.envelope);
0163         return ! geometry::detail::disjoint::disjoint_box_box(
0164                     box, item.envelope, m_strategy);
0165     }
0166
0167     Strategy const& m_strategy;
0168 };
0169
0170 // Segments intersection Strategy
0171 template
0172 <
0173     typename Geometry1,
0174     typename Geometry2,
0175     typename Collection,
0176     typename RingMap,
0177     typename Strategy
0178 >
0179 struct assign_visitor
0180 {
0181     using ring_info_type = typename RingMap::mapped_type;
0182
0183     Geometry1 const& m_geometry1;
0184     Geometry2 const& m_geometry2;
0185     Collection const& m_collection;
0186     RingMap& m_ring_map;
0187     Strategy const& m_strategy;
0188     bool m_check_for_orientation;
0189
0190     inline assign_visitor(Geometry1 const& g1, Geometry2 const& g2, Collection const& c,
0191                           RingMap& map, Strategy const& strategy, bool check)
0192         : m_geometry1(g1)
0193         , m_geometry2(g2)
0194         , m_collection(c)
0195         , m_ring_map(map)
0196         , m_strategy(strategy)
0197         , m_check_for_orientation(check)
0198     {}
0199
0200     template <typename Item>
0201     inline bool apply(Item const& outer, Item const& inner, bool first = true)
0202     {
0203         if (first && outer.abs_area < inner.abs_area)
0204         {
0205             // Apply with reversed arguments
0206             apply(inner, outer, false);
0207             return true;
0208         }
0209
0210         if (m_check_for_orientation
0211          || (math::larger(outer.real_area, 0)
0212           && math::smaller(inner.real_area, 0)))
0213         {
0214             ring_info_type& inner_in_map = m_ring_map[inner.id];
0215
0216             if (geometry::covered_by(inner_in_map.point, outer.envelope, m_strategy)
0217                && within_selected_input(inner_in_map, inner.id, outer.id,
0218                                         m_geometry1, m_geometry2, m_collection,
0219                                         m_strategy)
0220                )
0221             {
0222                 // Assign a parent if there was no earlier parent, or the newly
0223                 // found parent is smaller than the previous one
0224                 if (inner_in_map.parent.source_index == -1
0225                     || outer.abs_area < inner_in_map.parent_area)
0226                 {
0227                     inner_in_map.parent = outer.id;
0228                     inner_in_map.parent_area = outer.abs_area;
0229                 }
0230             }
0231         }
0232
0233         return true;
0234     }
0235 };
0236
0237
0238 template
0239 <
0240     overlay_type OverlayType,
0241     typename Geometry1, typename Geometry2,
0242     typename RingCollection,
0243     typename RingMap,
0244     typename Strategy
0245 >
0246 inline void assign_parents(Geometry1 const& geometry1,
0247             Geometry2 const& geometry2,
0248             RingCollection const& collection,
0249             RingMap& ring_map,
0250             Strategy const& strategy)
0251 {
0252     static bool const is_difference = OverlayType == overlay_difference;
0253     static bool const is_buffer = OverlayType == overlay_buffer;
0254     static bool const is_dissolve = OverlayType == overlay_dissolve;
0255     static bool const check_for_orientation = is_buffer || is_dissolve;
0256
0257     using tag1 = geometry::tag_t<Geometry1>;
0258     using tag2 = geometry::tag_t<Geometry2>;
0259
0260     using ring_info_type = typename RingMap::mapped_type;
0261     using point_type = typename ring_info_type::point_type;
0262     using box_type = model::box<point_type>;
0263     using area_result_type = typename geometry::area_result
0264         <
0265             point_type, Strategy // TODO: point_type is technically incorrect
0266         >::type;
0267
0268     {
0269         std::size_t count_total = ring_map.size();
0270         std::size_t count_positive = 0;
0271         std::size_t index_positive = 0; // only used if count_positive>0
0272
0273         // Copy to vector (this might be obsolete, using the map directly)
0274         // The index in the map is also the index in the vector.
0275         using helper = ring_info_helper<point_type, area_result_type>;
0276         std::vector<helper> vector(count_total);
0277
0278         for (auto const& enumerated : util::enumerate(ring_map))
0279         {
0280             auto const& ring_id = enumerated.value.first;
0281             auto const& info = enumerated.value.second;
0282             vector[enumerated.index] = helper(ring_id, info.get_area());
0283             helper& item = vector[enumerated.index];
0284             switch(ring_id.source_index)
0285             {
0286                 case 0 :
0287                     geometry::envelope(get_ring<tag1>::apply(ring_id, geometry1),
0288                                        item.envelope, strategy);
0289                     break;
0290                 case 1 :
0291                     geometry::envelope(get_ring<tag2>::apply(ring_id, geometry2),
0292                                        item.envelope, strategy);
0293                     break;
0294                 case 2 :
0295                     geometry::envelope(get_ring<void>::apply(ring_id, collection),
0296                                        item.envelope, strategy);
0297                     break;
0298             }
0299
0300             // Expand envelope slightly
0301             expand_by_epsilon(item.envelope);
0302
0303             if (item.real_area > 0)
0304             {
0305                 count_positive++;
0306                 index_positive = enumerated.index;
0307             }
0308         }
0309
0310         if (! check_for_orientation)
0311         {
0312             if (count_positive == count_total)
0313             {
0314                 // Optimization for only positive rings
0315                 // -> no assignment of parents or reversal necessary, ready here.
0316                 return;
0317             }
0318
0319             if (count_positive == 1 && ! is_difference && ! is_dissolve)
0320             {
0321                 // Optimization for one outer ring
0322                 // -> assign this as parent to all others (all interior rings)
0323                 // In unions, this is probably the most occuring case and gives
0324                 //    a dramatic improvement (factor 5 for star_comb testcase)
0325                 // In difference or other cases where interior rings might be
0326                 // located outside the outer ring, this cannot be done
0327                 ring_identifier id_of_positive = vector[index_positive].id;
0328                 ring_info_type& outer = ring_map[id_of_positive];
0329                 for (auto const& item : util::enumerate(vector))
0330                 {
0331                     if (item.index != index_positive)
0332                     {
0333                         auto const id = item.value.id;
0334                         ring_info_type& inner = ring_map[id];
0335                         inner.parent = id_of_positive;
0336                         outer.children.push_back(id);
0337                     }
0338                 }
0339                 return;
0340             }
0341         }
0342
0343         assign_visitor
0344             <
0345                 Geometry1, Geometry2,
0346                 RingCollection, RingMap,
0347                 Strategy
0348             > visitor(geometry1, geometry2, collection, ring_map, strategy, check_for_orientation);
0349
0350         geometry::partition
0351             <
0352                 box_type
0353             >::apply(vector, visitor,
0354                      ring_info_helper_get_box<Strategy>(strategy),
0355                      ring_info_helper_overlaps_box<Strategy>(strategy));
0356     }
0357
0358     if (check_for_orientation)
0359     {
0360         for (auto& pair : ring_map)
0361         {
0362             ring_info_type& info = pair.second;
0363             if (geometry::math::equals(info.get_area(), 0))
0364             {
0365                 info.discarded = true;
0366             }
0367             else if (info.parent.source_index >= 0)
0368             {
0369                 ring_info_type const& parent = ring_map[info.parent];
0370                 bool const pos = math::larger(info.get_area(), 0);
0371                 bool const parent_pos = math::larger(parent.area, 0);
0372
0373                 bool const double_neg = is_dissolve && ! pos && ! parent_pos;
0374
0375                 if ((pos && parent_pos) || double_neg)
0376                 {
0377                     // Discard positive inner ring with positive parent
0378                     // Also, for some cases (dissolve), negative inner ring
0379                     // with negative parent should be discarded
0380                     info.discarded = true;
0381                 }
0382
0383                 if (pos || info.discarded)
0384                 {
0385                     // Remove parent ID from any positive or discarded inner rings
0386                     info.parent.source_index = -1;
0387                 }
0388             }
0389             else if (info.parent.source_index < 0
0390                     && math::smaller(info.get_area(), 0))
0391             {
0392                 // Reverse negative ring without parent
0393                 info.reversed = true;
0394             }
0395         }
0396     }
0397
0398     // Assign childlist
0399     for (auto& pair : ring_map)
0400     {
0401         if (pair.second.parent.source_index >= 0)
0402         {
0403             ring_map[pair.second.parent].children.push_back(pair.first);
0404         }
0405     }
0406 }
0407
0408
0409 // Version for one geometry (called by buffer/dissolve)
0410 template
0411 <
0412     overlay_type OverlayType,
0413     typename Geometry,
0414     typename RingCollection,
0415     typename RingMap,
0416     typename Strategy
0417 >
0418 inline void assign_parents(Geometry const& geometry,
0419             RingCollection const& collection,
0420             RingMap& ring_map,
0421             Strategy const& strategy)
0422 {
0423     // Call it with an empty geometry as second geometry (source_id == 1)
0424     // (ring_map should be empty for source_id==1)
0425     Geometry empty;
0426     assign_parents<OverlayType>(geometry, empty,
0427             collection, ring_map, strategy);
0428 }
0429
0430
0431 }} // namespace detail::overlay
0432 #endif // DOXYGEN_NO_DETAIL
0433
0434
0435 }} // namespace geometry
0436
0437
0438 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP