boost/geometry/algorithms/detail/overlay/intersection_insert.hpp

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