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