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