ceph/src/boost/boost/geometry/algorithms/detail/buffer/turn_in_original_visitor.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2014 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // This file was modified by Oracle on 2016, 2018.
   6 // Modifications copyright (c) 2016-2018 Oracle and/or its affiliates.
   7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   8
   9 // Use, modification and distribution is subject to the Boost Software License,
  10 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  11 // http://www.boost.org/LICENSE_1_0.txt)
  12
  13 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_ORIGINAL_VISITOR
  14 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_ORIGINAL_VISITOR
  15
  16
  17 #include <boost/core/ignore_unused.hpp>
  18 #include <boost/geometry/core/coordinate_type.hpp>
  19
  20 #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp>
  21 #include <boost/geometry/algorithms/expand.hpp>
  22 #include <boost/geometry/strategies/agnostic/point_in_poly_winding.hpp>
  23 #include <boost/geometry/strategies/buffer.hpp>
  24
  25
  26 namespace boost { namespace geometry
  27 {
  28
  29
  30 #ifndef DOXYGEN_NO_DETAIL
  31 namespace detail { namespace buffer
  32 {
  33
  34 struct original_get_box
  35 {
  36     template <typename Box, typename Original>
  37     static inline void apply(Box& total, Original const& original)
  38     {
  39         assert_coordinate_type_equal(total, original.m_box);
  40         typedef typename strategy::expand::services::default_strategy
  41             <
  42                 box_tag, typename cs_tag<Box>::type
  43             >::type expand_strategy_type;
  44
  45         geometry::expand(total, original.m_box, expand_strategy_type());
  46     }
  47 };
  48
  49 template <typename DisjointBoxBoxStrategy>
  50 struct original_overlaps_box
  51 {
  52     template <typename Box, typename Original>
  53     static inline bool apply(Box const& box, Original const& original)
  54     {
  55         assert_coordinate_type_equal(box, original.m_box);
  56         return ! detail::disjoint::disjoint_box_box(box, original.m_box,
  57                                                     DisjointBoxBoxStrategy());
  58     }
  59 };
  60
  61 struct include_turn_policy
  62 {
  63     template <typename Turn>
  64     static inline bool apply(Turn const& turn)
  65     {
  66         return turn.is_turn_traversable;
  67     }
  68 };
  69
  70 template <typename DisjointPointBoxStrategy>
  71 struct turn_in_original_overlaps_box
  72 {
  73     template <typename Box, typename Turn>
  74     static inline bool apply(Box const& box, Turn const& turn)
  75     {
  76         if (! turn.is_turn_traversable || turn.within_original)
  77         {
  78             // Skip all points already processed
  79             return false;
  80         }
  81
  82         return ! geometry::detail::disjoint::disjoint_point_box(
  83                     turn.point, box, DisjointPointBoxStrategy());
  84     }
  85 };
  86
  87 //! Check if specified is in range of specified iterators
  88 //! Return value of strategy (true if we can bail out)
  89 template
  90 <
  91     typename Strategy,
  92     typename State,
  93     typename Point,
  94     typename Iterator
  95 >
  96 inline bool point_in_range(Strategy& strategy, State& state,
  97         Point const& point, Iterator begin, Iterator end)
  98 {
  99     boost::ignore_unused(strategy);
 100
 101     Iterator it = begin;
 102     for (Iterator previous = it++; it != end; ++previous, ++it)
 103     {
 104         if (! strategy.apply(point, *previous, *it, state))
 105         {
 106             // We're probably on the boundary
 107             return false;
 108         }
 109     }
 110     return true;
 111 }
 112
 113 template
 114 <
 115     typename Strategy,
 116     typename State,
 117     typename Point,
 118     typename CoordinateType,
 119     typename Iterator
 120 >
 121 inline bool point_in_section(Strategy& strategy, State& state,
 122         Point const& point, CoordinateType const& point_x,
 123         Iterator begin, Iterator end,
 124         int direction)
 125 {
 126     if (direction == 0)
 127     {
 128         // Not a monotonic section, or no change in X-direction
 129         return point_in_range(strategy, state, point, begin, end);
 130     }
 131
 132     // We're in a monotonic section in x-direction
 133     Iterator it = begin;
 134
 135     for (Iterator previous = it++; it != end; ++previous, ++it)
 136     {
 137         // Depending on sections.direction we can quit for this section
 138         CoordinateType const previous_x = geometry::get<0>(*previous);
 139
 140         if (direction == 1 && point_x < previous_x)
 141         {
 142             // Section goes upwards, x increases, point is is below section
 143             return true;
 144         }
 145         else if (direction == -1 && point_x > previous_x)
 146         {
 147             // Section goes downwards, x decreases, point is above section
 148             return true;
 149         }
 150
 151         if (! strategy.apply(point, *previous, *it, state))
 152         {
 153             // We're probably on the boundary
 154             return false;
 155         }
 156     }
 157     return true;
 158 }
 159
 160
 161 template <typename Point, typename Original, typename PointInGeometryStrategy>
 162 inline int point_in_original(Point const& point, Original const& original,
 163                              PointInGeometryStrategy const& strategy)
 164 {
 165     typename PointInGeometryStrategy::state_type state;
 166
 167     if (boost::size(original.m_sections) == 0
 168         || boost::size(original.m_ring) - boost::size(original.m_sections) < 16)
 169     {
 170         // There are no sections, or it does not profit to walk over sections
 171         // instead of over points. Boundary of 16 is arbitrary but can influence
 172         // performance
 173         point_in_range(strategy, state, point,
 174                 original.m_ring.begin(), original.m_ring.end());
 175         return strategy.result(state);
 176     }
 177
 178     typedef typename Original::sections_type sections_type;
 179     typedef typename boost::range_iterator<sections_type const>::type iterator_type;
 180     typedef typename boost::range_value<sections_type const>::type section_type;
 181     typedef typename geometry::coordinate_type<Point>::type coordinate_type;
 182
 183     coordinate_type const point_x = geometry::get<0>(point);
 184
 185     // Walk through all monotonic sections of this original
 186     for (iterator_type it = boost::begin(original.m_sections);
 187         it != boost::end(original.m_sections);
 188         ++it)
 189     {
 190         section_type const& section = *it;
 191
 192         if (! section.duplicate
 193             && section.begin_index < section.end_index
 194             && point_x >= geometry::get<min_corner, 0>(section.bounding_box)
 195             && point_x <= geometry::get<max_corner, 0>(section.bounding_box))
 196         {
 197             // x-coordinate of point overlaps with section
 198             if (! point_in_section(strategy, state, point, point_x,
 199                     boost::begin(original.m_ring) + section.begin_index,
 200                     boost::begin(original.m_ring) + section.end_index + 1,
 201                     section.directions[0]))
 202             {
 203                 // We're probably on the boundary
 204                 break;
 205             }
 206         }
 207     }
 208
 209     return strategy.result(state);
 210 }
 211
 212
 213 template <typename Turns, typename PointInGeometryStrategy>
 214 class turn_in_original_visitor
 215 {
 216 public:
 217     turn_in_original_visitor(Turns& turns, PointInGeometryStrategy const& strategy)
 218         : m_mutable_turns(turns)
 219         , m_point_in_geometry_strategy(strategy)
 220     {}
 221
 222     template <typename Turn, typename Original>
 223     inline bool apply(Turn const& turn, Original const& original)
 224     {
 225         if (boost::empty(original.m_ring))
 226         {
 227             // Skip empty rings
 228             return true;
 229         }
 230
 231         if (! turn.is_turn_traversable || turn.within_original)
 232         {
 233             // Skip all points already processed
 234             return true;
 235         }
 236
 237         if (geometry::disjoint(turn.point, original.m_box))
 238         {
 239             // Skip all disjoint
 240             return true;
 241         }
 242
 243         int const code = point_in_original(turn.point, original, m_point_in_geometry_strategy);
 244
 245         if (code == -1)
 246         {
 247             return true;
 248         }
 249
 250         Turn& mutable_turn = m_mutable_turns[turn.turn_index];
 251
 252         if (code == 0)
 253         {
 254             // On border of original: always discard
 255             mutable_turn.is_turn_traversable = false;
 256         }
 257
 258         // Point is inside an original ring
 259         if (original.m_is_interior)
 260         {
 261             mutable_turn.count_in_original--;
 262         }
 263         else if (original.m_has_interiors)
 264         {
 265             mutable_turn.count_in_original++;
 266         }
 267         else
 268         {
 269             // It is an exterior ring and there are no interior rings.
 270             // Then we are completely ready with this turn
 271             mutable_turn.within_original = true;
 272             mutable_turn.count_in_original = 1;
 273         }
 274
 275         return true;
 276     }
 277
 278 private :
 279     Turns& m_mutable_turns;
 280     PointInGeometryStrategy const& m_point_in_geometry_strategy;
 281 };
 282
 283
 284 }} // namespace detail::buffer
 285 #endif // DOXYGEN_NO_DETAIL
 286
 287
 288 }} // namespace boost::geometry
 289
 290 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_ORIGINAL_VISITOR