]>
Commit | Line | Data |
---|---|---|
b32b8144 FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | ||
20effc67 TL |
5 | // This file was modified by Oracle on 2017, 2019, 2020. |
6 | // Modifications copyright (c) 2017-2020, Oracle and/or its affiliates. | |
b32b8144 FG |
7 | |
8 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
9 | ||
10 | // Use, modification and distribution is subject to the Boost Software License, | |
11 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
12 | // http://www.boost.org/LICENSE_1_0.txt) | |
13 | ||
14 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DIFFERENCE_HPP | |
15 | #define BOOST_GEOMETRY_ALGORITHMS_DIFFERENCE_HPP | |
16 | ||
17 | ||
18 | #include <boost/variant/apply_visitor.hpp> | |
19 | #include <boost/variant/static_visitor.hpp> | |
20 | #include <boost/variant/variant_fwd.hpp> | |
21 | ||
20effc67 | 22 | #include <boost/geometry/algorithms/detail/intersection/multi.hpp> |
b32b8144 FG |
23 | #include <boost/geometry/algorithms/detail/overlay/intersection_insert.hpp> |
24 | #include <boost/geometry/policies/robustness/get_rescale_policy.hpp> | |
25 | #include <boost/geometry/strategies/default_strategy.hpp> | |
26 | #include <boost/geometry/util/range.hpp> | |
27 | ||
28 | ||
29 | namespace boost { namespace geometry | |
30 | { | |
31 | ||
32 | #ifndef DOXYGEN_NO_DETAIL | |
33 | namespace detail { namespace difference | |
34 | { | |
35 | ||
20effc67 TL |
36 | template |
37 | < | |
38 | typename Geometry1, | |
39 | typename Geometry2, | |
40 | typename SingleOut, | |
41 | typename OutTag = typename detail::setop_insert_output_tag<SingleOut>::type, | |
42 | bool ReturnGeometry1 = (topological_dimension<Geometry1>::value | |
43 | > topological_dimension<Geometry2>::value) | |
44 | > | |
45 | struct call_intersection_insert | |
46 | { | |
47 | template | |
48 | < | |
49 | typename OutputIterator, | |
50 | typename RobustPolicy, | |
51 | typename Strategy | |
52 | > | |
53 | static inline OutputIterator apply(Geometry1 const& geometry1, | |
54 | Geometry2 const& geometry2, | |
55 | RobustPolicy const& robust_policy, | |
56 | OutputIterator out, | |
57 | Strategy const& strategy) | |
58 | { | |
59 | return geometry::dispatch::intersection_insert | |
60 | < | |
61 | Geometry1, Geometry2, | |
62 | SingleOut, | |
63 | overlay_difference, | |
64 | geometry::detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value, | |
65 | geometry::detail::overlay::do_reverse<geometry::point_order<Geometry2>::value, true>::value | |
66 | >::apply(geometry1, geometry2, robust_policy, out, strategy); | |
67 | } | |
68 | }; | |
69 | ||
70 | template | |
71 | < | |
72 | typename Geometry1, | |
73 | typename Geometry2, | |
74 | typename SingleOut | |
75 | > | |
76 | struct call_intersection_insert_tupled_base | |
77 | { | |
78 | typedef typename geometry::detail::single_tag_from_base_tag | |
79 | < | |
80 | typename geometry::tag_cast | |
81 | < | |
82 | typename geometry::tag<Geometry1>::type, | |
83 | pointlike_tag, linear_tag, areal_tag | |
84 | >::type | |
85 | >::type single_tag; | |
86 | ||
87 | typedef detail::expect_output | |
88 | < | |
89 | Geometry1, Geometry2, SingleOut, single_tag | |
90 | > expect_check; | |
91 | ||
92 | typedef typename geometry::detail::output_geometry_access | |
93 | < | |
94 | SingleOut, single_tag, single_tag | |
95 | > access; | |
96 | }; | |
97 | ||
98 | template | |
99 | < | |
100 | typename Geometry1, | |
101 | typename Geometry2, | |
102 | typename SingleOut | |
103 | > | |
104 | struct call_intersection_insert | |
105 | < | |
106 | Geometry1, Geometry2, SingleOut, | |
107 | detail::tupled_output_tag, | |
108 | false | |
109 | > | |
110 | : call_intersection_insert_tupled_base<Geometry1, Geometry2, SingleOut> | |
111 | { | |
112 | typedef call_intersection_insert_tupled_base<Geometry1, Geometry2, SingleOut> base_t; | |
113 | ||
114 | template | |
115 | < | |
116 | typename OutputIterator, | |
117 | typename RobustPolicy, | |
118 | typename Strategy | |
119 | > | |
120 | static inline OutputIterator apply(Geometry1 const& geometry1, | |
121 | Geometry2 const& geometry2, | |
122 | RobustPolicy const& robust_policy, | |
123 | OutputIterator out, | |
124 | Strategy const& strategy) | |
125 | { | |
126 | base_t::access::get(out) = call_intersection_insert | |
127 | < | |
128 | Geometry1, Geometry2, | |
129 | typename base_t::access::type | |
130 | >::apply(geometry1, geometry2, robust_policy, | |
131 | base_t::access::get(out), strategy); | |
132 | ||
133 | return out; | |
134 | } | |
135 | }; | |
136 | ||
137 | template | |
138 | < | |
139 | typename Geometry1, | |
140 | typename Geometry2, | |
141 | typename SingleOut | |
142 | > | |
143 | struct call_intersection_insert | |
144 | < | |
145 | Geometry1, Geometry2, SingleOut, | |
146 | detail::tupled_output_tag, | |
147 | true | |
148 | > | |
149 | : call_intersection_insert_tupled_base<Geometry1, Geometry2, SingleOut> | |
150 | { | |
151 | typedef call_intersection_insert_tupled_base<Geometry1, Geometry2, SingleOut> base_t; | |
152 | ||
153 | template | |
154 | < | |
155 | typename OutputIterator, | |
156 | typename RobustPolicy, | |
157 | typename Strategy | |
158 | > | |
159 | static inline OutputIterator apply(Geometry1 const& geometry1, | |
160 | Geometry2 const& geometry2, | |
161 | RobustPolicy const& robust_policy, | |
162 | OutputIterator out, | |
163 | Strategy const& strategy) | |
164 | { | |
165 | base_t::access::get(out) = geometry::detail::convert_to_output | |
166 | < | |
167 | Geometry1, | |
168 | typename base_t::access::type | |
169 | >::apply(geometry1, base_t::access::get(out)); | |
170 | ||
171 | return out; | |
172 | } | |
173 | }; | |
174 | ||
175 | ||
b32b8144 FG |
176 | /*! |
177 | \brief_calc2{difference} \brief_strategy | |
178 | \ingroup difference | |
179 | \details \details_calc2{difference_insert, spatial set theoretic difference} | |
180 | \brief_strategy. \details_inserter{difference} | |
181 | \tparam GeometryOut output geometry type, must be specified | |
182 | \tparam Geometry1 \tparam_geometry | |
183 | \tparam Geometry2 \tparam_geometry | |
184 | \tparam OutputIterator output iterator | |
185 | \tparam Strategy \tparam_strategy_overlay | |
186 | \param geometry1 \param_geometry | |
187 | \param geometry2 \param_geometry | |
188 | \param out \param_out{difference} | |
189 | \param strategy \param_strategy{difference} | |
190 | \return \return_out | |
191 | ||
192 | \qbk{distinguish,with strategy} | |
193 | */ | |
194 | template | |
195 | < | |
196 | typename GeometryOut, | |
197 | typename Geometry1, | |
198 | typename Geometry2, | |
b32b8144 FG |
199 | typename OutputIterator, |
200 | typename Strategy | |
201 | > | |
202 | inline OutputIterator difference_insert(Geometry1 const& geometry1, | |
203 | Geometry2 const& geometry2, | |
b32b8144 FG |
204 | OutputIterator out, |
205 | Strategy const& strategy) | |
206 | { | |
207 | concepts::check<Geometry1 const>(); | |
208 | concepts::check<Geometry2 const>(); | |
20effc67 TL |
209 | //concepts::check<GeometryOut>(); |
210 | geometry::detail::output_geometry_concept_check<GeometryOut>::apply(); | |
b32b8144 | 211 | |
92f5a8d4 TL |
212 | typedef typename geometry::rescale_overlay_policy_type |
213 | < | |
214 | Geometry1, | |
215 | Geometry2, | |
216 | typename Strategy::cs_tag | |
217 | >::type rescale_policy_type; | |
218 | ||
219 | rescale_policy_type robust_policy | |
20effc67 TL |
220 | = geometry::get_rescale_policy<rescale_policy_type>( |
221 | geometry1, geometry2, strategy); | |
92f5a8d4 | 222 | |
20effc67 | 223 | return geometry::detail::difference::call_intersection_insert |
b32b8144 | 224 | < |
20effc67 | 225 | Geometry1, Geometry2, GeometryOut |
b32b8144 FG |
226 | >::apply(geometry1, geometry2, robust_policy, out, strategy); |
227 | } | |
228 | ||
229 | /*! | |
230 | \brief_calc2{difference} | |
231 | \ingroup difference | |
232 | \details \details_calc2{difference_insert, spatial set theoretic difference}. | |
233 | \details_insert{difference} | |
234 | \tparam GeometryOut output geometry type, must be specified | |
235 | \tparam Geometry1 \tparam_geometry | |
236 | \tparam Geometry2 \tparam_geometry | |
237 | \tparam OutputIterator output iterator | |
238 | \param geometry1 \param_geometry | |
239 | \param geometry2 \param_geometry | |
240 | \param out \param_out{difference} | |
241 | \return \return_out | |
242 | ||
243 | \qbk{[include reference/algorithms/difference_insert.qbk]} | |
244 | */ | |
245 | template | |
246 | < | |
247 | typename GeometryOut, | |
248 | typename Geometry1, | |
249 | typename Geometry2, | |
b32b8144 FG |
250 | typename OutputIterator |
251 | > | |
252 | inline OutputIterator difference_insert(Geometry1 const& geometry1, | |
253 | Geometry2 const& geometry2, | |
b32b8144 FG |
254 | OutputIterator out) |
255 | { | |
256 | typedef typename strategy::relate::services::default_strategy | |
257 | < | |
258 | Geometry1, | |
259 | Geometry2 | |
260 | >::type strategy_type; | |
261 | ||
92f5a8d4 TL |
262 | return difference_insert<GeometryOut>(geometry1, geometry2, out, |
263 | strategy_type()); | |
b32b8144 FG |
264 | } |
265 | ||
266 | ||
267 | }} // namespace detail::difference | |
268 | #endif // DOXYGEN_NO_DETAIL | |
269 | ||
270 | ||
271 | namespace resolve_strategy { | |
272 | ||
273 | struct difference | |
274 | { | |
275 | template | |
276 | < | |
277 | typename Geometry1, | |
278 | typename Geometry2, | |
b32b8144 FG |
279 | typename Collection, |
280 | typename Strategy | |
281 | > | |
282 | static inline void apply(Geometry1 const& geometry1, | |
283 | Geometry2 const& geometry2, | |
b32b8144 FG |
284 | Collection & output_collection, |
285 | Strategy const& strategy) | |
286 | { | |
20effc67 TL |
287 | typedef typename geometry::detail::output_geometry_value |
288 | < | |
289 | Collection | |
290 | >::type single_out; | |
b32b8144 | 291 | |
20effc67 | 292 | detail::difference::difference_insert<single_out>( |
92f5a8d4 | 293 | geometry1, geometry2, |
20effc67 | 294 | geometry::detail::output_geometry_back_inserter(output_collection), |
b32b8144 FG |
295 | strategy); |
296 | } | |
297 | ||
298 | template | |
299 | < | |
300 | typename Geometry1, | |
301 | typename Geometry2, | |
b32b8144 FG |
302 | typename Collection |
303 | > | |
304 | static inline void apply(Geometry1 const& geometry1, | |
305 | Geometry2 const& geometry2, | |
b32b8144 FG |
306 | Collection & output_collection, |
307 | default_strategy) | |
308 | { | |
20effc67 TL |
309 | typedef typename strategy::relate::services::default_strategy |
310 | < | |
311 | Geometry1, | |
312 | Geometry2 | |
313 | >::type strategy_type; | |
b32b8144 | 314 | |
20effc67 | 315 | apply(geometry1, geometry2, output_collection, strategy_type()); |
b32b8144 FG |
316 | } |
317 | }; | |
318 | ||
319 | } // resolve_strategy | |
320 | ||
321 | ||
322 | namespace resolve_variant | |
323 | { | |
324 | ||
325 | template <typename Geometry1, typename Geometry2> | |
326 | struct difference | |
327 | { | |
328 | template <typename Collection, typename Strategy> | |
329 | static inline void apply(Geometry1 const& geometry1, | |
330 | Geometry2 const& geometry2, | |
331 | Collection& output_collection, | |
332 | Strategy const& strategy) | |
333 | { | |
b32b8144 | 334 | resolve_strategy::difference::apply(geometry1, geometry2, |
b32b8144 FG |
335 | output_collection, |
336 | strategy); | |
337 | } | |
338 | }; | |
339 | ||
340 | ||
341 | template <BOOST_VARIANT_ENUM_PARAMS(typename T), typename Geometry2> | |
342 | struct difference<variant<BOOST_VARIANT_ENUM_PARAMS(T)>, Geometry2> | |
343 | { | |
344 | template <typename Collection, typename Strategy> | |
345 | struct visitor: static_visitor<> | |
346 | { | |
347 | Geometry2 const& m_geometry2; | |
348 | Collection& m_output_collection; | |
349 | Strategy const& m_strategy; | |
350 | ||
351 | visitor(Geometry2 const& geometry2, | |
352 | Collection& output_collection, | |
353 | Strategy const& strategy) | |
354 | : m_geometry2(geometry2) | |
355 | , m_output_collection(output_collection) | |
356 | , m_strategy(strategy) | |
357 | {} | |
358 | ||
359 | template <typename Geometry1> | |
360 | void operator()(Geometry1 const& geometry1) const | |
361 | { | |
362 | difference | |
363 | < | |
364 | Geometry1, | |
365 | Geometry2 | |
366 | >::apply(geometry1, m_geometry2, m_output_collection, m_strategy); | |
367 | } | |
368 | }; | |
369 | ||
370 | template <typename Collection, typename Strategy> | |
371 | static inline void | |
372 | apply(variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry1, | |
373 | Geometry2 const& geometry2, | |
374 | Collection& output_collection, | |
375 | Strategy const& strategy) | |
376 | { | |
377 | boost::apply_visitor(visitor<Collection, Strategy>(geometry2, | |
378 | output_collection, | |
379 | strategy), | |
380 | geometry1); | |
381 | } | |
382 | }; | |
383 | ||
384 | ||
385 | template <typename Geometry1, BOOST_VARIANT_ENUM_PARAMS(typename T)> | |
386 | struct difference<Geometry1, variant<BOOST_VARIANT_ENUM_PARAMS(T)> > | |
387 | { | |
388 | template <typename Collection, typename Strategy> | |
389 | struct visitor: static_visitor<> | |
390 | { | |
391 | Geometry1 const& m_geometry1; | |
392 | Collection& m_output_collection; | |
393 | Strategy const& m_strategy; | |
394 | ||
395 | visitor(Geometry1 const& geometry1, | |
396 | Collection& output_collection, | |
397 | Strategy const& strategy) | |
398 | : m_geometry1(geometry1) | |
399 | , m_output_collection(output_collection) | |
400 | , m_strategy(strategy) | |
401 | {} | |
402 | ||
403 | template <typename Geometry2> | |
404 | void operator()(Geometry2 const& geometry2) const | |
405 | { | |
406 | difference | |
407 | < | |
408 | Geometry1, | |
409 | Geometry2 | |
410 | >::apply(m_geometry1, geometry2, m_output_collection, m_strategy); | |
411 | } | |
412 | }; | |
413 | ||
414 | template <typename Collection, typename Strategy> | |
415 | static inline void | |
416 | apply(Geometry1 const& geometry1, | |
417 | variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry2, | |
418 | Collection& output_collection, | |
419 | Strategy const& strategy) | |
420 | { | |
421 | boost::apply_visitor(visitor<Collection, Strategy>(geometry1, | |
422 | output_collection, | |
423 | strategy), | |
424 | geometry2); | |
425 | } | |
426 | }; | |
427 | ||
428 | ||
429 | template <BOOST_VARIANT_ENUM_PARAMS(typename T1), BOOST_VARIANT_ENUM_PARAMS(typename T2)> | |
430 | struct difference<variant<BOOST_VARIANT_ENUM_PARAMS(T1)>, variant<BOOST_VARIANT_ENUM_PARAMS(T2)> > | |
431 | { | |
432 | template <typename Collection, typename Strategy> | |
433 | struct visitor: static_visitor<> | |
434 | { | |
435 | Collection& m_output_collection; | |
436 | Strategy const& m_strategy; | |
437 | ||
438 | visitor(Collection& output_collection, Strategy const& strategy) | |
439 | : m_output_collection(output_collection) | |
440 | , m_strategy(strategy) | |
441 | {} | |
442 | ||
443 | template <typename Geometry1, typename Geometry2> | |
444 | void operator()(Geometry1 const& geometry1, | |
445 | Geometry2 const& geometry2) const | |
446 | { | |
447 | difference | |
448 | < | |
449 | Geometry1, | |
450 | Geometry2 | |
451 | >::apply(geometry1, geometry2, m_output_collection, m_strategy); | |
452 | } | |
453 | }; | |
454 | ||
455 | template <typename Collection, typename Strategy> | |
456 | static inline void | |
457 | apply(variant<BOOST_VARIANT_ENUM_PARAMS(T1)> const& geometry1, | |
458 | variant<BOOST_VARIANT_ENUM_PARAMS(T2)> const& geometry2, | |
459 | Collection& output_collection, | |
460 | Strategy const& strategy) | |
461 | { | |
462 | boost::apply_visitor(visitor<Collection, Strategy>(output_collection, | |
463 | strategy), | |
464 | geometry1, geometry2); | |
465 | } | |
466 | }; | |
467 | ||
468 | } // namespace resolve_variant | |
469 | ||
470 | ||
471 | /*! | |
472 | \brief_calc2{difference} | |
473 | \ingroup difference | |
474 | \details \details_calc2{difference, spatial set theoretic difference}. | |
475 | \tparam Geometry1 \tparam_geometry | |
476 | \tparam Geometry2 \tparam_geometry | |
477 | \tparam Collection \tparam_output_collection | |
478 | \tparam Strategy \tparam_strategy{Difference} | |
479 | \param geometry1 \param_geometry | |
480 | \param geometry2 \param_geometry | |
481 | \param output_collection the output collection | |
482 | \param strategy \param_strategy{difference} | |
483 | ||
484 | \qbk{distinguish,with strategy} | |
485 | \qbk{[include reference/algorithms/difference.qbk]} | |
486 | */ | |
487 | template | |
488 | < | |
489 | typename Geometry1, | |
490 | typename Geometry2, | |
491 | typename Collection, | |
492 | typename Strategy | |
493 | > | |
494 | inline void difference(Geometry1 const& geometry1, | |
495 | Geometry2 const& geometry2, | |
496 | Collection& output_collection, | |
497 | Strategy const& strategy) | |
498 | { | |
499 | resolve_variant::difference | |
500 | < | |
501 | Geometry1, | |
502 | Geometry2 | |
503 | >::apply(geometry1, geometry2, output_collection, strategy); | |
504 | } | |
505 | ||
506 | ||
507 | /*! | |
508 | \brief_calc2{difference} | |
509 | \ingroup difference | |
510 | \details \details_calc2{difference, spatial set theoretic difference}. | |
511 | \tparam Geometry1 \tparam_geometry | |
512 | \tparam Geometry2 \tparam_geometry | |
513 | \tparam Collection \tparam_output_collection | |
514 | \param geometry1 \param_geometry | |
515 | \param geometry2 \param_geometry | |
516 | \param output_collection the output collection | |
517 | ||
518 | \qbk{[include reference/algorithms/difference.qbk]} | |
519 | */ | |
520 | template | |
521 | < | |
522 | typename Geometry1, | |
523 | typename Geometry2, | |
524 | typename Collection | |
525 | > | |
526 | inline void difference(Geometry1 const& geometry1, | |
527 | Geometry2 const& geometry2, | |
528 | Collection& output_collection) | |
529 | { | |
530 | resolve_variant::difference | |
531 | < | |
532 | Geometry1, | |
533 | Geometry2 | |
534 | >::apply(geometry1, geometry2, output_collection, default_strategy()); | |
535 | } | |
536 | ||
537 | ||
538 | }} // namespace boost::geometry | |
539 | ||
540 | ||
541 | #endif // BOOST_GEOMETRY_ALGORITHMS_DIFFERENCE_HPP |