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
  19 #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp>
  20 #include <boost/geometry/algorithms/expand.hpp>
  21 #include <boost/geometry/strategies/agnostic/point_in_poly_winding.hpp>
  22 #include <boost/geometry/strategies/buffer.hpp>
  23
  24
  25 namespace boost { namespace geometry
  26 {
  27
  28
  29 #ifndef DOXYGEN_NO_DETAIL
  30 namespace detail { namespace buffer
  31 {
  32
  33 struct original_get_box
  34 {
  35     template <typename Box, typename Original>
  36     static inline void apply(Box& total, Original const& original)
  37     {
  38         geometry::expand(total, original.m_box);
  39     }
  40 };
  41
  42 template <typename DisjointBoxBoxStrategy>
  43 struct original_ovelaps_box
  44 {
  45     template <typename Box, typename Original>
  46     static inline bool apply(Box const& box, Original const& original)
  47     {
  48         return ! detail::disjoint::disjoint_box_box(box, original.m_box,
  49                                                     DisjointBoxBoxStrategy());
  50     }
  51 };
  52
  53 struct include_turn_policy
  54 {
  55     template <typename Turn>
  56     static inline bool apply(Turn const& turn)
  57     {
  58         return turn.location == location_ok;
  59     }
  60 };
  61
  62 template <typename DisjointPointBoxStrategy>
  63 struct turn_in_original_ovelaps_box
  64 {
  65     template <typename Box, typename Turn>
  66     static inline bool apply(Box const& box, Turn const& turn)
  67     {
  68         if (turn.location != location_ok || turn.within_original)
  69         {
  70             // Skip all points already processed
  71             return false;
  72         }
  73
  74         return ! geometry::detail::disjoint::disjoint_point_box(
  75                     turn.robust_point, box, DisjointPointBoxStrategy());
  76     }
  77 };
  78
  79 //! Check if specified is in range of specified iterators
  80 //! Return value of strategy (true if we can bail out)
  81 template
  82 <
  83     typename Strategy,
  84     typename State,
  85     typename Point,
  86     typename Iterator
  87 >
  88 inline bool point_in_range(Strategy& strategy, State& state,
  89         Point const& point, Iterator begin, Iterator end)
  90 {
  91     boost::ignore_unused(strategy);
  92
  93     Iterator it = begin;
  94     for (Iterator previous = it++; it != end; ++previous, ++it)
  95     {
  96         if (! strategy.apply(point, *previous, *it, state))
  97         {
  98             // We're probably on the boundary
  99             return false;
 100         }
 101     }
 102     return true;
 103 }
 104
 105 template
 106 <
 107     typename Strategy,
 108     typename State,
 109     typename Point,
 110     typename CoordinateType,
 111     typename Iterator
 112 >
 113 inline bool point_in_section(Strategy& strategy, State& state,
 114         Point const& point, CoordinateType const& point_x,
 115         Iterator begin, Iterator end,
 116         int direction)
 117 {
 118     if (direction == 0)
 119     {
 120         // Not a monotonic section, or no change in X-direction
 121         return point_in_range(strategy, state, point, begin, end);
 122     }
 123
 124     // We're in a monotonic section in x-direction
 125     Iterator it = begin;
 126
 127     for (Iterator previous = it++; it != end; ++previous, ++it)
 128     {
 129         // Depending on sections.direction we can quit for this section
 130         CoordinateType const previous_x = geometry::get<0>(*previous);
 131
 132         if (direction == 1 && point_x < previous_x)
 133         {
 134             // Section goes upwards, x increases, point is is below section
 135             return true;
 136         }
 137         else if (direction == -1 && point_x > previous_x)
 138         {
 139             // Section goes downwards, x decreases, point is above section
 140             return true;
 141         }
 142
 143         if (! strategy.apply(point, *previous, *it, state))
 144         {
 145             // We're probably on the boundary
 146             return false;
 147         }
 148     }
 149     return true;
 150 }
 151
 152
 153 template <typename Point, typename Original, typename PointInGeometryStrategy>
 154 inline int point_in_original(Point const& point, Original const& original,
 155                              PointInGeometryStrategy const& strategy)
 156 {
 157     typename PointInGeometryStrategy::state_type state;
 158
 159     if (boost::size(original.m_sections) == 0
 160         || boost::size(original.m_ring) - boost::size(original.m_sections) < 16)
 161     {
 162         // There are no sections, or it does not profit to walk over sections
 163         // instead of over points. Boundary of 16 is arbitrary but can influence
 164         // performance
 165         point_in_range(strategy, state, point,
 166                 original.m_ring.begin(), original.m_ring.end());
 167         return strategy.result(state);
 168     }
 169
 170     typedef typename Original::sections_type sections_type;
 171     typedef typename boost::range_iterator<sections_type const>::type iterator_type;
 172     typedef typename boost::range_value<sections_type const>::type section_type;
 173     typedef typename geometry::coordinate_type<Point>::type coordinate_type;
 174
 175     coordinate_type const point_x = geometry::get<0>(point);
 176
 177     // Walk through all monotonic sections of this original
 178     for (iterator_type it = boost::begin(original.m_sections);
 179         it != boost::end(original.m_sections);
 180         ++it)
 181     {
 182         section_type const& section = *it;
 183
 184         if (! section.duplicate
 185             && section.begin_index < section.end_index
 186             && point_x >= geometry::get<min_corner, 0>(section.bounding_box)
 187             && point_x <= geometry::get<max_corner, 0>(section.bounding_box))
 188         {
 189             // x-coordinate of point overlaps with section
 190             if (! point_in_section(strategy, state, point, point_x,
 191                     boost::begin(original.m_ring) + section.begin_index,
 192                     boost::begin(original.m_ring) + section.end_index + 1,
 193                     section.directions[0]))
 194             {
 195                 // We're probably on the boundary
 196                 break;
 197             }
 198         }
 199     }
 200
 201     return strategy.result(state);
 202 }
 203
 204
 205 template <typename Turns, typename PointInGeometryStrategy>
 206 class turn_in_original_visitor
 207 {
 208 public:
 209     turn_in_original_visitor(Turns& turns, PointInGeometryStrategy const& strategy)
 210         : m_mutable_turns(turns)
 211         , m_point_in_geometry_strategy(strategy)
 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(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, m_point_in_geometry_strategy);
 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     PointInGeometryStrategy const& m_point_in_geometry_strategy;
 269 };
 270
 271
 272 }} // namespace detail::buffer
 273 #endif // DOXYGEN_NO_DETAIL
 274
 275
 276 }} // namespace boost::geometry
 277
 278 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_ORIGINAL_VISITOR