]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | ||
5 | // This file was modified by Oracle on 2013, 2014. | |
6 | // Modifications copyright (c) 2013-2014 Oracle and/or its affiliates. | |
7 | ||
8 | // Use, modification and distribution is subject to the Boost Software License, | |
9 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
10 | // http://www.boost.org/LICENSE_1_0.txt) | |
11 | ||
12 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
13 | ||
14 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_FOLLOW_HELPERS_HPP | |
15 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_FOLLOW_HELPERS_HPP | |
16 | ||
17 | #include <boost/geometry/core/assert.hpp> | |
18 | ||
19 | #include <boost/geometry/util/condition.hpp> | |
20 | #include <boost/geometry/util/range.hpp> | |
21 | //#include <boost/geometry/algorithms/detail/sub_range.hpp> | |
22 | ||
23 | namespace boost { namespace geometry | |
24 | { | |
25 | ||
26 | #ifndef DOXYGEN_NO_DETAIL | |
27 | namespace detail { namespace relate { | |
28 | ||
29 | // NOTE: This iterates through single geometries for which turns were not generated. | |
30 | // It doesn't mean that the geometry is disjoint, only that no turns were detected. | |
31 | ||
32 | template <std::size_t OpId, | |
33 | typename Geometry, | |
34 | typename Tag = typename geometry::tag<Geometry>::type, | |
35 | bool IsMulti = boost::is_base_of<multi_tag, Tag>::value | |
36 | > | |
37 | struct for_each_disjoint_geometry_if | |
38 | : public not_implemented<Tag> | |
39 | {}; | |
40 | ||
41 | template <std::size_t OpId, typename Geometry, typename Tag> | |
42 | struct for_each_disjoint_geometry_if<OpId, Geometry, Tag, false> | |
43 | { | |
44 | template <typename TurnIt, typename Pred> | |
45 | static inline bool apply(TurnIt first, TurnIt last, | |
46 | Geometry const& geometry, | |
47 | Pred & pred) | |
48 | { | |
49 | if ( first != last ) | |
50 | return false; | |
51 | pred(geometry); | |
52 | return true; | |
53 | } | |
54 | }; | |
55 | ||
56 | template <std::size_t OpId, typename Geometry, typename Tag> | |
57 | struct for_each_disjoint_geometry_if<OpId, Geometry, Tag, true> | |
58 | { | |
59 | template <typename TurnIt, typename Pred> | |
60 | static inline bool apply(TurnIt first, TurnIt last, | |
61 | Geometry const& geometry, | |
62 | Pred & pred) | |
63 | { | |
64 | if ( first != last ) | |
65 | return for_turns(first, last, geometry, pred); | |
66 | else | |
67 | return for_empty(geometry, pred); | |
68 | } | |
69 | ||
70 | template <typename Pred> | |
71 | static inline bool for_empty(Geometry const& geometry, | |
72 | Pred & pred) | |
73 | { | |
74 | typedef typename boost::range_iterator<Geometry const>::type iterator; | |
75 | ||
76 | // O(N) | |
77 | // check predicate for each contained geometry without generated turn | |
78 | for ( iterator it = boost::begin(geometry) ; | |
79 | it != boost::end(geometry) ; ++it ) | |
80 | { | |
81 | bool cont = pred(*it); | |
82 | if ( !cont ) | |
83 | break; | |
84 | } | |
85 | ||
86 | return !boost::empty(geometry); | |
87 | } | |
88 | ||
89 | template <typename TurnIt, typename Pred> | |
90 | static inline bool for_turns(TurnIt first, TurnIt last, | |
91 | Geometry const& geometry, | |
92 | Pred & pred) | |
93 | { | |
94 | BOOST_GEOMETRY_ASSERT(first != last); | |
95 | ||
96 | const std::size_t count = boost::size(geometry); | |
97 | boost::ignore_unused_variable_warning(count); | |
98 | ||
99 | // O(I) | |
100 | // gather info about turns generated for contained geometries | |
101 | std::vector<bool> detected_intersections(count, false); | |
102 | for ( TurnIt it = first ; it != last ; ++it ) | |
103 | { | |
104 | signed_size_type multi_index = it->operations[OpId].seg_id.multi_index; | |
105 | BOOST_GEOMETRY_ASSERT(multi_index >= 0); | |
106 | std::size_t const index = static_cast<std::size_t>(multi_index); | |
107 | BOOST_GEOMETRY_ASSERT(index < count); | |
108 | detected_intersections[index] = true; | |
109 | } | |
110 | ||
111 | bool found = false; | |
112 | ||
113 | // O(N) | |
114 | // check predicate for each contained geometry without generated turn | |
115 | for ( std::vector<bool>::iterator it = detected_intersections.begin() ; | |
116 | it != detected_intersections.end() ; ++it ) | |
117 | { | |
118 | // if there were no intersections for this multi_index | |
119 | if ( *it == false ) | |
120 | { | |
121 | found = true; | |
122 | std::size_t const index = std::size_t(std::distance(detected_intersections.begin(), it)); | |
123 | bool cont = pred(range::at(geometry, index)); | |
124 | if ( !cont ) | |
125 | break; | |
126 | } | |
127 | } | |
128 | ||
129 | return found; | |
130 | } | |
131 | }; | |
132 | ||
133 | // WARNING! This class stores pointers! | |
134 | // Passing a reference to local variable will result in undefined behavior! | |
135 | template <typename Point> | |
136 | class point_info | |
137 | { | |
138 | public: | |
139 | point_info() : sid_ptr(NULL), pt_ptr(NULL) {} | |
140 | point_info(Point const& pt, segment_identifier const& sid) | |
141 | : sid_ptr(boost::addressof(sid)) | |
142 | , pt_ptr(boost::addressof(pt)) | |
143 | {} | |
144 | segment_identifier const& seg_id() const | |
145 | { | |
146 | BOOST_GEOMETRY_ASSERT(sid_ptr); | |
147 | return *sid_ptr; | |
148 | } | |
149 | Point const& point() const | |
150 | { | |
151 | BOOST_GEOMETRY_ASSERT(pt_ptr); | |
152 | return *pt_ptr; | |
153 | } | |
154 | ||
155 | //friend bool operator==(point_identifier const& l, point_identifier const& r) | |
156 | //{ | |
157 | // return l.seg_id() == r.seg_id() | |
158 | // && detail::equals::equals_point_point(l.point(), r.point()); | |
159 | //} | |
160 | ||
161 | private: | |
162 | const segment_identifier * sid_ptr; | |
163 | const Point * pt_ptr; | |
164 | }; | |
165 | ||
166 | // WARNING! This class stores pointers! | |
167 | // Passing a reference to local variable will result in undefined behavior! | |
168 | class same_single | |
169 | { | |
170 | public: | |
171 | same_single(segment_identifier const& sid) | |
172 | : sid_ptr(boost::addressof(sid)) | |
173 | {} | |
174 | ||
175 | bool operator()(segment_identifier const& sid) const | |
176 | { | |
177 | return sid.multi_index == sid_ptr->multi_index; | |
178 | } | |
179 | ||
180 | template <typename Point> | |
181 | bool operator()(point_info<Point> const& pid) const | |
182 | { | |
183 | return operator()(pid.seg_id()); | |
184 | } | |
185 | ||
186 | private: | |
187 | const segment_identifier * sid_ptr; | |
188 | }; | |
189 | ||
190 | class same_ring | |
191 | { | |
192 | public: | |
193 | same_ring(segment_identifier const& sid) | |
194 | : sid_ptr(boost::addressof(sid)) | |
195 | {} | |
196 | ||
197 | bool operator()(segment_identifier const& sid) const | |
198 | { | |
199 | return sid.multi_index == sid_ptr->multi_index | |
200 | && sid.ring_index == sid_ptr->ring_index; | |
201 | } | |
202 | ||
203 | private: | |
204 | const segment_identifier * sid_ptr; | |
205 | }; | |
206 | ||
207 | // WARNING! This class stores pointers! | |
208 | // Passing a reference to local variable will result in undefined behavior! | |
209 | template <typename SameRange = same_single> | |
210 | class segment_watcher | |
211 | { | |
212 | public: | |
213 | segment_watcher() | |
214 | : m_seg_id_ptr(NULL) | |
215 | {} | |
216 | ||
217 | bool update(segment_identifier const& seg_id) | |
218 | { | |
219 | bool result = m_seg_id_ptr == 0 || !SameRange(*m_seg_id_ptr)(seg_id); | |
220 | m_seg_id_ptr = boost::addressof(seg_id); | |
221 | return result; | |
222 | } | |
223 | ||
224 | private: | |
225 | const segment_identifier * m_seg_id_ptr; | |
226 | }; | |
227 | ||
228 | // WARNING! This class stores pointers! | |
229 | // Passing a reference to local variable will result in undefined behavior! | |
230 | template <typename TurnInfo, std::size_t OpId> | |
231 | class exit_watcher | |
232 | { | |
233 | static const std::size_t op_id = OpId; | |
234 | static const std::size_t other_op_id = (OpId + 1) % 2; | |
235 | ||
236 | typedef typename TurnInfo::point_type point_type; | |
237 | typedef detail::relate::point_info<point_type> point_info; | |
238 | ||
239 | public: | |
240 | exit_watcher() | |
241 | : m_exit_operation(overlay::operation_none) | |
242 | , m_exit_turn_ptr(NULL) | |
243 | {} | |
244 | ||
245 | void enter(TurnInfo const& turn) | |
246 | { | |
247 | m_other_entry_points.push_back( | |
248 | point_info(turn.point, turn.operations[other_op_id].seg_id) ); | |
249 | } | |
250 | ||
251 | // TODO: exit_per_geometry parameter looks not very safe | |
252 | // wrong value may be easily passed | |
253 | ||
254 | void exit(TurnInfo const& turn, bool exit_per_geometry = true) | |
255 | { | |
256 | //segment_identifier const& seg_id = turn.operations[op_id].seg_id; | |
257 | segment_identifier const& other_id = turn.operations[other_op_id].seg_id; | |
258 | overlay::operation_type exit_op = turn.operations[op_id].operation; | |
259 | ||
260 | typedef typename std::vector<point_info>::iterator point_iterator; | |
261 | // search for the entry point in the same range of other geometry | |
262 | point_iterator entry_it = std::find_if(m_other_entry_points.begin(), | |
263 | m_other_entry_points.end(), | |
264 | same_single(other_id)); | |
265 | ||
266 | // this end point has corresponding entry point | |
267 | if ( entry_it != m_other_entry_points.end() ) | |
268 | { | |
269 | // erase the corresponding entry point | |
270 | m_other_entry_points.erase(entry_it); | |
271 | ||
272 | if ( exit_per_geometry || m_other_entry_points.empty() ) | |
273 | { | |
274 | // here we know that we possibly left LS | |
275 | // we must still check if we didn't get back on the same point | |
276 | m_exit_operation = exit_op; | |
277 | m_exit_turn_ptr = boost::addressof(turn); | |
278 | } | |
279 | } | |
280 | } | |
281 | ||
282 | bool is_outside() const | |
283 | { | |
284 | // if we didn't entered anything in the past, we're outside | |
285 | return m_other_entry_points.empty(); | |
286 | } | |
287 | ||
288 | bool is_outside(TurnInfo const& turn) const | |
289 | { | |
290 | return m_other_entry_points.empty() | |
291 | || std::find_if(m_other_entry_points.begin(), | |
292 | m_other_entry_points.end(), | |
293 | same_single( | |
294 | turn.operations[other_op_id].seg_id)) | |
295 | == m_other_entry_points.end(); | |
296 | } | |
297 | ||
298 | overlay::operation_type get_exit_operation() const | |
299 | { | |
300 | return m_exit_operation; | |
301 | } | |
302 | ||
303 | point_type const& get_exit_point() const | |
304 | { | |
305 | BOOST_GEOMETRY_ASSERT(m_exit_operation != overlay::operation_none); | |
306 | BOOST_GEOMETRY_ASSERT(m_exit_turn_ptr); | |
307 | return m_exit_turn_ptr->point; | |
308 | } | |
309 | ||
310 | TurnInfo const& get_exit_turn() const | |
311 | { | |
312 | BOOST_GEOMETRY_ASSERT(m_exit_operation != overlay::operation_none); | |
313 | BOOST_GEOMETRY_ASSERT(m_exit_turn_ptr); | |
314 | return *m_exit_turn_ptr; | |
315 | } | |
316 | ||
317 | void reset_detected_exit() | |
318 | { | |
319 | m_exit_operation = overlay::operation_none; | |
320 | } | |
321 | ||
322 | void reset() | |
323 | { | |
324 | m_exit_operation = overlay::operation_none; | |
325 | m_other_entry_points.clear(); | |
326 | } | |
327 | ||
328 | private: | |
329 | overlay::operation_type m_exit_operation; | |
330 | const TurnInfo * m_exit_turn_ptr; | |
331 | std::vector<point_info> m_other_entry_points; // TODO: use map here or sorted vector? | |
332 | }; | |
333 | ||
334 | template <std::size_t OpId, typename Turn> | |
335 | inline bool turn_on_the_same_ip(Turn const& prev_turn, Turn const& curr_turn) | |
336 | { | |
337 | segment_identifier const& prev_seg_id = prev_turn.operations[OpId].seg_id; | |
338 | segment_identifier const& curr_seg_id = curr_turn.operations[OpId].seg_id; | |
339 | ||
340 | if ( prev_seg_id.multi_index != curr_seg_id.multi_index | |
341 | || prev_seg_id.ring_index != curr_seg_id.ring_index ) | |
342 | { | |
343 | return false; | |
344 | } | |
345 | ||
346 | // TODO: will this work if between segments there will be some number of degenerated ones? | |
347 | ||
348 | if ( prev_seg_id.segment_index != curr_seg_id.segment_index | |
349 | && ( ! curr_turn.operations[OpId].fraction.is_zero() | |
350 | || prev_seg_id.segment_index + 1 != curr_seg_id.segment_index ) ) | |
351 | { | |
352 | return false; | |
353 | } | |
354 | ||
355 | return detail::equals::equals_point_point(prev_turn.point, curr_turn.point); | |
356 | } | |
357 | ||
358 | template <boundary_query BoundaryQuery, | |
359 | typename Point, | |
360 | typename BoundaryChecker> | |
361 | static inline bool is_endpoint_on_boundary(Point const& pt, | |
362 | BoundaryChecker & boundary_checker) | |
363 | { | |
364 | return boundary_checker.template is_endpoint_boundary<BoundaryQuery>(pt); | |
365 | } | |
366 | ||
367 | template <boundary_query BoundaryQuery, | |
368 | typename IntersectionPoint, | |
369 | typename OperationInfo, | |
370 | typename BoundaryChecker> | |
371 | static inline bool is_ip_on_boundary(IntersectionPoint const& ip, | |
372 | OperationInfo const& operation_info, | |
373 | BoundaryChecker & boundary_checker, | |
374 | segment_identifier const& seg_id) | |
375 | { | |
376 | boost::ignore_unused_variable_warning(seg_id); | |
377 | ||
378 | bool res = false; | |
379 | ||
380 | // IP on the last point of the linestring | |
381 | if ( BOOST_GEOMETRY_CONDITION(BoundaryQuery == boundary_back || BoundaryQuery == boundary_any) | |
382 | && operation_info.position == overlay::position_back ) | |
383 | { | |
384 | // check if this point is a boundary | |
385 | res = boundary_checker.template is_endpoint_boundary<boundary_back>(ip); | |
386 | } | |
387 | // IP on the last point of the linestring | |
388 | else if ( BOOST_GEOMETRY_CONDITION(BoundaryQuery == boundary_front || BoundaryQuery == boundary_any) | |
389 | && operation_info.position == overlay::position_front ) | |
390 | { | |
391 | // check if this point is a boundary | |
392 | res = boundary_checker.template is_endpoint_boundary<boundary_front>(ip); | |
393 | } | |
394 | ||
395 | return res; | |
396 | } | |
397 | ||
398 | ||
399 | }} // namespace detail::relate | |
400 | #endif // DOXYGEN_NO_DETAIL | |
401 | ||
402 | }} // namespace boost::geometry | |
403 | ||
404 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_FOLLOW_HELPERS_HPP |