text: // Boost.Geometry (aka GGL, Generic Geometry Library)
  
  // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands.
  // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
  
  // This file was modified by Oracle on 2017, 2018.
  // Modifications copyright (c) 2017-2018 Oracle and/or its affiliates.
  // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  
  // Use, modification and distribution is subject to the Boost Software License,
  // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  // http://www.boost.org/LICENSE_1_0.txt)
  
  #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_GET_PIECE_TURNS_HPP
  #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_GET_PIECE_TURNS_HPP
  
  #include <boost/core/ignore_unused.hpp>
  #include <boost/range.hpp>
  
  #include <boost/geometry/core/assert.hpp>
  #include <boost/geometry/algorithms/equals.hpp>
  #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
  #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
  #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
  #include <boost/geometry/algorithms/detail/sections/section_functions.hpp>
  #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp>
  
  
  namespace boost { namespace geometry
  {
  
  
  #ifndef DOXYGEN_NO_DETAIL
  namespace detail { namespace buffer
  {
  
  // Implements a unique_sub_range for a buffered piece,
  // the range can return subsequent points
  // known as "i", "j" and "k" (and further),  indexed as 0,1,2,3
  template <typename Ring>
  struct unique_sub_range_from_piece
  {
      typedef typename boost::range_iterator<Ring const>::type iterator_type;
      typedef typename geometry::point_type<Ring const>::type point_type;
  
      unique_sub_range_from_piece(Ring const& ring,
                                  iterator_type iterator_at_i, iterator_type iterator_at_j)
          : m_ring(ring)
          , m_iterator_at_i(iterator_at_i)
          , m_iterator_at_j(iterator_at_j)
          , m_point_retrieved(false)
      {}
  
      static inline bool is_first_segment() { return false; }
      static inline bool is_last_segment() { return false; }
  
      static inline std::size_t size() { return 3u; }
  
      inline point_type const& at(std::size_t index) const
      {
          BOOST_GEOMETRY_ASSERT(index < size());
          switch (index)
          {
              case 0 : return *m_iterator_at_i;
              case 1 : return *m_iterator_at_j;
              case 2 : return get_point_k();
              default : return *m_iterator_at_i;
          }
      }
  
  private :
  
      inline point_type const& get_point_k() const
      {
          if (! m_point_retrieved)
          {
              m_iterator_at_k = advance_one(m_iterator_at_j);
              m_point_retrieved = true;
          }
          return *m_iterator_at_k;
      }
  
      inline void circular_advance_one(iterator_type& next) const
      {
          ++next;
          if (next == boost::end(m_ring))
          {
              next = boost::begin(m_ring) + 1;
          }
      }
  
      inline iterator_type advance_one(iterator_type it) const
      {
          iterator_type result = it;
          circular_advance_one(result);
  
          // TODO: we could also use piece-boundaries
          // to check if the point equals the last one
          while (geometry::equals(*it, *result))
          {
              circular_advance_one(result);
          }
          return result;
      }
  
      Ring const& m_ring;
      iterator_type m_iterator_at_i;
      iterator_type m_iterator_at_j;
      mutable iterator_type m_iterator_at_k;
      mutable bool m_point_retrieved;
  };
  
  template
  <
      typename Pieces,
      typename Rings,
      typename Turns,
      typename IntersectionStrategy,
      typename RobustPolicy
  >
  class piece_turn_visitor
  {
      Pieces const& m_pieces;
      Rings const& m_rings;
      Turns& m_turns;
      IntersectionStrategy const& m_intersection_strategy;
      RobustPolicy const& m_robust_policy;
  
      template <typename Piece>
      inline bool is_adjacent(Piece const& piece1, Piece const& piece2) const
      {
          if (piece1.first_seg_id.multi_index != piece2.first_seg_id.multi_index)
          {
              return false;
          }
  
          return piece1.index == piece2.left_index
              || piece1.index == piece2.right_index;
      }
  
      template <typename Piece>
      inline bool is_on_same_convex_ring(Piece const& piece1, Piece const& piece2) const
      {
          if (piece1.first_seg_id.multi_index != piece2.first_seg_id.multi_index)
          {
              return false;
          }
  
          return ! m_rings[piece1.first_seg_id.multi_index].has_concave;
      }
  
  
      template <std::size_t Dimension, typename Iterator, typename Box>
      inline void move_begin_iterator(Iterator& it_begin, Iterator it_beyond,
                                      signed_size_type& index, int dir,
                                      Box const& this_bounding_box,
                                      Box const& other_bounding_box)
      {
          for(; it_begin != it_beyond
                  && it_begin + 1 != it_beyond
                  && detail::section::preceding<Dimension>(dir, *(it_begin + 1),
                                                           this_bounding_box,
                                                           other_bounding_box,
                                                           m_robust_policy);
              ++it_begin, index++)
          {}
      }
  
      template <std::size_t Dimension, typename Iterator, typename Box>
      inline void move_end_iterator(Iterator it_begin, Iterator& it_beyond,
                                    int dir, Box const& this_bounding_box,
                                    Box const& other_bounding_box)
      {
          while (it_beyond != it_begin
              && it_beyond - 1 != it_begin
              && it_beyond - 2 != it_begin)
          {
              if (detail::section::exceeding<Dimension>(dir, *(it_beyond - 2),
                          this_bounding_box, other_bounding_box, m_robust_policy))
              {
                  --it_beyond;
              }
              else
              {
                  return;
              }
          }
      }
  
      template <typename Piece, typename Section>
      inline void calculate_turns(Piece const& piece1, Piece const& piece2,
          Section const& section1, Section const& section2)
      {
          typedef typename boost::range_value<Rings const>::type ring_type;
          typedef typename boost::range_value<Turns const>::type turn_type;
          typedef typename boost::range_iterator<ring_type const>::type iterator;
  
          signed_size_type const piece1_first_index = piece1.first_seg_id.segment_index;
          signed_size_type const piece2_first_index = piece2.first_seg_id.segment_index;
          if (piece1_first_index < 0 || piece2_first_index < 0)
          {
              return;
          }
  
          // Get indices of part of offsetted_rings for this monotonic section:
          signed_size_type const sec1_first_index = piece1_first_index + section1.begin_index;
          signed_size_type const sec2_first_index = piece2_first_index + section2.begin_index;
  
          // index of last point in section, beyond-end is one further
          signed_size_type const sec1_last_index = piece1_first_index + section1.end_index;
          signed_size_type const sec2_last_index = piece2_first_index + section2.end_index;
  
          // get geometry and iterators over these sections
          ring_type const& ring1 = m_rings[piece1.first_seg_id.multi_index];
          iterator it1_first = boost::begin(ring1) + sec1_first_index;
          iterator it1_beyond = boost::begin(ring1) + sec1_last_index + 1;
  
          ring_type const& ring2 = m_rings[piece2.first_seg_id.multi_index];
          iterator it2_first = boost::begin(ring2) + sec2_first_index;
          iterator it2_beyond = boost::begin(ring2) + sec2_last_index + 1;
  
          // Set begin/end of monotonic ranges, in both x/y directions
          signed_size_type index1 = sec1_first_index;
          move_begin_iterator<0>(it1_first, it1_beyond, index1,
                      section1.directions[0], section1.bounding_box, section2.bounding_box);
          move_end_iterator<0>(it1_first, it1_beyond,
                      section1.directions[0], section1.bounding_box, section2.bounding_box);
          move_begin_iterator<1>(it1_first, it1_beyond, index1,
                      section1.directions[1], section1.bounding_box, section2.bounding_box);
          move_end_iterator<1>(it1_first, it1_beyond,
                      section1.directions[1], section1.bounding_box, section2.bounding_box);
  
          signed_size_type index2 = sec2_first_index;
          move_begin_iterator<0>(it2_first, it2_beyond, index2,
                      section2.directions[0], section2.bounding_box, section1.bounding_box);
          move_end_iterator<0>(it2_first, it2_beyond,
                      section2.directions[0], section2.bounding_box, section1.bounding_box);
          move_begin_iterator<1>(it2_first, it2_beyond, index2,
                      section2.directions[1], section2.bounding_box, section1.bounding_box);
          move_end_iterator<1>(it2_first, it2_beyond,
                      section2.directions[1], section2.bounding_box, section1.bounding_box);
  
          turn_type the_model;
          the_model.operations[0].piece_index = piece1.index;
          the_model.operations[0].seg_id = piece1.first_seg_id;
          the_model.operations[0].seg_id.segment_index = index1; // override
  
          iterator it1 = it1_first;
          for (iterator prev1 = it1++;
                  it1 != it1_beyond;
                  prev1 = it1++, the_model.operations[0].seg_id.segment_index++)
          {
              the_model.operations[1].piece_index = piece2.index;
              the_model.operations[1].seg_id = piece2.first_seg_id;
              the_model.operations[1].seg_id.segment_index = index2; // override
              geometry::recalculate(the_model.rob_pi, *prev1, m_robust_policy);
              geometry::recalculate(the_model.rob_pj, *it1, m_robust_policy);
  
              unique_sub_range_from_piece<ring_type> unique_sub_range1(ring1, prev1, it1);
  
              iterator it2 = it2_first;
              for (iterator prev2 = it2++;
                      it2 != it2_beyond;
                      prev2 = it2++, the_model.operations[1].seg_id.segment_index++)
              {
                  unique_sub_range_from_piece<ring_type> unique_sub_range2(ring2, prev2, it2);
                  geometry::recalculate(the_model.rob_qi, *prev2, m_robust_policy);
                  geometry::recalculate(the_model.rob_qj, *it2, m_robust_policy);
  
                  // TODO: internally get_turn_info calculates robust points.
                  // But they are already calculated.
                  // We should be able to use them.
                  // this means passing them to this visitor,
                  // and iterating in sync with them...
                  typedef detail::overlay::get_turn_info
                      <
                          detail::overlay::assign_null_policy
                      > turn_policy;
  
                  turn_policy::apply(unique_sub_range1, unique_sub_range2,
                                     the_model,
                                     m_intersection_strategy,
                                     m_robust_policy,
                                     std::back_inserter(m_turns));
              }
          }
      }
  
  public:
  
      piece_turn_visitor(Pieces const& pieces,
              Rings const& ring_collection,
              Turns& turns,
              IntersectionStrategy const& intersection_strategy,
              RobustPolicy const& robust_policy)
          : m_pieces(pieces)
          , m_rings(ring_collection)
          , m_turns(turns)
          , m_intersection_strategy(intersection_strategy)
          , m_robust_policy(robust_policy)
      {}
  
      template <typename Section>
      inline bool apply(Section const& section1, Section const& section2,
                      bool first = true)
      {
          boost::ignore_unused(first);
  
          typedef typename boost::range_value<Pieces const>::type piece_type;
          piece_type const& piece1 = m_pieces[section1.ring_id.source_index];
          piece_type const& piece2 = m_pieces[section2.ring_id.source_index];
  
          if ( piece1.index == piece2.index
            || is_adjacent(piece1, piece2)
            || is_on_same_convex_ring(piece1, piece2)
            || detail::disjoint::disjoint_box_box(section1.bounding_box,
                                                  section2.bounding_box,
                                                  m_intersection_strategy.get_disjoint_box_box_strategy()) )
          {
              return true;
          }
  
          calculate_turns(piece1, piece2, section1, section2);
  
          return true;
      }
  };
  
  
  }} // namespace detail::buffer
  #endif // DOXYGEN_NO_DETAIL
  
  
  }} // namespace boost::geometry
  
  #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_GET_PIECE_TURNS_HPP
  