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