detail/overlay/get_turns.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2014-2023 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2014-2021.
0007 // Modifications copyright (c) 2014-2021 Oracle and/or its affiliates.
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Use, modification and distribution is subject to the Boost Software License,
0011 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0012 // http://www.boost.org/LICENSE_1_0.txt)
0013
0014 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
0016
0017
0018 #include <array>
0019 #include <cstddef>
0020 #include <map>
0021
0022 #include <boost/concept_check.hpp>
0023 #include <boost/core/ignore_unused.hpp>
0024 #include <boost/range/begin.hpp>
0025 #include <boost/range/end.hpp>
0026 #include <boost/range/size.hpp>
0027 #include <boost/range/value_type.hpp>
0028
0029 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
0030 #include <boost/geometry/algorithms/detail/disjoint/point_point.hpp>
0031 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
0032 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp>
0033 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp>
0034 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
0035 #include <boost/geometry/algorithms/detail/partition.hpp>
0036 #include <boost/geometry/algorithms/detail/recalculate.hpp>
0037 #include <boost/geometry/algorithms/detail/sections/range_by_section.hpp>
0038 #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp>
0039 #include <boost/geometry/algorithms/detail/sections/section_functions.hpp>
0040 #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
0041
0042 #include <boost/geometry/core/assert.hpp>
0043 #include <boost/geometry/core/coordinate_dimension.hpp>
0044 #include <boost/geometry/core/exterior_ring.hpp>
0045 #include <boost/geometry/core/interior_rings.hpp>
0046 #include <boost/geometry/core/reverse_dispatch.hpp>
0047 #include <boost/geometry/core/ring_type.hpp>
0048 #include <boost/geometry/core/tags.hpp>
0049
0050 #include <boost/geometry/geometries/box.hpp>
0051 #include <boost/geometry/geometries/concepts/check.hpp>
0052 #include <boost/geometry/geometries/segment.hpp>
0053
0054 #include <boost/geometry/iterators/ever_circling_iterator.hpp>
0055
0056 #include <boost/geometry/strategies/intersection_strategies.hpp>
0057 #include <boost/geometry/strategies/intersection_result.hpp>
0058
0059 #include <boost/geometry/util/math.hpp>
0060 #include <boost/geometry/util/type_traits.hpp>
0061
0062 #include <boost/geometry/views/detail/closed_clockwise_view.hpp>
0063
0064
0065 #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
0066 #  include <sstream>
0067 #  include <boost/geometry/io/dsv/write.hpp>
0068 #endif
0069
0070
0071 namespace boost { namespace geometry
0072 {
0073
0074 // Silence warning C4127: conditional expression is constant
0075 #if defined(_MSC_VER)
0076 #pragma warning(push)
0077 #pragma warning(disable : 4127)
0078 #endif
0079
0080
0081 #ifndef DOXYGEN_NO_DETAIL
0082 namespace detail { namespace get_turns
0083 {
0084
0085
0086 struct no_interrupt_policy
0087 {
0088     static bool const enabled = false;
0089
0090     // variable required by self_get_turn_points::get_turns
0091     static bool const has_intersections = false;
0092
0093     template <typename Range>
0094     static inline bool apply(Range const&)
0095     {
0096         return false;
0097     }
0098 };
0099
0100 template
0101 <
0102     bool IsAreal,
0103     typename Section,
0104     typename Point,
0105     typename CircularIterator,
0106     typename Strategy,
0107     typename RobustPolicy
0108 >
0109 struct unique_sub_range_from_section
0110 {
0111     using point_type = Point;
0112
0113     unique_sub_range_from_section(Section const& section, signed_size_type index,
0114                           CircularIterator circular_iterator,
0115                           Point const& previous, Point const& current,
0116                           Strategy const& strategy,
0117                           RobustPolicy const& robust_policy)
0118         : m_section(section)
0119         , m_index(index)
0120         , m_previous_point(previous)
0121         , m_current_point(current)
0122         , m_circular_iterator(circular_iterator)
0123         , m_next_point_retrieved(false)
0124         , m_strategy(strategy)
0125         , m_robust_policy(robust_policy)
0126     {}
0127
0128     inline bool is_first_segment() const
0129     {
0130         return !IsAreal && m_section.is_non_duplicate_first && m_index == m_section.begin_index;
0131     }
0132     inline bool is_last_segment() const
0133     {
0134         return size() == 2u;
0135     }
0136
0137     inline std::size_t size() const
0138     {
0139         return IsAreal ? 3
0140             : m_section.is_non_duplicate_last && m_index + 1 >= m_section.end_index ? 2 : 3;
0141     }
0142
0143     inline Point const& at(std::size_t index) const
0144     {
0145         BOOST_GEOMETRY_ASSERT(index < size());
0146         switch (index)
0147         {
0148             case 0 : return m_previous_point;
0149             case 1 : return m_current_point;
0150             case 2 : return get_next_point();
0151             default : return m_previous_point;
0152         }
0153     }
0154
0155 private :
0156     inline Point const& get_next_point() const
0157     {
0158         if (! m_next_point_retrieved)
0159         {
0160             advance_to_non_duplicate_next(m_current_point, m_circular_iterator);
0161             m_next_point_retrieved = true;
0162         }
0163         return *m_circular_iterator;
0164     }
0165
0166     inline void advance_to_non_duplicate_next(Point const& current, CircularIterator& circular_iterator) const
0167     {
0168         using box_point_type = typename geometry::point_type<typename Section::box_type>::type;
0169         using robust_point_type = typename robust_point_type<box_point_type, RobustPolicy>::type;
0170         robust_point_type current_robust_point;
0171         robust_point_type next_robust_point;
0172         geometry::recalculate(current_robust_point, current, m_robust_policy);
0173         geometry::recalculate(next_robust_point, *circular_iterator, m_robust_policy);
0174
0175         // To see where the next segments bend to, in case of touch/intersections
0176         // on end points, we need (in case of degenerate/duplicate points) an extra
0177         // iterator which moves to the REAL next point, so non duplicate.
0178         // This needs an extra comparison (disjoint).
0179         // (Note that within sections, non duplicate points are already asserted,
0180         //   by the sectionalize process).
0181
0182         // So advance to the "non duplicate next"
0183         // (the check is defensive, to avoid endless loops)
0184         std::size_t check = 0;
0185         while (! detail::disjoint::disjoint_point_point(
0186                     current_robust_point, next_robust_point, m_strategy)
0187                && check++ < m_section.range_count)
0188         {
0189             circular_iterator++;
0190             geometry::recalculate(next_robust_point, *circular_iterator, m_robust_policy);
0191         }
0192     }
0193
0194     Section const& m_section;
0195     signed_size_type m_index;
0196     Point const& m_previous_point;
0197     Point const& m_current_point;
0198     mutable CircularIterator m_circular_iterator;
0199     mutable bool m_next_point_retrieved;
0200     Strategy m_strategy;
0201     RobustPolicy m_robust_policy;
0202 };
0203
0204 template
0205 <
0206     typename Geometry1, typename Geometry2,
0207     bool Reverse1, bool Reverse2,
0208     typename Section1, typename Section2,
0209     typename TurnPolicy
0210 >
0211 class get_turns_in_sections
0212 {
0213     using range1_view = detail::closed_clockwise_view
0214         <
0215             typename ring_type<Geometry1>::type const,
0216             geometry::closure<Geometry1>::value,
0217             Reverse1 ? counterclockwise : clockwise
0218         >;
0219     using range2_view = detail::closed_clockwise_view
0220         <
0221             typename ring_type<Geometry2>::type const,
0222             geometry::closure<Geometry2>::value,
0223             Reverse2 ? counterclockwise : clockwise
0224         >;
0225
0226     using range1_iterator = typename boost::range_iterator<range1_view const>::type;
0227     using range2_iterator = typename boost::range_iterator<range2_view const>::type;
0228
0229     using circular1_iterator = ever_circling_iterator<range1_iterator>;
0230     using circular2_iterator = ever_circling_iterator<range2_iterator>;
0231
0232     template <typename Geometry, typename Section>
0233     static inline bool adjacent(Section const& section,
0234             signed_size_type index1, signed_size_type index2)
0235     {
0236         // About n-2:
0237         //   (square: range_count=5, indices 0,1,2,3
0238         //    -> 0-3 are adjacent, don't check on intersections)
0239         // Also tested for open polygons, and/or duplicates
0240         // About first condition: will be optimized by compiler (static)
0241         // It checks if it is areal (box, ring, (multi)polygon)
0242         signed_size_type const n = static_cast<signed_size_type>(section.range_count);
0243
0244         boost::ignore_unused(n, index1, index2);
0245
0246         return util::is_areal<Geometry>::value
0247                && index1 == 0
0248                && index2 >= n - 2
0249                 ;
0250     }
0251
0252
0253 public :
0254     // Returns true if terminated, false if interrupted
0255     template <typename Strategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
0256     static inline bool apply(
0257             int source_id1, Geometry1 const& geometry1, Section1 const& sec1,
0258             int source_id2, Geometry2 const& geometry2, Section2 const& sec2,
0259             bool skip_larger, bool skip_adjacent,
0260             Strategy const& strategy,
0261             RobustPolicy const& robust_policy,
0262             Turns& turns,
0263             InterruptPolicy& interrupt_policy)
0264     {
0265         boost::ignore_unused(interrupt_policy);
0266
0267         static bool const areal1 = util::is_areal<Geometry1>::value;
0268         static bool const areal2 = util::is_areal<Geometry2>::value;
0269
0270         if ((sec1.duplicate && (sec1.count + 1) < sec1.range_count)
0271            || (sec2.duplicate && (sec2.count + 1) < sec2.range_count))
0272         {
0273             // Skip sections containig only duplicates.
0274             // They are still important (can indicate non-disjointness)
0275             // but they will be found processing adjacent sections.
0276             // Do NOT skip if they are the ONLY section
0277             return true;
0278         }
0279
0280         range1_view const view1(range_by_section(geometry1, sec1));
0281         range2_view const view2(range_by_section(geometry2, sec2));
0282
0283         range1_iterator begin_range_1 = boost::begin(view1);
0284         range1_iterator end_range_1 = boost::end(view1);
0285
0286         range2_iterator begin_range_2 = boost::begin(view2);
0287         range2_iterator end_range_2 = boost::end(view2);
0288
0289         int const dir1 = sec1.directions[0];
0290         int const dir2 = sec2.directions[0];
0291         signed_size_type index1 = sec1.begin_index;
0292         signed_size_type ndi1 = sec1.non_duplicate_index;
0293
0294         range1_iterator prev1, it1, end1;
0295
0296         get_start_point_iterator(sec1, view1, prev1, it1, end1,
0297                     index1, ndi1, dir1, sec2.bounding_box, robust_policy);
0298
0299         // We need a circular iterator because it might run through the closing point.
0300         // One circle is actually enough but this one is just convenient.
0301         circular1_iterator next1(begin_range_1, end_range_1, it1, true);
0302         next1++;
0303
0304         // Walk through section and stop if we exceed the other box
0305         // section 2:    [--------------]
0306         // section 1: |----|---|---|---|---|
0307         for (prev1 = it1++, next1++;
0308             it1 != end1 && ! detail::section::exceeding<0>(dir1, *prev1, sec1.bounding_box, sec2.bounding_box, robust_policy);
0309             ++prev1, ++it1, ++index1, ++next1, ++ndi1)
0310         {
0311             unique_sub_range_from_section
0312                 <
0313                     areal1, Section1, point1_type, circular1_iterator,
0314                     Strategy, RobustPolicy
0315                 > unique_sub_range1(sec1, index1,
0316                                     circular1_iterator(begin_range_1, end_range_1, next1, true),
0317                                     *prev1, *it1,
0318                                     strategy, robust_policy);
0319
0320             signed_size_type index2 = sec2.begin_index;
0321             signed_size_type ndi2 = sec2.non_duplicate_index;
0322
0323             range2_iterator prev2, it2, end2;
0324
0325             get_start_point_iterator(sec2, view2, prev2, it2, end2,
0326                         index2, ndi2, dir2, sec1.bounding_box, robust_policy);
0327             circular2_iterator next2(begin_range_2, end_range_2, it2, true);
0328             next2++;
0329
0330             for (prev2 = it2++, next2++;
0331                 it2 != end2 && ! detail::section::exceeding<0>(dir2, *prev2, sec2.bounding_box, sec1.bounding_box, robust_policy);
0332                 ++prev2, ++it2, ++index2, ++next2, ++ndi2)
0333             {
0334                 bool skip = false;
0335
0336                 if (source_id1 == source_id2
0337                         && sec1.ring_id.multi_index == sec2.ring_id.multi_index
0338                         && sec1.ring_id.ring_index == sec2.ring_id.ring_index)
0339                 {
0340                     // Sources and rings are the same
0341
0342                     if (skip_larger && index1 >= index2)
0343                     {
0344                         // Skip to avoid getting all intersections twice
0345                         skip = true;
0346                     }
0347                     else if (skip_adjacent)
0348                     {
0349                         // In some cases (dissolve, has_self_intersections)
0350                         // neighbouring segments should be checked
0351                         // (for example to detect spikes properly)
0352
0353                         // skip if it is a neighbouring segment.
0354                         // (including, for areas, first-last segment
0355                         //  and two segments with one or more degenerate/duplicate
0356                         //  (zero-length) segments in between)
0357                         skip = ndi2 == ndi1 + 1
0358                             || adjacent<Geometry1>(sec1, index1, index2);
0359                     }
0360                 }
0361
0362                 if (! skip)
0363                 {
0364                     unique_sub_range_from_section
0365                         <
0366                             areal2, Section2, point2_type, circular2_iterator,
0367                             Strategy, RobustPolicy
0368                         > unique_sub_range2(sec2, index2,
0369                                             circular2_iterator(begin_range_2, end_range_2, next2),
0370                                             *prev2, *it2,
0371                                             strategy, robust_policy);
0372
0373                     typedef typename boost::range_value<Turns>::type turn_info;
0374
0375                     turn_info ti;
0376                     ti.operations[0].seg_id
0377                         = segment_identifier(source_id1, sec1.ring_id.multi_index,
0378                                              sec1.ring_id.ring_index, index1);
0379                     ti.operations[1].seg_id
0380                         = segment_identifier(source_id2, sec2.ring_id.multi_index,
0381                                              sec2.ring_id.ring_index, index2);
0382
0383                     std::size_t const size_before = boost::size(turns);
0384
0385                     TurnPolicy::apply(unique_sub_range1, unique_sub_range2,
0386                                       ti, strategy, robust_policy,
0387                                       std::back_inserter(turns));
0388
0389                     if (InterruptPolicy::enabled)
0390                     {
0391                         if (interrupt_policy.apply(
0392                                 std::make_pair(range::pos(turns, size_before),
0393                                                boost::end(turns))))
0394                         {
0395                             return false;
0396                         }
0397                     }
0398                 }
0399             }
0400         }
0401         return true;
0402     }
0403
0404
0405 private :
0406     typedef typename geometry::point_type<Geometry1>::type point1_type;
0407     typedef typename geometry::point_type<Geometry2>::type point2_type;
0408
0409     // It is NOT possible to have section-iterators here
0410     // because of the logistics of "index" (the section-iterator automatically
0411     // skips to the begin-point, we loose the index or have to recalculate it)
0412     // So we mimic it here
0413     template <typename Range, typename Section, typename Box, typename RobustPolicy>
0414     static inline void get_start_point_iterator(Section const& section,
0415             Range const& range,
0416             typename boost::range_iterator<Range const>::type& it,
0417             typename boost::range_iterator<Range const>::type& prev,
0418             typename boost::range_iterator<Range const>::type& end,
0419             signed_size_type& index, signed_size_type& ndi,
0420             int dir, Box const& other_bounding_box, RobustPolicy const& robust_policy)
0421     {
0422         it = boost::begin(range) + section.begin_index;
0423         end = boost::begin(range) + section.end_index + 1;
0424
0425         // Mimic section-iterator:
0426         // Skip to point such that section interects other box
0427         prev = it++;
0428         for(; it != end && detail::section::preceding<0>(dir, *it, section.bounding_box, other_bounding_box, robust_policy);
0429             prev = it++, index++, ndi++)
0430         {}
0431         // Go back one step because we want to start completely preceding
0432         it = prev;
0433     }
0434 };
0435
0436 template
0437 <
0438     typename Geometry1, typename Geometry2,
0439     bool Reverse1, bool Reverse2,
0440     typename TurnPolicy,
0441     typename Strategy,
0442     typename RobustPolicy,
0443     typename Turns,
0444     typename InterruptPolicy
0445 >
0446 struct section_visitor
0447 {
0448     int m_source_id1;
0449     Geometry1 const& m_geometry1;
0450     int m_source_id2;
0451     Geometry2 const& m_geometry2;
0452     Strategy const& m_strategy;
0453     RobustPolicy const& m_rescale_policy;
0454     Turns& m_turns;
0455     InterruptPolicy& m_interrupt_policy;
0456
0457     section_visitor(int id1, Geometry1 const& g1,
0458                     int id2, Geometry2 const& g2,
0459                     Strategy const& strategy,
0460                     RobustPolicy const& robust_policy,
0461                     Turns& turns,
0462                     InterruptPolicy& ip)
0463         : m_source_id1(id1), m_geometry1(g1)
0464         , m_source_id2(id2), m_geometry2(g2)
0465         , m_strategy(strategy)
0466         , m_rescale_policy(robust_policy)
0467         , m_turns(turns)
0468         , m_interrupt_policy(ip)
0469     {}
0470
0471     template <typename Section>
0472     inline bool apply(Section const& sec1, Section const& sec2)
0473     {
0474         if (! detail::disjoint::disjoint_box_box(sec1.bounding_box,
0475                                                  sec2.bounding_box,
0476                                                  m_strategy) )
0477         {
0478             // false if interrupted
0479             return get_turns_in_sections
0480                     <
0481                         Geometry1,
0482                         Geometry2,
0483                         Reverse1, Reverse2,
0484                         Section, Section,
0485                         TurnPolicy
0486                     >::apply(m_source_id1, m_geometry1, sec1,
0487                              m_source_id2, m_geometry2, sec2,
0488                              false, false,
0489                              m_strategy,
0490                              m_rescale_policy,
0491                              m_turns, m_interrupt_policy);
0492         }
0493         return true;
0494     }
0495
0496 };
0497
0498 template
0499 <
0500     typename Geometry1, typename Geometry2,
0501     bool Reverse1, bool Reverse2,
0502     typename TurnPolicy
0503 >
0504 class get_turns_generic
0505 {
0506
0507 public:
0508     template <typename Strategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
0509     static inline void apply(
0510             int source_id1, Geometry1 const& geometry1,
0511             int source_id2, Geometry2 const& geometry2,
0512             Strategy const& strategy,
0513             RobustPolicy const& robust_policy,
0514             Turns& turns,
0515             InterruptPolicy& interrupt_policy)
0516     {
0517         // First create monotonic sections...
0518         typedef typename boost::range_value<Turns>::type ip_type;
0519         typedef typename ip_type::point_type point_type;
0520
0521         typedef model::box
0522             <
0523                 typename geometry::robust_point_type
0524                 <
0525                     point_type, RobustPolicy
0526                 >::type
0527             > box_type;
0528         typedef geometry::sections<box_type, 2> sections_type;
0529
0530         sections_type sec1, sec2;
0531         typedef std::integer_sequence<std::size_t, 0, 1> dimensions;
0532
0533         geometry::sectionalize<Reverse1, dimensions>(geometry1, robust_policy,
0534                                                      sec1, strategy, 0);
0535         geometry::sectionalize<Reverse2, dimensions>(geometry2, robust_policy,
0536                                                      sec2, strategy, 1);
0537
0538         // ... and then partition them, intersecting overlapping sections in visitor method
0539         section_visitor
0540             <
0541                 Geometry1, Geometry2,
0542                 Reverse1, Reverse2,
0543                 TurnPolicy,
0544                 Strategy, RobustPolicy,
0545                 Turns, InterruptPolicy
0546             > visitor(source_id1, geometry1, source_id2, geometry2,
0547                       strategy, robust_policy, turns, interrupt_policy);
0548
0549         geometry::partition
0550             <
0551                 box_type
0552             >::apply(sec1, sec2, visitor,
0553                      detail::section::get_section_box<Strategy>(strategy),
0554                      detail::section::overlaps_section_box<Strategy>(strategy));
0555     }
0556 };
0557
0558
0559 // Get turns for a range with a box, following Cohen-Sutherland (cs) approach
0560 template
0561 <
0562     typename Range, typename Box,
0563     bool ReverseRange, bool ReverseBox,
0564     typename TurnPolicy
0565 >
0566 struct get_turns_cs
0567 {
0568     typedef typename geometry::point_type<Range>::type range_point_type;
0569     typedef typename geometry::point_type<Box>::type box_point_type;
0570     typedef std::array<box_point_type, 4> box_array;
0571
0572     using view_type = detail::closed_clockwise_view
0573         <
0574             Range const,
0575             geometry::closure<Range>::value,
0576             ReverseRange ? counterclockwise : clockwise
0577         >;
0578
0579     using iterator_type = typename boost::range_iterator<view_type const>::type;
0580
0581     struct unique_sub_range_from_box_policy
0582     {
0583         typedef box_point_type point_type;
0584
0585         unique_sub_range_from_box_policy(box_array const& box)
0586           : m_box(box)
0587           , m_index(0)
0588         {}
0589
0590         static inline bool is_first_segment() { return false; }
0591         static inline bool is_last_segment() { return false; }
0592         static inline std::size_t size() { return 4; }
0593
0594         inline box_point_type const& at(std::size_t index) const
0595         {
0596             BOOST_GEOMETRY_ASSERT(index < size());
0597             return m_box[(m_index + index) % 4];
0598         }
0599
0600         inline void next()
0601         {
0602             m_index++;
0603         }
0604
0605     private :
0606         box_array const& m_box;
0607         std::size_t m_index;
0608     };
0609
0610     struct unique_sub_range_from_view_policy
0611     {
0612         typedef range_point_type point_type;
0613
0614         unique_sub_range_from_view_policy(view_type const& view, point_type const& pi, point_type const& pj, iterator_type it)
0615           : m_view(view)
0616           , m_pi(pi)
0617           , m_pj(pj)
0618           , m_circular_iterator(boost::begin(view), boost::end(view), it, true)
0619         {
0620             ++m_circular_iterator;
0621         }
0622
0623         static inline bool is_first_segment() { return false; }
0624         static inline bool is_last_segment() { return false; }
0625         static inline std::size_t size() { return 3; }
0626
0627         inline point_type const& at(std::size_t index) const
0628         {
0629             BOOST_GEOMETRY_ASSERT(index < size());
0630             switch (index)
0631             {
0632                 case 0 : return m_pi;
0633                 case 1 : return m_pj;
0634                 case 2 : return *m_circular_iterator;
0635                 default : return m_pi;
0636             }
0637         }
0638
0639     private :
0640         view_type const& m_view;
0641         point_type const& m_pi;
0642         point_type const& m_pj;
0643         ever_circling_iterator<iterator_type> m_circular_iterator;
0644     };
0645
0646     template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
0647     static inline void apply(
0648                 int source_id1, Range const& range,
0649                 int source_id2, Box const& box,
0650                 IntersectionStrategy const& intersection_strategy,
0651                 RobustPolicy const& robust_policy,
0652                 Turns& turns,
0653                 InterruptPolicy& interrupt_policy,
0654                 signed_size_type multi_index = -1,
0655                 signed_size_type ring_index = -1)
0656     {
0657         if ( boost::size(range) <= 1)
0658         {
0659             return;
0660         }
0661
0662         box_array box_points;
0663         assign_box_corners_oriented<ReverseBox>(box, box_points);
0664
0665         view_type const view(range);
0666
0667         // TODO: in this code, possible duplicate points are not yet taken
0668         // into account (not in the iterator, nor in the retrieve policy)
0669         iterator_type it = boost::begin(view);
0670
0671         signed_size_type index = 0;
0672
0673         for (iterator_type prev = it++;
0674             it != boost::end(view);
0675             prev = it++, index++)
0676         {
0677             segment_identifier seg_id(source_id1,
0678                         multi_index, ring_index, index);
0679
0680             unique_sub_range_from_view_policy view_unique_sub_range(view, *prev, *it, it);
0681
0682             get_turns_with_box(seg_id, source_id2,
0683                     view_unique_sub_range,
0684                     box_points,
0685                     intersection_strategy,
0686                     robust_policy,
0687                     turns,
0688                     interrupt_policy);
0689             // Future performance enhancement:
0690             // return if told by the interrupt policy
0691         }
0692     }
0693
0694 private:
0695
0696     template
0697     <
0698         typename IntersectionStrategy,
0699         typename Turns,
0700         typename InterruptPolicy,
0701         typename RobustPolicy
0702     >
0703     static inline void get_turns_with_box(segment_identifier const& seg_id, int source_id2,
0704             unique_sub_range_from_view_policy const& range_unique_sub_range,
0705             box_array const& box,
0706             IntersectionStrategy const& intersection_strategy,
0707             RobustPolicy const& robust_policy,
0708             // Output
0709             Turns& turns,
0710             InterruptPolicy& interrupt_policy)
0711     {
0712         boost::ignore_unused(interrupt_policy);
0713
0714         // Depending on code some relations can be left out
0715
0716         typedef typename boost::range_value<Turns>::type turn_info;
0717
0718         turn_info ti;
0719         ti.operations[0].seg_id = seg_id;
0720
0721         unique_sub_range_from_box_policy box_unique_sub_range(box);
0722         ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 0);
0723         TurnPolicy::apply(range_unique_sub_range, box_unique_sub_range,
0724                           ti, intersection_strategy, robust_policy,
0725                           std::back_inserter(turns));
0726
0727         ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 1);
0728         box_unique_sub_range.next();
0729         TurnPolicy::apply(range_unique_sub_range, box_unique_sub_range,
0730                           ti, intersection_strategy, robust_policy,
0731                           std::back_inserter(turns));
0732
0733         ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 2);
0734         box_unique_sub_range.next();
0735         TurnPolicy::apply(range_unique_sub_range, box_unique_sub_range,
0736                           ti, intersection_strategy, robust_policy,
0737                           std::back_inserter(turns));
0738
0739         ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 3);
0740         box_unique_sub_range.next();
0741         TurnPolicy::apply(range_unique_sub_range, box_unique_sub_range,
0742                           ti, intersection_strategy, robust_policy,
0743                           std::back_inserter(turns));
0744
0745         if (InterruptPolicy::enabled)
0746         {
0747             interrupt_policy.apply(turns);
0748         }
0749
0750     }
0751
0752 };
0753
0754
0755 template
0756 <
0757     typename Polygon, typename Box,
0758     bool Reverse, bool ReverseBox,
0759     typename TurnPolicy
0760 >
0761 struct get_turns_polygon_cs
0762 {
0763     template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
0764     static inline void apply(
0765             int source_id1, Polygon const& polygon,
0766             int source_id2, Box const& box,
0767             IntersectionStrategy const& intersection_strategy,
0768             RobustPolicy const& robust_policy,
0769             Turns& turns,
0770             InterruptPolicy& interrupt_policy,
0771             signed_size_type multi_index = -1)
0772     {
0773         typedef typename geometry::ring_type<Polygon>::type ring_type;
0774
0775         typedef detail::get_turns::get_turns_cs
0776             <
0777                 ring_type, Box,
0778                 Reverse, ReverseBox,
0779                 TurnPolicy
0780             > intersector_type;
0781
0782         intersector_type::apply(
0783                 source_id1, geometry::exterior_ring(polygon),
0784                 source_id2, box,
0785                 intersection_strategy,
0786                 robust_policy,
0787                 turns,
0788                 interrupt_policy,
0789                 multi_index, -1);
0790
0791         signed_size_type i = 0;
0792
0793         auto const& rings = interior_rings(polygon);
0794         for (auto it = boost::begin(rings); it != boost::end(rings); ++it, ++i)
0795         {
0796             intersector_type::apply(
0797                     source_id1, *it,
0798                     source_id2, box,
0799                     intersection_strategy,
0800                     robust_policy,
0801                     turns, interrupt_policy,
0802                     multi_index, i);
0803         }
0804
0805     }
0806 };
0807
0808
0809 template
0810 <
0811     typename Multi, typename Box,
0812     bool Reverse, bool ReverseBox,
0813     typename TurnPolicy
0814 >
0815 struct get_turns_multi_polygon_cs
0816 {
0817     template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
0818     static inline void apply(
0819             int source_id1, Multi const& multi,
0820             int source_id2, Box const& box,
0821             IntersectionStrategy const& intersection_strategy,
0822             RobustPolicy const& robust_policy,
0823             Turns& turns,
0824             InterruptPolicy& interrupt_policy)
0825     {
0826         signed_size_type i = 0;
0827         for (auto it = boost::begin(multi); it != boost::end(multi); ++it, ++i)
0828         {
0829             // Call its single version
0830             get_turns_polygon_cs
0831                 <
0832                     typename boost::range_value<Multi>::type, Box,
0833                     Reverse, ReverseBox,
0834                     TurnPolicy
0835                 >::apply(source_id1, *it, source_id2, box,
0836                          intersection_strategy, robust_policy,
0837                          turns, interrupt_policy, i);
0838         }
0839     }
0840 };
0841
0842
0843 // GET_TURN_INFO_TYPE
0844
0845 template <typename Geometry>
0846 struct topological_tag_base
0847 {
0848     typedef typename tag_cast<typename tag<Geometry>::type, pointlike_tag, linear_tag, areal_tag>::type type;
0849 };
0850
0851 template <typename Geometry1, typename Geometry2, typename AssignPolicy,
0852           typename Tag1 = typename tag<Geometry1>::type, typename Tag2 = typename tag<Geometry2>::type,
0853           typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type>
0854 struct get_turn_info_type
0855     : overlay::get_turn_info<AssignPolicy>
0856 {};
0857
0858 template <typename Geometry1, typename Geometry2, typename AssignPolicy, typename Tag1, typename Tag2>
0859 struct get_turn_info_type<Geometry1, Geometry2, AssignPolicy, Tag1, Tag2, linear_tag, linear_tag>
0860     : overlay::get_turn_info_linear_linear<AssignPolicy>
0861 {};
0862
0863 template <typename Geometry1, typename Geometry2, typename AssignPolicy, typename Tag1, typename Tag2>
0864 struct get_turn_info_type<Geometry1, Geometry2, AssignPolicy, Tag1, Tag2, linear_tag, areal_tag>
0865     : overlay::get_turn_info_linear_areal<AssignPolicy>
0866 {};
0867
0868 template <typename Geometry1, typename Geometry2, typename Point, typename SegmentRatio,
0869           typename Tag1 = typename tag<Geometry1>::type, typename Tag2 = typename tag<Geometry2>::type,
0870           typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type>
0871 struct turn_operation_type
0872 {
0873     using type = overlay::turn_operation<Point, SegmentRatio>;
0874 };
0875
0876 template <typename Geometry1, typename Geometry2, typename Point, typename SegmentRatio, typename Tag1, typename Tag2>
0877 struct turn_operation_type<Geometry1, Geometry2, Point, SegmentRatio, Tag1, Tag2, linear_tag, linear_tag>
0878 {
0879     using type = overlay::turn_operation_linear<Point, SegmentRatio>;
0880 };
0881
0882 template <typename Geometry1, typename Geometry2, typename Point, typename SegmentRatio, typename Tag1, typename Tag2>
0883 struct turn_operation_type<Geometry1, Geometry2, Point, SegmentRatio, Tag1, Tag2, linear_tag, areal_tag>
0884 {
0885     using type = overlay::turn_operation_linear<Point, SegmentRatio>;
0886 };
0887
0888 }} // namespace detail::get_turns
0889 #endif // DOXYGEN_NO_DETAIL
0890
0891
0892 #ifndef DOXYGEN_NO_DISPATCH
0893 namespace dispatch
0894 {
0895
0896 // Because this is "detail" method, and most implementations will use "generic",
0897 // we take the freedom to derive it from "generic".
0898 template
0899 <
0900     typename GeometryTag1, typename GeometryTag2,
0901     typename Geometry1, typename Geometry2,
0902     bool Reverse1, bool Reverse2,
0903     typename TurnPolicy
0904 >
0905 struct get_turns
0906     : detail::get_turns::get_turns_generic
0907         <
0908             Geometry1, Geometry2,
0909             Reverse1, Reverse2,
0910             TurnPolicy
0911         >
0912 {};
0913
0914
0915 template
0916 <
0917     typename Polygon, typename Box,
0918     bool ReversePolygon, bool ReverseBox,
0919     typename TurnPolicy
0920 >
0921 struct get_turns
0922     <
0923         polygon_tag, box_tag,
0924         Polygon, Box,
0925         ReversePolygon, ReverseBox,
0926         TurnPolicy
0927     > : detail::get_turns::get_turns_polygon_cs
0928             <
0929                 Polygon, Box,
0930                 ReversePolygon, ReverseBox,
0931                 TurnPolicy
0932             >
0933 {};
0934
0935
0936 template
0937 <
0938     typename Ring, typename Box,
0939     bool ReverseRing, bool ReverseBox,
0940     typename TurnPolicy
0941 >
0942 struct get_turns
0943     <
0944         ring_tag, box_tag,
0945         Ring, Box,
0946         ReverseRing, ReverseBox,
0947         TurnPolicy
0948     > : detail::get_turns::get_turns_cs
0949             <
0950                 Ring, Box, ReverseRing, ReverseBox,
0951                 TurnPolicy
0952             >
0953
0954 {};
0955
0956
0957 template
0958 <
0959     typename MultiPolygon,
0960     typename Box,
0961     bool ReverseMultiPolygon, bool ReverseBox,
0962     typename TurnPolicy
0963 >
0964 struct get_turns
0965     <
0966         multi_polygon_tag, box_tag,
0967         MultiPolygon, Box,
0968         ReverseMultiPolygon, ReverseBox,
0969         TurnPolicy
0970     >
0971     : detail::get_turns::get_turns_multi_polygon_cs
0972         <
0973             MultiPolygon, Box,
0974             ReverseMultiPolygon, ReverseBox,
0975             TurnPolicy
0976         >
0977 {};
0978
0979
0980 template
0981 <
0982     typename GeometryTag1, typename GeometryTag2,
0983     typename Geometry1, typename Geometry2,
0984     bool Reverse1, bool Reverse2,
0985     typename TurnPolicy
0986 >
0987 struct get_turns_reversed
0988 {
0989     template <typename Strategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
0990     static inline void apply(int source_id1, Geometry1 const& g1,
0991                              int source_id2, Geometry2 const& g2,
0992                              Strategy const& strategy,
0993                              RobustPolicy const& robust_policy,
0994                              Turns& turns,
0995                              InterruptPolicy& interrupt_policy)
0996     {
0997         get_turns
0998             <
0999                 GeometryTag2, GeometryTag1,
1000                 Geometry2, Geometry1,
1001                 Reverse2, Reverse1,
1002                 TurnPolicy
1003             >::apply(source_id2, g2, source_id1, g1,
1004                      strategy, robust_policy,
1005                      turns, interrupt_policy);
1006     }
1007 };
1008
1009
1010 } // namespace dispatch
1011 #endif // DOXYGEN_NO_DISPATCH
1012
1013
1014
1015 /*!
1016 \brief \brief_calc2{turn points}
1017 \ingroup overlay
1018 \tparam Geometry1 \tparam_geometry
1019 \tparam Geometry2 \tparam_geometry
1020 \tparam Turns type of turn-container (e.g. vector of "intersection/turn point"'s)
1021 \param geometry1 \param_geometry
1022 \param geometry2 \param_geometry
1023 \param intersection_strategy segments intersection strategy
1024 \param robust_policy policy to handle robustness issues
1025 \param turns container which will contain turn points
1026 \param interrupt_policy policy determining if process is stopped
1027     when intersection is found
1028  */
1029 template
1030 <
1031     bool Reverse1, bool Reverse2,
1032     typename AssignPolicy,
1033     typename Geometry1,
1034     typename Geometry2,
1035     typename Strategy,
1036     typename RobustPolicy,
1037     typename Turns,
1038     typename InterruptPolicy
1039 >
1040 inline void get_turns(Geometry1 const& geometry1,
1041                       Geometry2 const& geometry2,
1042                       Strategy const& strategy,
1043                       RobustPolicy const& robust_policy,
1044                       Turns& turns,
1045                       InterruptPolicy& interrupt_policy)
1046 {
1047     concepts::check_concepts_and_equal_dimensions<Geometry1 const, Geometry2 const>();
1048
1049     typedef detail::overlay::get_turn_info<AssignPolicy> TurnPolicy;
1050     //typedef detail::get_turns::get_turn_info_type<Geometry1, Geometry2, AssignPolicy> TurnPolicy;
1051
1052     std::conditional_t
1053         <
1054             reverse_dispatch<Geometry1, Geometry2>::type::value,
1055             dispatch::get_turns_reversed
1056             <
1057                 typename tag<Geometry1>::type,
1058                 typename tag<Geometry2>::type,
1059                 Geometry1, Geometry2,
1060                 Reverse1, Reverse2,
1061                 TurnPolicy
1062             >,
1063             dispatch::get_turns
1064             <
1065                 typename tag<Geometry1>::type,
1066                 typename tag<Geometry2>::type,
1067                 Geometry1, Geometry2,
1068                 Reverse1, Reverse2,
1069                 TurnPolicy
1070             >
1071         >::apply(0, geometry1,
1072                  1, geometry2,
1073                  strategy,
1074                  robust_policy,
1075                  turns, interrupt_policy);
1076 }
1077
1078 #if defined(_MSC_VER)
1079 #pragma warning(pop)
1080 #endif
1081
1082 }} // namespace boost::geometry
1083
1084 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP