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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2014-2017 Adam Wulkiewicz, Lodz, Poland.
   5
   6 // This file was modified by Oracle on 2014, 2016, 2017, 2018.
   7 // Modifications copyright (c) 2014-2018 Oracle and/or its affiliates.
   8
   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_GET_TURNS_HPP
  16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
  17
  18
  19 #include <cstddef>
  20 #include <map>
  21
  22 #include <boost/array.hpp>
  23 #include <boost/concept_check.hpp>
  24 #include <boost/core/ignore_unused.hpp>
  25 #include <boost/mpl/if.hpp>
  26 #include <boost/mpl/vector_c.hpp>
  27 #include <boost/range.hpp>
  28
  29 #include <boost/geometry/core/access.hpp>
  30 #include <boost/geometry/core/assert.hpp>
  31 #include <boost/geometry/core/coordinate_dimension.hpp>
  32 #include <boost/geometry/core/exterior_ring.hpp>
  33 #include <boost/geometry/core/interior_rings.hpp>
  34 #include <boost/geometry/core/reverse_dispatch.hpp>
  35 #include <boost/geometry/core/ring_type.hpp>
  36 #include <boost/geometry/core/tags.hpp>
  37
  38 #include <boost/geometry/geometries/concepts/check.hpp>
  39
  40 #include <boost/geometry/util/math.hpp>
  41 #include <boost/geometry/views/closeable_view.hpp>
  42 #include <boost/geometry/views/reversible_view.hpp>
  43 #include <boost/geometry/views/detail/range_type.hpp>
  44
  45 #include <boost/geometry/geometries/box.hpp>
  46 #include <boost/geometry/geometries/segment.hpp>
  47
  48 #include <boost/geometry/iterators/ever_circling_iterator.hpp>
  49
  50 #include <boost/geometry/strategies/intersection_strategies.hpp>
  51 #include <boost/geometry/strategies/intersection_result.hpp>
  52
  53 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
  54 #include <boost/geometry/algorithms/detail/disjoint/point_point.hpp>
  55
  56 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
  57 #include <boost/geometry/algorithms/detail/partition.hpp>
  58 #include <boost/geometry/algorithms/detail/recalculate.hpp>
  59 #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp>
  60
  61 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
  62 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp>
  63 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp>
  64 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
  65
  66 #include <boost/geometry/algorithms/detail/sections/range_by_section.hpp>
  67 #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
  68 #include <boost/geometry/algorithms/detail/sections/section_functions.hpp>
  69
  70 #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
  71 #  include <sstream>
  72 #  include <boost/geometry/io/dsv/write.hpp>
  73 #endif
  74
  75
  76 namespace boost { namespace geometry
  77 {
  78
  79 // Silence warning C4127: conditional expression is constant
  80 #if defined(_MSC_VER)
  81 #pragma warning(push)
  82 #pragma warning(disable : 4127)
  83 #endif
  84
  85
  86 #ifndef DOXYGEN_NO_DETAIL
  87 namespace detail { namespace get_turns
  88 {
  89
  90
  91 struct no_interrupt_policy
  92 {
  93     static bool const enabled = false;
  94
  95     // variable required by self_get_turn_points::get_turns
  96     static bool const has_intersections = false;
  97
  98     template <typename Range>
  99     static inline bool apply(Range const&)
 100     {
 101         return false;
 102     }
 103 };
 104
 105 template
 106 <
 107     bool IsAreal,
 108     typename Section,
 109     typename Point,
 110     typename CircularIterator,
 111     typename IntersectionStrategy,
 112     typename RobustPolicy
 113 >
 114 struct unique_sub_range_from_section
 115 {
 116     typedef Point point_type;
 117
 118     unique_sub_range_from_section(Section const& section, signed_size_type index,
 119                           CircularIterator circular_iterator,
 120                           Point const& previous, Point const& current,
 121                           RobustPolicy const& robust_policy)
 122       : m_section(section)
 123       , m_index(index)
 124       , m_previous_point(previous)
 125       , m_current_point(current)
 126       , m_circular_iterator(circular_iterator)
 127       , m_point_retrieved(false)
 128       , m_robust_policy(robust_policy)
 129     {
 130     }
 131
 132     inline bool is_first_segment() const
 133     {
 134         return !IsAreal && m_section.is_non_duplicate_first && m_index == m_section.begin_index;
 135     }
 136     inline bool is_last_segment() const
 137     {
 138         return size() == 2u;
 139     }
 140
 141     inline std::size_t size() const
 142     {
 143         return IsAreal ? 3
 144             : m_section.is_non_duplicate_last && m_index + 1 >= m_section.end_index ? 2 : 3;
 145     }
 146
 147     inline Point const& at(std::size_t index) const
 148     {
 149         BOOST_GEOMETRY_ASSERT(index < size());
 150         switch (index)
 151         {
 152             case 0 : return m_previous_point;
 153             case 1 : return m_current_point;
 154             case 2 : return get_next_point();
 155             default : return m_previous_point;
 156         }
 157     }
 158
 159 private :
 160     inline Point const& get_next_point() const
 161     {
 162         if (! m_point_retrieved)
 163         {
 164             advance_to_non_duplicate_next(m_current_point, m_circular_iterator);
 165             m_point = *m_circular_iterator;
 166             m_point_retrieved = true;
 167         }
 168         return m_point;
 169     }
 170
 171     inline void advance_to_non_duplicate_next(Point const& current, CircularIterator& circular_iterator) const
 172     {
 173         typedef typename IntersectionStrategy::point_in_point_strategy_type disjoint_strategy_type;
 174         typedef typename robust_point_type<Point, RobustPolicy>::type robust_point_type;
 175         robust_point_type current_robust_point;
 176         robust_point_type next_robust_point;
 177         geometry::recalculate(current_robust_point, current, m_robust_policy);
 178         geometry::recalculate(next_robust_point, *circular_iterator, m_robust_policy);
 179
 180         // To see where the next segments bend to, in case of touch/intersections
 181         // on end points, we need (in case of degenerate/duplicate points) an extra
 182         // iterator which moves to the REAL next point, so non duplicate.
 183         // This needs an extra comparison (disjoint).
 184         // (Note that within sections, non duplicate points are already asserted,
 185         //   by the sectionalize process).
 186
 187         // So advance to the "non duplicate next"
 188         // (the check is defensive, to avoid endless loops)
 189         std::size_t check = 0;
 190         while(! detail::disjoint::disjoint_point_point
 191                 (
 192                     current_robust_point, next_robust_point,
 193                     disjoint_strategy_type()
 194                 )
 195             && check++ < m_section.range_count)
 196         {
 197             circular_iterator++;
 198             geometry::recalculate(next_robust_point, *circular_iterator, m_robust_policy);
 199         }
 200     }
 201
 202     Section const& m_section;
 203     signed_size_type m_index;
 204     Point const& m_previous_point;
 205     Point const& m_current_point;
 206     mutable CircularIterator m_circular_iterator;
 207     mutable Point m_point;
 208     mutable bool m_point_retrieved;
 209     RobustPolicy m_robust_policy;
 210 };
 211
 212 template
 213 <
 214     typename Geometry1, typename Geometry2,
 215     bool Reverse1, bool Reverse2,
 216     typename Section1, typename Section2,
 217     typename TurnPolicy
 218 >
 219 class get_turns_in_sections
 220 {
 221     typedef typename closeable_view
 222         <
 223             typename range_type<Geometry1>::type const,
 224             closure<Geometry1>::value
 225         >::type cview_type1;
 226     typedef typename closeable_view
 227         <
 228             typename range_type<Geometry2>::type const,
 229             closure<Geometry2>::value
 230         >::type cview_type2;
 231
 232     typedef typename reversible_view
 233         <
 234             cview_type1 const,
 235             Reverse1 ? iterate_reverse : iterate_forward
 236         >::type view_type1;
 237     typedef typename reversible_view
 238         <
 239             cview_type2 const,
 240             Reverse2 ? iterate_reverse : iterate_forward
 241         >::type view_type2;
 242
 243     typedef typename boost::range_iterator
 244         <
 245             view_type1 const
 246         >::type range1_iterator;
 247
 248     typedef typename boost::range_iterator
 249         <
 250             view_type2 const
 251         >::type range2_iterator;
 252
 253     typedef ever_circling_iterator<range1_iterator> circular1_iterator;
 254     typedef ever_circling_iterator<range2_iterator> circular2_iterator;
 255
 256     template <typename Geometry, typename Section>
 257     static inline bool adjacent(Section const& section,
 258             signed_size_type index1, signed_size_type index2)
 259     {
 260         // About n-2:
 261         //   (square: range_count=5, indices 0,1,2,3
 262         //    -> 0-3 are adjacent, don't check on intersections)
 263         // Also tested for open polygons, and/or duplicates
 264         // About first condition: will be optimized by compiler (static)
 265         // It checks if it is areal (box, ring, (multi)polygon)
 266         signed_size_type const n = static_cast<signed_size_type>(section.range_count);
 267
 268         boost::ignore_unused(n, index1, index2);
 269
 270         return boost::is_same
 271                     <
 272                         typename tag_cast
 273                             <
 274                                 typename geometry::tag<Geometry>::type,
 275                                 areal_tag
 276                             >::type,
 277                         areal_tag
 278                     >::value
 279                && index1 == 0
 280                && index2 >= n - 2
 281                 ;
 282     }
 283
 284
 285 public :
 286     // Returns true if terminated, false if interrupted
 287     template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
 288     static inline bool apply(
 289             int source_id1, Geometry1 const& geometry1, Section1 const& sec1,
 290             int source_id2, Geometry2 const& geometry2, Section2 const& sec2,
 291             bool skip_larger, bool skip_adjacent,
 292             IntersectionStrategy const& intersection_strategy,
 293             RobustPolicy const& robust_policy,
 294             Turns& turns,
 295             InterruptPolicy& interrupt_policy)
 296     {
 297         boost::ignore_unused(interrupt_policy);
 298
 299         static bool const areal1 = boost::is_same
 300             <
 301                 typename tag_cast<typename tag<Geometry1>::type, areal_tag>::type,
 302                 areal_tag
 303             >::type::value;
 304         static bool const areal2 = boost::is_same
 305             <
 306                 typename tag_cast<typename tag<Geometry2>::type, areal_tag>::type,
 307                 areal_tag
 308             >::type::value;
 309
 310
 311         if ((sec1.duplicate && (sec1.count + 1) < sec1.range_count)
 312            || (sec2.duplicate && (sec2.count + 1) < sec2.range_count))
 313         {
 314             // Skip sections containig only duplicates.
 315             // They are still important (can indicate non-disjointness)
 316             // but they will be found processing adjacent sections.
 317             // Do NOT skip if they are the ONLY section
 318             return true;
 319         }
 320
 321         cview_type1 cview1(range_by_section(geometry1, sec1));
 322         cview_type2 cview2(range_by_section(geometry2, sec2));
 323         view_type1 view1(cview1);
 324         view_type2 view2(cview2);
 325
 326         range1_iterator begin_range_1 = boost::begin(view1);
 327         range1_iterator end_range_1 = boost::end(view1);
 328
 329         range2_iterator begin_range_2 = boost::begin(view2);
 330         range2_iterator end_range_2 = boost::end(view2);
 331
 332         int const dir1 = sec1.directions[0];
 333         int const dir2 = sec2.directions[0];
 334         signed_size_type index1 = sec1.begin_index;
 335         signed_size_type ndi1 = sec1.non_duplicate_index;
 336
 337         range1_iterator prev1, it1, end1;
 338
 339         get_start_point_iterator(sec1, view1, prev1, it1, end1,
 340                     index1, ndi1, dir1, sec2.bounding_box, robust_policy);
 341
 342         // We need a circular iterator because it might run through the closing point.
 343         // One circle is actually enough but this one is just convenient.
 344         ever_circling_iterator<range1_iterator> next1(begin_range_1, end_range_1, it1, true);
 345         next1++;
 346
 347         // Walk through section and stop if we exceed the other box
 348         // section 2:    [--------------]
 349         // section 1: |----|---|---|---|---|
 350         for (prev1 = it1++, next1++;
 351             it1 != end1 && ! detail::section::exceeding<0>(dir1, *prev1, sec1.bounding_box, sec2.bounding_box, robust_policy);
 352             ++prev1, ++it1, ++index1, ++next1, ++ndi1)
 353         {
 354             unique_sub_range_from_section
 355                 <
 356                     areal1, Section1, point1_type, circular1_iterator,
 357                     IntersectionStrategy, RobustPolicy
 358                 > unique_sub_range1(sec1, index1,
 359                                     circular1_iterator(begin_range_1, end_range_1, next1, true),
 360                                     *prev1, *it1,
 361                                     robust_policy);
 362
 363             signed_size_type index2 = sec2.begin_index;
 364             signed_size_type ndi2 = sec2.non_duplicate_index;
 365
 366             range2_iterator prev2, it2, end2;
 367
 368             get_start_point_iterator(sec2, view2, prev2, it2, end2,
 369                         index2, ndi2, dir2, sec1.bounding_box, robust_policy);
 370             ever_circling_iterator<range2_iterator> next2(begin_range_2, end_range_2, it2, true);
 371             next2++;
 372
 373             for (prev2 = it2++, next2++;
 374                 it2 != end2 && ! detail::section::exceeding<0>(dir2, *prev2, sec2.bounding_box, sec1.bounding_box, robust_policy);
 375                 ++prev2, ++it2, ++index2, ++next2, ++ndi2)
 376             {
 377                 bool skip = false;
 378
 379                 if (source_id1 == source_id2
 380                         && sec1.ring_id.multi_index == sec2.ring_id.multi_index
 381                         && sec1.ring_id.ring_index == sec2.ring_id.ring_index)
 382                 {
 383                     // Sources and rings are the same
 384
 385                     if (skip_larger && index1 >= index2)
 386                     {
 387                         // Skip to avoid getting all intersections twice
 388                         skip = true;
 389                     }
 390                     else if (skip_adjacent)
 391                     {
 392                         // In some cases (dissolve, has_self_intersections)
 393                         // neighbouring segments should be checked
 394                         // (for example to detect spikes properly)
 395
 396                         // skip if it is a neighbouring segment.
 397                         // (including, for areas, first-last segment
 398                         //  and two segments with one or more degenerate/duplicate
 399                         //  (zero-length) segments in between)
 400                         skip = ndi2 == ndi1 + 1
 401                             || adjacent<Geometry1>(sec1, index1, index2);
 402                     }
 403                 }
 404
 405                 if (! skip)
 406                 {
 407                     unique_sub_range_from_section
 408                         <
 409                             areal2, Section2, point2_type, circular2_iterator,
 410                             IntersectionStrategy, RobustPolicy
 411                         > unique_sub_range2(sec2, index2,
 412                                             circular2_iterator(begin_range_2, end_range_2, next2),
 413                                             *prev2, *it2,
 414                                             robust_policy);
 415
 416                     typedef typename boost::range_value<Turns>::type turn_info;
 417
 418                     turn_info ti;
 419                     ti.operations[0].seg_id
 420                         = segment_identifier(source_id1, sec1.ring_id.multi_index,
 421                                              sec1.ring_id.ring_index, index1);
 422                     ti.operations[1].seg_id
 423                         = segment_identifier(source_id2, sec2.ring_id.multi_index,
 424                                              sec2.ring_id.ring_index, index2);
 425
 426                     std::size_t const size_before = boost::size(turns);
 427
 428                     TurnPolicy::apply(unique_sub_range1, unique_sub_range2,
 429                                       ti, intersection_strategy, robust_policy,
 430                                       std::back_inserter(turns));
 431
 432                     if (InterruptPolicy::enabled)
 433                     {
 434                         if (interrupt_policy.apply(
 435                                 std::make_pair(range::pos(turns, size_before),
 436                                                boost::end(turns))))
 437                         {
 438                             return false;
 439                         }
 440                     }
 441                 }
 442             }
 443         }
 444         return true;
 445     }
 446
 447
 448 private :
 449     typedef typename geometry::point_type<Geometry1>::type point1_type;
 450     typedef typename geometry::point_type<Geometry2>::type point2_type;
 451     typedef typename model::referring_segment<point1_type const> segment1_type;
 452     typedef typename model::referring_segment<point2_type const> segment2_type;
 453
 454     // It is NOT possible to have section-iterators here
 455     // because of the logistics of "index" (the section-iterator automatically
 456     // skips to the begin-point, we loose the index or have to recalculate it)
 457     // So we mimic it here
 458     template <typename Range, typename Section, typename Box, typename RobustPolicy>
 459     static inline void get_start_point_iterator(Section const& section,
 460             Range const& range,
 461             typename boost::range_iterator<Range const>::type& it,
 462             typename boost::range_iterator<Range const>::type& prev,
 463             typename boost::range_iterator<Range const>::type& end,
 464             signed_size_type& index, signed_size_type& ndi,
 465             int dir, Box const& other_bounding_box, RobustPolicy const& robust_policy)
 466     {
 467         it = boost::begin(range) + section.begin_index;
 468         end = boost::begin(range) + section.end_index + 1;
 469
 470         // Mimic section-iterator:
 471         // Skip to point such that section interects other box
 472         prev = it++;
 473         for(; it != end && detail::section::preceding<0>(dir, *it, section.bounding_box, other_bounding_box, robust_policy);
 474             prev = it++, index++, ndi++)
 475         {}
 476         // Go back one step because we want to start completely preceding
 477         it = prev;
 478     }
 479 };
 480
 481 template
 482 <
 483     typename Geometry1, typename Geometry2,
 484     bool Reverse1, bool Reverse2,
 485     typename TurnPolicy,
 486     typename IntersectionStrategy,
 487     typename RobustPolicy,
 488     typename Turns,
 489     typename InterruptPolicy
 490 >
 491 struct section_visitor
 492 {
 493     int m_source_id1;
 494     Geometry1 const& m_geometry1;
 495     int m_source_id2;
 496     Geometry2 const& m_geometry2;
 497     IntersectionStrategy const& m_intersection_strategy;
 498     RobustPolicy const& m_rescale_policy;
 499     Turns& m_turns;
 500     InterruptPolicy& m_interrupt_policy;
 501
 502     section_visitor(int id1, Geometry1 const& g1,
 503                     int id2, Geometry2 const& g2,
 504                     IntersectionStrategy const& intersection_strategy,
 505                     RobustPolicy const& robust_policy,
 506                     Turns& turns,
 507                     InterruptPolicy& ip)
 508         : m_source_id1(id1), m_geometry1(g1)
 509         , m_source_id2(id2), m_geometry2(g2)
 510         , m_intersection_strategy(intersection_strategy)
 511         , m_rescale_policy(robust_policy)
 512         , m_turns(turns)
 513         , m_interrupt_policy(ip)
 514     {}
 515
 516     template <typename Section>
 517     inline bool apply(Section const& sec1, Section const& sec2)
 518     {
 519         if (! detail::disjoint::disjoint_box_box(sec1.bounding_box,
 520                                                  sec2.bounding_box,
 521                                                  m_intersection_strategy.get_disjoint_box_box_strategy()))
 522         {
 523             // false if interrupted
 524             return get_turns_in_sections
 525                     <
 526                         Geometry1,
 527                         Geometry2,
 528                         Reverse1, Reverse2,
 529                         Section, Section,
 530                         TurnPolicy
 531                     >::apply(m_source_id1, m_geometry1, sec1,
 532                              m_source_id2, m_geometry2, sec2,
 533                              false, false,
 534                              m_intersection_strategy,
 535                              m_rescale_policy,
 536                              m_turns, m_interrupt_policy);
 537         }
 538         return true;
 539     }
 540
 541 };
 542
 543 template
 544 <
 545     typename Geometry1, typename Geometry2,
 546     bool Reverse1, bool Reverse2,
 547     typename TurnPolicy
 548 >
 549 class get_turns_generic
 550 {
 551
 552 public:
 553     template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
 554     static inline void apply(
 555             int source_id1, Geometry1 const& geometry1,
 556             int source_id2, Geometry2 const& geometry2,
 557             IntersectionStrategy const& intersection_strategy,
 558             RobustPolicy const& robust_policy,
 559             Turns& turns,
 560             InterruptPolicy& interrupt_policy)
 561     {
 562         // First create monotonic sections...
 563         typedef typename boost::range_value<Turns>::type ip_type;
 564         typedef typename ip_type::point_type point_type;
 565
 566         typedef model::box
 567             <
 568                 typename geometry::robust_point_type
 569                 <
 570                     point_type, RobustPolicy
 571                 >::type
 572             > box_type;
 573         typedef geometry::sections<box_type, 2> sections_type;
 574
 575         sections_type sec1, sec2;
 576         typedef boost::mpl::vector_c<std::size_t, 0, 1> dimensions;
 577
 578         typename IntersectionStrategy::envelope_strategy_type const
 579             envelope_strategy = intersection_strategy.get_envelope_strategy();
 580         typename IntersectionStrategy::expand_strategy_type const
 581             expand_strategy = intersection_strategy.get_expand_strategy();
 582
 583         geometry::sectionalize<Reverse1, dimensions>(geometry1, robust_policy,
 584                 sec1, envelope_strategy, expand_strategy, 0);
 585         geometry::sectionalize<Reverse2, dimensions>(geometry2, robust_policy,
 586                 sec2, envelope_strategy, expand_strategy, 1);
 587
 588         // ... and then partition them, intersecting overlapping sections in visitor method
 589         section_visitor
 590             <
 591                 Geometry1, Geometry2,
 592                 Reverse1, Reverse2,
 593                 TurnPolicy,
 594                 IntersectionStrategy, RobustPolicy,
 595                 Turns, InterruptPolicy
 596             > visitor(source_id1, geometry1, source_id2, geometry2,
 597                       intersection_strategy, robust_policy,
 598                       turns, interrupt_policy);
 599
 600         typedef detail::section::get_section_box
 601             <
 602                 typename IntersectionStrategy::expand_box_strategy_type
 603             > get_section_box_type;
 604         typedef detail::section::overlaps_section_box
 605             <
 606                 typename IntersectionStrategy::disjoint_box_box_strategy_type
 607             > overlaps_section_box_type;
 608
 609         geometry::partition
 610             <
 611                 box_type
 612             >::apply(sec1, sec2, visitor,
 613                      get_section_box_type(),
 614                      overlaps_section_box_type());
 615     }
 616 };
 617
 618
 619 // Get turns for a range with a box, following Cohen-Sutherland (cs) approach
 620 template
 621 <
 622     typename Range, typename Box,
 623     bool ReverseRange, bool ReverseBox,
 624     typename TurnPolicy
 625 >
 626 struct get_turns_cs
 627 {
 628     typedef typename geometry::point_type<Range>::type range_point_type;
 629     typedef typename geometry::point_type<Box>::type box_point_type;
 630     typedef boost::array<box_point_type, 4> box_array;
 631
 632     typedef typename closeable_view
 633         <
 634             Range const,
 635             closure<Range>::value
 636         >::type cview_type;
 637
 638     typedef typename reversible_view
 639         <
 640             cview_type const,
 641             ReverseRange ? iterate_reverse : iterate_forward
 642         >::type view_type;
 643
 644     typedef typename boost::range_iterator
 645         <
 646             view_type const
 647         >::type iterator_type;
 648
 649     struct unique_sub_range_from_box_policy
 650     {
 651         typedef box_point_type point_type;
 652
 653         unique_sub_range_from_box_policy(box_array const& box)
 654           : m_box(box)
 655           , m_index(0)
 656         {}
 657
 658         static inline bool is_first_segment() { return false; }
 659         static inline bool is_last_segment() { return false; }
 660         static inline std::size_t size() { return 4; }
 661
 662         inline box_point_type const& at(std::size_t index) const
 663         {
 664             BOOST_GEOMETRY_ASSERT(index < size());
 665             return m_box[(m_index + index) % 4];
 666         }
 667
 668         inline void next()
 669         {
 670             m_index++;
 671         }
 672
 673     private :
 674         box_array const& m_box;
 675         std::size_t m_index;
 676     };
 677
 678     struct unique_sub_range_from_view_policy
 679     {
 680         typedef range_point_type point_type;
 681
 682         unique_sub_range_from_view_policy(view_type const& view, point_type const& pi, point_type const& pj, iterator_type it)
 683           : m_view(view)
 684           , m_pi(pi)
 685           , m_pj(pj)
 686           , m_circular_iterator(boost::begin(view), boost::end(view), it, true)
 687         {
 688             ++m_circular_iterator;
 689         }
 690
 691         static inline bool is_first_segment() { return false; }
 692         static inline bool is_last_segment() { return false; }
 693         static inline std::size_t size() { return 3; }
 694
 695         inline point_type const& at(std::size_t index) const
 696         {
 697             BOOST_GEOMETRY_ASSERT(index < size());
 698             switch (index)
 699             {
 700                 case 0 : return m_pi;
 701                 case 1 : return m_pj;
 702                 case 2 : return *m_circular_iterator;
 703                 default : return m_pi;
 704             }
 705         }
 706
 707     private :
 708         view_type const& m_view;
 709         point_type const& m_pi;
 710         point_type const& m_pj;
 711         ever_circling_iterator<iterator_type> m_circular_iterator;
 712     };
 713
 714     template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
 715     static inline void apply(
 716                 int source_id1, Range const& range,
 717                 int source_id2, Box const& box,
 718                 IntersectionStrategy const& intersection_strategy,
 719                 RobustPolicy const& robust_policy,
 720                 Turns& turns,
 721                 InterruptPolicy& interrupt_policy,
 722                 signed_size_type multi_index = -1,
 723                 signed_size_type ring_index = -1)
 724     {
 725         if ( boost::size(range) <= 1)
 726         {
 727             return;
 728         }
 729
 730         box_array box_points;
 731         assign_box_corners_oriented<ReverseBox>(box, box_points);
 732
 733         cview_type cview(range);
 734         view_type view(cview);
 735
 736         // TODO: in this code, possible duplicate points are not yet taken
 737         // into account (not in the iterator, nor in the retrieve policy)
 738         iterator_type it = boost::begin(view);
 739
 740         //bool first = true;
 741
 742         //char previous_side[2] = {0, 0};
 743
 744         signed_size_type index = 0;
 745
 746         for (iterator_type prev = it++;
 747             it != boost::end(view);
 748             prev = it++, index++)
 749         {
 750             segment_identifier seg_id(source_id1,
 751                         multi_index, ring_index, index);
 752
 753             unique_sub_range_from_view_policy view_unique_sub_range(view, *prev, *it, it);
 754
 755             /*if (first)
 756             {
 757                 previous_side[0] = get_side<0>(box, *prev);
 758                 previous_side[1] = get_side<1>(box, *prev);
 759             }
 760
 761             char current_side[2];
 762             current_side[0] = get_side<0>(box, *it);
 763             current_side[1] = get_side<1>(box, *it);
 764
 765             // There can NOT be intersections if
 766             // 1) EITHER the two points are lying on one side of the box (! 0 && the same)
 767             // 2) OR same in Y-direction
 768             // 3) OR all points are inside the box (0)
 769             if (! (
 770                 (current_side[0] != 0 && current_side[0] == previous_side[0])
 771                 || (current_side[1] != 0 && current_side[1] == previous_side[1])
 772                 || (current_side[0] == 0
 773                         && current_side[1] == 0
 774                         && previous_side[0] == 0
 775                         && previous_side[1] == 0)
 776                   )
 777                 )*/
 778             if (true)
 779             {
 780                 get_turns_with_box(seg_id, source_id2,
 781                         view_unique_sub_range,
 782                         box_points,
 783                         intersection_strategy,
 784                         robust_policy,
 785                         turns,
 786                         interrupt_policy);
 787                 // Future performance enhancement:
 788                 // return if told by the interrupt policy
 789             }
 790         }
 791     }
 792
 793 private:
 794     template<std::size_t Index, typename Point>
 795     static inline int get_side(Box const& box, Point const& point)
 796     {
 797         // Inside -> 0
 798         // Outside -> -1 (left/below) or 1 (right/above)
 799         // On border -> -2 (left/lower) or 2 (right/upper)
 800         // The only purpose of the value is to not be the same,
 801         // and to denote if it is inside (0)
 802
 803         typename coordinate_type<Point>::type const& c = get<Index>(point);
 804         typename coordinate_type<Box>::type const& left = get<min_corner, Index>(box);
 805         typename coordinate_type<Box>::type const& right = get<max_corner, Index>(box);
 806
 807         if (geometry::math::equals(c, left)) return -2;
 808         else if (geometry::math::equals(c, right)) return 2;
 809         else if (c < left) return -1;
 810         else if (c > right) return 1;
 811         else return 0;
 812     }
 813
 814     template
 815     <
 816         typename IntersectionStrategy,
 817         typename Turns,
 818         typename InterruptPolicy,
 819         typename RobustPolicy
 820     >
 821     static inline void get_turns_with_box(segment_identifier const& seg_id, int source_id2,
 822             unique_sub_range_from_view_policy const& range_unique_sub_range,
 823             box_array const& box,
 824             IntersectionStrategy const& intersection_strategy,
 825             RobustPolicy const& robust_policy,
 826             // Output
 827             Turns& turns,
 828             InterruptPolicy& interrupt_policy)
 829     {
 830         boost::ignore_unused(interrupt_policy);
 831
 832         // Depending on code some relations can be left out
 833
 834         typedef typename boost::range_value<Turns>::type turn_info;
 835
 836         turn_info ti;
 837         ti.operations[0].seg_id = seg_id;
 838
 839         unique_sub_range_from_box_policy box_unique_sub_range(box);
 840         ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 0);
 841         TurnPolicy::apply(range_unique_sub_range, box_unique_sub_range,
 842                           ti, intersection_strategy, robust_policy,
 843                           std::back_inserter(turns));
 844
 845         ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 1);
 846         box_unique_sub_range.next();
 847         TurnPolicy::apply(range_unique_sub_range, box_unique_sub_range,
 848                           ti, intersection_strategy, robust_policy,
 849                           std::back_inserter(turns));
 850
 851         ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 2);
 852         box_unique_sub_range.next();
 853         TurnPolicy::apply(range_unique_sub_range, box_unique_sub_range,
 854                           ti, intersection_strategy, robust_policy,
 855                           std::back_inserter(turns));
 856
 857         ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 3);
 858         box_unique_sub_range.next();
 859         TurnPolicy::apply(range_unique_sub_range, box_unique_sub_range,
 860                           ti, intersection_strategy, robust_policy,
 861                           std::back_inserter(turns));
 862
 863         if (InterruptPolicy::enabled)
 864         {
 865             interrupt_policy.apply(turns);
 866         }
 867
 868     }
 869
 870 };
 871
 872
 873 template
 874 <
 875     typename Polygon, typename Box,
 876     bool Reverse, bool ReverseBox,
 877     typename TurnPolicy
 878 >
 879 struct get_turns_polygon_cs
 880 {
 881     template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
 882     static inline void apply(
 883             int source_id1, Polygon const& polygon,
 884             int source_id2, Box const& box,
 885             IntersectionStrategy const& intersection_strategy,
 886             RobustPolicy const& robust_policy,
 887             Turns& turns,
 888             InterruptPolicy& interrupt_policy,
 889             signed_size_type multi_index = -1)
 890     {
 891         typedef typename geometry::ring_type<Polygon>::type ring_type;
 892
 893         typedef detail::get_turns::get_turns_cs
 894             <
 895                 ring_type, Box,
 896                 Reverse, ReverseBox,
 897                 TurnPolicy
 898             > intersector_type;
 899
 900         intersector_type::apply(
 901                 source_id1, geometry::exterior_ring(polygon),
 902                 source_id2, box,
 903                 intersection_strategy,
 904                 robust_policy,
 905                 turns,
 906                 interrupt_policy,
 907                 multi_index, -1);
 908
 909         signed_size_type i = 0;
 910
 911         typename interior_return_type<Polygon const>::type
 912             rings = interior_rings(polygon);
 913         for (typename detail::interior_iterator<Polygon const>::type
 914                 it = boost::begin(rings); it != boost::end(rings); ++it, ++i)
 915         {
 916             intersector_type::apply(
 917                     source_id1, *it,
 918                     source_id2, box,
 919                     intersection_strategy,
 920                     robust_policy,
 921                     turns, interrupt_policy,
 922                     multi_index, i);
 923         }
 924
 925     }
 926 };
 927
 928
 929 template
 930 <
 931     typename Multi, typename Box,
 932     bool Reverse, bool ReverseBox,
 933     typename TurnPolicy
 934 >
 935 struct get_turns_multi_polygon_cs
 936 {
 937     template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
 938     static inline void apply(
 939             int source_id1, Multi const& multi,
 940             int source_id2, Box const& box,
 941             IntersectionStrategy const& intersection_strategy,
 942             RobustPolicy const& robust_policy,
 943             Turns& turns,
 944             InterruptPolicy& interrupt_policy)
 945     {
 946         typedef typename boost::range_iterator
 947             <
 948                 Multi const
 949             >::type iterator_type;
 950
 951         signed_size_type i = 0;
 952         for (iterator_type it = boost::begin(multi);
 953              it != boost::end(multi);
 954              ++it, ++i)
 955         {
 956             // Call its single version
 957             get_turns_polygon_cs
 958                 <
 959                     typename boost::range_value<Multi>::type, Box,
 960                     Reverse, ReverseBox,
 961                     TurnPolicy
 962                 >::apply(source_id1, *it, source_id2, box,
 963                          intersection_strategy, robust_policy,
 964                          turns, interrupt_policy, i);
 965         }
 966     }
 967 };
 968
 969
 970 // GET_TURN_INFO_TYPE
 971
 972 template <typename Geometry>
 973 struct topological_tag_base
 974 {
 975     typedef typename tag_cast<typename tag<Geometry>::type, pointlike_tag, linear_tag, areal_tag>::type type;
 976 };
 977
 978 template <typename Geometry1, typename Geometry2, typename AssignPolicy,
 979           typename Tag1 = typename tag<Geometry1>::type, typename Tag2 = typename tag<Geometry2>::type,
 980           typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type>
 981 struct get_turn_info_type
 982     : overlay::get_turn_info<AssignPolicy>
 983 {};
 984
 985 template <typename Geometry1, typename Geometry2, typename AssignPolicy, typename Tag1, typename Tag2>
 986 struct get_turn_info_type<Geometry1, Geometry2, AssignPolicy, Tag1, Tag2, linear_tag, linear_tag>
 987     : overlay::get_turn_info_linear_linear<AssignPolicy>
 988 {};
 989
 990 template <typename Geometry1, typename Geometry2, typename AssignPolicy, typename Tag1, typename Tag2>
 991 struct get_turn_info_type<Geometry1, Geometry2, AssignPolicy, Tag1, Tag2, linear_tag, areal_tag>
 992     : overlay::get_turn_info_linear_areal<AssignPolicy>
 993 {};
 994
 995 template <typename Geometry1, typename Geometry2, typename SegmentRatio,
 996           typename Tag1 = typename tag<Geometry1>::type, typename Tag2 = typename tag<Geometry2>::type,
 997           typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type>
 998 struct turn_operation_type
 999 {
1000     typedef overlay::turn_operation<typename point_type<Geometry1>::type, SegmentRatio> type;
1001 };
1002
1003 template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2>
1004 struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, linear_tag>
1005 {
1006     typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type;
1007 };
1008
1009 template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2>
1010 struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, areal_tag>
1011 {
1012     typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type;
1013 };
1014
1015 }} // namespace detail::get_turns
1016 #endif // DOXYGEN_NO_DETAIL
1017
1018
1019 #ifndef DOXYGEN_NO_DISPATCH
1020 namespace dispatch
1021 {
1022
1023 // Because this is "detail" method, and most implementations will use "generic",
1024 // we take the freedom to derive it from "generic".
1025 template
1026 <
1027     typename GeometryTag1, typename GeometryTag2,
1028     typename Geometry1, typename Geometry2,
1029     bool Reverse1, bool Reverse2,
1030     typename TurnPolicy
1031 >
1032 struct get_turns
1033     : detail::get_turns::get_turns_generic
1034         <
1035             Geometry1, Geometry2,
1036             Reverse1, Reverse2,
1037             TurnPolicy
1038         >
1039 {};
1040
1041
1042 template
1043 <
1044     typename Polygon, typename Box,
1045     bool ReversePolygon, bool ReverseBox,
1046     typename TurnPolicy
1047 >
1048 struct get_turns
1049     <
1050         polygon_tag, box_tag,
1051         Polygon, Box,
1052         ReversePolygon, ReverseBox,
1053         TurnPolicy
1054     > : detail::get_turns::get_turns_polygon_cs
1055             <
1056                 Polygon, Box,
1057                 ReversePolygon, ReverseBox,
1058                 TurnPolicy
1059             >
1060 {};
1061
1062
1063 template
1064 <
1065     typename Ring, typename Box,
1066     bool ReverseRing, bool ReverseBox,
1067     typename TurnPolicy
1068 >
1069 struct get_turns
1070     <
1071         ring_tag, box_tag,
1072         Ring, Box,
1073         ReverseRing, ReverseBox,
1074         TurnPolicy
1075     > : detail::get_turns::get_turns_cs
1076             <
1077                 Ring, Box, ReverseRing, ReverseBox,
1078                 TurnPolicy
1079             >
1080
1081 {};
1082
1083
1084 template
1085 <
1086     typename MultiPolygon,
1087     typename Box,
1088     bool ReverseMultiPolygon, bool ReverseBox,
1089     typename TurnPolicy
1090 >
1091 struct get_turns
1092     <
1093         multi_polygon_tag, box_tag,
1094         MultiPolygon, Box,
1095         ReverseMultiPolygon, ReverseBox,
1096         TurnPolicy
1097     >
1098     : detail::get_turns::get_turns_multi_polygon_cs
1099         <
1100             MultiPolygon, Box,
1101             ReverseMultiPolygon, ReverseBox,
1102             TurnPolicy
1103         >
1104 {};
1105
1106
1107 template
1108 <
1109     typename GeometryTag1, typename GeometryTag2,
1110     typename Geometry1, typename Geometry2,
1111     bool Reverse1, bool Reverse2,
1112     typename TurnPolicy
1113 >
1114 struct get_turns_reversed
1115 {
1116     template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
1117     static inline void apply(int source_id1, Geometry1 const& g1,
1118                              int source_id2, Geometry2 const& g2,
1119                              IntersectionStrategy const& intersection_strategy,
1120                              RobustPolicy const& robust_policy,
1121                              Turns& turns,
1122                              InterruptPolicy& interrupt_policy)
1123     {
1124         get_turns
1125             <
1126                 GeometryTag2, GeometryTag1,
1127                 Geometry2, Geometry1,
1128                 Reverse2, Reverse1,
1129                 TurnPolicy
1130             >::apply(source_id2, g2, source_id1, g1,
1131                      intersection_strategy, robust_policy,
1132                      turns, interrupt_policy);
1133     }
1134 };
1135
1136
1137 } // namespace dispatch
1138 #endif // DOXYGEN_NO_DISPATCH
1139
1140
1141
1142 /*!
1143 \brief \brief_calc2{turn points}
1144 \ingroup overlay
1145 \tparam Geometry1 \tparam_geometry
1146 \tparam Geometry2 \tparam_geometry
1147 \tparam Turns type of turn-container (e.g. vector of "intersection/turn point"'s)
1148 \param geometry1 \param_geometry
1149 \param geometry2 \param_geometry
1150 \param intersection_strategy segments intersection strategy
1151 \param robust_policy policy to handle robustness issues
1152 \param turns container which will contain turn points
1153 \param interrupt_policy policy determining if process is stopped
1154     when intersection is found
1155  */
1156 template
1157 <
1158     bool Reverse1, bool Reverse2,
1159     typename AssignPolicy,
1160     typename Geometry1,
1161     typename Geometry2,
1162     typename IntersectionStrategy,
1163     typename RobustPolicy,
1164     typename Turns,
1165     typename InterruptPolicy
1166 >
1167 inline void get_turns(Geometry1 const& geometry1,
1168                       Geometry2 const& geometry2,
1169                       IntersectionStrategy const& intersection_strategy,
1170                       RobustPolicy const& robust_policy,
1171                       Turns& turns,
1172                       InterruptPolicy& interrupt_policy)
1173 {
1174     concepts::check_concepts_and_equal_dimensions<Geometry1 const, Geometry2 const>();
1175
1176     typedef detail::overlay::get_turn_info<AssignPolicy> TurnPolicy;
1177     //typedef detail::get_turns::get_turn_info_type<Geometry1, Geometry2, AssignPolicy> TurnPolicy;
1178
1179     boost::mpl::if_c
1180         <
1181             reverse_dispatch<Geometry1, Geometry2>::type::value,
1182             dispatch::get_turns_reversed
1183             <
1184                 typename tag<Geometry1>::type,
1185                 typename tag<Geometry2>::type,
1186                 Geometry1, Geometry2,
1187                 Reverse1, Reverse2,
1188                 TurnPolicy
1189             >,
1190             dispatch::get_turns
1191             <
1192                 typename tag<Geometry1>::type,
1193                 typename tag<Geometry2>::type,
1194                 Geometry1, Geometry2,
1195                 Reverse1, Reverse2,
1196                 TurnPolicy
1197             >
1198         >::type::apply(0, geometry1,
1199                        1, geometry2,
1200                        intersection_strategy,
1201                        robust_policy,
1202                        turns, interrupt_policy);
1203 }
1204
1205 #if defined(_MSC_VER)
1206 #pragma warning(pop)
1207 #endif
1208
1209 }} // namespace boost::geometry
1210
1211 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP