1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
5 // This file was modified by Oracle on 2015, 2017, 2019, 2020.
6 // Modifications copyright (c) 2015-2020 Oracle and/or its affiliates.
8 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
11 // Use, modification and distribution is subject to the Boost Software License,
12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
13 // http://www.boost.org/LICENSE_1_0.txt)
15 #ifndef BOOST_GEOMETRY_ALGORITHMS_SYM_DIFFERENCE_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_SYM_DIFFERENCE_HPP
23 #include <boost/variant/apply_visitor.hpp>
24 #include <boost/variant/static_visitor.hpp>
25 #include <boost/variant/variant_fwd.hpp>
27 #include <boost/geometry/algorithms/intersection.hpp>
28 #include <boost/geometry/algorithms/union.hpp>
29 #include <boost/geometry/geometries/multi_polygon.hpp>
30 #include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
31 #include <boost/geometry/strategies/default_strategy.hpp>
32 #include <boost/geometry/strategies/relate.hpp>
33 #include <boost/geometry/util/range.hpp>
36 namespace boost { namespace geometry
39 #ifndef DOXYGEN_NO_DETAIL
40 namespace detail { namespace sym_difference
44 template <typename GeometryOut>
45 struct compute_difference
51 typename RobustPolicy,
52 typename OutputIterator,
55 static inline OutputIterator apply(Geometry1 const& geometry1,
56 Geometry2 const& geometry2,
57 RobustPolicy const& robust_policy,
59 Strategy const& strategy)
61 return geometry::dispatch::intersection_insert
67 geometry::detail::overlay::do_reverse
69 geometry::point_order<Geometry1>::value
71 geometry::detail::overlay::do_reverse
73 geometry::point_order<Geometry2>::value, true
75 >::apply(geometry1, geometry2, robust_policy, out, strategy);
81 template <typename GeometryOut, typename Geometry1, typename Geometry2>
82 struct sym_difference_generic
86 typename RobustPolicy,
87 typename OutputIterator,
90 static inline OutputIterator apply(Geometry1 const& geometry1,
91 Geometry2 const& geometry2,
92 RobustPolicy const& robust_policy,
94 Strategy const& strategy)
96 out = compute_difference
99 >::apply(geometry1, geometry2, robust_policy, out, strategy);
101 return compute_difference
104 >::apply(geometry2, geometry1, robust_policy, out, strategy);
109 template <typename GeometryOut, typename Areal1, typename Areal2>
110 struct sym_difference_areal_areal
114 typename RobustPolicy,
115 typename OutputIterator,
118 static inline OutputIterator apply(Areal1 const& areal1,
119 Areal2 const& areal2,
120 RobustPolicy const& robust_policy,
122 Strategy const& strategy)
124 typedef geometry::model::multi_polygon
127 > helper_geometry_type;
129 helper_geometry_type diff12, diff21;
131 std::back_insert_iterator<helper_geometry_type> oit12(diff12);
132 std::back_insert_iterator<helper_geometry_type> oit21(diff21);
137 >::apply(areal1, areal2, robust_policy, oit12, strategy);
142 >::apply(areal2, areal1, robust_policy, oit21, strategy);
144 return geometry::dispatch::union_insert
146 helper_geometry_type,
147 helper_geometry_type,
149 >::apply(diff12, diff21, robust_policy, out, strategy);
156 typename GeometryOut,
158 template <typename, typename, typename> class Algorithm
160 struct sym_difference_same_inputs_tupled_output
166 typename RobustPolicy,
167 typename OutputIterator,
170 static inline OutputIterator apply(Geometry1 const& geometry1,
171 Geometry2 const& geometry2,
172 RobustPolicy const& robust_policy,
174 Strategy const& strategy)
176 typedef typename geometry::detail::output_geometry_access
178 GeometryOut, SingleTag, SingleTag
181 access::get(out) = Algorithm
183 typename access::type, Geometry1, Geometry2
184 >::apply(geometry1, geometry2, robust_policy, access::get(out), strategy);
193 typename GeometryOut,
196 bool Reverse = (geometry::core_dispatch::top_dim<SingleTag1>::value
197 > geometry::core_dispatch::top_dim<SingleTag2>::value)
199 struct sym_difference_different_inputs_tupled_output
205 typename RobustPolicy,
206 typename OutputIterator,
209 static inline OutputIterator apply(Geometry1 const& geometry1,
210 Geometry2 const& geometry2,
211 RobustPolicy const& robust_policy,
213 Strategy const& strategy)
215 return sym_difference_different_inputs_tupled_output
217 GeometryOut, SingleTag2, SingleTag1
218 >::apply(geometry2, geometry1, robust_policy, out, strategy);
224 typename GeometryOut,
228 struct sym_difference_different_inputs_tupled_output
230 GeometryOut, SingleTag1, SingleTag2, false
237 typename RobustPolicy,
238 typename OutputIterator,
241 static inline OutputIterator apply(Geometry1 const& geometry1,
242 Geometry2 const& geometry2,
243 RobustPolicy const& robust_policy,
245 Strategy const& strategy)
247 typedef typename geometry::detail::output_geometry_access
249 GeometryOut, SingleTag1, SingleTag1
251 typedef typename geometry::detail::output_geometry_access
253 GeometryOut, SingleTag2, SingleTag2
256 access1::get(out) = compute_difference
258 typename access1::type
259 >::apply(geometry1, geometry2, robust_policy, access1::get(out), strategy);
261 access2::get(out) = geometry::detail::convert_to_output
264 typename access2::type
265 >::apply(geometry2, access2::get(out));
272 }} // namespace detail::sym_difference
273 #endif // DOXYGEN_NO_DETAIL
277 #ifndef DOXYGEN_NO_DISPATCH
286 typename GeometryOut,
287 typename TagIn1 = typename geometry::tag_cast
289 typename tag<Geometry1>::type, pointlike_tag, linear_tag, areal_tag
291 typename TagIn2 = typename geometry::tag_cast
293 typename tag<Geometry2>::type, pointlike_tag, linear_tag, areal_tag
295 typename TagOut = typename detail::setop_insert_output_tag<GeometryOut>::type
297 struct sym_difference_insert
298 : detail::sym_difference::sym_difference_generic
300 GeometryOut, Geometry1, Geometry2
309 typename GeometryOut,
312 struct sym_difference_insert
314 Areal1, Areal2, GeometryOut,
315 areal_tag, areal_tag, TagOut
316 > : detail::sym_difference::sym_difference_areal_areal
318 GeometryOut, Areal1, Areal2
330 struct sym_difference_insert
332 PointLike1, PointLike2, GeometryOut,
333 pointlike_tag, pointlike_tag, detail::tupled_output_tag
335 : detail::expect_output<PointLike1, PointLike2, GeometryOut, point_tag>
336 , detail::sym_difference::sym_difference_same_inputs_tupled_output
340 detail::sym_difference::sym_difference_generic
350 struct sym_difference_insert
352 Linear1, Linear2, GeometryOut,
353 linear_tag, linear_tag, detail::tupled_output_tag
355 : detail::expect_output<Linear1, Linear2, GeometryOut, linestring_tag>
356 , detail::sym_difference::sym_difference_same_inputs_tupled_output
360 detail::sym_difference::sym_difference_generic
370 struct sym_difference_insert
372 Areal1, Areal2, GeometryOut,
373 areal_tag, areal_tag, detail::tupled_output_tag
375 : detail::expect_output<Areal1, Areal2, GeometryOut, polygon_tag>
376 , detail::sym_difference::sym_difference_same_inputs_tupled_output
380 detail::sym_difference::sym_difference_areal_areal
388 typename GeometryOut,
392 struct sym_difference_insert
394 Geometry1, Geometry2, GeometryOut,
395 TagIn1, TagIn2, detail::tupled_output_tag
397 : detail::expect_output
399 Geometry1, Geometry2, GeometryOut,
400 typename detail::single_tag_from_base_tag<TagIn1>::type,
401 typename detail::single_tag_from_base_tag<TagIn2>::type
403 , detail::sym_difference::sym_difference_different_inputs_tupled_output
406 typename detail::single_tag_from_base_tag<TagIn1>::type,
407 typename detail::single_tag_from_base_tag<TagIn2>::type
412 } // namespace dispatch
413 #endif // DOXYGEN_NO_DISPATCH
417 #ifndef DOXYGEN_NO_DETAIL
418 namespace detail { namespace sym_difference
424 \brief \brief_calc2{symmetric difference} \brief_strategy
425 \ingroup sym_difference
426 \details \details_calc2{symmetric difference, spatial set theoretic symmetric difference (XOR)}
427 \brief_strategy. \details_insert{sym_difference}
428 \tparam GeometryOut output geometry type, must be specified
429 \tparam Geometry1 \tparam_geometry
430 \tparam Geometry2 \tparam_geometry
431 \tparam Strategy \tparam_strategy_overlay
432 \param geometry1 \param_geometry
433 \param geometry2 \param_geometry
434 \param out \param_out{difference}
435 \param strategy \param_strategy{difference}
438 \qbk{distinguish,with strategy}
442 typename GeometryOut,
445 typename OutputIterator,
448 inline OutputIterator sym_difference_insert(Geometry1 const& geometry1,
449 Geometry2 const& geometry2,
451 Strategy const& strategy)
453 concepts::check<Geometry1 const>();
454 concepts::check<Geometry2 const>();
455 //concepts::check<GeometryOut>();
456 geometry::detail::output_geometry_concept_check<GeometryOut>::apply();
458 typedef typename geometry::rescale_overlay_policy_type
462 typename Strategy::cs_tag
463 >::type rescale_policy_type;
465 rescale_policy_type robust_policy
466 = geometry::get_rescale_policy<rescale_policy_type>(
467 geometry1, geometry2, strategy);
469 return dispatch::sym_difference_insert
471 Geometry1, Geometry2, GeometryOut
472 >::apply(geometry1, geometry2, robust_policy, out, strategy);
477 \brief \brief_calc2{symmetric difference}
478 \ingroup sym_difference
479 \details \details_calc2{symmetric difference, spatial set theoretic symmetric difference (XOR)}
480 \details_insert{sym_difference}
481 \tparam GeometryOut output geometry type, must be specified
482 \tparam Geometry1 \tparam_geometry
483 \tparam Geometry2 \tparam_geometry
484 \param geometry1 \param_geometry
485 \param geometry2 \param_geometry
486 \param out \param_out{difference}
492 typename GeometryOut,
495 typename OutputIterator
497 inline OutputIterator sym_difference_insert(Geometry1 const& geometry1,
498 Geometry2 const& geometry2, OutputIterator out)
500 typedef typename strategy::intersection::services::default_strategy
502 typename cs_tag<GeometryOut>::type
503 >::type strategy_type;
505 return sym_difference_insert<GeometryOut>(geometry1, geometry2, out, strategy_type());
508 }} // namespace detail::sym_difference
509 #endif // DOXYGEN_NO_DETAIL
512 namespace resolve_strategy {
514 struct sym_difference
523 static inline void apply(Geometry1 const& geometry1,
524 Geometry2 const& geometry2,
525 Collection & output_collection,
526 Strategy const& strategy)
528 typedef typename geometry::detail::output_geometry_value
533 detail::sym_difference::sym_difference_insert<single_out>(
534 geometry1, geometry2,
535 geometry::detail::output_geometry_back_inserter(output_collection),
545 static inline void apply(Geometry1 const& geometry1,
546 Geometry2 const& geometry2,
547 Collection & output_collection,
550 typedef typename strategy::relate::services::default_strategy
553 >::type strategy_type;
555 apply(geometry1, geometry2, output_collection, strategy_type());
559 } // resolve_strategy
562 namespace resolve_variant
565 template <typename Geometry1, typename Geometry2>
566 struct sym_difference
568 template <typename Collection, typename Strategy>
569 static inline void apply(Geometry1 const& geometry1,
570 Geometry2 const& geometry2,
571 Collection& output_collection,
572 Strategy const& strategy)
574 resolve_strategy::sym_difference::apply(geometry1, geometry2,
581 template <BOOST_VARIANT_ENUM_PARAMS(typename T), typename Geometry2>
582 struct sym_difference<variant<BOOST_VARIANT_ENUM_PARAMS(T)>, Geometry2>
584 template <typename Collection, typename Strategy>
585 struct visitor: static_visitor<>
587 Geometry2 const& m_geometry2;
588 Collection& m_output_collection;
589 Strategy const& m_strategy;
591 visitor(Geometry2 const& geometry2,
592 Collection& output_collection,
593 Strategy const& strategy)
594 : m_geometry2(geometry2)
595 , m_output_collection(output_collection)
596 , m_strategy(strategy)
599 template <typename Geometry1>
600 void operator()(Geometry1 const& geometry1) const
606 >::apply(geometry1, m_geometry2, m_output_collection, m_strategy);
610 template <typename Collection, typename Strategy>
612 apply(variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry1,
613 Geometry2 const& geometry2,
614 Collection& output_collection,
615 Strategy const& strategy)
617 boost::apply_visitor(visitor<Collection, Strategy>(geometry2,
625 template <typename Geometry1, BOOST_VARIANT_ENUM_PARAMS(typename T)>
626 struct sym_difference<Geometry1, variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
628 template <typename Collection, typename Strategy>
629 struct visitor: static_visitor<>
631 Geometry1 const& m_geometry1;
632 Collection& m_output_collection;
633 Strategy const& m_strategy;
635 visitor(Geometry1 const& geometry1,
636 Collection& output_collection,
637 Strategy const& strategy)
638 : m_geometry1(geometry1)
639 , m_output_collection(output_collection)
640 , m_strategy(strategy)
643 template <typename Geometry2>
644 void operator()(Geometry2 const& geometry2) const
650 >::apply(m_geometry1, geometry2, m_output_collection, m_strategy);
654 template <typename Collection, typename Strategy>
656 apply(Geometry1 const& geometry1,
657 variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry2,
658 Collection& output_collection,
659 Strategy const& strategy)
661 boost::apply_visitor(visitor<Collection, Strategy>(geometry1,
669 template <BOOST_VARIANT_ENUM_PARAMS(typename T1), BOOST_VARIANT_ENUM_PARAMS(typename T2)>
670 struct sym_difference<variant<BOOST_VARIANT_ENUM_PARAMS(T1)>, variant<BOOST_VARIANT_ENUM_PARAMS(T2)> >
672 template <typename Collection, typename Strategy>
673 struct visitor: static_visitor<>
675 Collection& m_output_collection;
676 Strategy const& m_strategy;
678 visitor(Collection& output_collection, Strategy const& strategy)
679 : m_output_collection(output_collection)
680 , m_strategy(strategy)
683 template <typename Geometry1, typename Geometry2>
684 void operator()(Geometry1 const& geometry1,
685 Geometry2 const& geometry2) const
691 >::apply(geometry1, geometry2, m_output_collection, m_strategy);
695 template <typename Collection, typename Strategy>
697 apply(variant<BOOST_VARIANT_ENUM_PARAMS(T1)> const& geometry1,
698 variant<BOOST_VARIANT_ENUM_PARAMS(T2)> const& geometry2,
699 Collection& output_collection,
700 Strategy const& strategy)
702 boost::apply_visitor(visitor<Collection, Strategy>(output_collection,
704 geometry1, geometry2);
708 } // namespace resolve_variant
712 \brief \brief_calc2{symmetric difference}
713 \ingroup sym_difference
714 \details \details_calc2{symmetric difference, spatial set theoretic symmetric difference (XOR)}.
715 \tparam Geometry1 \tparam_geometry
716 \tparam Geometry2 \tparam_geometry
717 \tparam Collection output collection, either a multi-geometry,
718 or a std::vector<Geometry> / std::deque<Geometry> etc
719 \tparam Strategy \tparam_strategy{Sym_difference}
720 \param geometry1 \param_geometry
721 \param geometry2 \param_geometry
722 \param output_collection the output collection
723 \param strategy \param_strategy{sym_difference}
725 \qbk{distinguish,with strategy}
726 \qbk{[include reference/algorithms/sym_difference.qbk]}
735 inline void sym_difference(Geometry1 const& geometry1,
736 Geometry2 const& geometry2,
737 Collection& output_collection,
738 Strategy const& strategy)
740 resolve_variant::sym_difference
744 >::apply(geometry1, geometry2, output_collection, strategy);
749 \brief \brief_calc2{symmetric difference}
750 \ingroup sym_difference
751 \details \details_calc2{symmetric difference, spatial set theoretic symmetric difference (XOR)}.
752 \tparam Geometry1 \tparam_geometry
753 \tparam Geometry2 \tparam_geometry
754 \tparam Collection output collection, either a multi-geometry,
755 or a std::vector<Geometry> / std::deque<Geometry> etc
756 \param geometry1 \param_geometry
757 \param geometry2 \param_geometry
758 \param output_collection the output collection
760 \qbk{[include reference/algorithms/sym_difference.qbk]}
768 inline void sym_difference(Geometry1 const& geometry1,
769 Geometry2 const& geometry2,
770 Collection& output_collection)
772 resolve_variant::sym_difference
776 >::apply(geometry1, geometry2, output_collection, default_strategy());
780 }} // namespace boost::geometry
783 #endif // BOOST_GEOMETRY_ALGORITHMS_SYM_DIFFERENCE_HPP