1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
4
5 // This file was modified by Oracle on 2014, 2017, 2018, 2019, 2020.
6 // Modifications copyright (c) 2014-2020 Oracle and/or its affiliates.
7
8 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
10
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)
14
15 #ifndef BOOST_GEOMETRY_ALGORITHMS_UNION_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_UNION_HPP
17
18
19 #include <boost/range/metafunctions.hpp>
20
21 #include <boost/geometry/core/point_order.hpp>
22 #include <boost/geometry/core/reverse_dispatch.hpp>
23 #include <boost/geometry/geometries/concepts/check.hpp>
24 #include <boost/geometry/algorithms/not_implemented.hpp>
25 #include <boost/geometry/algorithms/detail/overlay/overlay.hpp>
26 #include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
27 #include <boost/geometry/strategies/default_strategy.hpp>
28 #include <boost/geometry/util/range.hpp>
29
30 #include <boost/geometry/algorithms/detail/intersection/multi.hpp>
31 #include <boost/geometry/algorithms/detail/overlay/intersection_insert.hpp>
32 #include <boost/geometry/algorithms/detail/overlay/linear_linear.hpp>
33 #include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp>
34
35
36 namespace boost { namespace geometry
37 {
38
39 #ifndef DOXYGEN_NO_DISPATCH
40 namespace dispatch
41 {
42
43 template
44 <
45 typename Geometry1, typename Geometry2, typename GeometryOut,
46 typename TagIn1 = typename tag<Geometry1>::type,
47 typename TagIn2 = typename tag<Geometry2>::type,
48 typename TagOut = typename detail::setop_insert_output_tag<GeometryOut>::type,
49 typename CastedTagIn1 = typename geometry::tag_cast<TagIn1, areal_tag, linear_tag, pointlike_tag>::type,
50 typename CastedTagIn2 = typename geometry::tag_cast<TagIn2, areal_tag, linear_tag, pointlike_tag>::type,
51 typename CastedTagOut = typename geometry::tag_cast<TagOut, areal_tag, linear_tag, pointlike_tag>::type,
52 bool Reverse = geometry::reverse_dispatch<Geometry1, Geometry2>::type::value
53 >
54 struct union_insert: not_implemented<TagIn1, TagIn2, TagOut>
55 {};
56
57
58 // If reversal is needed, perform it first
59
60 template
61 <
62 typename Geometry1, typename Geometry2, typename GeometryOut,
63 typename TagIn1, typename TagIn2, typename TagOut,
64 typename CastedTagIn1, typename CastedTagIn2, typename CastedTagOut
65 >
66 struct union_insert
67 <
68 Geometry1, Geometry2, GeometryOut,
69 TagIn1, TagIn2, TagOut,
70 CastedTagIn1, CastedTagIn2, CastedTagOut,
71 true
72 >
73 {
74 template <typename RobustPolicy, typename OutputIterator, typename Strategy>
applyboost::geometry::dispatch::union_insert75 static inline OutputIterator apply(Geometry1 const& g1,
76 Geometry2 const& g2,
77 RobustPolicy const& robust_policy,
78 OutputIterator out,
79 Strategy const& strategy)
80 {
81 return union_insert
82 <
83 Geometry2, Geometry1, GeometryOut
84 >::apply(g2, g1, robust_policy, out, strategy);
85 }
86 };
87
88
89 template
90 <
91 typename Geometry1, typename Geometry2, typename GeometryOut,
92 typename TagIn1, typename TagIn2, typename TagOut
93 >
94 struct union_insert
95 <
96 Geometry1, Geometry2, GeometryOut,
97 TagIn1, TagIn2, TagOut,
98 areal_tag, areal_tag, areal_tag,
99 false
100 > : detail::overlay::overlay
101 <
102 Geometry1, Geometry2,
103 detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
104 detail::overlay::do_reverse<geometry::point_order<Geometry2>::value>::value,
105 detail::overlay::do_reverse<geometry::point_order<GeometryOut>::value>::value,
106 GeometryOut,
107 overlay_union
108 >
109 {};
110
111
112 // dispatch for union of linear geometries
113 template
114 <
115 typename Linear1, typename Linear2, typename LineStringOut,
116 typename TagIn1, typename TagIn2
117 >
118 struct union_insert
119 <
120 Linear1, Linear2, LineStringOut,
121 TagIn1, TagIn2, linestring_tag,
122 linear_tag, linear_tag, linear_tag,
123 false
124 > : detail::overlay::linear_linear_linestring
125 <
126 Linear1, Linear2, LineStringOut, overlay_union
127 >
128 {};
129
130
131 // dispatch for point-like geometries
132 template
133 <
134 typename PointLike1, typename PointLike2, typename PointOut,
135 typename TagIn1, typename TagIn2
136 >
137 struct union_insert
138 <
139 PointLike1, PointLike2, PointOut,
140 TagIn1, TagIn2, point_tag,
141 pointlike_tag, pointlike_tag, pointlike_tag,
142 false
143 > : detail::overlay::union_pointlike_pointlike_point
144 <
145 PointLike1, PointLike2, PointOut
146 >
147 {};
148
149
150 template
151 <
152 typename Geometry1, typename Geometry2, typename SingleTupledOut,
153 typename TagIn1, typename TagIn2,
154 typename CastedTagIn
155 >
156 struct union_insert
157 <
158 Geometry1, Geometry2, SingleTupledOut,
159 TagIn1, TagIn2, detail::tupled_output_tag,
160 CastedTagIn, CastedTagIn, detail::tupled_output_tag,
161 false
162 >
163 {
164 typedef typename geometry::detail::single_tag_from_base_tag
165 <
166 CastedTagIn
167 >::type single_tag;
168
169 typedef detail::expect_output
170 <
171 Geometry1, Geometry2, SingleTupledOut, single_tag
172 > expect_check;
173
174 typedef typename geometry::detail::output_geometry_access
175 <
176 SingleTupledOut, single_tag, single_tag
177 > access;
178
179 template <typename RobustPolicy, typename OutputIterator, typename Strategy>
applyboost::geometry::dispatch::union_insert180 static inline OutputIterator apply(Geometry1 const& g1,
181 Geometry2 const& g2,
182 RobustPolicy const& robust_policy,
183 OutputIterator out,
184 Strategy const& strategy)
185 {
186 access::get(out) = union_insert
187 <
188 Geometry2, Geometry1, typename access::type
189 >::apply(g2, g1, robust_policy, access::get(out), strategy);
190
191 return out;
192 }
193 };
194
195
196 template
197 <
198 typename Geometry1, typename Geometry2, typename SingleTupledOut,
199 typename SingleTag1, typename SingleTag2,
200 bool Geometry1LesserTopoDim = (topological_dimension<Geometry1>::value
201 < topological_dimension<Geometry2>::value)
202 >
203 struct union_insert_tupled_different
204 {
205 typedef typename geometry::detail::output_geometry_access
206 <
207 SingleTupledOut, SingleTag1, SingleTag1
208 > access1;
209
210 typedef typename geometry::detail::output_geometry_access
211 <
212 SingleTupledOut, SingleTag2, SingleTag2
213 > access2;
214
215 template <typename RobustPolicy, typename OutputIterator, typename Strategy>
applyboost::geometry::dispatch::union_insert_tupled_different216 static inline OutputIterator apply(Geometry1 const& g1,
217 Geometry2 const& g2,
218 RobustPolicy const& robust_policy,
219 OutputIterator out,
220 Strategy const& strategy)
221 {
222 access1::get(out) = geometry::dispatch::intersection_insert
223 <
224 Geometry1, Geometry2,
225 typename access1::type,
226 overlay_difference,
227 geometry::detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
228 geometry::detail::overlay::do_reverse<geometry::point_order<Geometry2>::value, true>::value
229 >::apply(g1, g2, robust_policy, access1::get(out), strategy);
230
231 access2::get(out) = geometry::detail::convert_to_output
232 <
233 Geometry2,
234 typename access2::type
235 >::apply(g2, access2::get(out));
236
237 return out;
238 }
239 };
240
241
242 template
243 <
244 typename Geometry1, typename Geometry2, typename SingleTupledOut,
245 typename SingleTag1, typename SingleTag2
246 >
247 struct union_insert_tupled_different
248 <
249 Geometry1, Geometry2, SingleTupledOut, SingleTag1, SingleTag2, false
250 >
251 {
252 template <typename RobustPolicy, typename OutputIterator, typename Strategy>
applyboost::geometry::dispatch::union_insert_tupled_different253 static inline OutputIterator apply(Geometry1 const& g1,
254 Geometry2 const& g2,
255 RobustPolicy const& robust_policy,
256 OutputIterator out,
257 Strategy const& strategy)
258 {
259 return union_insert_tupled_different
260 <
261 Geometry2, Geometry1, SingleTupledOut, SingleTag2, SingleTag1, true
262 >::apply(g2, g1, robust_policy, out, strategy);
263 }
264 };
265
266
267 template
268 <
269 typename Geometry1, typename Geometry2, typename SingleTupledOut,
270 typename TagIn1, typename TagIn2,
271 typename CastedTagIn1, typename CastedTagIn2
272 >
273 struct union_insert
274 <
275 Geometry1, Geometry2, SingleTupledOut,
276 TagIn1, TagIn2, detail::tupled_output_tag,
277 CastedTagIn1, CastedTagIn2, detail::tupled_output_tag,
278 false
279 >
280 {
281 typedef typename geometry::detail::single_tag_from_base_tag
282 <
283 CastedTagIn1
284 >::type single_tag1;
285
286 typedef detail::expect_output
287 <
288 Geometry1, Geometry2, SingleTupledOut, single_tag1
289 > expect_check1;
290
291 typedef typename geometry::detail::single_tag_from_base_tag
292 <
293 CastedTagIn2
294 >::type single_tag2;
295
296 typedef detail::expect_output
297 <
298 Geometry1, Geometry2, SingleTupledOut, single_tag2
299 > expect_check2;
300
301 template <typename RobustPolicy, typename OutputIterator, typename Strategy>
applyboost::geometry::dispatch::union_insert302 static inline OutputIterator apply(Geometry1 const& g1,
303 Geometry2 const& g2,
304 RobustPolicy const& robust_policy,
305 OutputIterator out,
306 Strategy const& strategy)
307 {
308 return union_insert_tupled_different
309 <
310 Geometry1, Geometry2, SingleTupledOut, single_tag1, single_tag2
311 >::apply(g1, g2, robust_policy, out, strategy);
312 }
313 };
314
315
316 } // namespace dispatch
317 #endif // DOXYGEN_NO_DISPATCH
318
319 #ifndef DOXYGEN_NO_DETAIL
320 namespace detail { namespace union_
321 {
322
323 /*!
324 \brief_calc2{union}
325 \ingroup union
326 \details \details_calc2{union_insert, spatial set theoretic union}.
327 \details_insert{union}
328 \tparam GeometryOut output geometry type, must be specified
329 \tparam Geometry1 \tparam_geometry
330 \tparam Geometry2 \tparam_geometry
331 \tparam OutputIterator output iterator
332 \param geometry1 \param_geometry
333 \param geometry2 \param_geometry
334 \param out \param_out{union}
335 \return \return_out
336 */
337 template
338 <
339 typename GeometryOut,
340 typename Geometry1,
341 typename Geometry2,
342 typename OutputIterator
343 >
union_insert(Geometry1 const & geometry1,Geometry2 const & geometry2,OutputIterator out)344 inline OutputIterator union_insert(Geometry1 const& geometry1,
345 Geometry2 const& geometry2,
346 OutputIterator out)
347 {
348 concepts::check<Geometry1 const>();
349 concepts::check<Geometry2 const>();
350 geometry::detail::output_geometry_concept_check<GeometryOut>::apply();
351
352 typename strategy::intersection::services::default_strategy
353 <
354 typename cs_tag<GeometryOut>::type
355 >::type strategy;
356
357 typedef typename geometry::rescale_overlay_policy_type
358 <
359 Geometry1,
360 Geometry2
361 >::type rescale_policy_type;
362
363 rescale_policy_type robust_policy
364 = geometry::get_rescale_policy<rescale_policy_type>(
365 geometry1, geometry2, strategy);
366
367 return dispatch::union_insert
368 <
369 Geometry1, Geometry2, GeometryOut
370 >::apply(geometry1, geometry2, robust_policy, out, strategy);
371 }
372
373
374 }} // namespace detail::union_
375 #endif // DOXYGEN_NO_DETAIL
376
377
378 namespace resolve_strategy {
379
380 struct union_
381 {
382 template
383 <
384 typename Geometry1,
385 typename Geometry2,
386 typename Collection,
387 typename Strategy
388 >
applyboost::geometry::resolve_strategy::union_389 static inline void apply(Geometry1 const& geometry1,
390 Geometry2 const& geometry2,
391 Collection & output_collection,
392 Strategy const& strategy)
393 {
394 typedef typename geometry::detail::output_geometry_value
395 <
396 Collection
397 >::type single_out;
398
399 typedef typename geometry::rescale_overlay_policy_type
400 <
401 Geometry1,
402 Geometry2,
403 typename Strategy::cs_tag
404 >::type rescale_policy_type;
405
406 rescale_policy_type robust_policy
407 = geometry::get_rescale_policy<rescale_policy_type>(
408 geometry1, geometry2, strategy);
409
410 dispatch::union_insert
411 <
412 Geometry1, Geometry2, single_out
413 >::apply(geometry1, geometry2, robust_policy,
414 geometry::detail::output_geometry_back_inserter(output_collection),
415 strategy);
416 }
417
418 template
419 <
420 typename Geometry1,
421 typename Geometry2,
422 typename Collection
423 >
applyboost::geometry::resolve_strategy::union_424 static inline void apply(Geometry1 const& geometry1,
425 Geometry2 const& geometry2,
426 Collection & output_collection,
427 default_strategy)
428 {
429 typedef typename strategy::relate::services::default_strategy
430 <
431 Geometry1,
432 Geometry2
433 >::type strategy_type;
434
435 apply(geometry1, geometry2, output_collection, strategy_type());
436 }
437 };
438
439 } // resolve_strategy
440
441
442 namespace resolve_variant
443 {
444
445 template <typename Geometry1, typename Geometry2>
446 struct union_
447 {
448 template <typename Collection, typename Strategy>
applyboost::geometry::resolve_variant::union_449 static inline void apply(Geometry1 const& geometry1,
450 Geometry2 const& geometry2,
451 Collection& output_collection,
452 Strategy const& strategy)
453 {
454 concepts::check<Geometry1 const>();
455 concepts::check<Geometry2 const>();
456 //concepts::check<typename boost::range_value<Collection>::type>();
457 geometry::detail::output_geometry_concept_check
458 <
459 typename geometry::detail::output_geometry_value
460 <
461 Collection
462 >::type
463 >::apply();
464
465 resolve_strategy::union_::apply(geometry1, geometry2,
466 output_collection,
467 strategy);
468 }
469 };
470
471
472 template <BOOST_VARIANT_ENUM_PARAMS(typename T), typename Geometry2>
473 struct union_<variant<BOOST_VARIANT_ENUM_PARAMS(T)>, Geometry2>
474 {
475 template <typename Collection, typename Strategy>
476 struct visitor: static_visitor<>
477 {
478 Geometry2 const& m_geometry2;
479 Collection& m_output_collection;
480 Strategy const& m_strategy;
481
visitorboost::geometry::resolve_variant::union_::visitor482 visitor(Geometry2 const& geometry2,
483 Collection& output_collection,
484 Strategy const& strategy)
485 : m_geometry2(geometry2)
486 , m_output_collection(output_collection)
487 , m_strategy(strategy)
488 {}
489
490 template <typename Geometry1>
operator ()boost::geometry::resolve_variant::union_::visitor491 void operator()(Geometry1 const& geometry1) const
492 {
493 union_
494 <
495 Geometry1,
496 Geometry2
497 >::apply(geometry1, m_geometry2, m_output_collection, m_strategy);
498 }
499 };
500
501 template <typename Collection, typename Strategy>
502 static inline void
applyboost::geometry::resolve_variant::union_503 apply(variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry1,
504 Geometry2 const& geometry2,
505 Collection& output_collection,
506 Strategy const& strategy)
507 {
508 boost::apply_visitor(visitor<Collection, Strategy>(geometry2,
509 output_collection,
510 strategy),
511 geometry1);
512 }
513 };
514
515
516 template <typename Geometry1, BOOST_VARIANT_ENUM_PARAMS(typename T)>
517 struct union_<Geometry1, variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
518 {
519 template <typename Collection, typename Strategy>
520 struct visitor: static_visitor<>
521 {
522 Geometry1 const& m_geometry1;
523 Collection& m_output_collection;
524 Strategy const& m_strategy;
525
visitorboost::geometry::resolve_variant::union_::visitor526 visitor(Geometry1 const& geometry1,
527 Collection& output_collection,
528 Strategy const& strategy)
529 : m_geometry1(geometry1)
530 , m_output_collection(output_collection)
531 , m_strategy(strategy)
532 {}
533
534 template <typename Geometry2>
operator ()boost::geometry::resolve_variant::union_::visitor535 void operator()(Geometry2 const& geometry2) const
536 {
537 union_
538 <
539 Geometry1,
540 Geometry2
541 >::apply(m_geometry1, geometry2, m_output_collection, m_strategy);
542 }
543 };
544
545 template <typename Collection, typename Strategy>
546 static inline void
applyboost::geometry::resolve_variant::union_547 apply(Geometry1 const& geometry1,
548 variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry2,
549 Collection& output_collection,
550 Strategy const& strategy)
551 {
552 boost::apply_visitor(visitor<Collection, Strategy>(geometry1,
553 output_collection,
554 strategy),
555 geometry2);
556 }
557 };
558
559
560 template <BOOST_VARIANT_ENUM_PARAMS(typename T1), BOOST_VARIANT_ENUM_PARAMS(typename T2)>
561 struct union_<variant<BOOST_VARIANT_ENUM_PARAMS(T1)>, variant<BOOST_VARIANT_ENUM_PARAMS(T2)> >
562 {
563 template <typename Collection, typename Strategy>
564 struct visitor: static_visitor<>
565 {
566 Collection& m_output_collection;
567 Strategy const& m_strategy;
568
visitorboost::geometry::resolve_variant::union_::visitor569 visitor(Collection& output_collection, Strategy const& strategy)
570 : m_output_collection(output_collection)
571 , m_strategy(strategy)
572 {}
573
574 template <typename Geometry1, typename Geometry2>
operator ()boost::geometry::resolve_variant::union_::visitor575 void operator()(Geometry1 const& geometry1,
576 Geometry2 const& geometry2) const
577 {
578 union_
579 <
580 Geometry1,
581 Geometry2
582 >::apply(geometry1, geometry2, m_output_collection, m_strategy);
583 }
584 };
585
586 template <typename Collection, typename Strategy>
587 static inline void
applyboost::geometry::resolve_variant::union_588 apply(variant<BOOST_VARIANT_ENUM_PARAMS(T1)> const& geometry1,
589 variant<BOOST_VARIANT_ENUM_PARAMS(T2)> const& geometry2,
590 Collection& output_collection,
591 Strategy const& strategy)
592 {
593 boost::apply_visitor(visitor<Collection, Strategy>(output_collection,
594 strategy),
595 geometry1, geometry2);
596 }
597 };
598
599 } // namespace resolve_variant
600
601
602 /*!
603 \brief Combines two geometries which each other
604 \ingroup union
605 \details \details_calc2{union, spatial set theoretic union}.
606 \tparam Geometry1 \tparam_geometry
607 \tparam Geometry2 \tparam_geometry
608 \tparam Collection output collection, either a multi-geometry,
609 or a std::vector<Geometry> / std::deque<Geometry> etc
610 \tparam Strategy \tparam_strategy{Union_}
611 \param geometry1 \param_geometry
612 \param geometry2 \param_geometry
613 \param output_collection the output collection
614 \param strategy \param_strategy{union_}
615 \note Called union_ because union is a reserved word.
616
617 \qbk{distinguish,with strategy}
618 \qbk{[include reference/algorithms/union.qbk]}
619 */
620 template
621 <
622 typename Geometry1,
623 typename Geometry2,
624 typename Collection,
625 typename Strategy
626 >
union_(Geometry1 const & geometry1,Geometry2 const & geometry2,Collection & output_collection,Strategy const & strategy)627 inline void union_(Geometry1 const& geometry1,
628 Geometry2 const& geometry2,
629 Collection& output_collection,
630 Strategy const& strategy)
631 {
632 resolve_variant::union_
633 <
634 Geometry1,
635 Geometry2
636 >::apply(geometry1, geometry2, output_collection, strategy);
637 }
638
639
640 /*!
641 \brief Combines two geometries which each other
642 \ingroup union
643 \details \details_calc2{union, spatial set theoretic union}.
644 \tparam Geometry1 \tparam_geometry
645 \tparam Geometry2 \tparam_geometry
646 \tparam Collection output collection, either a multi-geometry,
647 or a std::vector<Geometry> / std::deque<Geometry> etc
648 \param geometry1 \param_geometry
649 \param geometry2 \param_geometry
650 \param output_collection the output collection
651 \note Called union_ because union is a reserved word.
652
653 \qbk{[include reference/algorithms/union.qbk]}
654 */
655 template
656 <
657 typename Geometry1,
658 typename Geometry2,
659 typename Collection
660 >
union_(Geometry1 const & geometry1,Geometry2 const & geometry2,Collection & output_collection)661 inline void union_(Geometry1 const& geometry1,
662 Geometry2 const& geometry2,
663 Collection& output_collection)
664 {
665 resolve_variant::union_
666 <
667 Geometry1,
668 Geometry2
669 >::apply(geometry1, geometry2, output_collection, default_strategy());
670 }
671
672
673 }} // namespace boost::geometry
674
675
676 #endif // BOOST_GEOMETRY_ALGORITHMS_UNION_HPP
677