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