detail/overlay/select_rings.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2017-2022.
0007 // Modifications copyright (c) 2017-2022 Oracle and/or its affiliates.
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Use, modification and distribution is subject to the Boost Software License,
0011 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0012 // http://www.boost.org/LICENSE_1_0.txt)
0013
0014 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP
0016
0017
0018 #include <map>
0019
0020 #include <boost/range/begin.hpp>
0021 #include <boost/range/end.hpp>
0022 #include <boost/range/size.hpp>
0023
0024 #include <boost/geometry/core/tags.hpp>
0025
0026 #include <boost/geometry/algorithms/detail/covered_by/implementation.hpp>
0027 #include <boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp>
0028 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
0029 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0030 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
0031
0032
0033 namespace boost { namespace geometry
0034 {
0035
0036
0037 #ifndef DOXYGEN_NO_DETAIL
0038 namespace detail { namespace overlay
0039 {
0040
0041 struct ring_turn_info
0042 {
0043     bool has_traversed_turn;
0044     bool has_blocked_turn;
0045     bool within_other;
0046
0047     ring_turn_info()
0048         : has_traversed_turn(false)
0049         , has_blocked_turn(false)
0050         , within_other(false)
0051     {}
0052 };
0053
0054 namespace dispatch
0055 {
0056
0057     template <typename Tag, typename Geometry>
0058     struct select_rings
0059     {};
0060
0061     template <typename Box>
0062     struct select_rings<box_tag, Box>
0063     {
0064         template <typename Geometry, typename RingPropertyMap, typename Strategy>
0065         static inline void apply(Box const& box, Geometry const& ,
0066                 ring_identifier const& id, RingPropertyMap& ring_properties,
0067                 Strategy const& strategy)
0068         {
0069             ring_properties[id] = typename RingPropertyMap::mapped_type(box, strategy);
0070         }
0071
0072         template <typename RingPropertyMap, typename Strategy>
0073         static inline void apply(Box const& box,
0074                 ring_identifier const& id, RingPropertyMap& ring_properties,
0075                 Strategy const& strategy)
0076         {
0077             ring_properties[id] = typename RingPropertyMap::mapped_type(box, strategy);
0078         }
0079     };
0080
0081     template <typename Ring>
0082     struct select_rings<ring_tag, Ring>
0083     {
0084         template <typename Geometry, typename RingPropertyMap, typename Strategy>
0085         static inline void apply(Ring const& ring, Geometry const& ,
0086                     ring_identifier const& id, RingPropertyMap& ring_properties,
0087                     Strategy const& strategy)
0088         {
0089             if (boost::size(ring) > 0)
0090             {
0091                 ring_properties[id] = typename RingPropertyMap::mapped_type(ring, strategy);
0092             }
0093         }
0094
0095         template <typename RingPropertyMap, typename Strategy>
0096         static inline void apply(Ring const& ring,
0097                     ring_identifier const& id, RingPropertyMap& ring_properties,
0098                     Strategy const& strategy)
0099         {
0100             if (boost::size(ring) > 0)
0101             {
0102                 ring_properties[id] = typename RingPropertyMap::mapped_type(ring, strategy);
0103             }
0104         }
0105     };
0106
0107
0108     template <typename Polygon>
0109     struct select_rings<polygon_tag, Polygon>
0110     {
0111         template <typename Geometry, typename RingPropertyMap, typename Strategy>
0112         static inline void apply(Polygon const& polygon, Geometry const& geometry,
0113                     ring_identifier id, RingPropertyMap& ring_properties,
0114                     Strategy const& strategy)
0115         {
0116             using per_ring = select_rings<ring_tag, geometry::ring_type_t<Polygon>>;
0117
0118             per_ring::apply(exterior_ring(polygon), geometry, id, ring_properties, strategy);
0119
0120             auto const& rings = interior_rings(polygon);
0121             for (auto it = boost::begin(rings); it != boost::end(rings); ++it)
0122             {
0123                 id.ring_index++;
0124                 per_ring::apply(*it, geometry, id, ring_properties, strategy);
0125             }
0126         }
0127
0128         template <typename RingPropertyMap, typename Strategy>
0129         static inline void apply(Polygon const& polygon,
0130                 ring_identifier id, RingPropertyMap& ring_properties,
0131                 Strategy const& strategy)
0132         {
0133             using per_ring = select_rings<ring_tag, geometry::ring_type_t<Polygon>>;
0134
0135             per_ring::apply(exterior_ring(polygon), id, ring_properties, strategy);
0136
0137             auto const& rings = interior_rings(polygon);
0138             for (auto it = boost::begin(rings); it != boost::end(rings); ++it)
0139             {
0140                 id.ring_index++;
0141                 per_ring::apply(*it, id, ring_properties, strategy);
0142             }
0143         }
0144     };
0145
0146     template <typename Multi>
0147     struct select_rings<multi_polygon_tag, Multi>
0148     {
0149         template <typename Geometry, typename RingPropertyMap, typename Strategy>
0150         static inline void apply(Multi const& multi, Geometry const& geometry,
0151                     ring_identifier id, RingPropertyMap& ring_properties,
0152                     Strategy const& strategy)
0153         {
0154             using per_polygon = select_rings<polygon_tag, typename boost::range_value<Multi>::type>;
0155
0156             id.multi_index = 0;
0157             for (auto it = boost::begin(multi); it != boost::end(multi); ++it)
0158             {
0159                 id.ring_index = -1;
0160                 per_polygon::apply(*it, geometry, id, ring_properties, strategy);
0161                 id.multi_index++;
0162             }
0163         }
0164     };
0165
0166 } // namespace dispatch
0167
0168
0169 template<overlay_type OverlayType>
0170 struct decide
0171 {
0172     // Default implementation (union, inflate, deflate, dissolve)
0173     static bool include(ring_identifier const& , ring_turn_info const& info)
0174     {
0175         return ! info.within_other;
0176     }
0177
0178     static bool reversed(ring_identifier const& , ring_turn_info const& )
0179     {
0180         return false;
0181     }
0182
0183 };
0184
0185 template<>
0186 struct decide<overlay_difference>
0187 {
0188     static bool include(ring_identifier const& id, ring_turn_info const& info)
0189     {
0190         // Difference: A - B
0191
0192         // If this is A (source_index=0), then the ring is inside B
0193         // If this is B (source_index=1), then the ring is NOT inside A
0194
0195         // If this is A and the ring is within the other geometry,
0196         // then we should NOT include it.
0197         // If this is B then we SHOULD include it.
0198
0199         return id.source_index == 0
0200             ? ! info.within_other
0201             : info.within_other;
0202     }
0203
0204     static bool reversed(ring_identifier const& id, ring_turn_info const& info)
0205     {
0206         // Difference: A - B
0207         // If this is B, and the ring is included, it should be reversed afterwards
0208
0209         return id.source_index == 1 && include(id, info);
0210     }
0211 };
0212
0213 template<>
0214 struct decide<overlay_intersection>
0215 {
0216     static bool include(ring_identifier const& , ring_turn_info const& info)
0217     {
0218         return info.within_other;
0219     }
0220
0221     static bool reversed(ring_identifier const& , ring_turn_info const& )
0222     {
0223         return false;
0224     }
0225 };
0226
0227 template
0228 <
0229     overlay_type OverlayType,
0230     typename Geometry1,
0231     typename Geometry2,
0232     typename TurnInfoMap,
0233     typename RingPropertyMap,
0234     typename Strategy
0235 >
0236 inline void update_ring_selection(Geometry1 const& geometry1,
0237             Geometry2 const& geometry2,
0238             TurnInfoMap const& turn_info_map,
0239             RingPropertyMap const& all_ring_properties,
0240             RingPropertyMap& selected_ring_properties,
0241             Strategy const& strategy)
0242 {
0243     selected_ring_properties.clear();
0244
0245     for (auto const& pair : all_ring_properties)
0246     {
0247         ring_identifier const& id = pair.first;
0248
0249         ring_turn_info info;
0250
0251         auto tcit = turn_info_map.find(id);
0252         if (tcit != turn_info_map.end())
0253         {
0254             info = tcit->second; // Copy by value
0255         }
0256
0257         if (info.has_traversed_turn || info.has_blocked_turn)
0258         {
0259             // This turn is traversed or blocked,
0260             // don't include the original ring
0261             continue;
0262         }
0263
0264         // Check if the ring is within the other geometry, by taking
0265         // a point lying on the ring
0266         switch(id.source_index)
0267         {
0268             // within
0269             case 0 :
0270                 info.within_other = range_in_geometry(pair.second.point,
0271                                                       geometry1, geometry2,
0272                                                       strategy) > 0;
0273                 break;
0274             case 1 :
0275                 info.within_other = range_in_geometry(pair.second.point,
0276                                                       geometry2, geometry1,
0277                                                       strategy) > 0;
0278                 break;
0279         }
0280
0281         if (decide<OverlayType>::include(id, info))
0282         {
0283             auto properties = pair.second; // Copy by value
0284             properties.reversed = decide<OverlayType>::reversed(id, info);
0285             selected_ring_properties[id] = properties;
0286         }
0287     }
0288 }
0289
0290
0291 /*!
0292 \brief The function select_rings select rings based on the overlay-type (union,intersection)
0293 */
0294 template
0295 <
0296     overlay_type OverlayType,
0297     typename Geometry1,
0298     typename Geometry2,
0299     typename RingTurnInfoMap,
0300     typename RingPropertyMap,
0301     typename Strategy
0302 >
0303 inline void select_rings(Geometry1 const& geometry1, Geometry2 const& geometry2,
0304             RingTurnInfoMap const& turn_info_per_ring,
0305             RingPropertyMap& selected_ring_properties,
0306             Strategy const& strategy)
0307 {
0308     using tag1 = geometry::tag_t<Geometry1>;
0309     using tag2 = geometry::tag_t<Geometry2>;
0310
0311     RingPropertyMap all_ring_properties;
0312     dispatch::select_rings<tag1, Geometry1>::apply(geometry1, geometry2,
0313                 ring_identifier(0, -1, -1), all_ring_properties,
0314                 strategy);
0315     dispatch::select_rings<tag2, Geometry2>::apply(geometry2, geometry1,
0316                 ring_identifier(1, -1, -1), all_ring_properties,
0317                 strategy);
0318
0319     update_ring_selection<OverlayType>(geometry1, geometry2, turn_info_per_ring,
0320                 all_ring_properties, selected_ring_properties,
0321                 strategy);
0322 }
0323
0324 template
0325 <
0326     overlay_type OverlayType,
0327     typename Geometry,
0328     typename RingTurnInfoMap,
0329     typename RingPropertyMap,
0330     typename Strategy
0331 >
0332 inline void select_rings(Geometry const& geometry,
0333             RingTurnInfoMap const& turn_info_per_ring,
0334             RingPropertyMap& selected_ring_properties,
0335             Strategy const& strategy)
0336 {
0337     RingPropertyMap all_ring_properties;
0338     dispatch::select_rings<geometry::tag_t<Geometry>, Geometry>::apply(geometry,
0339                 ring_identifier(0, -1, -1), all_ring_properties,
0340                 strategy);
0341
0342     update_ring_selection<OverlayType>(geometry, geometry, turn_info_per_ring,
0343                 all_ring_properties, selected_ring_properties,
0344                 strategy);
0345 }
0346
0347
0348 }} // namespace detail::overlay
0349 #endif // DOXYGEN_NO_DETAIL
0350
0351
0352 }} // namespace boost::geometry
0353
0354
0355 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP