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     >
72     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     >
141     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>
183     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>
198     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 #ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
212 
213     class is_crossing_turn
214     {
215         // return true is the operation is intersection or blocked
216         template <std::size_t Index, typename Turn>
217         static inline bool has_op_i_or_b(Turn const& t)
218         {
219             return
220                 t.operations[Index].operation == overlay::operation_intersection
221                 ||
222                 t.operations[Index].operation == overlay::operation_blocked;
223         }
224 
225         template <typename Turn>
226         static inline bool has_method_crosses(Turn const& t)
227         {
228             return t.method == overlay::method_crosses;
229         }
230 
231         template <typename Turn>
232         static inline bool is_cc(Turn const& t)
233         {
234             return
235                 (t.method == overlay::method_touch_interior
236                  ||
237                  t.method == overlay::method_equal
238                  ||
239                  t.method == overlay::method_collinear)
240                 &&
241                 t.operations[0].operation == t.operations[1].operation
242                 &&
243                 t.operations[0].operation == overlay::operation_continue
244                 ;
245         }
246 
247         template <typename Turn>
248         static inline bool has_i_or_b_ops(Turn const& t)
249         {
250             return
251                 (t.method == overlay::method_touch
252                  ||
253                  t.method == overlay::method_touch_interior
254                  ||
255                  t.method == overlay::method_collinear)
256                 &&
257                 t.operations[1].operation != t.operations[0].operation
258                 &&
259                 (has_op_i_or_b<0>(t) || has_op_i_or_b<1>(t));
260         }
261 
262     public:
263         template <typename Turn>
264         static inline bool apply(Turn const& t)
265         {
266             bool const is_crossing
267                 = has_method_crosses(t) || is_cc(t) || has_i_or_b_ops(t);
268 #if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
269             debug_turn(t, ! is_crossing);
270 #endif
271             return is_crossing;
272         }
273     };
274 
275     struct is_non_crossing_turn
276     {
277         template <typename Turn>
278         static inline bool apply(Turn const& t)
279         {
280             return ! is_crossing_turn::apply(t);
281         }
282     };
283 
284     template <typename Turns>
285     static inline bool no_crossing_turns_or_empty(Turns const& turns)
286     {
287         return detail::check_iterator_range
288             <
289                 is_non_crossing_turn,
290                 true // allow an empty turns range
291             >::apply(boost::begin(turns), boost::end(turns));
292     }
293 
294     template <typename Turns>
295     static inline int inside_or_outside_turn(Turns const& turns)
296     {
297         using namespace overlay;
298         for (typename Turns::const_iterator it = turns.begin();
299                 it != turns.end(); ++it)
300         {
301             operation_type op0 = it->operations[0].operation;
302             operation_type op1 = it->operations[1].operation;
303             if (op0 == operation_intersection && op1 == operation_intersection)
304             {
305                 return 1; // inside
306             }
307             else if (op0 == operation_union && op1 == operation_union)
308             {
309                 return -1; // outside
310             }
311         }
312         return 0;
313     }
314 
315 #else // BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
316 
317     template <typename Linestring, typename Areal, typename Strategy, typename Turns>
318     static inline bool simple_turns_analysis(Linestring const& linestring,
319                                              Areal const& areal,
320                                              Strategy const& strategy,
321                                              Turns const& turns,
322                                              int & inside_value)
323     {
324         using namespace overlay;
325 
326         bool found_continue = false;
327         bool found_intersection = false;
328         bool found_union = false;
329         bool found_front = false;
330 
331         for (typename Turns::const_iterator it = turns.begin();
332                 it != turns.end(); ++it)
333         {
334             method_type const method = it->method;
335             operation_type const op = it->operations[0].operation;
336 
337             if (method == method_crosses)
338             {
339                 return false;
340             }
341             else if (op == operation_intersection)
342             {
343                 found_intersection = true;
344             }
345             else if (op == operation_union)
346             {
347                 found_union = true;
348             }
349             else if (op == operation_continue)
350             {
351                 found_continue = true;
352             }
353 
354             if ((found_intersection || found_continue) && found_union)
355             {
356                 return false;
357             }
358 
359             if (it->operations[0].position == position_front)
360             {
361                 found_front = true;
362             }
363         }
364 
365         if (found_front)
366         {
367             if (found_intersection)
368             {
369                 inside_value = 1; // inside
370             }
371             else if (found_union)
372             {
373                 inside_value = -1; // outside
374             }
375             else // continue and blocked
376             {
377                 inside_value = 0;
378             }
379             return true;
380         }
381 
382         // if needed analyse points of a linestring
383         // NOTE: range_in_geometry checks points of a linestring
384         // until a point inside/outside areal is found
385         // TODO: Could be replaced with point_in_geometry() because found_front is false
386         inside_value = range_in_geometry(linestring, areal, strategy);
387 
388         if ( (found_intersection && inside_value == -1) // going in from outside
389           || (found_continue && inside_value == -1) // going on boundary from outside
390           || (found_union && inside_value == 1) ) // going out from inside
391         {
392             return false;
393         }
394 
395         return true;
396     }
397 
398 #endif // BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
399 
400     template
401     <
402         typename LineString, typename Areal,
403         typename RobustPolicy,
404         typename OutputIterator, typename Strategy
405     >
406     static inline OutputIterator apply(LineString const& linestring, Areal const& areal,
407             RobustPolicy const& robust_policy,
408             OutputIterator out,
409             Strategy const& strategy)
410     {
411         if (boost::size(linestring) == 0)
412         {
413             return out;
414         }
415 
416         typedef detail::overlay::follow
417                 <
418                     LineStringOut,
419                     LineString,
420                     Areal,
421                     OverlayType,
422                     false // do not remove spikes for linear geometries
423                 > follower;
424 
425         typedef typename point_type<LineStringOut>::type point_type;
426 #ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
427         typedef detail::overlay::traversal_turn_info
428             <
429                 point_type,
430                 typename geometry::segment_ratio_type<point_type, RobustPolicy>::type
431             > turn_info;
432 #else
433         typedef detail::overlay::turn_info
434             <
435                 point_type,
436                 typename geometry::segment_ratio_type<point_type, RobustPolicy>::type,
437                 detail::overlay::turn_operation_linear
438                     <
439                         point_type,
440                         typename geometry::segment_ratio_type<point_type, RobustPolicy>::type
441                     >
442             > turn_info;
443 #endif
444         std::deque<turn_info> turns;
445 
446         detail::get_turns::no_interrupt_policy policy;
447 
448 #ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
449 
450         geometry::get_turns
451             <
452                 false,
453                 (OverlayType == overlay_intersection ? ReverseAreal : !ReverseAreal),
454                 detail::overlay::assign_null_policy
455             >(linestring, areal, strategy, robust_policy, turns, policy);
456 
457         if (no_crossing_turns_or_empty(turns))
458         {
459             // No intersection points, it is either
460             // inside (interior + borders)
461             // or outside (exterior + borders)
462 
463             // analyse the turns
464             int inside_value = inside_or_outside_turn(turns);
465             if (inside_value == 0)
466             {
467                 // if needed analyse points of a linestring
468                 // NOTE: range_in_geometry checks points of a linestring
469                 // until a point inside/outside areal is found
470                 inside_value = overlay::range_in_geometry(linestring, areal, strategy);
471             }
472             // add linestring to the output if conditions are met
473             if (inside_value != 0 && follower::included(inside_value))
474             {
475                 LineStringOut copy;
476                 geometry::convert(linestring, copy);
477                 *out++ = copy;
478             }
479             return out;
480         }
481 
482 #else // BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
483 
484         typedef detail::overlay::get_turn_info_linear_areal
485             <
486                 detail::overlay::assign_null_policy
487             > turn_policy;
488 
489         dispatch::get_turns
490             <
491                 typename geometry::tag<LineString>::type,
492                 typename geometry::tag<Areal>::type,
493                 LineString,
494                 Areal,
495                 false,
496                 (OverlayType == overlay_intersection ? ReverseAreal : !ReverseAreal),
497                 turn_policy
498             >::apply(0, linestring, 1, areal,
499                      strategy, robust_policy,
500                      turns, policy);
501 
502         int inside_value = 0;
503         if (simple_turns_analysis(linestring, areal, strategy, turns, inside_value))
504         {
505             // No crossing the boundary, it is either
506             // inside (interior + borders)
507             // or outside (exterior + borders)
508             // or on boundary
509 
510             // add linestring to the output if conditions are met
511             if (follower::included(inside_value))
512             {
513                 LineStringOut copy;
514                 geometry::convert(linestring, copy);
515                 *out++ = copy;
516             }
517 
518             return out;
519         }
520 
521 #endif // BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
522 
523 #if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
524         int index = 0;
525         for(typename std::deque<turn_info>::const_iterator
526             it = turns.begin(); it != turns.end(); ++it)
527         {
528             debug_follow(*it, it->operations[0], index++);
529         }
530 #endif
531 
532         return follower::apply
533                 (
534                     linestring, areal,
535                     geometry::detail::overlay::operation_intersection,
536                     turns, robust_policy, out, strategy
537                 );
538     }
539 };
540 
541 
542 template <typename Turns, typename OutputIterator>
543 inline OutputIterator intersection_output_turn_points(Turns const& turns,
544                                                       OutputIterator out)
545 {
546     for (typename Turns::const_iterator
547             it = turns.begin(); it != turns.end(); ++it)
548     {
549         *out++ = it->point;
550     }
551 
552     return out;
553 }
554 
555 template <typename PointOut>
556 struct intersection_areal_areal_point
557 {
558     template
559     <
560         typename Geometry1, typename Geometry2,
561         typename RobustPolicy,
562         typename OutputIterator,
563         typename Strategy
564     >
565     static inline OutputIterator apply(Geometry1 const& geometry1,
566                                        Geometry2 const& geometry2,
567                                        RobustPolicy const& robust_policy,
568                                        OutputIterator out,
569                                        Strategy const& strategy)
570     {
571         typedef detail::overlay::turn_info
572             <
573                 PointOut,
574                 typename segment_ratio_type<PointOut, RobustPolicy>::type
575             > turn_info;
576         std::vector<turn_info> turns;
577 
578         detail::get_turns::no_interrupt_policy policy;
579 
580         geometry::get_turns
581             <
582                 false, false, detail::overlay::assign_null_policy
583             >(geometry1, geometry2, strategy, robust_policy, turns, policy);
584 
585         return intersection_output_turn_points(turns, out);
586     }
587 };
588 
589 template <typename PointOut>
590 struct intersection_linear_areal_point
591 {
592     template
593     <
594         typename Geometry1, typename Geometry2,
595         typename RobustPolicy,
596         typename OutputIterator,
597         typename Strategy
598     >
599     static inline OutputIterator apply(Geometry1 const& geometry1,
600                                        Geometry2 const& geometry2,
601                                        RobustPolicy const& robust_policy,
602                                        OutputIterator out,
603                                        Strategy const& strategy)
604     {
605         typedef typename geometry::segment_ratio_type
606             <
607                 PointOut, RobustPolicy
608             >::type segment_ratio_type;
609 
610         typedef detail::overlay::turn_info
611             <
612                 PointOut,
613                 segment_ratio_type,
614                 detail::overlay::turn_operation_linear
615                     <
616                         PointOut,
617                         segment_ratio_type
618                     >
619             > turn_info;
620 
621         typedef detail::overlay::get_turn_info_linear_areal
622             <
623                 detail::overlay::assign_null_policy
624             > turn_policy;
625 
626         std::vector<turn_info> turns;
627 
628         detail::get_turns::no_interrupt_policy interrupt_policy;
629 
630         dispatch::get_turns
631             <
632                 typename geometry::tag<Geometry1>::type,
633                 typename geometry::tag<Geometry2>::type,
634                 Geometry1,
635                 Geometry2,
636                 false,
637                 false,
638                 turn_policy
639             >::apply(0, geometry1, 1, geometry2,
640                      strategy, robust_policy,
641                      turns, interrupt_policy);
642 
643         return intersection_output_turn_points(turns, out);
644     }
645 };
646 
647 template <typename PointOut>
648 struct intersection_areal_linear_point
649 {
650     template
651     <
652         typename Geometry1, typename Geometry2,
653         typename RobustPolicy,
654         typename OutputIterator,
655         typename Strategy
656     >
657     static inline OutputIterator apply(Geometry1 const& geometry1,
658                                        Geometry2 const& geometry2,
659                                        RobustPolicy const& robust_policy,
660                                        OutputIterator out,
661                                        Strategy const& strategy)
662     {
663         return intersection_linear_areal_point
664             <
665                 PointOut
666             >::apply(geometry2, geometry1, robust_policy, out, strategy);
667     }
668 };
669 
670 
671 }} // namespace detail::intersection
672 #endif // DOXYGEN_NO_DETAIL
673 
674 
675 
676 #ifndef DOXYGEN_NO_DISPATCH
677 namespace dispatch
678 {
679 
680 template
681 <
682     // real types
683     typename Geometry1,
684     typename Geometry2,
685     typename GeometryOut,
686     overlay_type OverlayType,
687     // orientation
688     bool Reverse1 = detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
689     bool Reverse2 = detail::overlay::do_reverse<geometry::point_order<Geometry2>::value>::value,
690     bool ReverseOut = detail::overlay::do_reverse<geometry::point_order<GeometryOut>::value>::value,
691     // tag dispatching:
692     typename TagIn1 = typename geometry::tag<Geometry1>::type,
693     typename TagIn2 = typename geometry::tag<Geometry2>::type,
694     typename TagOut = typename geometry::tag<GeometryOut>::type,
695     // metafunction finetuning helpers:
696     typename CastedTagIn1 = typename geometry::tag_cast<TagIn1, areal_tag, linear_tag, pointlike_tag>::type,
697     typename CastedTagIn2 = typename geometry::tag_cast<TagIn2, areal_tag, linear_tag, pointlike_tag>::type,
698     typename CastedTagOut = typename geometry::tag_cast<TagOut, areal_tag, linear_tag, pointlike_tag>::type
699 >
700 struct intersection_insert
701 {
702     BOOST_MPL_ASSERT_MSG
703         (
704             false, NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPES_OR_ORIENTATIONS
705             , (types<Geometry1, Geometry2, GeometryOut>)
706         );
707 };
708 
709 
710 template
711 <
712     typename Geometry1, typename Geometry2,
713     typename GeometryOut,
714     overlay_type OverlayType,
715     bool Reverse1, bool Reverse2, bool ReverseOut,
716     typename TagIn1, typename TagIn2, typename TagOut
717 >
718 struct intersection_insert
719     <
720         Geometry1, Geometry2,
721         GeometryOut,
722         OverlayType,
723         Reverse1, Reverse2, ReverseOut,
724         TagIn1, TagIn2, TagOut,
725         areal_tag, areal_tag, areal_tag
726     > : detail::overlay::overlay
727         <Geometry1, Geometry2, Reverse1, Reverse2, ReverseOut, GeometryOut, OverlayType>
728 {};
729 
730 
731 // Any areal type with box:
732 template
733 <
734     typename Geometry, typename Box,
735     typename GeometryOut,
736     overlay_type OverlayType,
737     bool Reverse1, bool Reverse2, bool ReverseOut,
738     typename TagIn, typename TagOut
739 >
740 struct intersection_insert
741     <
742         Geometry, Box,
743         GeometryOut,
744         OverlayType,
745         Reverse1, Reverse2, ReverseOut,
746         TagIn, box_tag, TagOut,
747         areal_tag, areal_tag, areal_tag
748     > : detail::overlay::overlay
749         <Geometry, Box, Reverse1, Reverse2, ReverseOut, GeometryOut, OverlayType>
750 {};
751 
752 
753 template
754 <
755     typename Segment1, typename Segment2,
756     typename GeometryOut,
757     overlay_type OverlayType,
758     bool Reverse1, bool Reverse2, bool ReverseOut
759 >
760 struct intersection_insert
761     <
762         Segment1, Segment2,
763         GeometryOut,
764         OverlayType,
765         Reverse1, Reverse2, ReverseOut,
766         segment_tag, segment_tag, point_tag,
767         linear_tag, linear_tag, pointlike_tag
768     > : detail::intersection::intersection_segment_segment_point<GeometryOut>
769 {};
770 
771 
772 template
773 <
774     typename Linestring1, typename Linestring2,
775     typename GeometryOut,
776     overlay_type OverlayType,
777     bool Reverse1, bool Reverse2, bool ReverseOut
778 >
779 struct intersection_insert
780     <
781         Linestring1, Linestring2,
782         GeometryOut,
783         OverlayType,
784         Reverse1, Reverse2, ReverseOut,
785         linestring_tag, linestring_tag, point_tag,
786         linear_tag, linear_tag, pointlike_tag
787     > : detail::intersection::intersection_linestring_linestring_point<GeometryOut>
788 {};
789 
790 
791 template
792 <
793     typename Linestring, typename Box,
794     typename GeometryOut,
795     bool Reverse1, bool Reverse2, bool ReverseOut
796 >
797 struct intersection_insert
798     <
799         Linestring, Box,
800         GeometryOut,
801         overlay_intersection,
802         Reverse1, Reverse2, ReverseOut,
803         linestring_tag, box_tag, linestring_tag,
804         linear_tag, areal_tag, linear_tag
805     >
806 {
807     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
808     static inline OutputIterator apply(Linestring const& linestring,
809             Box const& box,
810             RobustPolicy const& robust_policy,
811             OutputIterator out, Strategy const& )
812     {
813         typedef typename point_type<GeometryOut>::type point_type;
814         strategy::intersection::liang_barsky<Box, point_type> lb_strategy;
815         return detail::intersection::clip_range_with_box
816             <GeometryOut>(box, linestring, robust_policy, out, lb_strategy);
817     }
818 };
819 
820 
821 template
822 <
823     typename Linestring, typename Polygon,
824     typename GeometryOut,
825     overlay_type OverlayType,
826     bool ReverseLinestring, bool ReversePolygon, bool ReverseOut
827 >
828 struct intersection_insert
829     <
830         Linestring, Polygon,
831         GeometryOut,
832         OverlayType,
833         ReverseLinestring, ReversePolygon, ReverseOut,
834         linestring_tag, polygon_tag, linestring_tag,
835         linear_tag, areal_tag, linear_tag
836     > : detail::intersection::intersection_of_linestring_with_areal
837             <
838                 ReversePolygon,
839                 GeometryOut,
840                 OverlayType
841             >
842 {};
843 
844 
845 template
846 <
847     typename Linestring, typename Ring,
848     typename GeometryOut,
849     overlay_type OverlayType,
850     bool ReverseLinestring, bool ReverseRing, bool ReverseOut
851 >
852 struct intersection_insert
853     <
854         Linestring, Ring,
855         GeometryOut,
856         OverlayType,
857         ReverseLinestring, ReverseRing, ReverseOut,
858         linestring_tag, ring_tag, linestring_tag,
859         linear_tag, areal_tag, linear_tag
860     > : detail::intersection::intersection_of_linestring_with_areal
861             <
862                 ReverseRing,
863                 GeometryOut,
864                 OverlayType
865             >
866 {};
867 
868 template
869 <
870     typename Segment, typename Box,
871     typename GeometryOut,
872     overlay_type OverlayType,
873     bool Reverse1, bool Reverse2, bool ReverseOut
874 >
875 struct intersection_insert
876     <
877         Segment, Box,
878         GeometryOut,
879         OverlayType,
880         Reverse1, Reverse2, ReverseOut,
881         segment_tag, box_tag, linestring_tag,
882         linear_tag, areal_tag, linear_tag
883     >
884 {
885     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
886     static inline OutputIterator apply(Segment const& segment,
887             Box const& box,
888             RobustPolicy const& robust_policy,
889             OutputIterator out, Strategy const& )
890     {
891         geometry::segment_view<Segment> range(segment);
892 
893         typedef typename point_type<GeometryOut>::type point_type;
894         strategy::intersection::liang_barsky<Box, point_type> lb_strategy;
895         return detail::intersection::clip_range_with_box
896             <GeometryOut>(box, range, robust_policy, out, lb_strategy);
897     }
898 };
899 
900 template
901 <
902     typename Geometry1, typename Geometry2,
903     typename PointOut,
904     overlay_type OverlayType,
905     bool Reverse1, bool Reverse2, bool ReverseOut,
906     typename Tag1, typename Tag2
907 >
908 struct intersection_insert
909     <
910         Geometry1, Geometry2,
911         PointOut,
912         OverlayType,
913         Reverse1, Reverse2, ReverseOut,
914         Tag1, Tag2, point_tag,
915         areal_tag, areal_tag, pointlike_tag
916     >
917     : public detail::intersection::intersection_areal_areal_point
918         <
919             PointOut
920         >
921 {};
922 
923 template
924 <
925     typename Geometry1, typename Geometry2,
926     typename PointOut,
927     overlay_type OverlayType,
928     bool Reverse1, bool Reverse2, bool ReverseOut,
929     typename Tag1, typename Tag2
930 >
931 struct intersection_insert
932     <
933         Geometry1, Geometry2,
934         PointOut,
935         OverlayType,
936         Reverse1, Reverse2, ReverseOut,
937         Tag1, Tag2, point_tag,
938         linear_tag, areal_tag, pointlike_tag
939     >
940     : public detail::intersection::intersection_linear_areal_point
941         <
942             PointOut
943         >
944 {};
945 
946 template
947 <
948     typename Geometry1, typename Geometry2,
949     typename PointOut,
950     overlay_type OverlayType,
951     bool Reverse1, bool Reverse2, bool ReverseOut,
952     typename Tag1, typename Tag2
953 >
954 struct intersection_insert
955     <
956         Geometry1, Geometry2,
957         PointOut,
958         OverlayType,
959         Reverse1, Reverse2, ReverseOut,
960         Tag1, Tag2, point_tag,
961         areal_tag, linear_tag, pointlike_tag
962     >
963     : public detail::intersection::intersection_areal_linear_point
964         <
965             PointOut
966         >
967 {};
968 
969 template
970 <
971     typename Geometry1, typename Geometry2, typename GeometryOut,
972     overlay_type OverlayType,
973     bool Reverse1, bool Reverse2, bool ReverseOut
974 >
975 struct intersection_insert_reversed
976 {
977     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
978     static inline OutputIterator apply(Geometry1 const& g1,
979                 Geometry2 const& g2,
980                 RobustPolicy const& robust_policy,
981                 OutputIterator out,
982                 Strategy const& strategy)
983     {
984         return intersection_insert
985             <
986                 Geometry2, Geometry1, GeometryOut,
987                 OverlayType,
988                 Reverse2, Reverse1, ReverseOut
989             >::apply(g2, g1, robust_policy, out, strategy);
990     }
991 };
992 
993 
994 // dispatch for intersection(areal, areal, linear)
995 template
996 <
997     typename Geometry1, typename Geometry2,
998     typename LinestringOut,
999     bool Reverse1, bool Reverse2, bool ReverseOut,
1000     typename Tag1, typename Tag2
1001 >
1002 struct intersection_insert
1003     <
1004         Geometry1, Geometry2,
1005         LinestringOut,
1006         overlay_intersection,
1007         Reverse1, Reverse2, ReverseOut,
1008         Tag1, Tag2, linestring_tag,
1009         areal_tag, areal_tag, linear_tag
1010     >
1011 {
1012     template
1013     <
1014         typename RobustPolicy, typename OutputIterator, typename Strategy
1015     >
1016     static inline OutputIterator apply(Geometry1 const& geometry1,
1017                                        Geometry2 const& geometry2,
1018                                        RobustPolicy const& robust_policy,
1019                                        OutputIterator oit,
1020                                        Strategy const& strategy)
1021     {
1022         detail::boundary_view<Geometry1 const> view1(geometry1);
1023         detail::boundary_view<Geometry2 const> view2(geometry2);
1024 
1025         return detail::overlay::linear_linear_linestring
1026             <
1027                 detail::boundary_view<Geometry1 const>,
1028                 detail::boundary_view<Geometry2 const>,
1029                 LinestringOut,
1030                 overlay_intersection
1031             >::apply(view1, view2, robust_policy, oit, strategy);
1032     }
1033 };
1034 
1035 // dispatch for difference/intersection of linear geometries
1036 template
1037 <
1038     typename Linear1, typename Linear2, typename LineStringOut,
1039     overlay_type OverlayType,
1040     bool Reverse1, bool Reverse2, bool ReverseOut,
1041     typename TagIn1, typename TagIn2
1042 >
1043 struct intersection_insert
1044     <
1045         Linear1, Linear2, LineStringOut, OverlayType,
1046         Reverse1, Reverse2, ReverseOut,
1047         TagIn1, TagIn2, linestring_tag,
1048         linear_tag, linear_tag, linear_tag
1049     > : detail::overlay::linear_linear_linestring
1050         <
1051             Linear1, Linear2, LineStringOut, OverlayType
1052         >
1053 {};
1054 
1055 
1056 // dispatch for difference/intersection of point-like geometries
1057 
1058 template
1059 <
1060     typename Point1, typename Point2, typename PointOut,
1061     overlay_type OverlayType,
1062     bool Reverse1, bool Reverse2, bool ReverseOut
1063 >
1064 struct intersection_insert
1065     <
1066         Point1, Point2, PointOut, OverlayType,
1067         Reverse1, Reverse2, ReverseOut,
1068         point_tag, point_tag, point_tag,
1069         pointlike_tag, pointlike_tag, pointlike_tag
1070     > : detail::overlay::point_point_point
1071         <
1072             Point1, Point2, PointOut, OverlayType
1073         >
1074 {};
1075 
1076 
1077 template
1078 <
1079     typename MultiPoint, typename Point, typename PointOut,
1080     overlay_type OverlayType,
1081     bool Reverse1, bool Reverse2, bool ReverseOut
1082 >
1083 struct intersection_insert
1084     <
1085         MultiPoint, Point, PointOut, OverlayType,
1086         Reverse1, Reverse2, ReverseOut,
1087         multi_point_tag, point_tag, point_tag,
1088         pointlike_tag, pointlike_tag, pointlike_tag
1089     > : detail::overlay::multipoint_point_point
1090         <
1091             MultiPoint, Point, PointOut, OverlayType
1092         >
1093 {};
1094 
1095 
1096 template
1097 <
1098     typename Point, typename MultiPoint, typename PointOut,
1099     overlay_type OverlayType,
1100     bool Reverse1, bool Reverse2, bool ReverseOut
1101 >
1102 struct intersection_insert
1103     <
1104         Point, MultiPoint, PointOut, OverlayType,
1105         Reverse1, Reverse2, ReverseOut,
1106         point_tag, multi_point_tag, point_tag,
1107         pointlike_tag, pointlike_tag, pointlike_tag
1108     > : detail::overlay::point_multipoint_point
1109         <
1110             Point, MultiPoint, PointOut, OverlayType
1111         >
1112 {};
1113 
1114 
1115 template
1116 <
1117     typename MultiPoint1, typename MultiPoint2, typename PointOut,
1118     overlay_type OverlayType,
1119     bool Reverse1, bool Reverse2, bool ReverseOut
1120 >
1121 struct intersection_insert
1122     <
1123         MultiPoint1, MultiPoint2, PointOut, OverlayType,
1124         Reverse1, Reverse2, ReverseOut,
1125         multi_point_tag, multi_point_tag, point_tag,
1126         pointlike_tag, pointlike_tag, pointlike_tag
1127     > : detail::overlay::multipoint_multipoint_point
1128         <
1129             MultiPoint1, MultiPoint2, PointOut, OverlayType
1130         >
1131 {};
1132 
1133 
1134 // dispatch for difference/intersection of pointlike-linear geometries
1135 template
1136 <
1137     typename Point, typename Linear, typename PointOut,
1138     overlay_type OverlayType,
1139     bool Reverse1, bool Reverse2, bool ReverseOut,
1140     typename Tag
1141 >
1142 struct intersection_insert
1143     <
1144         Point, Linear, PointOut, OverlayType,
1145         Reverse1, Reverse2, ReverseOut,
1146         point_tag, Tag, point_tag,
1147         pointlike_tag, linear_tag, pointlike_tag
1148     > : detail_dispatch::overlay::pointlike_linear_point
1149         <
1150             Point, Linear, PointOut, OverlayType,
1151             point_tag, typename tag_cast<Tag, segment_tag, linear_tag>::type
1152         >
1153 {};
1154 
1155 
1156 template
1157 <
1158     typename MultiPoint, typename Linear, typename PointOut,
1159     overlay_type OverlayType,
1160     bool Reverse1, bool Reverse2, bool ReverseOut,
1161     typename Tag
1162 >
1163 struct intersection_insert
1164     <
1165         MultiPoint, Linear, PointOut, OverlayType,
1166         Reverse1, Reverse2, ReverseOut,
1167         multi_point_tag, Tag, point_tag,
1168         pointlike_tag, linear_tag, pointlike_tag
1169     > : detail_dispatch::overlay::pointlike_linear_point
1170         <
1171             MultiPoint, Linear, PointOut, OverlayType,
1172             multi_point_tag,
1173             typename tag_cast<Tag, segment_tag, linear_tag>::type
1174         >
1175 {};
1176 
1177 
1178 template
1179 <
1180     typename Linestring, typename MultiPoint, typename PointOut,
1181     bool Reverse1, bool Reverse2, bool ReverseOut
1182 >
1183 struct intersection_insert
1184     <
1185         Linestring, MultiPoint, PointOut, overlay_intersection,
1186         Reverse1, Reverse2, ReverseOut,
1187         linestring_tag, multi_point_tag, point_tag,
1188         linear_tag, pointlike_tag, pointlike_tag
1189     >
1190 {
1191     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
1192     static inline OutputIterator apply(Linestring const& linestring,
1193                                        MultiPoint const& multipoint,
1194                                        RobustPolicy const& robust_policy,
1195                                        OutputIterator out,
1196                                        Strategy const& strategy)
1197     {
1198         return detail_dispatch::overlay::pointlike_linear_point
1199             <
1200                 MultiPoint, Linestring, PointOut, overlay_intersection,
1201                 multi_point_tag, linear_tag
1202             >::apply(multipoint, linestring, robust_policy, out, strategy);
1203     }
1204 };
1205 
1206 
1207 } // namespace dispatch
1208 #endif // DOXYGEN_NO_DISPATCH
1209 
1210 
1211 #ifndef DOXYGEN_NO_DETAIL
1212 namespace detail { namespace intersection
1213 {
1214 
1215 
1216 template
1217 <
1218     typename GeometryOut,
1219     bool ReverseSecond,
1220     overlay_type OverlayType,
1221     typename Geometry1, typename Geometry2,
1222     typename RobustPolicy,
1223     typename OutputIterator,
1224     typename Strategy
1225 >
1226 inline OutputIterator insert(Geometry1 const& geometry1,
1227             Geometry2 const& geometry2,
1228             RobustPolicy robust_policy,
1229             OutputIterator out,
1230             Strategy const& strategy)
1231 {
1232     return boost::mpl::if_c
1233     <
1234         geometry::reverse_dispatch<Geometry1, Geometry2>::type::value,
1235         geometry::dispatch::intersection_insert_reversed
1236         <
1237             Geometry1, Geometry2,
1238             GeometryOut,
1239             OverlayType,
1240             overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
1241             overlay::do_reverse<geometry::point_order<Geometry2>::value, ReverseSecond>::value,
1242             overlay::do_reverse<geometry::point_order<GeometryOut>::value>::value
1243         >,
1244         geometry::dispatch::intersection_insert
1245         <
1246             Geometry1, Geometry2,
1247             GeometryOut,
1248             OverlayType,
1249             geometry::detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
1250             geometry::detail::overlay::do_reverse<geometry::point_order<Geometry2>::value, ReverseSecond>::value
1251         >
1252     >::type::apply(geometry1, geometry2, robust_policy, out, strategy);
1253 }
1254 
1255 
1256 /*!
1257 \brief \brief_calc2{intersection} \brief_strategy
1258 \ingroup intersection
1259 \details \details_calc2{intersection_insert, spatial set theoretic intersection}
1260     \brief_strategy. \details_insert{intersection}
1261 \tparam GeometryOut \tparam_geometry{\p_l_or_c}
1262 \tparam Geometry1 \tparam_geometry
1263 \tparam Geometry2 \tparam_geometry
1264 \tparam OutputIterator \tparam_out{\p_l_or_c}
1265 \tparam Strategy \tparam_strategy_overlay
1266 \param geometry1 \param_geometry
1267 \param geometry2 \param_geometry
1268 \param out \param_out{intersection}
1269 \param strategy \param_strategy{intersection}
1270 \return \return_out
1271 
1272 \qbk{distinguish,with strategy}
1273 \qbk{[include reference/algorithms/intersection.qbk]}
1274 */
1275 template
1276 <
1277     typename GeometryOut,
1278     typename Geometry1,
1279     typename Geometry2,
1280     typename OutputIterator,
1281     typename Strategy
1282 >
1283 inline OutputIterator intersection_insert(Geometry1 const& geometry1,
1284             Geometry2 const& geometry2,
1285             OutputIterator out,
1286             Strategy const& strategy)
1287 {
1288     concepts::check<Geometry1 const>();
1289     concepts::check<Geometry2 const>();
1290 
1291     typedef typename geometry::rescale_policy_type
1292         <
1293             typename geometry::point_type<Geometry1>::type // TODO from both
1294         >::type rescale_policy_type;
1295 
1296     rescale_policy_type robust_policy
1297             = geometry::get_rescale_policy<rescale_policy_type>(geometry1, geometry2);
1298 
1299     return detail::intersection::insert
1300         <
1301             GeometryOut, false, overlay_intersection
1302         >(geometry1, geometry2, robust_policy, out, strategy);
1303 }
1304 
1305 
1306 /*!
1307 \brief \brief_calc2{intersection}
1308 \ingroup intersection
1309 \details \details_calc2{intersection_insert, spatial set theoretic intersection}.
1310     \details_insert{intersection}
1311 \tparam GeometryOut \tparam_geometry{\p_l_or_c}
1312 \tparam Geometry1 \tparam_geometry
1313 \tparam Geometry2 \tparam_geometry
1314 \tparam OutputIterator \tparam_out{\p_l_or_c}
1315 \param geometry1 \param_geometry
1316 \param geometry2 \param_geometry
1317 \param out \param_out{intersection}
1318 \return \return_out
1319 
1320 \qbk{[include reference/algorithms/intersection.qbk]}
1321 */
1322 template
1323 <
1324     typename GeometryOut,
1325     typename Geometry1,
1326     typename Geometry2,
1327     typename OutputIterator
1328 >
1329 inline OutputIterator intersection_insert(Geometry1 const& geometry1,
1330             Geometry2 const& geometry2,
1331             OutputIterator out)
1332 {
1333     concepts::check<Geometry1 const>();
1334     concepts::check<Geometry2 const>();
1335 
1336     typedef typename strategy::intersection::services::default_strategy
1337         <
1338             typename cs_tag<GeometryOut>::type
1339         >::type strategy_type;
1340 
1341     return intersection_insert<GeometryOut>(geometry1, geometry2, out,
1342                                             strategy_type());
1343 }
1344 
1345 }} // namespace detail::intersection
1346 #endif // DOXYGEN_NO_DETAIL
1347 
1348 
1349 
1350 }} // namespace boost::geometry
1351 
1352 
1353 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INTERSECTION_INSERT_HPP
1354