Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@101: // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP
Chris@16: #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP
Chris@16: 
Chris@16: #include <algorithm>
Chris@16: #include <boost/range.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/core/coordinate_type.hpp>
Chris@16: #include <boost/geometry/core/point_type.hpp>
Chris@16: 
Chris@101: #include <boost/geometry/policies/compare.hpp>
Chris@16: #include <boost/geometry/iterators/closing_iterator.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/algorithms/detail/get_left_turns.hpp>
Chris@16: 
Chris@16: 
Chris@16: namespace boost { namespace geometry
Chris@16: {
Chris@16: 
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_DETAIL
Chris@16: namespace detail
Chris@16: {
Chris@16: 
Chris@16: template <typename Point, typename T>
Chris@16: struct angle_info
Chris@16: {
Chris@16:     typedef T angle_type;
Chris@16:     typedef Point point_type;
Chris@16: 
Chris@16:     segment_identifier seg_id;
Chris@16:     int turn_index;
Chris@16:     int operation_index;
Chris@101:     std::size_t cluster_index;
Chris@16:     Point intersection_point;
Chris@101:     Point point; // either incoming or outgoing point
Chris@16:     bool incoming;
Chris@101:     bool blocked;
Chris@101:     bool included;
Chris@101: 
Chris@101:     inline angle_info()
Chris@101:         : blocked(false)
Chris@101:         , included(false)
Chris@101:     {}
Chris@16: };
Chris@16: 
Chris@16: template <typename AngleInfo>
Chris@16: class occupation_info
Chris@16: {
Chris@101: public :
Chris@16:     typedef std::vector<AngleInfo> collection_type;
Chris@16: 
Chris@101:     int count;
Chris@16: 
Chris@16:     inline occupation_info()
Chris@101:         : count(0)
Chris@16:     {}
Chris@16: 
Chris@101:     template <typename RobustPoint>
Chris@101:     inline void add(RobustPoint const& incoming_point,
Chris@101:                     RobustPoint const& outgoing_point,
Chris@101:                     RobustPoint const& intersection_point,
Chris@16:                     int turn_index, int operation_index,
Chris@101:                     segment_identifier const& seg_id)
Chris@16:     {
Chris@101:         geometry::equal_to<RobustPoint> comparator;
Chris@101:         if (comparator(incoming_point, intersection_point))
Chris@16:         {
Chris@101:             return;
Chris@101:         }
Chris@101:         if (comparator(outgoing_point, intersection_point))
Chris@101:         {
Chris@16:             return;
Chris@16:         }
Chris@16: 
Chris@16:         AngleInfo info;
Chris@16:         info.seg_id = seg_id;
Chris@16:         info.turn_index = turn_index;
Chris@16:         info.operation_index = operation_index;
Chris@16:         info.intersection_point = intersection_point;
Chris@16: 
Chris@101:         {
Chris@101:             info.point = incoming_point;
Chris@101:             info.incoming = true;
Chris@101:             m_angles.push_back(info);
Chris@101:         }
Chris@101:         {
Chris@101:             info.point = outgoing_point;
Chris@101:             info.incoming = false;
Chris@101:             m_angles.push_back(info);
Chris@101:         }
Chris@16:     }
Chris@16: 
Chris@101:     template <typename RobustPoint, typename Turns>
Chris@101:     inline void get_left_turns(RobustPoint const& origin, Turns& turns)
Chris@16:     {
Chris@101:         // Sort on angle
Chris@101:         std::sort(m_angles.begin(), m_angles.end(),
Chris@101:                 detail::left_turns::angle_less<typename AngleInfo::point_type>(origin));
Chris@101: 
Chris@101:         // Group same-angled elements
Chris@101:         std::size_t cluster_size = detail::left_turns::assign_cluster_indices(m_angles, origin);
Chris@101:         // Block all turns on the right side of any turn
Chris@101:         detail::left_turns::block_turns(m_angles, cluster_size);
Chris@101:         detail::left_turns::get_left_turns(m_angles, turns);
Chris@16:     }
Chris@16: 
Chris@101: #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
Chris@101:     template <typename RobustPoint>
Chris@101:     inline bool has_rounding_issues(RobustPoint const& origin) const
Chris@16:     {
Chris@101:         return detail::left_turns::has_rounding_issues(angles, origin);
Chris@16:     }
Chris@101: #endif
Chris@101: 
Chris@101: private :
Chris@101:     collection_type m_angles; // each turn splitted in incoming/outgoing vectors
Chris@16: };
Chris@16: 
Chris@101: template<typename Pieces>
Chris@101: inline void move_index(Pieces const& pieces, int& index, int& piece_index, int direction)
Chris@101: {
Chris@101:     BOOST_ASSERT(direction == 1 || direction == -1);
Chris@101:     BOOST_ASSERT(piece_index >= 0 && piece_index < static_cast<int>(boost::size(pieces)) );
Chris@101:     BOOST_ASSERT(index >= 0 && index < static_cast<int>(boost::size(pieces[piece_index].robust_ring)));
Chris@16: 
Chris@101:     index += direction;
Chris@101:     if (direction == -1 && index < 0)
Chris@101:     {
Chris@101:         piece_index--;
Chris@101:         if (piece_index < 0)
Chris@101:         {
Chris@101:             piece_index = boost::size(pieces) - 1;
Chris@101:         }
Chris@101:         index = boost::size(pieces[piece_index].robust_ring) - 1;
Chris@101:     }
Chris@101:     if (direction == 1
Chris@101:         && index >= static_cast<int>(boost::size(pieces[piece_index].robust_ring)))
Chris@101:     {
Chris@101:         piece_index++;
Chris@101:         if (piece_index >= static_cast<int>(boost::size(pieces)))
Chris@101:         {
Chris@101:             piece_index = 0;
Chris@101:         }
Chris@101:         index = 0;
Chris@101:     }
Chris@101: }
Chris@101: 
Chris@101: 
Chris@101: template
Chris@101: <
Chris@101:     typename RobustPoint,
Chris@101:     typename Turn,
Chris@101:     typename Pieces,
Chris@101:     typename Info
Chris@101: >
Chris@101: inline void add_incoming_and_outgoing_angles(
Chris@101:                 RobustPoint const& intersection_point, // rescaled
Chris@101:                 Turn const& turn,
Chris@101:                 Pieces const& pieces, // using rescaled offsets of it
Chris@16:                 int operation_index,
Chris@16:                 segment_identifier seg_id,
Chris@16:                 Info& info)
Chris@16: {
Chris@101:     segment_identifier real_seg_id = seg_id;
Chris@101:     geometry::equal_to<RobustPoint> comparator;
Chris@16: 
Chris@101:     // Move backward and forward
Chris@101:     RobustPoint direction_points[2];
Chris@101:     for (int i = 0; i < 2; i++)
Chris@16:     {
Chris@101:         int index = turn.operations[operation_index].index_in_robust_ring;
Chris@101:         int piece_index = turn.operations[operation_index].piece_index;
Chris@101:         while(comparator(pieces[piece_index].robust_ring[index], intersection_point))
Chris@101:         {
Chris@101:             move_index(pieces, index, piece_index, i == 0 ? -1 : 1);
Chris@101:         }
Chris@101:         direction_points[i] = pieces[piece_index].robust_ring[index];
Chris@16:     }
Chris@16: 
Chris@101:     info.add(direction_points[0], direction_points[1], intersection_point,
Chris@101:         turn.turn_index, operation_index, real_seg_id);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: } // namespace detail
Chris@16: #endif // DOXYGEN_NO_DETAIL
Chris@16: 
Chris@16: 
Chris@16: }} // namespace boost::geometry
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP