1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2014 Barend Gehrels, Amsterdam, the Netherlands.
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
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)
13 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_ORIGINAL_VISITOR
14 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_ORIGINAL_VISITOR
17 #include <boost/core/ignore_unused.hpp>
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>
24 namespace boost { namespace geometry
28 #ifndef DOXYGEN_NO_DETAIL
29 namespace detail { namespace buffer
32 struct original_get_box
34 template <typename Box, typename Original>
35 static inline void apply(Box& total, Original const& original)
37 geometry::expand(total, original.m_box);
41 struct original_ovelaps_box
43 template <typename Box, typename Original>
44 static inline bool apply(Box const& box, Original const& original)
46 return ! detail::disjoint::disjoint_box_box(box, original.m_box);
50 struct include_turn_policy
52 template <typename Turn>
53 static inline bool apply(Turn const& turn)
55 return turn.location == location_ok;
59 struct turn_in_original_ovelaps_box
61 template <typename Box, typename Turn>
62 static inline bool apply(Box const& box, Turn const& turn)
64 if (turn.location != location_ok || turn.within_original)
66 // Skip all points already processed
70 return ! geometry::detail::disjoint::disjoint_point_box(
71 turn.robust_point, box);
75 //! Check if specified is in range of specified iterators
76 //! Return value of strategy (true if we can bail out)
84 inline bool point_in_range(Strategy& strategy, State& state,
85 Point const& point, Iterator begin, Iterator end)
87 boost::ignore_unused(strategy);
90 for (Iterator previous = it++; it != end; ++previous, ++it)
92 if (! strategy.apply(point, *previous, *it, state))
94 // We're probably on the boundary
106 typename CoordinateType,
109 inline bool point_in_section(Strategy& strategy, State& state,
110 Point const& point, CoordinateType const& point_x,
111 Iterator begin, Iterator end,
116 // Not a monotonic section, or no change in X-direction
117 return point_in_range(strategy, state, point, begin, end);
120 // We're in a monotonic section in x-direction
123 for (Iterator previous = it++; it != end; ++previous, ++it)
125 // Depending on sections.direction we can quit for this section
126 CoordinateType const previous_x = geometry::get<0>(*previous);
128 if (direction == 1 && point_x < previous_x)
130 // Section goes upwards, x increases, point is is below section
133 else if (direction == -1 && point_x > previous_x)
135 // Section goes downwards, x decreases, point is above section
139 if (! strategy.apply(point, *previous, *it, state))
141 // We're probably on the boundary
149 template <typename Point, typename Original>
150 inline int point_in_original(Point const& point, Original const& original)
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;
157 typename strategy_type::state_type state;
158 strategy_type strategy;
160 if (boost::size(original.m_sections) == 0
161 || boost::size(original.m_ring) - boost::size(original.m_sections) < 16)
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
166 point_in_range(strategy, state, point,
167 original.m_ring.begin(), original.m_ring.end());
168 return strategy.result(state);
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;
176 coordinate_type const point_x = geometry::get<0>(point);
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);
183 section_type const& section = *it;
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))
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]))
196 // We're probably on the boundary
202 return strategy.result(state);
206 template <typename Turns>
207 class turn_in_original_visitor
210 turn_in_original_visitor(Turns& turns)
211 : m_mutable_turns(turns)
214 template <typename Turn, typename Original>
215 inline void apply(Turn const& turn, Original const& original, bool first = true)
217 boost::ignore_unused_variable_warning(first);
219 if (turn.location != location_ok || turn.within_original)
221 // Skip all points already processed
225 if (geometry::disjoint(turn.robust_point, original.m_box))
231 int const code = point_in_original(turn.robust_point, original);
238 Turn& mutable_turn = m_mutable_turns[turn.turn_index];
242 // On border of original: always discard
243 mutable_turn.location = location_discard;
246 // Point is inside an original ring
247 if (original.m_is_interior)
249 mutable_turn.count_in_original--;
251 else if (original.m_has_interiors)
253 mutable_turn.count_in_original++;
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;
265 Turns& m_mutable_turns;
269 }} // namespace detail::buffer
270 #endif // DOXYGEN_NO_DETAIL
273 }} // namespace boost::geometry
275 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_ORIGINAL_VISITOR