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