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