diff options
Diffstat (limited to 'boost/geometry/algorithms/union.hpp')
| -rw-r--r-- | boost/geometry/algorithms/union.hpp | 523 |
1 files changed, 376 insertions, 147 deletions
diff --git a/boost/geometry/algorithms/union.hpp b/boost/geometry/algorithms/union.hpp index 1a9bcd64dc..3d88cc1414 100644 --- a/boost/geometry/algorithms/union.hpp +++ b/boost/geometry/algorithms/union.hpp @@ -2,9 +2,9 @@ // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. -// This file was modified by Oracle on 2014-2021. -// Modifications copyright (c) 2014-2021 Oracle and/or its affiliates. - +// This file was modified by Oracle on 2014-2023. +// Modifications copyright (c) 2014-2023 Oracle and/or its affiliates. +// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle @@ -16,9 +16,8 @@ #define BOOST_GEOMETRY_ALGORITHMS_UNION_HPP -#include <boost/range/value_type.hpp> - -#include <boost/geometry/algorithms/detail/intersection/multi.hpp> +#include <boost/geometry/algorithms/detail/gc_group_elements.hpp> +#include <boost/geometry/algorithms/detail/intersection/gc.hpp> #include <boost/geometry/algorithms/detail/overlay/intersection_insert.hpp> #include <boost/geometry/algorithms/detail/overlay/linear_linear.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay.hpp> @@ -26,6 +25,7 @@ #include <boost/geometry/algorithms/not_implemented.hpp> #include <boost/geometry/core/point_order.hpp> #include <boost/geometry/core/reverse_dispatch.hpp> +#include <boost/geometry/geometries/adapted/boost_variant.hpp> #include <boost/geometry/geometries/concepts/check.hpp> #include <boost/geometry/policies/robustness/get_rescale_policy.hpp> #include <boost/geometry/strategies/default_strategy.hpp> @@ -33,8 +33,9 @@ #include <boost/geometry/strategies/relate/cartesian.hpp> #include <boost/geometry/strategies/relate/geographic.hpp> #include <boost/geometry/strategies/relate/spherical.hpp> -#include <boost/geometry/util/range.hpp> - +#include <boost/geometry/util/type_traits_std.hpp> +#include <boost/geometry/views/detail/geometry_collection_view.hpp> +#include <boost/geometry/views/detail/random_access_view.hpp> namespace boost { namespace geometry @@ -165,20 +166,20 @@ struct union_insert false > { - typedef typename geometry::detail::single_tag_from_base_tag + using single_tag = typename geometry::detail::single_tag_from_base_tag < CastedTagIn - >::type single_tag; + >::type; - typedef detail::expect_output + using expect_check = detail::expect_output < Geometry1, Geometry2, SingleTupledOut, single_tag - > expect_check; + >; - typedef typename geometry::detail::output_geometry_access + using access = typename geometry::detail::output_geometry_access < SingleTupledOut, single_tag, single_tag - > access; + >; template <typename RobustPolicy, typename OutputIterator, typename Strategy> static inline OutputIterator apply(Geometry1 const& g1, @@ -206,15 +207,15 @@ template > struct union_insert_tupled_different { - typedef typename geometry::detail::output_geometry_access + using access1 = typename geometry::detail::output_geometry_access < SingleTupledOut, SingleTag1, SingleTag1 - > access1; + >; - typedef typename geometry::detail::output_geometry_access + using access2 = typename geometry::detail::output_geometry_access < SingleTupledOut, SingleTag2, SingleTag2 - > access2; + >; template <typename RobustPolicy, typename OutputIterator, typename Strategy> static inline OutputIterator apply(Geometry1 const& g1, @@ -282,25 +283,25 @@ struct union_insert false > { - typedef typename geometry::detail::single_tag_from_base_tag + using single_tag1 = typename geometry::detail::single_tag_from_base_tag < CastedTagIn1 - >::type single_tag1; + >::type; - typedef detail::expect_output + using expect_check1 = detail::expect_output < Geometry1, Geometry2, SingleTupledOut, single_tag1 - > expect_check1; + >; - typedef typename geometry::detail::single_tag_from_base_tag + using single_tag2 = typename geometry::detail::single_tag_from_base_tag < CastedTagIn2 - >::type single_tag2; + >::type; - typedef detail::expect_output + using expect_check2 = detail::expect_output < Geometry1, Geometry2, SingleTupledOut, single_tag2 - > expect_check2; + >; template <typename RobustPolicy, typename OutputIterator, typename Strategy> static inline OutputIterator apply(Geometry1 const& g1, @@ -358,11 +359,11 @@ inline OutputIterator union_insert(Geometry1 const& geometry1, Geometry1, Geometry2 >::type strategy; - typedef typename geometry::rescale_overlay_policy_type + using rescale_policy_type = typename geometry::rescale_overlay_policy_type < Geometry1, Geometry2 - >::type rescale_policy_type; + >::type; rescale_policy_type robust_policy = geometry::get_rescale_policy<rescale_policy_type>( @@ -379,32 +380,33 @@ inline OutputIterator union_insert(Geometry1 const& geometry1, #endif // DOXYGEN_NO_DETAIL -namespace resolve_strategy { +namespace resolve_collection +{ template < - typename Strategy, - bool IsUmbrella = strategies::detail::is_umbrella_strategy<Strategy>::value + typename Geometry1, typename Geometry2, typename GeometryOut, + typename Tag1 = typename geometry::tag<Geometry1>::type, + typename Tag2 = typename geometry::tag<Geometry2>::type, + typename TagOut = typename geometry::tag<GeometryOut>::type > struct union_ { - template <typename Geometry1, typename Geometry2, typename Collection> - static inline void apply(Geometry1 const& geometry1, - Geometry2 const& geometry2, - Collection & output_collection, - Strategy const& strategy) + template <typename Strategy> + static void apply(Geometry1 const& geometry1, Geometry2 const& geometry2, + GeometryOut & geometry_out, Strategy const& strategy) { - typedef typename geometry::detail::output_geometry_value + using single_out = typename geometry::detail::output_geometry_value < - Collection - >::type single_out; + GeometryOut + >::type; - typedef typename geometry::rescale_overlay_policy_type + using rescale_policy_type = typename geometry::rescale_overlay_policy_type < Geometry1, Geometry2, typename Strategy::cs_tag - >::type rescale_policy_type; + >::type; rescale_policy_type robust_policy = geometry::get_rescale_policy<rescale_policy_type>( @@ -414,11 +416,303 @@ struct union_ < Geometry1, Geometry2, single_out >::apply(geometry1, geometry2, robust_policy, - geometry::detail::output_geometry_back_inserter(output_collection), + geometry::detail::output_geometry_back_inserter(geometry_out), strategy); } }; +template +< + typename Geometry1, typename Geometry2, typename GeometryOut +> +struct union_ + < + Geometry1, Geometry2, GeometryOut, + geometry_collection_tag, geometry_collection_tag, geometry_collection_tag + > +{ + // NOTE: for now require all of the possible output types + // technically only a subset could be needed. + using multi_point_t = typename util::sequence_find_if + < + typename traits::geometry_types<GeometryOut>::type, + util::is_multi_point + >::type; + using multi_linestring_t = typename util::sequence_find_if + < + typename traits::geometry_types<GeometryOut>::type, + util::is_multi_linestring + >::type; + using multi_polygon_t = typename util::sequence_find_if + < + typename traits::geometry_types<GeometryOut>::type, + util::is_multi_polygon + >::type; + using tuple_out_t = boost::tuple<multi_point_t, multi_linestring_t, multi_polygon_t>; + + template <typename Strategy> + static inline void apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + GeometryOut& geometry_out, + Strategy const& strategy) + { + detail::random_access_view<Geometry1 const> gc1_view(geometry1); + detail::random_access_view<Geometry2 const> gc2_view(geometry2); + + detail::gc_group_elements(gc1_view, gc2_view, strategy, + [&](auto const& inters_group) + { + tuple_out_t out; + merge_group(gc1_view, gc2_view, strategy, inters_group, out); + detail::intersection::gc_move_multi_back(geometry_out, boost::get<0>(out)); + detail::intersection::gc_move_multi_back(geometry_out, boost::get<1>(out)); + detail::intersection::gc_move_multi_back(geometry_out, boost::get<2>(out)); + return true; + }, + [&](auto const& disjoint_group) + { + copy_disjoint(gc1_view, gc2_view, disjoint_group, geometry_out); + }); + } + +private: + template <typename GC1View, typename GC2View, typename Strategy, typename Group> + static inline void merge_group(GC1View const& gc1_view, GC2View const& gc2_view, + Strategy const& strategy, Group const& inters_group, + tuple_out_t& out) + { + for (auto const& id : inters_group) + { + if (id.source_id == 0) + { + traits::iter_visit<GC1View>::apply([&](auto const& g1) + { + merge_one(out, g1, strategy); + }, boost::begin(gc1_view) + id.gc_id); + } + else + { + traits::iter_visit<GC2View>::apply([&](auto const& g2) + { + merge_one(out, g2, strategy); + }, boost::begin(gc2_view) + id.gc_id); + } + } + /* + // L = L \ A + { + multi_linestring_t l; + subtract_greater_topodim(boost::get<1>(out), boost::get<2>(out), l, strategy); + boost::get<1>(out) = std::move(l); + } + // P = P \ A + { + multi_point_t p; + subtract_greater_topodim(boost::get<0>(out), boost::get<2>(out), p, strategy); + boost::get<0>(out) = std::move(p); + } + // P = P \ L + { + multi_point_t p; + subtract_greater_topodim(boost::get<0>(out), boost::get<1>(out), p, strategy); + boost::get<0>(out) = std::move(p); + } + */ + } + + template <typename G, typename Strategy, std::enable_if_t<util::is_pointlike<G>::value, int> = 0> + static inline void merge_one(tuple_out_t& out, G const& g, Strategy const& strategy) + { + multi_point_t p; + union_<multi_point_t, G, multi_point_t>::apply(boost::get<0>(out), g, p, strategy); + boost::get<0>(out) = std::move(p); + } + + template <typename G, typename Strategy, std::enable_if_t<util::is_linear<G>::value, int> = 0> + static inline void merge_one(tuple_out_t& out, G const& g, Strategy const& strategy) + { + multi_linestring_t l; + union_<multi_linestring_t, G, multi_linestring_t>::apply(boost::get<1>(out), g, l, strategy); + boost::get<1>(out) = std::move(l); + } + + template <typename G, typename Strategy, std::enable_if_t<util::is_areal<G>::value, int> = 0> + static inline void merge_one(tuple_out_t& out, G const& g, Strategy const& strategy) + { + multi_polygon_t a; + union_<multi_polygon_t, G, multi_polygon_t>::apply(boost::get<2>(out), g, a, strategy); + boost::get<2>(out) = std::move(a); + } + + template <typename GC1View, typename GC2View, typename Group> + static inline void copy_disjoint(GC1View const& gc1_view, GC2View const& gc2_view, + Group const& disjoint_group, GeometryOut& geometry_out) + { + for (auto const& id : disjoint_group) + { + if (id.source_id == 0) + { + traits::iter_visit<GC1View>::apply([&](auto const& g1) + { + copy_one(g1, geometry_out); + }, boost::begin(gc1_view) + id.gc_id); + } + else + { + traits::iter_visit<GC2View>::apply([&](auto const& g2) + { + copy_one(g2, geometry_out); + }, boost::begin(gc2_view) + id.gc_id); + } + } + } + + template <typename G, std::enable_if_t<util::is_pointlike<G>::value, int> = 0> + static inline void copy_one(G const& g, GeometryOut& geometry_out) + { + multi_point_t p; + geometry::convert(g, p); + detail::intersection::gc_move_multi_back(geometry_out, p); + } + + template <typename G, std::enable_if_t<util::is_linear<G>::value, int> = 0> + static inline void copy_one(G const& g, GeometryOut& geometry_out) + { + multi_linestring_t l; + geometry::convert(g, l); + detail::intersection::gc_move_multi_back(geometry_out, l); + } + + template <typename G, std::enable_if_t<util::is_areal<G>::value, int> = 0> + static inline void copy_one(G const& g, GeometryOut& geometry_out) + { + multi_polygon_t a; + geometry::convert(g, a); + detail::intersection::gc_move_multi_back(geometry_out, a); + } + /* + template <typename Multi1, typename Multi2, typename Strategy> + static inline void subtract_greater_topodim(Multi1 const& multi1, Multi2 const& multi2, Multi1& multi_out, Strategy const& strategy) + { + using rescale_policy_type = typename geometry::rescale_overlay_policy_type + < + Multi1, Multi2 + >::type; + + rescale_policy_type robust_policy + = geometry::get_rescale_policy<rescale_policy_type>( + multi1, multi2, strategy); + + geometry::dispatch::intersection_insert + < + Multi1, Multi2, + typename boost::range_value<Multi1>::type, + overlay_difference, + geometry::detail::overlay::do_reverse<geometry::point_order<Multi1>::value>::value, + geometry::detail::overlay::do_reverse<geometry::point_order<Multi2>::value, true>::value + >::apply(multi1, multi2, robust_policy, range::back_inserter(multi_out), strategy); + } + */ +}; + +template +< + typename Geometry1, typename Geometry2, typename GeometryOut, typename Tag1 +> +struct union_ + < + Geometry1, Geometry2, GeometryOut, + Tag1, geometry_collection_tag, geometry_collection_tag + > +{ + template <typename Strategy> + static inline void apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + GeometryOut& geometry_out, + Strategy const& strategy) + { + using gc_view_t = geometry::detail::geometry_collection_view<Geometry1>; + union_ + < + gc_view_t, Geometry2, GeometryOut + >::apply(gc_view_t(geometry1), geometry2, geometry_out, strategy); + } +}; + +template +< + typename Geometry1, typename Geometry2, typename GeometryOut, typename Tag2 +> +struct union_ + < + Geometry1, Geometry2, GeometryOut, + geometry_collection_tag, Tag2, geometry_collection_tag + > +{ + template <typename Strategy> + static inline void apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + GeometryOut& geometry_out, + Strategy const& strategy) + { + using gc_view_t = geometry::detail::geometry_collection_view<Geometry2>; + union_ + < + Geometry1, gc_view_t, GeometryOut + >::apply(geometry1, gc_view_t(geometry2), geometry_out, strategy); + } +}; + +template +< + typename Geometry1, typename Geometry2, typename GeometryOut, typename Tag1, typename Tag2 +> +struct union_ + < + Geometry1, Geometry2, GeometryOut, + Tag1, Tag2, geometry_collection_tag + > +{ + template <typename Strategy> + static inline void apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + GeometryOut& geometry_out, + Strategy const& strategy) + { + using gc1_view_t = geometry::detail::geometry_collection_view<Geometry1>; + using gc2_view_t = geometry::detail::geometry_collection_view<Geometry2>; + union_ + < + gc1_view_t, gc2_view_t, GeometryOut + >::apply(gc1_view_t(geometry1), gc2_view_t(geometry2), geometry_out, strategy); + } +}; + +} // namespace resolve_collection + + +namespace resolve_strategy { + +template +< + typename Strategy, + bool IsUmbrella = strategies::detail::is_umbrella_strategy<Strategy>::value +> +struct union_ +{ + template <typename Geometry1, typename Geometry2, typename Collection> + static inline void apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + Collection & output_collection, + Strategy const& strategy) + { + resolve_collection::union_ + < + Geometry1, Geometry2, Collection + >::apply(geometry1, geometry2, output_collection, strategy); + } +}; + template <typename Strategy> struct union_<Strategy, false> { @@ -447,11 +741,11 @@ struct union_<default_strategy, false> Collection & output_collection, default_strategy) { - typedef typename strategies::relate::services::default_strategy + using strategy_type = typename strategies::relate::services::default_strategy < Geometry1, Geometry2 - >::type strategy_type; + >::type; union_ < @@ -463,10 +757,15 @@ struct union_<default_strategy, false> } // resolve_strategy -namespace resolve_variant +namespace resolve_dynamic { - -template <typename Geometry1, typename Geometry2> + +template +< + typename Geometry1, typename Geometry2, + typename Tag1 = typename geometry::tag<Geometry1>::type, + typename Tag2 = typename geometry::tag<Geometry2>::type +> struct union_ { template <typename Collection, typename Strategy> @@ -494,134 +793,64 @@ struct union_ }; -template <BOOST_VARIANT_ENUM_PARAMS(typename T), typename Geometry2> -struct union_<variant<BOOST_VARIANT_ENUM_PARAMS(T)>, Geometry2> +template <typename DynamicGeometry1, typename Geometry2, typename Tag2> +struct union_<DynamicGeometry1, Geometry2, dynamic_geometry_tag, Tag2> { template <typename Collection, typename Strategy> - struct visitor: static_visitor<> + static inline void apply(DynamicGeometry1 const& geometry1, Geometry2 const& geometry2, + Collection& output_collection, Strategy const& strategy) { - Geometry2 const& m_geometry2; - Collection& m_output_collection; - Strategy const& m_strategy; - - visitor(Geometry2 const& geometry2, - Collection& output_collection, - Strategy const& strategy) - : m_geometry2(geometry2) - , m_output_collection(output_collection) - , m_strategy(strategy) - {} - - template <typename Geometry1> - void operator()(Geometry1 const& geometry1) const + traits::visit<DynamicGeometry1>::apply([&](auto const& g1) { union_ < - Geometry1, + util::remove_cref_t<decltype(g1)>, Geometry2 - >::apply(geometry1, m_geometry2, m_output_collection, m_strategy); - } - }; - - template <typename Collection, typename Strategy> - static inline void - apply(variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry1, - Geometry2 const& geometry2, - Collection& output_collection, - Strategy const& strategy) - { - boost::apply_visitor(visitor<Collection, Strategy>(geometry2, - output_collection, - strategy), - geometry1); + >::apply(g1, geometry2, output_collection, strategy); + }, geometry1); } }; -template <typename Geometry1, BOOST_VARIANT_ENUM_PARAMS(typename T)> -struct union_<Geometry1, variant<BOOST_VARIANT_ENUM_PARAMS(T)> > +template <typename Geometry1, typename DynamicGeometry2, typename Tag1> +struct union_<Geometry1, DynamicGeometry2, Tag1, dynamic_geometry_tag> { template <typename Collection, typename Strategy> - struct visitor: static_visitor<> + static inline void apply(Geometry1 const& geometry1, DynamicGeometry2 const& geometry2, + Collection& output_collection, Strategy const& strategy) { - Geometry1 const& m_geometry1; - Collection& m_output_collection; - Strategy const& m_strategy; - - visitor(Geometry1 const& geometry1, - Collection& output_collection, - Strategy const& strategy) - : m_geometry1(geometry1) - , m_output_collection(output_collection) - , m_strategy(strategy) - {} - - template <typename Geometry2> - void operator()(Geometry2 const& geometry2) const + traits::visit<DynamicGeometry2>::apply([&](auto const& g2) { union_ < Geometry1, - Geometry2 - >::apply(m_geometry1, geometry2, m_output_collection, m_strategy); - } - }; - - template <typename Collection, typename Strategy> - static inline void - apply(Geometry1 const& geometry1, - variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry2, - Collection& output_collection, - Strategy const& strategy) - { - boost::apply_visitor(visitor<Collection, Strategy>(geometry1, - output_collection, - strategy), - geometry2); + util::remove_cref_t<decltype(g2)> + >::apply(geometry1, g2, output_collection, strategy); + }, geometry2); } }; -template <BOOST_VARIANT_ENUM_PARAMS(typename T1), BOOST_VARIANT_ENUM_PARAMS(typename T2)> -struct union_<variant<BOOST_VARIANT_ENUM_PARAMS(T1)>, variant<BOOST_VARIANT_ENUM_PARAMS(T2)> > +template <typename DynamicGeometry1, typename DynamicGeometry2> +struct union_<DynamicGeometry1, DynamicGeometry2, dynamic_geometry_tag, dynamic_geometry_tag> { template <typename Collection, typename Strategy> - struct visitor: static_visitor<> + static inline void apply(DynamicGeometry1 const& geometry1, DynamicGeometry2 const& geometry2, + Collection& output_collection, Strategy const& strategy) { - Collection& m_output_collection; - Strategy const& m_strategy; - - visitor(Collection& output_collection, Strategy const& strategy) - : m_output_collection(output_collection) - , m_strategy(strategy) - {} - - template <typename Geometry1, typename Geometry2> - void operator()(Geometry1 const& geometry1, - Geometry2 const& geometry2) const + traits::visit<DynamicGeometry1, DynamicGeometry2>::apply([&](auto const& g1, auto const& g2) { union_ < - Geometry1, - Geometry2 - >::apply(geometry1, geometry2, m_output_collection, m_strategy); - } - }; - - template <typename Collection, typename Strategy> - static inline void - apply(variant<BOOST_VARIANT_ENUM_PARAMS(T1)> const& geometry1, - variant<BOOST_VARIANT_ENUM_PARAMS(T2)> const& geometry2, - Collection& output_collection, - Strategy const& strategy) - { - boost::apply_visitor(visitor<Collection, Strategy>(output_collection, - strategy), - geometry1, geometry2); + util::remove_cref_t<decltype(g1)>, + util::remove_cref_t<decltype(g2)> + >::apply(g1, g2, output_collection, strategy); + }, geometry1, geometry2); } }; - -} // namespace resolve_variant + + +} // namespace resolve_dynamic /*! @@ -654,7 +883,7 @@ inline void union_(Geometry1 const& geometry1, Collection& output_collection, Strategy const& strategy) { - resolve_variant::union_ + resolve_dynamic::union_ < Geometry1, Geometry2 @@ -687,7 +916,7 @@ inline void union_(Geometry1 const& geometry1, Geometry2 const& geometry2, Collection& output_collection) { - resolve_variant::union_ + resolve_dynamic::union_ < Geometry1, Geometry2 |