diff options
Diffstat (limited to 'boost/geometry/algorithms/difference.hpp')
| -rw-r--r-- | boost/geometry/algorithms/difference.hpp | 449 |
1 files changed, 314 insertions, 135 deletions
diff --git a/boost/geometry/algorithms/difference.hpp b/boost/geometry/algorithms/difference.hpp index 2155b9e546..ec6e4ea734 100644 --- a/boost/geometry/algorithms/difference.hpp +++ b/boost/geometry/algorithms/difference.hpp @@ -2,9 +2,9 @@ // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. -// This file was modified by Oracle on 2017-2021. -// Modifications copyright (c) 2017-2021, Oracle and/or its affiliates. - +// This file was modified by Oracle on 2017-2023. +// Modifications copyright (c) 2017-2023, Oracle and/or its affiliates. +// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // Use, modification and distribution is subject to the Boost Software License, @@ -15,19 +15,21 @@ #define BOOST_GEOMETRY_ALGORITHMS_DIFFERENCE_HPP -#include <boost/variant/apply_visitor.hpp> -#include <boost/variant/static_visitor.hpp> -#include <boost/variant/variant_fwd.hpp> - +#include <boost/geometry/algorithms/detail/gc_make_rtree.hpp> +#include <boost/geometry/algorithms/detail/intersection/gc.hpp> #include <boost/geometry/algorithms/detail/intersection/multi.hpp> #include <boost/geometry/algorithms/detail/overlay/intersection_insert.hpp> +#include <boost/geometry/algorithms/detail/visit.hpp> +#include <boost/geometry/core/geometry_types.hpp> +#include <boost/geometry/geometries/adapted/boost_variant.hpp> // For backward compatibility #include <boost/geometry/policies/robustness/get_rescale_policy.hpp> #include <boost/geometry/strategies/default_strategy.hpp> #include <boost/geometry/strategies/detail.hpp> #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/sequence.hpp> +#include <boost/geometry/views/detail/geometry_collection_view.hpp> namespace boost { namespace geometry @@ -37,14 +39,23 @@ namespace boost { namespace geometry namespace detail { namespace difference { + +// True if the result of difference can be different than Geometry1 +template <typename Geometry1, typename Geometry2> +using is_subtractable_t = util::bool_constant + < + (geometry::topological_dimension<Geometry1>::value + <= geometry::topological_dimension<Geometry2>::value) + >; + + template < typename Geometry1, typename Geometry2, typename SingleOut, typename OutTag = typename detail::setop_insert_output_tag<SingleOut>::type, - bool ReturnGeometry1 = (topological_dimension<Geometry1>::value - > topological_dimension<Geometry2>::value) + bool ReturnGeometry1 = (! is_subtractable_t<Geometry1, Geometry2>::value) > struct call_intersection_insert { @@ -71,6 +82,26 @@ struct call_intersection_insert } }; + +template <typename Geometry1, typename Geometry2, typename SingleOut, typename OutTag> +struct call_intersection_insert<Geometry1, Geometry2, SingleOut, OutTag, true> +{ + template <typename OutputIterator, typename RobustPolicy, typename Strategy> + static inline OutputIterator apply(Geometry1 const& geometry1, + Geometry2 const& , + RobustPolicy const& , + OutputIterator out, + Strategy const& ) + { + return geometry::detail::convert_to_output + < + Geometry1, + SingleOut + >::apply(geometry1, out); + } +}; + + template < typename Geometry1, @@ -268,10 +299,237 @@ inline OutputIterator difference_insert(Geometry1 const& geometry1, } +template +< + typename Geometry, typename Collection, + typename CastedTag = typename geometry::tag_cast + < + typename geometry::tag<Geometry>::type, + pointlike_tag, linear_tag, areal_tag + >::type +> +struct multi_output_type +{ + BOOST_GEOMETRY_STATIC_ASSERT_FALSE( + "Not implemented this Geometry type.", + Geometry, CastedTag); +}; + +template <typename Geometry, typename Collection> +struct multi_output_type<Geometry, Collection, pointlike_tag> +{ + using type = typename util::sequence_find_if + < + typename traits::geometry_types<Collection>::type, + util::is_multi_point + >::type; +}; + +template <typename Geometry, typename Collection> +struct multi_output_type<Geometry, Collection, linear_tag> +{ + using type = typename util::sequence_find_if + < + typename traits::geometry_types<Collection>::type, + util::is_multi_linestring + >::type; +}; + +template <typename Geometry, typename Collection> +struct multi_output_type<Geometry, Collection, areal_tag> +{ + using type = typename util::sequence_find_if + < + typename traits::geometry_types<Collection>::type, + util::is_multi_polygon + >::type; +}; + + }} // namespace detail::difference #endif // DOXYGEN_NO_DETAIL +namespace resolve_collection +{ + + +template +< + typename Geometry1, typename Geometry2, typename Collection, + typename Tag1 = typename geometry::tag<Geometry1>::type, + typename Tag2 = typename geometry::tag<Geometry2>::type, + typename CollectionTag = typename geometry::tag<Collection>::type +> +struct difference +{ + template <typename Strategy> + static void apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + Collection & output_collection, + Strategy const& strategy) + { + using single_out = typename geometry::detail::output_geometry_value + < + Collection + >::type; + + detail::difference::difference_insert<single_out>( + geometry1, geometry2, + geometry::detail::output_geometry_back_inserter(output_collection), + strategy); + } +}; + +template <typename Geometry1, typename Geometry2, typename Collection> +struct difference + < + Geometry1, Geometry2, Collection, + geometry_collection_tag, geometry_collection_tag, geometry_collection_tag + > +{ + template <typename Strategy> + static void apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + Collection& output_collection, + Strategy const& strategy) + { + auto const rtree2 = detail::gc_make_rtree_iterators(geometry2, strategy); + detail::visit_breadth_first([&](auto const& g1) + { + // multi-point, multi-linestring or multi_polygon + typename detail::difference::multi_output_type + < + util::remove_cref_t<decltype(g1)>, Collection + >::type out; + + g1_minus_gc2(g1, rtree2, out, strategy); + + detail::intersection::gc_move_multi_back(output_collection, out); + + return true; + }, geometry1); + } + +private: + // Implemented as separate function because msvc is unable to do nested lambda capture + template <typename G1, typename Rtree2, typename MultiOut, typename Strategy> + static void g1_minus_gc2(G1 const& g1, Rtree2 const& rtree2, MultiOut& out, Strategy const& strategy) + { + { + using single_out_t = typename geometry::detail::output_geometry_value<MultiOut>::type; + auto out_it = geometry::detail::output_geometry_back_inserter(out); + geometry::detail::convert_to_output<G1, single_out_t>::apply(g1, out_it); + } + + using box1_t = detail::gc_make_rtree_box_t<G1>; + box1_t b1 = geometry::return_envelope<box1_t>(g1, strategy); + detail::expand_by_epsilon(b1); + + for (auto qit = rtree2.qbegin(index::intersects(b1)); qit != rtree2.qend(); ++qit) + { + traits::iter_visit<Geometry2>::apply([&](auto const& g2) + { + multi_out_minus_g2(out, g2, strategy); + }, qit->second); + + if (boost::empty(out)) + { + return; + } + } + } + + template + < + typename MultiOut, typename G2, typename Strategy, + std::enable_if_t<detail::difference::is_subtractable_t<MultiOut, G2>::value, int> = 0 + > + static void multi_out_minus_g2(MultiOut& out, G2 const& g2, Strategy const& strategy) + { + MultiOut result; + difference<MultiOut, G2, MultiOut>::apply(out, g2, result, strategy); + out = std::move(result); + } + + template + < + typename MultiOut, typename G2, typename Strategy, + std::enable_if_t<(! detail::difference::is_subtractable_t<MultiOut, G2>::value), int> = 0 + > + static void multi_out_minus_g2(MultiOut& , G2 const& , Strategy const& ) + {} +}; + + +template <typename Geometry1, typename Geometry2, typename Collection, typename Tag1> +struct difference + < + Geometry1, Geometry2, Collection, + Tag1, geometry_collection_tag, geometry_collection_tag + > +{ + template <typename Strategy> + static void apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + Collection & output_collection, + Strategy const& strategy) + { + using gc_view_t = geometry::detail::geometry_collection_view<Geometry1>; + difference + < + gc_view_t, Geometry2, Collection + >::apply(gc_view_t(geometry1), geometry2, output_collection, strategy); + } +}; + +template <typename Geometry1, typename Geometry2, typename Collection, typename Tag2> +struct difference + < + Geometry1, Geometry2, Collection, + geometry_collection_tag, Tag2, geometry_collection_tag + > +{ + template <typename Strategy> + static void apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + Collection & output_collection, + Strategy const& strategy) + { + using gc_view_t = geometry::detail::geometry_collection_view<Geometry2>; + difference + < + Geometry1, gc_view_t, Collection + >::apply(geometry1, gc_view_t(geometry2), output_collection, strategy); + } +}; + +template <typename Geometry1, typename Geometry2, typename Collection, typename Tag1, typename Tag2> +struct difference + < + Geometry1, Geometry2, Collection, + Tag1, Tag2, geometry_collection_tag + > +{ + template <typename Strategy> + static void apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + Collection & output_collection, + Strategy const& strategy) + { + using gc1_view_t = geometry::detail::geometry_collection_view<Geometry1>; + using gc2_view_t = geometry::detail::geometry_collection_view<Geometry2>; + difference + < + gc1_view_t, gc2_view_t, Collection + >::apply(gc1_view_t(geometry1), gc2_view_t(geometry2), output_collection, strategy); + } +}; + + +} // namespace resolve_collection + + namespace resolve_strategy { template @@ -287,15 +545,10 @@ struct difference Collection & output_collection, Strategy const& strategy) { - typedef typename geometry::detail::output_geometry_value + resolve_collection::difference < - Collection - >::type single_out; - - detail::difference::difference_insert<single_out>( - geometry1, geometry2, - geometry::detail::output_geometry_back_inserter(output_collection), - strategy); + Geometry1, Geometry2, Collection + >::apply(geometry1, geometry2, output_collection, strategy); } }; @@ -309,7 +562,7 @@ struct difference<Strategy, false> Strategy const& strategy) { using strategies::relate::services::strategy_converter; - + difference < decltype(strategy_converter<Strategy>::get(strategy)) @@ -332,7 +585,7 @@ struct difference<default_strategy, false> Geometry1, Geometry2 >::type strategy_type; - + difference < strategy_type @@ -343,17 +596,20 @@ struct difference<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 difference { template <typename Collection, typename Strategy> - static inline void apply(Geometry1 const& geometry1, - Geometry2 const& geometry2, - Collection& output_collection, - Strategy const& strategy) + static void apply(Geometry1 const& geometry1, Geometry2 const& geometry2, + Collection& output_collection, Strategy const& strategy) { resolve_strategy::difference < @@ -362,135 +618,58 @@ struct difference } }; - -template <BOOST_VARIANT_ENUM_PARAMS(typename T), typename Geometry2> -struct difference<variant<BOOST_VARIANT_ENUM_PARAMS(T)>, Geometry2> +template <typename DynamicGeometry1, typename Geometry2, typename Tag2> +struct difference<DynamicGeometry1, Geometry2, dynamic_geometry_tag, Tag2> { template <typename Collection, typename Strategy> - struct visitor: static_visitor<> + static 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) { - difference + resolve_strategy::difference < - Geometry1, - 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); + Strategy + >::apply(g1, geometry2, output_collection, strategy); + }, geometry1); } }; - -template <typename Geometry1, BOOST_VARIANT_ENUM_PARAMS(typename T)> -struct difference<Geometry1, variant<BOOST_VARIANT_ENUM_PARAMS(T)> > +template <typename Geometry1, typename DynamicGeometry2, typename Tag1> +struct difference<Geometry1, DynamicGeometry2, Tag1, dynamic_geometry_tag> { template <typename Collection, typename Strategy> - struct visitor: static_visitor<> + static 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) { - difference + resolve_strategy::difference < - 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); + Strategy + >::apply(geometry1, g2, output_collection, strategy); + }, geometry2); } }; - -template <BOOST_VARIANT_ENUM_PARAMS(typename T1), BOOST_VARIANT_ENUM_PARAMS(typename T2)> -struct difference<variant<BOOST_VARIANT_ENUM_PARAMS(T1)>, variant<BOOST_VARIANT_ENUM_PARAMS(T2)> > +template <typename DynamicGeometry1, typename DynamicGeometry2> +struct difference<DynamicGeometry1, DynamicGeometry2, dynamic_geometry_tag, dynamic_geometry_tag> { template <typename Collection, typename Strategy> - struct visitor: static_visitor<> + static 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) { - difference + resolve_strategy::difference < - 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); + Strategy + >::apply(g1, g2, output_collection, strategy); + }, geometry1, geometry2); } }; - -} // namespace resolve_variant + +} // namespace resolve_dynamic /*! @@ -521,7 +700,7 @@ inline void difference(Geometry1 const& geometry1, Collection& output_collection, Strategy const& strategy) { - resolve_variant::difference + resolve_dynamic::difference < Geometry1, Geometry2 @@ -552,7 +731,7 @@ inline void difference(Geometry1 const& geometry1, Geometry2 const& geometry2, Collection& output_collection) { - resolve_variant::difference + resolve_dynamic::difference < Geometry1, Geometry2 |