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