]> git.proxmox.com Git - ceph.git/blame - ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp
projects / ceph.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
bump version to 12.2.2-pve1
[ceph.git] / ceph / src / boost / libs / geometry / include / boost / geometry / algorithms / detail / overlay / intersection_insert.hpp
CommitLineData
7c673cae
FG		 1// Boost.Geometry (aka GGL, Generic Geometry Library)
2
3// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
4
5// This file was modified by Oracle on 2014, 2015.
6// Modifications copyright (c) 2014-2015 Oracle and/or its affiliates.
7
8// Contributed and/or modified by Menelaos Karavelas, 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_DETAIL_OVERLAY_INTERSECTION_INSERT_HPP
15#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INTERSECTION_INSERT_HPP
16
17
18#include <cstddef>
19
20#include <boost/mpl/if.hpp>
21#include <boost/mpl/assert.hpp>
22#include <boost/range/metafunctions.hpp>
23
24
25#include <boost/geometry/core/is_areal.hpp>
26#include <boost/geometry/core/point_order.hpp>
27#include <boost/geometry/core/reverse_dispatch.hpp>
28#include <boost/geometry/geometries/concepts/check.hpp>
29#include <boost/geometry/algorithms/convert.hpp>
30#include <boost/geometry/algorithms/detail/point_on_border.hpp>
31#include <boost/geometry/algorithms/detail/overlay/clip_linestring.hpp>
32#include <boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp>
33#include <boost/geometry/algorithms/detail/overlay/overlay.hpp>
34#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
35#include <boost/geometry/algorithms/detail/overlay/follow.hpp>
36
37#include <boost/geometry/policies/robustness/robust_point_type.hpp>
38#include <boost/geometry/policies/robustness/segment_ratio_type.hpp>
39#include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
40
41#include <boost/geometry/views/segment_view.hpp>
42#include <boost/geometry/views/detail/boundary_view.hpp>
43
44#include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
45#include <boost/geometry/algorithms/detail/overlay/linear_linear.hpp>
46#include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp>
47#include <boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp>
48
49#if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
50#include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
51#include <boost/geometry/io/wkt/wkt.hpp>
52#endif
53
54namespace boost { namespace geometry
55{
56
57#ifndef DOXYGEN_NO_DETAIL
58namespace detail { namespace intersection
59{
60
61template <typename PointOut>
62struct intersection_segment_segment_point
63{
64 template
65 <
66 typename Segment1, typename Segment2,
67 typename RobustPolicy,
68 typename OutputIterator, typename Strategy
69 >
70 static inline OutputIterator apply(Segment1 const& segment1,
71 Segment2 const& segment2,
72 RobustPolicy const& robust_policy,
73 OutputIterator out,
74 Strategy const& )
75 {
76 typedef typename point_type<PointOut>::type point_type;
77
78 typedef typename geometry::robust_point_type
79 <
80 typename geometry::point_type<Segment1>::type,
81 RobustPolicy
82 >::type robust_point_type;
83
84 // TODO: rescale segment -> robust points
85 robust_point_type pi_rob, pj_rob, qi_rob, qj_rob;
86 {
87 // Workaround:
88 point_type pi, pj, qi, qj;
89 assign_point_from_index<0>(segment1, pi);
90 assign_point_from_index<1>(segment1, pj);
91 assign_point_from_index<0>(segment2, qi);
92 assign_point_from_index<1>(segment2, qj);
93 geometry::recalculate(pi_rob, pi, robust_policy);
94 geometry::recalculate(pj_rob, pj, robust_policy);
95 geometry::recalculate(qi_rob, qi, robust_policy);
96 geometry::recalculate(qj_rob, qj, robust_policy);
97 }
98
99 // Get the intersection point (or two points)
100 typedef segment_intersection_points
101 <
102 point_type,
103 typename segment_ratio_type
104 <
105 point_type, RobustPolicy
106 >::type
107 > intersection_return_type;
108
109 typedef strategy::intersection::relate_cartesian_segments
110 <
111 policies::relate::segments_intersection_points
112 <
113 intersection_return_type
114 >
115 > policy;
116
117 intersection_return_type is = policy::apply(segment1, segment2,
118 robust_policy, pi_rob, pj_rob, qi_rob, qj_rob);
119
120 for (std::size_t i = 0; i < is.count; i++)
121 {
122 PointOut p;
123 geometry::convert(is.intersections[i], p);
124 *out++ = p;
125 }
126 return out;
127 }
128};
129
130template <typename PointOut>
131struct intersection_linestring_linestring_point
132{
133 template
134 <
135 typename Linestring1, typename Linestring2,
136 typename RobustPolicy,
137 typename OutputIterator, typename Strategy
138 >
139 static inline OutputIterator apply(Linestring1 const& linestring1,
140 Linestring2 const& linestring2,
141 RobustPolicy const& robust_policy,
142 OutputIterator out,
143 Strategy const& )
144 {
145 typedef typename point_type<PointOut>::type point_type;
146
147 typedef detail::overlay::turn_info
148 <
149 point_type,
150 typename segment_ratio_type<point_type, RobustPolicy>::type
151 > turn_info;
152 std::deque<turn_info> turns;
153
154 geometry::get_intersection_points(linestring1, linestring2, robust_policy, turns);
155
156 for (typename boost::range_iterator<std::deque<turn_info> const>::type
157 it = boost::begin(turns); it != boost::end(turns); ++it)
158 {
159 PointOut p;
160 geometry::convert(it->point, p);
161 *out++ = p;
162 }
163 return out;
164 }
165};
166
167/*!
168\brief Version of linestring with an areal feature (polygon or multipolygon)
169*/
170template
171<
172 bool ReverseAreal,
173 typename LineStringOut,
174 overlay_type OverlayType
175>
176struct intersection_of_linestring_with_areal
177{
178#if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
179 template <typename Turn, typename Operation>
180 static inline void debug_follow(Turn const& turn, Operation op,
181 int index)
182 {
183 std::cout << index
184 << " at " << op.seg_id
185 << " meth: " << method_char(turn.method)
186 << " op: " << operation_char(op.operation)
187 << " vis: " << visited_char(op.visited)
188 << " of: " << operation_char(turn.operations[0].operation)
189 << operation_char(turn.operations[1].operation)
190 << " " << geometry::wkt(turn.point)
191 << std::endl;
192 }
193
194 template <typename Turn>
195 static inline void debug_turn(Turn const& t, bool non_crossing)
196 {
197 std::cout << "checking turn @"
198 << geometry::wkt(t.point)
199 << "; " << method_char(t.method)
200 << ":" << operation_char(t.operations[0].operation)
201 << "/" << operation_char(t.operations[1].operation)
202 << "; non-crossing? "
203 << std::boolalpha << non_crossing << std::noboolalpha
204 << std::endl;
205 }
206#endif
207
208 class is_crossing_turn
209 {
210 // return true is the operation is intersection or blocked
211 template <std::size_t Index, typename Turn>
212 static inline bool has_op_i_or_b(Turn const& t)
213 {
214 return
215 t.operations[Index].operation == overlay::operation_intersection
216 ||
217 t.operations[Index].operation == overlay::operation_blocked;
218 }
219
220 template <typename Turn>
221 static inline bool has_method_crosses(Turn const& t)
222 {
223 return t.method == overlay::method_crosses;
224 }
225
226 template <typename Turn>
227 static inline bool is_cc(Turn const& t)
228 {
229 return
230 (t.method == overlay::method_touch_interior
231 ||
232 t.method == overlay::method_equal
233 ||
234 t.method == overlay::method_collinear)
235 &&
236 t.operations[0].operation == t.operations[1].operation
237 &&
238 t.operations[0].operation == overlay::operation_continue
239 ;
240 }
241
242 template <typename Turn>
243 static inline bool has_i_or_b_ops(Turn const& t)
244 {
245 return
246 (t.method == overlay::method_touch
247 ||
248 t.method == overlay::method_touch_interior
249 ||
250 t.method == overlay::method_collinear)
251 &&
252 t.operations[1].operation != t.operations[0].operation
253 &&
254 (has_op_i_or_b<0>(t) || has_op_i_or_b<1>(t));
255 }
256
257 public:
258 template <typename Turn>
259 static inline bool apply(Turn const& t)
260 {
261 bool const is_crossing
262 = has_method_crosses(t) || is_cc(t) || has_i_or_b_ops(t);
263#if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
264 debug_turn(t, ! is_crossing);
265#endif
266 return is_crossing;
267 }
268 };
269
270 struct is_non_crossing_turn
271 {
272 template <typename Turn>
273 static inline bool apply(Turn const& t)
274 {
275 return ! is_crossing_turn::apply(t);
276 }
277 };
278
279 template <typename Turns>
280 static inline bool no_crossing_turns_or_empty(Turns const& turns)
281 {
282 return detail::check_iterator_range
283 <
284 is_non_crossing_turn,
285 true // allow an empty turns range
286 >::apply(boost::begin(turns), boost::end(turns));
287 }
288
289 template
290 <
291 typename LineString, typename Areal,
292 typename RobustPolicy,
293 typename OutputIterator, typename Strategy
294 >
295 static inline OutputIterator apply(LineString const& linestring, Areal const& areal,
296 RobustPolicy const& robust_policy,
297 OutputIterator out,
298 Strategy const& )
299 {
300 if (boost::size(linestring) == 0)
301 {
302 return out;
303 }
304
305 typedef detail::overlay::follow
306 <
307 LineStringOut,
308 LineString,
309 Areal,
310 OverlayType,
311 false // do not remove spikes for linear geometries
312 > follower;
313
314 typedef typename point_type<LineStringOut>::type point_type;
315 typedef detail::overlay::traversal_turn_info
316 <
317 point_type,
318 typename geometry::segment_ratio_type<point_type, RobustPolicy>::type
319 > turn_info;
320 std::deque<turn_info> turns;
321
322 detail::get_turns::no_interrupt_policy policy;
323 geometry::get_turns
324 <
325 false,
326 (OverlayType == overlay_intersection ? ReverseAreal : !ReverseAreal),
327 detail::overlay::assign_null_policy
328 >(linestring, areal, robust_policy, turns, policy);
329
330 if (no_crossing_turns_or_empty(turns))
331 {
332 // No intersection points, it is either completely
333 // inside (interior + borders)
334 // or completely outside
335
336 // Use border point (on a segment) to check this
337 // (because turn points might skip some cases)
338 point_type border_point;
339 if (! geometry::point_on_border(border_point, linestring, true))
340 {
341 return out;
342 }
343
344 if (follower::included(border_point, areal, robust_policy))
345 {
346 LineStringOut copy;
347 geometry::convert(linestring, copy);
348 *out++ = copy;
349 }
350 return out;
351 }
352
353#if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
354 int index = 0;
355 for(typename std::deque<turn_info>::const_iterator
356 it = turns.begin(); it != turns.end(); ++it)
357 {
358 debug_follow(*it, it->operations[0], index++);
359 }
360#endif
361
362 return follower::apply
363 (
364 linestring, areal,
365 geometry::detail::overlay::operation_intersection,
366 turns, robust_policy, out
367 );
368 }
369};
370
371
372}} // namespace detail::intersection
373#endif // DOXYGEN_NO_DETAIL
374
375
376
377#ifndef DOXYGEN_NO_DISPATCH
378namespace dispatch
379{
380
381template
382<
383 // real types
384 typename Geometry1,
385 typename Geometry2,
386 typename GeometryOut,
387 overlay_type OverlayType,
388 // orientation
389 bool Reverse1 = detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
390 bool Reverse2 = detail::overlay::do_reverse<geometry::point_order<Geometry2>::value>::value,
391 bool ReverseOut = detail::overlay::do_reverse<geometry::point_order<GeometryOut>::value>::value,
392 // tag dispatching:
393 typename TagIn1 = typename geometry::tag<Geometry1>::type,
394 typename TagIn2 = typename geometry::tag<Geometry2>::type,
395 typename TagOut = typename geometry::tag<GeometryOut>::type,
396 // metafunction finetuning helpers:
397 bool Areal1 = geometry::is_areal<Geometry1>::value,
398 bool Areal2 = geometry::is_areal<Geometry2>::value,
399 bool ArealOut = geometry::is_areal<GeometryOut>::value
400>
401struct intersection_insert
402{
403 BOOST_MPL_ASSERT_MSG
404 (
405 false, NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPES_OR_ORIENTATIONS
406 , (types<Geometry1, Geometry2, GeometryOut>)
407 );
408};
409
410
411template
412<
413 typename Geometry1, typename Geometry2,
414 typename GeometryOut,
415 overlay_type OverlayType,
416 bool Reverse1, bool Reverse2, bool ReverseOut,
417 typename TagIn1, typename TagIn2, typename TagOut
418>
419struct intersection_insert
420 <
421 Geometry1, Geometry2,
422 GeometryOut,
423 OverlayType,
424 Reverse1, Reverse2, ReverseOut,
425 TagIn1, TagIn2, TagOut,
426 true, true, true
427 > : detail::overlay::overlay
428 <Geometry1, Geometry2, Reverse1, Reverse2, ReverseOut, GeometryOut, OverlayType>
429{};
430
431
432// Any areal type with box:
433template
434<
435 typename Geometry, typename Box,
436 typename GeometryOut,
437 overlay_type OverlayType,
438 bool Reverse1, bool Reverse2, bool ReverseOut,
439 typename TagIn, typename TagOut
440>
441struct intersection_insert
442 <
443 Geometry, Box,
444 GeometryOut,
445 OverlayType,
446 Reverse1, Reverse2, ReverseOut,
447 TagIn, box_tag, TagOut,
448 true, true, true
449 > : detail::overlay::overlay
450 <Geometry, Box, Reverse1, Reverse2, ReverseOut, GeometryOut, OverlayType>
451{};
452
453
454template
455<
456 typename Segment1, typename Segment2,
457 typename GeometryOut,
458 overlay_type OverlayType,
459 bool Reverse1, bool Reverse2, bool ReverseOut
460>
461struct intersection_insert
462 <
463 Segment1, Segment2,
464 GeometryOut,
465 OverlayType,
466 Reverse1, Reverse2, ReverseOut,
467 segment_tag, segment_tag, point_tag,
468 false, false, false
469 > : detail::intersection::intersection_segment_segment_point<GeometryOut>
470{};
471
472
473template
474<
475 typename Linestring1, typename Linestring2,
476 typename GeometryOut,
477 overlay_type OverlayType,
478 bool Reverse1, bool Reverse2, bool ReverseOut
479>
480struct intersection_insert
481 <
482 Linestring1, Linestring2,
483 GeometryOut,
484 OverlayType,
485 Reverse1, Reverse2, ReverseOut,
486 linestring_tag, linestring_tag, point_tag,
487 false, false, false
488 > : detail::intersection::intersection_linestring_linestring_point<GeometryOut>
489{};
490
491
492template
493<
494 typename Linestring, typename Box,
495 typename GeometryOut,
496 bool Reverse1, bool Reverse2, bool ReverseOut
497>
498struct intersection_insert
499 <
500 Linestring, Box,
501 GeometryOut,
502 overlay_intersection,
503 Reverse1, Reverse2, ReverseOut,
504 linestring_tag, box_tag, linestring_tag,
505 false, true, false
506 >
507{
508 template <typename RobustPolicy, typename OutputIterator, typename Strategy>
509 static inline OutputIterator apply(Linestring const& linestring,
510 Box const& box,
511 RobustPolicy const& robust_policy,
512 OutputIterator out, Strategy const& )
513 {
514 typedef typename point_type<GeometryOut>::type point_type;
515 strategy::intersection::liang_barsky<Box, point_type> lb_strategy;
516 return detail::intersection::clip_range_with_box
517 <GeometryOut>(box, linestring, robust_policy, out, lb_strategy);
518 }
519};
520
521
522template
523<
524 typename Linestring, typename Polygon,
525 typename GeometryOut,
526 overlay_type OverlayType,
527 bool ReverseLinestring, bool ReversePolygon, bool ReverseOut
528>
529struct intersection_insert
530 <
531 Linestring, Polygon,
532 GeometryOut,
533 OverlayType,
534 ReverseLinestring, ReversePolygon, ReverseOut,
535 linestring_tag, polygon_tag, linestring_tag,
536 false, true, false
537 > : detail::intersection::intersection_of_linestring_with_areal
538 <
539 ReversePolygon,
540 GeometryOut,
541 OverlayType
542 >
543{};
544
545
546template
547<
548 typename Linestring, typename Ring,
549 typename GeometryOut,
550 overlay_type OverlayType,
551 bool ReverseLinestring, bool ReverseRing, bool ReverseOut
552>
553struct intersection_insert
554 <
555 Linestring, Ring,
556 GeometryOut,
557 OverlayType,
558 ReverseLinestring, ReverseRing, ReverseOut,
559 linestring_tag, ring_tag, linestring_tag,
560 false, true, false
561 > : detail::intersection::intersection_of_linestring_with_areal
562 <
563 ReverseRing,
564 GeometryOut,
565 OverlayType
566 >
567{};
568
569template
570<
571 typename Segment, typename Box,
572 typename GeometryOut,
573 overlay_type OverlayType,
574 bool Reverse1, bool Reverse2, bool ReverseOut
575>
576struct intersection_insert
577 <
578 Segment, Box,
579 GeometryOut,
580 OverlayType,
581 Reverse1, Reverse2, ReverseOut,
582 segment_tag, box_tag, linestring_tag,
583 false, true, false
584 >
585{
586 template <typename RobustPolicy, typename OutputIterator, typename Strategy>
587 static inline OutputIterator apply(Segment const& segment,
588 Box const& box,
589 RobustPolicy const& robust_policy,
590 OutputIterator out, Strategy const& )
591 {
592 geometry::segment_view<Segment> range(segment);
593
594 typedef typename point_type<GeometryOut>::type point_type;
595 strategy::intersection::liang_barsky<Box, point_type> lb_strategy;
596 return detail::intersection::clip_range_with_box
597 <GeometryOut>(box, range, robust_policy, out, lb_strategy);
598 }
599};
600
601template
602<
603 typename Geometry1, typename Geometry2,
604 typename PointOut,
605 overlay_type OverlayType,
606 bool Reverse1, bool Reverse2, bool ReverseOut,
607 typename Tag1, typename Tag2,
608 bool Areal1, bool Areal2
609>
610struct intersection_insert
611 <
612 Geometry1, Geometry2,
613 PointOut,
614 OverlayType,
615 Reverse1, Reverse2, ReverseOut,
616 Tag1, Tag2, point_tag,
617 Areal1, Areal2, false
618 >
619{
620 template <typename RobustPolicy, typename OutputIterator, typename Strategy>
621 static inline OutputIterator apply(Geometry1 const& geometry1,
622 Geometry2 const& geometry2,
623 RobustPolicy const& robust_policy,
624 OutputIterator out, Strategy const& )
625 {
626
627 typedef detail::overlay::turn_info
628 <
629 PointOut,
630 typename segment_ratio_type<PointOut, RobustPolicy>::type
631 > turn_info;
632 std::vector<turn_info> turns;
633
634 detail::get_turns::no_interrupt_policy policy;
635 geometry::get_turns
636 <
637 false, false, detail::overlay::assign_null_policy
638 >(geometry1, geometry2, robust_policy, turns, policy);
639 for (typename std::vector<turn_info>::const_iterator it
640 = turns.begin(); it != turns.end(); ++it)
641 {
642 *out++ = it->point;
643 }
644
645 return out;
646 }
647};
648
649
650template
651<
652 typename Geometry1, typename Geometry2, typename GeometryOut,
653 overlay_type OverlayType,
654 bool Reverse1, bool Reverse2, bool ReverseOut
655>
656struct intersection_insert_reversed
657{
658 template <typename RobustPolicy, typename OutputIterator, typename Strategy>
659 static inline OutputIterator apply(Geometry1 const& g1,
660 Geometry2 const& g2,
661 RobustPolicy const& robust_policy,
662 OutputIterator out,
663 Strategy const& strategy)
664 {
665 return intersection_insert
666 <
667 Geometry2, Geometry1, GeometryOut,
668 OverlayType,
669 Reverse2, Reverse1, ReverseOut
670 >::apply(g2, g1, robust_policy, out, strategy);
671 }
672};
673
674
675// dispatch for intersection(areal, areal, linear)
676template
677<
678 typename Geometry1, typename Geometry2,
679 typename LinestringOut,
680 bool Reverse1, bool Reverse2, bool ReverseOut,
681 typename Tag1, typename Tag2
682>
683struct intersection_insert
684 <
685 Geometry1, Geometry2,
686 LinestringOut,
687 overlay_intersection,
688 Reverse1, Reverse2, ReverseOut,
689 Tag1, Tag2, linestring_tag,
690 true, true, false
691 >
692{
693 template
694 <
695 typename RobustPolicy, typename OutputIterator, typename Strategy
696 >
697 static inline OutputIterator apply(Geometry1 const& geometry1,
698 Geometry2 const& geometry2,
699 RobustPolicy const& robust_policy,
700 OutputIterator oit,
701 Strategy const& strategy)
702 {
703 detail::boundary_view<Geometry1 const> view1(geometry1);
704 detail::boundary_view<Geometry2 const> view2(geometry2);
705
706 return detail::overlay::linear_linear_linestring
707 <
708 detail::boundary_view<Geometry1 const>,
709 detail::boundary_view<Geometry2 const>,
710 LinestringOut,
711 overlay_intersection
712 >::apply(view1, view2, robust_policy, oit, strategy);
713 }
714};
715
716// dispatch for non-areal geometries
717template
718<
719 typename Geometry1, typename Geometry2, typename GeometryOut,
720 overlay_type OverlayType,
721 bool Reverse1, bool Reverse2, bool ReverseOut,
722 typename TagIn1, typename TagIn2
723>
724struct intersection_insert
725 <
726 Geometry1, Geometry2, GeometryOut,
727 OverlayType,
728 Reverse1, Reverse2, ReverseOut,
729 TagIn1, TagIn2, linestring_tag,
730 false, false, false
731 > : intersection_insert
732 <
733 Geometry1, Geometry2, GeometryOut,
734 OverlayType,
735 Reverse1, Reverse2, ReverseOut,
736 typename tag_cast<TagIn1, pointlike_tag, linear_tag>::type,
737 typename tag_cast<TagIn2, pointlike_tag, linear_tag>::type,
738 linestring_tag,
739 false, false, false
740 >
741{};
742
743
744// dispatch for difference/intersection of linear geometries
745template
746<
747 typename Linear1, typename Linear2, typename LineStringOut,
748 overlay_type OverlayType,
749 bool Reverse1, bool Reverse2, bool ReverseOut
750>
751struct intersection_insert
752 <
753 Linear1, Linear2, LineStringOut, OverlayType,
754 Reverse1, Reverse2, ReverseOut,
755 linear_tag, linear_tag, linestring_tag,
756 false, false, false
757 > : detail::overlay::linear_linear_linestring
758 <
759 Linear1, Linear2, LineStringOut, OverlayType
760 >
761{};
762
763
764// dispatch for difference/intersection of point-like geometries
765
766template
767<
768 typename Point1, typename Point2, typename PointOut,
769 overlay_type OverlayType,
770 bool Reverse1, bool Reverse2, bool ReverseOut
771>
772struct intersection_insert
773 <
774 Point1, Point2, PointOut, OverlayType,
775 Reverse1, Reverse2, ReverseOut,
776 point_tag, point_tag, point_tag,
777 false, false, false
778 > : detail::overlay::point_point_point
779 <
780 Point1, Point2, PointOut, OverlayType
781 >
782{};
783
784
785template
786<
787 typename MultiPoint, typename Point, typename PointOut,
788 overlay_type OverlayType,
789 bool Reverse1, bool Reverse2, bool ReverseOut
790>
791struct intersection_insert
792 <
793 MultiPoint, Point, PointOut, OverlayType,
794 Reverse1, Reverse2, ReverseOut,
795 multi_point_tag, point_tag, point_tag,
796 false, false, false
797 > : detail::overlay::multipoint_point_point
798 <
799 MultiPoint, Point, PointOut, OverlayType
800 >
801{};
802
803
804template
805<
806 typename Point, typename MultiPoint, typename PointOut,
807 overlay_type OverlayType,
808 bool Reverse1, bool Reverse2, bool ReverseOut
809>
810struct intersection_insert
811 <
812 Point, MultiPoint, PointOut, OverlayType,
813 Reverse1, Reverse2, ReverseOut,
814 point_tag, multi_point_tag, point_tag,
815 false, false, false
816 > : detail::overlay::point_multipoint_point
817 <
818 Point, MultiPoint, PointOut, OverlayType
819 >
820{};
821
822
823template
824<
825 typename MultiPoint1, typename MultiPoint2, typename PointOut,
826 overlay_type OverlayType,
827 bool Reverse1, bool Reverse2, bool ReverseOut
828>
829struct intersection_insert
830 <
831 MultiPoint1, MultiPoint2, PointOut, OverlayType,
832 Reverse1, Reverse2, ReverseOut,
833 multi_point_tag, multi_point_tag, point_tag,
834 false, false, false
835 > : detail::overlay::multipoint_multipoint_point
836 <
837 MultiPoint1, MultiPoint2, PointOut, OverlayType
838 >
839{};
840
841
842// dispatch for difference/intersection of pointlike-linear geometries
843template
844<
845 typename Point, typename Linear, typename PointOut,
846 overlay_type OverlayType,
847 bool Reverse1, bool Reverse2, bool ReverseOut,
848 typename Tag
849>
850struct intersection_insert
851 <
852 Point, Linear, PointOut, OverlayType,
853 Reverse1, Reverse2, ReverseOut,
854 point_tag, Tag, point_tag,
855 false, false, false
856 > : detail_dispatch::overlay::pointlike_linear_point
857 <
858 Point, Linear, PointOut, OverlayType,
859 point_tag, typename tag_cast<Tag, segment_tag, linear_tag>::type
860 >
861{};
862
863
864template
865<
866 typename MultiPoint, typename Linear, typename PointOut,
867 overlay_type OverlayType,
868 bool Reverse1, bool Reverse2, bool ReverseOut,
869 typename Tag
870>
871struct intersection_insert
872 <
873 MultiPoint, Linear, PointOut, OverlayType,
874 Reverse1, Reverse2, ReverseOut,
875 multi_point_tag, Tag, point_tag,
876 false, false, false
877 > : detail_dispatch::overlay::pointlike_linear_point
878 <
879 MultiPoint, Linear, PointOut, OverlayType,
880 multi_point_tag,
881 typename tag_cast<Tag, segment_tag, linear_tag>::type
882 >
883{};
884
885
886template
887<
888 typename Linestring, typename MultiPoint, typename PointOut,
889 bool Reverse1, bool Reverse2, bool ReverseOut
890>
891struct intersection_insert
892 <
893 Linestring, MultiPoint, PointOut, overlay_intersection,
894 Reverse1, Reverse2, ReverseOut,
895 linestring_tag, multi_point_tag, point_tag,
896 false, false, false
897 >
898{
899 template <typename RobustPolicy, typename OutputIterator, typename Strategy>
900 static inline OutputIterator apply(Linestring const& linestring,
901 MultiPoint const& multipoint,
902 RobustPolicy const& robust_policy,
903 OutputIterator out,
904 Strategy const& strategy)
905 {
906 return detail_dispatch::overlay::pointlike_linear_point
907 <
908 MultiPoint, Linestring, PointOut, overlay_intersection,
909 multi_point_tag, linear_tag
910 >::apply(multipoint, linestring, robust_policy, out, strategy);
911 }
912};
913
914
915} // namespace dispatch
916#endif // DOXYGEN_NO_DISPATCH
917
918
919#ifndef DOXYGEN_NO_DETAIL
920namespace detail { namespace intersection
921{
922
923
924template
925<
926 typename GeometryOut,
927 bool ReverseSecond,
928 overlay_type OverlayType,
929 typename Geometry1, typename Geometry2,
930 typename RobustPolicy,
931 typename OutputIterator,
932 typename Strategy
933>
934inline OutputIterator insert(Geometry1 const& geometry1,
935 Geometry2 const& geometry2,
936 RobustPolicy robust_policy,
937 OutputIterator out,
938 Strategy const& strategy)
939{
940 return boost::mpl::if_c
941 <
942 geometry::reverse_dispatch<Geometry1, Geometry2>::type::value,
943 geometry::dispatch::intersection_insert_reversed
944 <
945 Geometry1, Geometry2,
946 GeometryOut,
947 OverlayType,
948 overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
949 overlay::do_reverse<geometry::point_order<Geometry2>::value, ReverseSecond>::value,
950 overlay::do_reverse<geometry::point_order<GeometryOut>::value>::value
951 >,
952 geometry::dispatch::intersection_insert
953 <
954 Geometry1, Geometry2,
955 GeometryOut,
956 OverlayType,
957 geometry::detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
958 geometry::detail::overlay::do_reverse<geometry::point_order<Geometry2>::value, ReverseSecond>::value
959 >
960 >::type::apply(geometry1, geometry2, robust_policy, out, strategy);
961}
962
963
964/*!
965\brief \brief_calc2{intersection} \brief_strategy
966\ingroup intersection
967\details \details_calc2{intersection_insert, spatial set theoretic intersection}
968 \brief_strategy. \details_insert{intersection}
969\tparam GeometryOut \tparam_geometry{\p_l_or_c}
970\tparam Geometry1 \tparam_geometry
971\tparam Geometry2 \tparam_geometry
972\tparam OutputIterator \tparam_out{\p_l_or_c}
973\tparam Strategy \tparam_strategy_overlay
974\param geometry1 \param_geometry
975\param geometry2 \param_geometry
976\param out \param_out{intersection}
977\param strategy \param_strategy{intersection}
978\return \return_out
979
980\qbk{distinguish,with strategy}
981\qbk{[include reference/algorithms/intersection.qbk]}
982*/
983template
984<
985 typename GeometryOut,
986 typename Geometry1,
987 typename Geometry2,
988 typename OutputIterator,
989 typename Strategy
990>
991inline OutputIterator intersection_insert(Geometry1 const& geometry1,
992 Geometry2 const& geometry2,
993 OutputIterator out,
994 Strategy const& strategy)
995{
996 concepts::check<Geometry1 const>();
997 concepts::check<Geometry2 const>();
998
999 typedef typename Strategy::rescale_policy_type rescale_policy_type;
1000 rescale_policy_type robust_policy
1001 = geometry::get_rescale_policy<rescale_policy_type>(geometry1, geometry2);
1002
1003 return detail::intersection::insert
1004 <
1005 GeometryOut, false, overlay_intersection
1006 >(geometry1, geometry2, robust_policy, out, strategy);
1007}
1008
1009
1010/*!
1011\brief \brief_calc2{intersection}
1012\ingroup intersection
1013\details \details_calc2{intersection_insert, spatial set theoretic intersection}.
1014 \details_insert{intersection}
1015\tparam GeometryOut \tparam_geometry{\p_l_or_c}
1016\tparam Geometry1 \tparam_geometry
1017\tparam Geometry2 \tparam_geometry
1018\tparam OutputIterator \tparam_out{\p_l_or_c}
1019\param geometry1 \param_geometry
1020\param geometry2 \param_geometry
1021\param out \param_out{intersection}
1022\return \return_out
1023
1024\qbk{[include reference/algorithms/intersection.qbk]}
1025*/
1026template
1027<
1028 typename GeometryOut,
1029 typename Geometry1,
1030 typename Geometry2,
1031 typename OutputIterator
1032>
1033inline OutputIterator intersection_insert(Geometry1 const& geometry1,
1034 Geometry2 const& geometry2,
1035 OutputIterator out)
1036{
1037 concepts::check<Geometry1 const>();
1038 concepts::check<Geometry2 const>();
1039
1040 typedef typename geometry::rescale_policy_type
1041 <
1042 typename geometry::point_type<Geometry1>::type // TODO from both
1043 >::type rescale_policy_type;
1044
1045 typedef intersection_strategies
1046 <
1047 typename cs_tag<GeometryOut>::type,
1048 Geometry1,
1049 Geometry2,
1050 typename geometry::point_type<GeometryOut>::type,
1051 rescale_policy_type
1052 > strategy;
1053
1054 return intersection_insert<GeometryOut>(geometry1, geometry2, out,
1055 strategy());
1056}
1057
1058}} // namespace detail::intersection
1059#endif // DOXYGEN_NO_DETAIL
1060
1061
1062
1063}} // namespace boost::geometry
1064
1065
1066#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INTERSECTION_INSERT_HPP
Ceph