]>
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> | |
18 | ||
92f5a8d4 | 19 | #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp> |
7c673cae FG |
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 | ||
92f5a8d4 | 42 | template <typename DisjointBoxBoxStrategy> |
7c673cae FG |
43 | struct original_ovelaps_box |
44 | { | |
45 | template <typename Box, typename Original> | |
46 | static inline bool apply(Box const& box, Original const& original) | |
47 | { | |
92f5a8d4 TL |
48 | return ! detail::disjoint::disjoint_box_box(box, original.m_box, |
49 | DisjointBoxBoxStrategy()); | |
7c673cae FG |
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 | ||
92f5a8d4 | 62 | template <typename DisjointPointBoxStrategy> |
7c673cae FG |
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( | |
92f5a8d4 | 75 | turn.robust_point, box, DisjointPointBoxStrategy()); |
7c673cae FG |
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 | ||
92f5a8d4 TL |
153 | template <typename Point, typename Original, typename PointInGeometryStrategy> |
154 | inline int point_in_original(Point const& point, Original const& original, | |
155 | PointInGeometryStrategy const& strategy) | |
7c673cae | 156 | { |
92f5a8d4 | 157 | typename PointInGeometryStrategy::state_type state; |
7c673cae FG |
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 | ||
92f5a8d4 | 205 | template <typename Turns, typename PointInGeometryStrategy> |
7c673cae FG |
206 | class turn_in_original_visitor |
207 | { | |
208 | public: | |
92f5a8d4 | 209 | turn_in_original_visitor(Turns& turns, PointInGeometryStrategy const& strategy) |
7c673cae | 210 | : m_mutable_turns(turns) |
92f5a8d4 | 211 | , m_point_in_geometry_strategy(strategy) |
7c673cae FG |
212 | {} |
213 | ||
214 | template <typename Turn, typename Original> | |
b32b8144 | 215 | inline bool apply(Turn const& turn, Original const& original, bool first = true) |
7c673cae | 216 | { |
92f5a8d4 | 217 | boost::ignore_unused(first); |
7c673cae FG |
218 | |
219 | if (turn.location != location_ok || turn.within_original) | |
220 | { | |
221 | // Skip all points already processed | |
b32b8144 | 222 | return true; |
7c673cae FG |
223 | } |
224 | ||
225 | if (geometry::disjoint(turn.robust_point, original.m_box)) | |
226 | { | |
227 | // Skip all disjoint | |
b32b8144 | 228 | return true; |
7c673cae FG |
229 | } |
230 | ||
92f5a8d4 | 231 | int const code = point_in_original(turn.robust_point, original, m_point_in_geometry_strategy); |
7c673cae FG |
232 | |
233 | if (code == -1) | |
234 | { | |
b32b8144 | 235 | return true; |
7c673cae FG |
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 | } | |
b32b8144 FG |
262 | |
263 | return true; | |
7c673cae FG |
264 | } |
265 | ||
266 | private : | |
267 | Turns& m_mutable_turns; | |
92f5a8d4 | 268 | PointInGeometryStrategy const& m_point_in_geometry_strategy; |
7c673cae FG |
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 |