ceph/src/boost/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.
   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