boost/geometry/algorithms/detail/occupation_info.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // Use, modification and distribution is subject to the Boost Software License,
   6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP
  10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP
  11
  12 #include <algorithm>
  13 #include <boost/range.hpp>
  14
  15 #include <boost/geometry/core/coordinate_type.hpp>
  16 #include <boost/geometry/core/point_type.hpp>
  17
  18 #include <boost/geometry/policies/compare.hpp>
  19 #include <boost/geometry/iterators/closing_iterator.hpp>
  20
  21 #include <boost/geometry/algorithms/detail/get_left_turns.hpp>
  22
  23
  24 namespace boost { namespace geometry
  25 {
  26
  27
  28 #ifndef DOXYGEN_NO_DETAIL
  29 namespace detail
  30 {
  31
  32 template <typename Point, typename T>
  33 struct angle_info
  34 {
  35     typedef T angle_type;
  36     typedef Point point_type;
  37
  38     segment_identifier seg_id;
  39     int turn_index;
  40     int operation_index;
  41     std::size_t cluster_index;
  42     Point intersection_point;
  43     Point point; // either incoming or outgoing point
  44     bool incoming;
  45     bool blocked;
  46     bool included;
  47
  48     inline angle_info()
  49         : blocked(false)
  50         , included(false)
  51     {}
  52 };
  53
  54 template <typename AngleInfo>
  55 class occupation_info
  56 {
  57 public :
  58     typedef std::vector<AngleInfo> collection_type;
  59
  60     template <typename RobustPoint>
  61     inline void add(RobustPoint const& incoming_point,
  62                     RobustPoint const& outgoing_point,
  63                     RobustPoint const& intersection_point,
  64                     int turn_index, int operation_index,
  65                     segment_identifier const& seg_id)
  66     {
  67         geometry::equal_to<RobustPoint> comparator;
  68         if (comparator(incoming_point, intersection_point))
  69         {
  70             return;
  71         }
  72         if (comparator(outgoing_point, intersection_point))
  73         {
  74             return;
  75         }
  76
  77         AngleInfo info;
  78         info.seg_id = seg_id;
  79         info.turn_index = turn_index;
  80         info.operation_index = operation_index;
  81         info.intersection_point = intersection_point;
  82
  83         {
  84             info.point = incoming_point;
  85             info.incoming = true;
  86             m_angles.push_back(info);
  87         }
  88         {
  89             info.point = outgoing_point;
  90             info.incoming = false;
  91             m_angles.push_back(info);
  92         }
  93     }
  94
  95     template <typename RobustPoint, typename Turns>
  96     inline void get_left_turns(RobustPoint const& origin, Turns& turns)
  97     {
  98         // Sort on angle
  99         std::sort(m_angles.begin(), m_angles.end(),
 100                 detail::left_turns::angle_less<typename AngleInfo::point_type>(origin));
 101
 102         // Group same-angled elements
 103         std::size_t cluster_size = detail::left_turns::assign_cluster_indices(m_angles, origin);
 104         // Block all turns on the right side of any turn
 105         detail::left_turns::block_turns(m_angles, cluster_size);
 106         detail::left_turns::get_left_turns(m_angles, turns);
 107     }
 108
 109 #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
 110     template <typename RobustPoint>
 111     inline bool has_rounding_issues(RobustPoint const& origin) const
 112     {
 113         return detail::left_turns::has_rounding_issues(angles, origin);
 114     }
 115 #endif
 116
 117 private :
 118     collection_type m_angles; // each turn splitted in incoming/outgoing vectors
 119 };
 120
 121 template<typename Pieces>
 122 inline void move_index(Pieces const& pieces, int& index, int& piece_index, int direction)
 123 {
 124     BOOST_ASSERT(direction == 1 || direction == -1);
 125     BOOST_ASSERT(piece_index >= 0 && piece_index < static_cast<int>(boost::size(pieces)) );
 126     BOOST_ASSERT(index >= 0 && index < static_cast<int>(boost::size(pieces[piece_index].robust_ring)));
 127
 128     index += direction;
 129     if (direction == -1 && index < 0)
 130     {
 131         piece_index--;
 132         if (piece_index < 0)
 133         {
 134             piece_index = boost::size(pieces) - 1;
 135         }
 136         index = boost::size(pieces[piece_index].robust_ring) - 1;
 137     }
 138     if (direction == 1
 139         && index >= static_cast<int>(boost::size(pieces[piece_index].robust_ring)))
 140     {
 141         piece_index++;
 142         if (piece_index >= static_cast<int>(boost::size(pieces)))
 143         {
 144             piece_index = 0;
 145         }
 146         index = 0;
 147     }
 148 }
 149
 150
 151 template
 152 <
 153     typename RobustPoint,
 154     typename Turn,
 155     typename Pieces,
 156     typename Info
 157 >
 158 inline void add_incoming_and_outgoing_angles(
 159                 RobustPoint const& intersection_point, // rescaled
 160                 Turn const& turn,
 161                 Pieces const& pieces, // using rescaled offsets of it
 162                 int operation_index,
 163                 segment_identifier seg_id,
 164                 Info& info)
 165 {
 166     segment_identifier real_seg_id = seg_id;
 167     geometry::equal_to<RobustPoint> comparator;
 168
 169     // Move backward and forward
 170     RobustPoint direction_points[2];
 171     for (int i = 0; i < 2; i++)
 172     {
 173         int index = turn.operations[operation_index].index_in_robust_ring;
 174         int piece_index = turn.operations[operation_index].piece_index;
 175         while(comparator(pieces[piece_index].robust_ring[index], intersection_point))
 176         {
 177             move_index(pieces, index, piece_index, i == 0 ? -1 : 1);
 178         }
 179         direction_points[i] = pieces[piece_index].robust_ring[index];
 180     }
 181
 182     info.add(direction_points[0], direction_points[1], intersection_point,
 183         turn.turn_index, operation_index, real_seg_id);
 184 }
 185
 186
 187 } // namespace detail
 188 #endif // DOXYGEN_NO_DETAIL
 189
 190
 191 }} // namespace boost::geometry
 192
 193 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP