]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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. | |
6 | // Modifications copyright (c) 2016 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/expand.hpp> | |
20 | #include <boost/geometry/strategies/agnostic/point_in_poly_winding.hpp> | |
21 | #include <boost/geometry/strategies/buffer.hpp> | |
22 | ||
23 | ||
24 | namespace boost { namespace geometry | |
25 | { | |
26 | ||
27 | ||
28 | #ifndef DOXYGEN_NO_DETAIL | |
29 | namespace detail { namespace buffer | |
30 | { | |
31 | ||
32 | struct original_get_box | |
33 | { | |
34 | template <typename Box, typename Original> | |
35 | static inline void apply(Box& total, Original const& original) | |
36 | { | |
37 | geometry::expand(total, original.m_box); | |
38 | } | |
39 | }; | |
40 | ||
41 | struct original_ovelaps_box | |
42 | { | |
43 | template <typename Box, typename Original> | |
44 | static inline bool apply(Box const& box, Original const& original) | |
45 | { | |
46 | return ! detail::disjoint::disjoint_box_box(box, original.m_box); | |
47 | } | |
48 | }; | |
49 | ||
50 | struct include_turn_policy | |
51 | { | |
52 | template <typename Turn> | |
53 | static inline bool apply(Turn const& turn) | |
54 | { | |
55 | return turn.location == location_ok; | |
56 | } | |
57 | }; | |
58 | ||
59 | struct turn_in_original_ovelaps_box | |
60 | { | |
61 | template <typename Box, typename Turn> | |
62 | static inline bool apply(Box const& box, Turn const& turn) | |
63 | { | |
64 | if (turn.location != location_ok || turn.within_original) | |
65 | { | |
66 | // Skip all points already processed | |
67 | return false; | |
68 | } | |
69 | ||
70 | return ! geometry::detail::disjoint::disjoint_point_box( | |
71 | turn.robust_point, box); | |
72 | } | |
73 | }; | |
74 | ||
75 | //! Check if specified is in range of specified iterators | |
76 | //! Return value of strategy (true if we can bail out) | |
77 | template | |
78 | < | |
79 | typename Strategy, | |
80 | typename State, | |
81 | typename Point, | |
82 | typename Iterator | |
83 | > | |
84 | inline bool point_in_range(Strategy& strategy, State& state, | |
85 | Point const& point, Iterator begin, Iterator end) | |
86 | { | |
87 | boost::ignore_unused(strategy); | |
88 | ||
89 | Iterator it = begin; | |
90 | for (Iterator previous = it++; it != end; ++previous, ++it) | |
91 | { | |
92 | if (! strategy.apply(point, *previous, *it, state)) | |
93 | { | |
94 | // We're probably on the boundary | |
95 | return false; | |
96 | } | |
97 | } | |
98 | return true; | |
99 | } | |
100 | ||
101 | template | |
102 | < | |
103 | typename Strategy, | |
104 | typename State, | |
105 | typename Point, | |
106 | typename CoordinateType, | |
107 | typename Iterator | |
108 | > | |
109 | inline bool point_in_section(Strategy& strategy, State& state, | |
110 | Point const& point, CoordinateType const& point_x, | |
111 | Iterator begin, Iterator end, | |
112 | int direction) | |
113 | { | |
114 | if (direction == 0) | |
115 | { | |
116 | // Not a monotonic section, or no change in X-direction | |
117 | return point_in_range(strategy, state, point, begin, end); | |
118 | } | |
119 | ||
120 | // We're in a monotonic section in x-direction | |
121 | Iterator it = begin; | |
122 | ||
123 | for (Iterator previous = it++; it != end; ++previous, ++it) | |
124 | { | |
125 | // Depending on sections.direction we can quit for this section | |
126 | CoordinateType const previous_x = geometry::get<0>(*previous); | |
127 | ||
128 | if (direction == 1 && point_x < previous_x) | |
129 | { | |
130 | // Section goes upwards, x increases, point is is below section | |
131 | return true; | |
132 | } | |
133 | else if (direction == -1 && point_x > previous_x) | |
134 | { | |
135 | // Section goes downwards, x decreases, point is above section | |
136 | return true; | |
137 | } | |
138 | ||
139 | if (! strategy.apply(point, *previous, *it, state)) | |
140 | { | |
141 | // We're probably on the boundary | |
142 | return false; | |
143 | } | |
144 | } | |
145 | return true; | |
146 | } | |
147 | ||
148 | ||
149 | template <typename Point, typename Original> | |
150 | inline int point_in_original(Point const& point, Original const& original) | |
151 | { | |
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; | |
156 | ||
157 | typename strategy_type::state_type state; | |
158 | strategy_type strategy; | |
159 | ||
160 | if (boost::size(original.m_sections) == 0 | |
161 | || boost::size(original.m_ring) - boost::size(original.m_sections) < 16) | |
162 | { | |
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 | |
165 | // performance | |
166 | point_in_range(strategy, state, point, | |
167 | original.m_ring.begin(), original.m_ring.end()); | |
168 | return strategy.result(state); | |
169 | } | |
170 | ||
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; | |
175 | ||
176 | coordinate_type const point_x = geometry::get<0>(point); | |
177 | ||
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); | |
181 | ++it) | |
182 | { | |
183 | section_type const& section = *it; | |
184 | ||
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)) | |
189 | { | |
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])) | |
195 | { | |
196 | // We're probably on the boundary | |
197 | break; | |
198 | } | |
199 | } | |
200 | } | |
201 | ||
202 | return strategy.result(state); | |
203 | } | |
204 | ||
205 | ||
206 | template <typename Turns> | |
207 | class turn_in_original_visitor | |
208 | { | |
209 | public: | |
210 | turn_in_original_visitor(Turns& turns) | |
211 | : m_mutable_turns(turns) | |
212 | {} | |
213 | ||
214 | template <typename Turn, typename Original> | |
215 | inline void apply(Turn const& turn, Original const& original, bool first = true) | |
216 | { | |
217 | boost::ignore_unused_variable_warning(first); | |
218 | ||
219 | if (turn.location != location_ok || turn.within_original) | |
220 | { | |
221 | // Skip all points already processed | |
222 | return; | |
223 | } | |
224 | ||
225 | if (geometry::disjoint(turn.robust_point, original.m_box)) | |
226 | { | |
227 | // Skip all disjoint | |
228 | return; | |
229 | } | |
230 | ||
231 | int const code = point_in_original(turn.robust_point, original); | |
232 | ||
233 | if (code == -1) | |
234 | { | |
235 | return; | |
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 | } | |
262 | } | |
263 | ||
264 | private : | |
265 | Turns& m_mutable_turns; | |
266 | }; | |
267 | ||
268 | ||
269 | }} // namespace detail::buffer | |
270 | #endif // DOXYGEN_NO_DETAIL | |
271 | ||
272 | ||
273 | }} // namespace boost::geometry | |
274 | ||
275 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_ORIGINAL_VISITOR |