ceph/src/boost/boost/geometry/algorithms/detail/get_left_turns.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, 2018.
   6 // Modifications copyright (c) 2017-2018, 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_GET_LEFT_TURNS_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_GET_LEFT_TURNS_HPP
  16
  17 #include <set>
  18 #include <vector>
  19
  20 #include <boost/geometry/core/assert.hpp>
  21
  22 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
  23 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
  24 #include <boost/geometry/arithmetic/arithmetic.hpp>
  25 #include <boost/geometry/iterators/closing_iterator.hpp>
  26 #include <boost/geometry/iterators/ever_circling_iterator.hpp>
  27 #include <boost/geometry/strategies/side.hpp>
  28
  29 namespace boost { namespace geometry
  30 {
  31
  32
  33 #ifndef DOXYGEN_NO_DETAIL
  34 namespace detail
  35 {
  36
  37 // TODO: move this to /util/
  38 template <typename T>
  39 inline std::pair<T, T> ordered_pair(T const& first, T const& second)
  40 {
  41     return first < second ? std::make_pair(first, second) : std::make_pair(second, first);
  42 }
  43
  44 namespace left_turns
  45 {
  46
  47
  48
  49 template <typename Vector>
  50 inline int get_quadrant(Vector const& vector)
  51 {
  52     // Return quadrant as layouted in the code below:
  53     // 3 | 0
  54     // -----
  55     // 2 | 1
  56     return geometry::get<1>(vector) >= 0
  57         ? (geometry::get<0>(vector)  < 0 ? 3 : 0)
  58         : (geometry::get<0>(vector)  < 0 ? 2 : 1)
  59         ;
  60 }
  61
  62 template <typename Vector>
  63 inline int squared_length(Vector const& vector)
  64 {
  65     return geometry::get<0>(vector) * geometry::get<0>(vector)
  66          + geometry::get<1>(vector) * geometry::get<1>(vector)
  67          ;
  68 }
  69
  70
  71 template <typename Point, typename SideStrategy>
  72 struct angle_less
  73 {
  74     typedef Point vector_type;
  75
  76     angle_less(Point const& origin, SideStrategy const& strategy)
  77         : m_origin(origin)
  78         , m_strategy(strategy)
  79     {}
  80
  81     template <typename Angle>
  82     inline bool operator()(Angle const& p, Angle const& q) const
  83     {
  84         // Vector origin -> p and origin -> q
  85         vector_type pv = p.point;
  86         vector_type qv = q.point;
  87         geometry::subtract_point(pv, m_origin);
  88         geometry::subtract_point(qv, m_origin);
  89
  90         int const quadrant_p = get_quadrant(pv);
  91         int const quadrant_q = get_quadrant(qv);
  92         if (quadrant_p != quadrant_q)
  93         {
  94             return quadrant_p < quadrant_q;
  95         }
  96         // Same quadrant, check if p is located left of q
  97         int const side = m_strategy.apply(m_origin, q.point, p.point);
  98         if (side != 0)
  99         {
 100             return side == 1;
 101         }
 102         // Collinear, check if one is incoming, incoming angles come first
 103         if (p.incoming != q.incoming)
 104         {
 105             return int(p.incoming) < int(q.incoming);
 106         }
 107         // Same quadrant/side/direction, return longest first
 108         // TODO: maybe not necessary, decide this
 109         int const length_p = squared_length(pv);
 110         int const length_q = squared_length(qv);
 111         if (length_p != length_q)
 112         {
 113             return squared_length(pv) > squared_length(qv);
 114         }
 115         // They are still the same. Just compare on seg_id
 116         return p.seg_id < q.seg_id;
 117     }
 118
 119 private:
 120     Point m_origin;
 121     SideStrategy m_strategy;
 122 };
 123
 124 template <typename Point, typename SideStrategy>
 125 struct angle_equal_to
 126 {
 127     typedef Point vector_type;
 128
 129     inline angle_equal_to(Point const& origin, SideStrategy const& strategy)
 130         : m_origin(origin)
 131         , m_strategy(strategy)
 132     {}
 133
 134     template <typename Angle>
 135     inline bool operator()(Angle const& p, Angle const& q) const
 136     {
 137         // Vector origin -> p and origin -> q
 138         vector_type pv = p.point;
 139         vector_type qv = q.point;
 140         geometry::subtract_point(pv, m_origin);
 141         geometry::subtract_point(qv, m_origin);
 142
 143         if (get_quadrant(pv) != get_quadrant(qv))
 144         {
 145             return false;
 146         }
 147         // Same quadrant, check if p/q are collinear
 148         int const side = m_strategy.apply(m_origin, q.point, p.point);
 149         return side == 0;
 150     }
 151
 152 private:
 153     Point m_origin;
 154     SideStrategy m_strategy;
 155 };
 156
 157 template <typename AngleCollection, typename Turns>
 158 inline void get_left_turns(AngleCollection const& sorted_angles,
 159         Turns& turns)
 160 {
 161     std::set<std::size_t> good_incoming;
 162     std::set<std::size_t> good_outgoing;
 163
 164     for (typename boost::range_iterator<AngleCollection const>::type it =
 165         sorted_angles.begin(); it != sorted_angles.end(); ++it)
 166     {
 167         if (!it->blocked)
 168         {
 169             if (it->incoming)
 170             {
 171                 good_incoming.insert(it->turn_index);
 172             }
 173             else
 174             {
 175                 good_outgoing.insert(it->turn_index);
 176             }
 177         }
 178     }
 179
 180     if (good_incoming.empty() || good_outgoing.empty())
 181     {
 182         return;
 183     }
 184
 185     for (typename boost::range_iterator<AngleCollection const>::type it =
 186         sorted_angles.begin(); it != sorted_angles.end(); ++it)
 187     {
 188         if (good_incoming.count(it->turn_index) == 0
 189             || good_outgoing.count(it->turn_index) == 0)
 190         {
 191             turns[it->turn_index].remove_on_multi = true;
 192         }
 193     }
 194 }
 195
 196
 197 //! Returns the number of clusters
 198 template <typename Point, typename AngleCollection, typename SideStrategy>
 199 inline std::size_t assign_cluster_indices(AngleCollection& sorted, Point const& origin,
 200                                           SideStrategy const& strategy)
 201 {
 202     // Assign same cluster_index for all turns in same direction
 203     BOOST_GEOMETRY_ASSERT(boost::size(sorted) >= 4u);
 204
 205     angle_equal_to<Point, SideStrategy> comparator(origin, strategy);
 206     typename boost::range_iterator<AngleCollection>::type it = sorted.begin();
 207
 208     std::size_t cluster_index = 0;
 209     it->cluster_index = cluster_index;
 210     typename boost::range_iterator<AngleCollection>::type previous = it++;
 211     for (; it != sorted.end(); ++it)
 212     {
 213         if (!comparator(*previous, *it))
 214         {
 215             cluster_index++;
 216             previous = it;
 217         }
 218         it->cluster_index = cluster_index;
 219     }
 220     return cluster_index + 1;
 221 }
 222
 223 template <typename AngleCollection>
 224 inline void block_turns(AngleCollection& sorted, std::size_t cluster_size)
 225 {
 226     BOOST_GEOMETRY_ASSERT(boost::size(sorted) >= 4u && cluster_size > 0);
 227
 228     std::vector<std::pair<bool, bool> > directions;
 229     for (std::size_t i = 0; i < cluster_size; i++)
 230     {
 231         directions.push_back(std::make_pair(false, false));
 232     }
 233
 234     for (typename boost::range_iterator<AngleCollection const>::type it = sorted.begin();
 235         it != sorted.end(); ++it)
 236     {
 237         if (it->incoming)
 238         {
 239             directions[it->cluster_index].first = true;
 240         }
 241         else
 242         {
 243             directions[it->cluster_index].second = true;
 244         }
 245     }
 246
 247     for (typename boost::range_iterator<AngleCollection>::type it = sorted.begin();
 248         it != sorted.end(); ++it)
 249     {
 250         std::size_t const cluster_index = it->cluster_index;
 251         std::size_t const previous_index
 252                 = cluster_index == 0 ? cluster_size - 1 : cluster_index - 1;
 253         std::size_t const next_index
 254                 = cluster_index + 1 >= cluster_size ? 0 : cluster_index + 1;
 255
 256         if (directions[cluster_index].first
 257             && directions[cluster_index].second)
 258         {
 259             it->blocked = true;
 260         }
 261         else if (!directions[cluster_index].first
 262             && directions[cluster_index].second
 263             && directions[previous_index].second)
 264         {
 265             // Only outgoing, previous was also outgoing: block this one
 266             it->blocked = true;
 267         }
 268         else if (directions[cluster_index].first
 269             && !directions[cluster_index].second
 270             && !directions[previous_index].first
 271             && directions[previous_index].second)
 272         {
 273             // Only incoming, previous was only outgoing: block this one
 274             it->blocked = true;
 275         }
 276         else if (directions[cluster_index].first
 277             && !directions[cluster_index].second
 278             && directions[next_index].first
 279             && !directions[next_index].second)
 280         {
 281             // Only incoming, next also incoming, block this one
 282             it->blocked = true;
 283         }
 284     }
 285 }
 286
 287 #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
 288 template <typename AngleCollection, typename Point>
 289 inline bool has_rounding_issues(AngleCollection const& angles, Point const& origin)
 290 {
 291     for (typename boost::range_iterator<AngleCollection const>::type it =
 292         angles.begin(); it != angles.end(); ++it)
 293     {
 294         // Vector origin -> p and origin -> q
 295         typedef Point vector_type;
 296         vector_type v = it->point;
 297         geometry::subtract_point(v, origin);
 298         return geometry::math::abs(geometry::get<0>(v)) <= 1
 299             || geometry::math::abs(geometry::get<1>(v)) <= 1
 300             ;
 301     }
 302     return false;
 303 }
 304 #endif
 305
 306
 307 }  // namespace left_turns
 308
 309 } // namespace detail
 310 #endif // DOXYGEN_NO_DETAIL
 311
 312
 313 }} // namespace boost::geometry
 314
 315 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_GET_LEFT_TURNS_HPP