detail/intersection/gc.hpp

0001 // Boost.Geometry
0002
0003 // Copyright (c) 2022, Oracle and/or its affiliates.
0004 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0005
0006 // Licensed under the Boost Software License version 1.0.
0007 // http://www.boost.org/users/license.html
0008
0009 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_GC_HPP
0010 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_GC_HPP
0011
0012
0013 #include <tuple>
0014
0015 #include <boost/range/size.hpp>
0016
0017 #include <boost/geometry/algorithms/detail/gc_make_rtree.hpp>
0018 #include <boost/geometry/algorithms/detail/intersection/interface.hpp>
0019 #include <boost/geometry/views/detail/geometry_collection_view.hpp>
0020
0021
0022 namespace boost { namespace geometry
0023 {
0024
0025 #ifndef DOXYGEN_NO_DETAIL
0026 namespace detail { namespace intersection
0027 {
0028
0029
0030 template <typename GC, typename Multi>
0031 struct gc_can_move_element
0032 {
0033     template <typename G>
0034     using is_same_as_single = std::is_same<G, typename boost::range_value<Multi>::type>;
0035     using gc_types = typename traits::geometry_types<GC>::type;
0036     using found_type = typename util::sequence_find_if<gc_types, is_same_as_single>::type;
0037     static const bool value = ! std::is_void<found_type>::value;
0038 };
0039
0040 template <typename GC, typename Multi>
0041 struct gc_can_convert_element
0042 {
0043     template <typename G>
0044     using has_same_tag_as_single = std::is_same
0045         <
0046             typename geometry::tag<G>::type,
0047             typename geometry::tag<typename boost::range_value<Multi>::type>::type
0048         >;
0049     using gc_types = typename traits::geometry_types<GC>::type;
0050     using found_type = typename util::sequence_find_if<gc_types, has_same_tag_as_single>::type;
0051     static const bool value = ! std::is_void<found_type>::value;
0052 };
0053
0054 template
0055 <
0056     typename GC, typename Multi,
0057     std::enable_if_t<gc_can_move_element<GC, Multi>::value, int> = 0
0058 >
0059 inline void gc_move_one_elem_multi_back(GC& gc, Multi&& multi)
0060 {
0061     range::emplace_back(gc, std::move(*boost::begin(multi)));
0062 }
0063
0064 template
0065 <
0066     typename GC, typename Multi,
0067     std::enable_if_t<! gc_can_move_element<GC, Multi>::value && gc_can_convert_element<GC, Multi>::value, int> = 0
0068 >
0069 inline void gc_move_one_elem_multi_back(GC& gc, Multi&& multi)
0070 {
0071     typename gc_can_convert_element<GC, Multi>::found_type single_out;
0072     geometry::convert(*boost::begin(multi), single_out);
0073     range::emplace_back(gc, std::move(single_out));
0074 }
0075
0076 template
0077 <
0078     typename GC, typename Multi,
0079     std::enable_if_t<! gc_can_move_element<GC, Multi>::value && ! gc_can_convert_element<GC, Multi>::value, int> = 0
0080 >
0081 inline void gc_move_one_elem_multi_back(GC& gc, Multi&& multi)
0082 {
0083     range::emplace_back(gc, std::move(multi));
0084 }
0085
0086 template <typename GC, typename Multi>
0087 inline void gc_move_multi_back(GC& gc, Multi&& multi)
0088 {
0089     if (! boost::empty(multi))
0090     {
0091         if (boost::size(multi) == 1)
0092         {
0093             gc_move_one_elem_multi_back(gc, std::move(multi));
0094         }
0095         else
0096         {
0097             range::emplace_back(gc, std::move(multi));
0098         }
0099     }
0100 }
0101
0102
0103 }} // namespace detail::intersection
0104 #endif // DOXYGEN_NO_DETAIL
0105
0106
0107 namespace resolve_collection
0108 {
0109
0110
0111 template
0112 <
0113     typename Geometry1, typename Geometry2, typename GeometryOut
0114 >
0115 struct intersection
0116     <
0117         Geometry1, Geometry2, GeometryOut,
0118         geometry_collection_tag, geometry_collection_tag, geometry_collection_tag
0119     >
0120 {
0121     // NOTE: for now require all of the possible output types
0122     //       technically only a subset could be needed.
0123     using multi_point_t = typename util::sequence_find_if
0124         <
0125             typename traits::geometry_types<GeometryOut>::type,
0126             util::is_multi_point
0127         >::type;
0128     using multi_linestring_t = typename util::sequence_find_if
0129         <
0130             typename traits::geometry_types<GeometryOut>::type,
0131             util::is_multi_linestring
0132         >::type;
0133     using multi_polygon_t = typename util::sequence_find_if
0134         <
0135             typename traits::geometry_types<GeometryOut>::type,
0136             util::is_multi_polygon
0137         >::type;
0138     using tuple_out_t = boost::tuple<multi_point_t, multi_linestring_t, multi_polygon_t>;
0139
0140     template <typename Strategy>
0141     static inline bool apply(Geometry1 const& geometry1,
0142                              Geometry2 const& geometry2,
0143                              GeometryOut& geometry_out,
0144                              Strategy const& strategy)
0145     {
0146         bool result = false;
0147         tuple_out_t out;
0148
0149         auto const rtree2 = detail::gc_make_rtree_iterators(geometry2, strategy);
0150         detail::visit_breadth_first([&](auto const& g1)
0151         {
0152             bool r = g1_prod_gc2(g1, rtree2, out, strategy);
0153             result = result || r;
0154             return true;
0155         }, geometry1);
0156
0157         detail::intersection::gc_move_multi_back(geometry_out, boost::get<0>(out));
0158         detail::intersection::gc_move_multi_back(geometry_out, boost::get<1>(out));
0159         detail::intersection::gc_move_multi_back(geometry_out, boost::get<2>(out));
0160
0161         return result;
0162     }
0163
0164 private:
0165     // Implemented as separate function because msvc is unable to do nested lambda capture
0166     template <typename G1, typename Rtree2, typename TupleOut, typename Strategy>
0167     static bool g1_prod_gc2(G1 const& g1, Rtree2 const& rtree2, TupleOut& out, Strategy const& strategy)
0168     {
0169         bool result = false;
0170
0171         using box1_t = detail::gc_make_rtree_box_t<G1>;
0172         box1_t b1 = geometry::return_envelope<box1_t>(g1, strategy);
0173         detail::expand_by_epsilon(b1);
0174
0175         for (auto qit = rtree2.qbegin(index::intersects(b1)); qit != rtree2.qend(); ++qit)
0176         {
0177             traits::iter_visit<Geometry2>::apply([&](auto const& g2)
0178             {
0179                 TupleOut inters_result;
0180                 using g2_t = util::remove_cref_t<decltype(g2)>;
0181                 intersection<G1, g2_t, TupleOut>::apply(g1, g2, inters_result, strategy);
0182
0183                 // TODO: If possible merge based on adjacency lists, i.e. merge
0184                 //       only the intersections of elements that intersect each other
0185                 //       as subgroups. So the result could contain merged intersections
0186                 //       of several groups, not only one.
0187                 // TODO: It'd probably be better to gather all of the parts first
0188                 //       and then merge them with merge_elements.
0189                 // NOTE: template explicitly called because gcc-6 doesn't compile it
0190                 //       otherwise.
0191                 bool const r0 = intersection::template merge_result<0>(inters_result, out, strategy);
0192                 bool const r1 = intersection::template merge_result<1>(inters_result, out, strategy);
0193                 bool const r2 = intersection::template merge_result<2>(inters_result, out, strategy);
0194                 result = result || r0 || r1 || r2;
0195             }, qit->second);
0196         }
0197
0198         return result;
0199     }
0200
0201     template <std::size_t Index, typename Out, typename Strategy>
0202     static bool merge_result(Out const& inters_result, Out& out, Strategy const& strategy)
0203     {
0204         auto const& multi_result = boost::get<Index>(inters_result);
0205         auto& multi_out = boost::get<Index>(out);
0206         if (! boost::empty(multi_result))
0207         {
0208             std::remove_reference_t<decltype(multi_out)> temp_result;
0209             merge_two(multi_out, multi_result, temp_result, strategy);
0210             multi_out = std::move(temp_result);
0211             return true;
0212         }
0213         return false;
0214     }
0215
0216     template <typename Out, typename Strategy, std::enable_if_t<! util::is_pointlike<Out>::value, int> = 0>
0217     static void merge_two(Out const& g1, Out const& g2, Out& out, Strategy const& strategy)
0218     {
0219         using rescale_policy_type = typename geometry::rescale_overlay_policy_type
0220             <
0221                 Out, Out, typename Strategy::cs_tag
0222             >::type;
0223
0224         rescale_policy_type robust_policy
0225             = geometry::get_rescale_policy<rescale_policy_type>(
0226                     g1, g2, strategy);
0227
0228         geometry::dispatch::intersection_insert
0229             <
0230                 Out, Out, typename boost::range_value<Out>::type,
0231                 overlay_union
0232             >::apply(g1,
0233                      g2,
0234                      robust_policy,
0235                      geometry::range::back_inserter(out),
0236                      strategy);
0237     }
0238
0239     template <typename Out, typename Strategy, std::enable_if_t<util::is_pointlike<Out>::value, int> = 0>
0240     static void merge_two(Out const& g1, Out const& g2, Out& out, Strategy const& strategy)
0241     {
0242         detail::overlay::union_pointlike_pointlike_point
0243             <
0244                 Out, Out, typename boost::range_value<Out>::type
0245             >::apply(g1,
0246                      g2,
0247                      0, // dummy robust policy
0248                      geometry::range::back_inserter(out),
0249                      strategy);
0250     }
0251 };
0252
0253 template
0254 <
0255     typename Geometry1, typename Geometry2, typename GeometryOut, typename Tag1
0256 >
0257 struct intersection
0258     <
0259         Geometry1, Geometry2, GeometryOut,
0260         Tag1, geometry_collection_tag, geometry_collection_tag
0261     >
0262 {
0263     template <typename Strategy>
0264     static inline bool apply(Geometry1 const& geometry1,
0265                              Geometry2 const& geometry2,
0266                              GeometryOut& geometry_out,
0267                              Strategy const& strategy)
0268     {
0269         using gc_view_t = geometry::detail::geometry_collection_view<Geometry1>;
0270         return intersection
0271             <
0272                 gc_view_t, Geometry2, GeometryOut
0273             >::apply(gc_view_t(geometry1), geometry2, geometry_out, strategy);
0274     }
0275 };
0276
0277 template
0278 <
0279     typename Geometry1, typename Geometry2, typename GeometryOut, typename Tag2
0280 >
0281 struct intersection
0282     <
0283         Geometry1, Geometry2, GeometryOut,
0284         geometry_collection_tag, Tag2, geometry_collection_tag
0285     >
0286 {
0287     template <typename Strategy>
0288     static inline bool apply(Geometry1 const& geometry1,
0289                              Geometry2 const& geometry2,
0290                              GeometryOut& geometry_out,
0291                              Strategy const& strategy)
0292     {
0293         using gc_view_t = geometry::detail::geometry_collection_view<Geometry2>;
0294         return intersection
0295             <
0296                 Geometry1, gc_view_t, GeometryOut
0297             >::apply(geometry1, gc_view_t(geometry2), geometry_out, strategy);
0298     }
0299 };
0300
0301 template
0302 <
0303     typename Geometry1, typename Geometry2, typename GeometryOut, typename Tag1, typename Tag2
0304 >
0305 struct intersection
0306     <
0307         Geometry1, Geometry2, GeometryOut,
0308         Tag1, Tag2, geometry_collection_tag
0309     >
0310 {
0311     template <typename Strategy>
0312     static inline bool apply(Geometry1 const& geometry1,
0313                              Geometry2 const& geometry2,
0314                              GeometryOut& geometry_out,
0315                              Strategy const& strategy)
0316     {
0317         using gc1_view_t = geometry::detail::geometry_collection_view<Geometry1>;
0318         using gc2_view_t = geometry::detail::geometry_collection_view<Geometry2>;
0319         return intersection
0320             <
0321                 gc1_view_t, gc2_view_t, GeometryOut
0322             >::apply(gc1_view_t(geometry1), gc2_view_t(geometry2), geometry_out, strategy);
0323     }
0324 };
0325
0326
0327 } // namespace resolve_collection
0328
0329 }} // namespace boost::geometry
0330
0331 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_GC_HPP