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