ceph/src/boost/libs/geometry/include/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/assert.hpp>
  16 #include <boost/geometry/core/coordinate_type.hpp>
  17 #include <boost/geometry/core/point_type.hpp>
  18
  19 #include <boost/geometry/policies/compare.hpp>
  20 #include <boost/geometry/iterators/closing_iterator.hpp>
  21
  22 #include <boost/geometry/algorithms/detail/get_left_turns.hpp>
  23
  24
  25 namespace boost { namespace geometry
  26 {
  27
  28
  29 #ifndef DOXYGEN_NO_DETAIL
  30 namespace detail
  31 {
  32
  33 template <typename Point, typename T>
  34 struct angle_info
  35 {
  36     typedef T angle_type;
  37     typedef Point point_type;
  38
  39     segment_identifier seg_id;
  40     std::size_t turn_index;
  41     int operation_index;
  42     std::size_t cluster_index;
  43     Point intersection_point;
  44     Point point; // either incoming or outgoing point
  45     bool incoming;
  46     bool blocked;
  47     bool included;
  48
  49     inline angle_info()
  50         : blocked(false)
  51         , included(false)
  52     {}
  53 };
  54
  55 template <typename AngleInfo>
  56 class occupation_info
  57 {
  58 public :
  59     typedef std::vector<AngleInfo> collection_type;
  60
  61     std::size_t count;
  62
  63     inline occupation_info()
  64         : count(0)
  65     {}
  66
  67     template <typename RobustPoint>
  68     inline void add(RobustPoint const& incoming_point,
  69                     RobustPoint const& outgoing_point,
  70                     RobustPoint const& intersection_point,
  71                     std::size_t turn_index, int operation_index,
  72                     segment_identifier const& seg_id)
  73     {
  74         geometry::equal_to<RobustPoint> comparator;
  75         if (comparator(incoming_point, intersection_point))
  76         {
  77             return;
  78         }
  79         if (comparator(outgoing_point, intersection_point))
  80         {
  81             return;
  82         }
  83
  84         AngleInfo info;
  85         info.seg_id = seg_id;
  86         info.turn_index = turn_index;
  87         info.operation_index = operation_index;
  88         info.intersection_point = intersection_point;
  89
  90         {
  91             info.point = incoming_point;
  92             info.incoming = true;
  93             m_angles.push_back(info);
  94         }
  95         {
  96             info.point = outgoing_point;
  97             info.incoming = false;
  98             m_angles.push_back(info);
  99         }
 100     }
 101
 102     template <typename RobustPoint, typename Turns>
 103     inline void get_left_turns(RobustPoint const& origin, Turns& turns)
 104     {
 105         // Sort on angle
 106         std::sort(m_angles.begin(), m_angles.end(),
 107                 detail::left_turns::angle_less<typename AngleInfo::point_type>(origin));
 108
 109         // Group same-angled elements
 110         std::size_t cluster_size = detail::left_turns::assign_cluster_indices(m_angles, origin);
 111         // Block all turns on the right side of any turn
 112         detail::left_turns::block_turns(m_angles, cluster_size);
 113         detail::left_turns::get_left_turns(m_angles, turns);
 114     }
 115
 116 #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
 117     template <typename RobustPoint>
 118     inline bool has_rounding_issues(RobustPoint const& origin) const
 119     {
 120         return detail::left_turns::has_rounding_issues(angles, origin);
 121     }
 122 #endif
 123
 124 private :
 125     collection_type m_angles; // each turn splitted in incoming/outgoing vectors
 126 };
 127
 128 template<typename Pieces>
 129 inline void move_index(Pieces const& pieces, signed_size_type& index, signed_size_type& piece_index, int direction)
 130 {
 131     BOOST_GEOMETRY_ASSERT(direction == 1 || direction == -1);
 132     BOOST_GEOMETRY_ASSERT(
 133         piece_index >= 0
 134         && piece_index < static_cast<signed_size_type>(boost::size(pieces)) );
 135     BOOST_GEOMETRY_ASSERT(
 136         index >= 0
 137         && index < static_cast<signed_size_type>(boost::size(pieces[piece_index].robust_ring)));
 138
 139     // NOTE: both index and piece_index must be in valid range
 140     // this means that then they could be of type std::size_t
 141     // if the code below was refactored
 142
 143     index += direction;
 144     if (direction == -1 && index < 0)
 145     {
 146         piece_index--;
 147         if (piece_index < 0)
 148         {
 149             piece_index = boost::size(pieces) - 1;
 150         }
 151         index = boost::size(pieces[piece_index].robust_ring) - 1;
 152     }
 153     if (direction == 1
 154         && index >= static_cast<signed_size_type>(boost::size(pieces[piece_index].robust_ring)))
 155     {
 156         piece_index++;
 157         if (piece_index >= static_cast<signed_size_type>(boost::size(pieces)))
 158         {
 159             piece_index = 0;
 160         }
 161         index = 0;
 162     }
 163 }
 164
 165
 166 template
 167 <
 168     typename RobustPoint,
 169     typename Turn,
 170     typename Pieces,
 171     typename Info
 172 >
 173 inline void add_incoming_and_outgoing_angles(
 174                 RobustPoint const& intersection_point, // rescaled
 175                 Turn const& turn,
 176                 Pieces const& pieces, // using rescaled offsets of it
 177                 int operation_index,
 178                 segment_identifier seg_id,
 179                 Info& info)
 180 {
 181     segment_identifier real_seg_id = seg_id;
 182     geometry::equal_to<RobustPoint> comparator;
 183
 184     // Move backward and forward
 185     RobustPoint direction_points[2];
 186     for (int i = 0; i < 2; i++)
 187     {
 188         signed_size_type index = turn.operations[operation_index].index_in_robust_ring;
 189         signed_size_type piece_index = turn.operations[operation_index].piece_index;
 190         while(comparator(pieces[piece_index].robust_ring[index], intersection_point))
 191         {
 192             move_index(pieces, index, piece_index, i == 0 ? -1 : 1);
 193         }
 194         direction_points[i] = pieces[piece_index].robust_ring[index];
 195     }
 196
 197     info.add(direction_points[0], direction_points[1], intersection_point,
 198         turn.turn_index, operation_index, real_seg_id);
 199 }
 200
 201
 202 } // namespace detail
 203 #endif // DOXYGEN_NO_DETAIL
 204
 205
 206 }} // namespace boost::geometry
 207
 208 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP