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