]>
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 | ||
1e59de90 TL |
5 | // This file was modified by Oracle on 2013-2021. |
6 | // Modifications copyright (c) 2013-2021 Oracle and/or its affiliates. | |
7c673cae FG |
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 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LINEAR_AREAL_HPP | |
15 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LINEAR_AREAL_HPP | |
16 | ||
17 | #include <boost/core/ignore_unused.hpp> | |
18 | #include <boost/range/size.hpp> | |
19 | ||
20 | #include <boost/geometry/core/assert.hpp> | |
21 | #include <boost/geometry/core/topological_dimension.hpp> | |
22 | ||
23 | #include <boost/geometry/util/condition.hpp> | |
24 | #include <boost/geometry/util/range.hpp> | |
20effc67 | 25 | #include <boost/geometry/util/type_traits.hpp> |
7c673cae FG |
26 | |
27 | #include <boost/geometry/algorithms/num_interior_rings.hpp> | |
28 | #include <boost/geometry/algorithms/detail/point_on_border.hpp> | |
29 | #include <boost/geometry/algorithms/detail/sub_range.hpp> | |
30 | #include <boost/geometry/algorithms/detail/single_geometry.hpp> | |
31 | ||
32 | #include <boost/geometry/algorithms/detail/relate/point_geometry.hpp> | |
33 | #include <boost/geometry/algorithms/detail/relate/turns.hpp> | |
34 | #include <boost/geometry/algorithms/detail/relate/boundary_checker.hpp> | |
35 | #include <boost/geometry/algorithms/detail/relate/follow_helpers.hpp> | |
36 | ||
1e59de90 | 37 | #include <boost/geometry/views/detail/closed_clockwise_view.hpp> |
7c673cae FG |
38 | |
39 | namespace boost { namespace geometry | |
40 | { | |
41 | ||
42 | #ifndef DOXYGEN_NO_DETAIL | |
43 | namespace detail { namespace relate { | |
44 | ||
45 | // WARNING! | |
46 | // TODO: In the worst case calling this Pred in a loop for MultiLinestring/MultiPolygon may take O(NM) | |
47 | // Use the rtree in this case! | |
48 | ||
49 | // may be used to set IE and BE for a Linear geometry for which no turns were generated | |
b32b8144 FG |
50 | template |
51 | < | |
52 | typename Geometry2, | |
53 | typename Result, | |
54 | typename PointInArealStrategy, | |
55 | typename BoundaryChecker, | |
56 | bool TransposeResult | |
57 | > | |
7c673cae FG |
58 | class no_turns_la_linestring_pred |
59 | { | |
60 | public: | |
61 | no_turns_la_linestring_pred(Geometry2 const& geometry2, | |
62 | Result & res, | |
b32b8144 | 63 | PointInArealStrategy const& point_in_areal_strategy, |
7c673cae FG |
64 | BoundaryChecker const& boundary_checker) |
65 | : m_geometry2(geometry2) | |
66 | , m_result(res) | |
b32b8144 | 67 | , m_point_in_areal_strategy(point_in_areal_strategy) |
7c673cae FG |
68 | , m_boundary_checker(boundary_checker) |
69 | , m_interrupt_flags(0) | |
70 | { | |
71 | if ( ! may_update<interior, interior, '1', TransposeResult>(m_result) ) | |
72 | { | |
73 | m_interrupt_flags |= 1; | |
74 | } | |
75 | ||
76 | if ( ! may_update<interior, exterior, '1', TransposeResult>(m_result) ) | |
77 | { | |
78 | m_interrupt_flags |= 2; | |
79 | } | |
80 | ||
81 | if ( ! may_update<boundary, interior, '0', TransposeResult>(m_result) ) | |
82 | { | |
83 | m_interrupt_flags |= 4; | |
84 | } | |
85 | ||
86 | if ( ! may_update<boundary, exterior, '0', TransposeResult>(m_result) ) | |
87 | { | |
88 | m_interrupt_flags |= 8; | |
89 | } | |
90 | } | |
91 | ||
92 | template <typename Linestring> | |
93 | bool operator()(Linestring const& linestring) | |
94 | { | |
95 | std::size_t const count = boost::size(linestring); | |
96 | ||
97 | // invalid input | |
98 | if ( count < 2 ) | |
99 | { | |
100 | // ignore | |
101 | // TODO: throw an exception? | |
102 | return true; | |
103 | } | |
104 | ||
105 | // if those flags are set nothing will change | |
106 | if ( m_interrupt_flags == 0xF ) | |
107 | { | |
108 | return false; | |
109 | } | |
110 | ||
b32b8144 FG |
111 | int const pig = detail::within::point_in_geometry(range::front(linestring), |
112 | m_geometry2, | |
113 | m_point_in_areal_strategy); | |
7c673cae FG |
114 | //BOOST_GEOMETRY_ASSERT_MSG(pig != 0, "There should be no IPs"); |
115 | ||
116 | if ( pig > 0 ) | |
117 | { | |
118 | update<interior, interior, '1', TransposeResult>(m_result); | |
119 | m_interrupt_flags |= 1; | |
120 | } | |
121 | else | |
122 | { | |
123 | update<interior, exterior, '1', TransposeResult>(m_result); | |
124 | m_interrupt_flags |= 2; | |
125 | } | |
126 | ||
127 | // check if there is a boundary | |
128 | if ( ( m_interrupt_flags & 0xC ) != 0xC // if wasn't already set | |
129 | && ( m_boundary_checker.template | |
130 | is_endpoint_boundary<boundary_front>(range::front(linestring)) | |
131 | || m_boundary_checker.template | |
132 | is_endpoint_boundary<boundary_back>(range::back(linestring)) ) ) | |
133 | { | |
134 | if ( pig > 0 ) | |
135 | { | |
136 | update<boundary, interior, '0', TransposeResult>(m_result); | |
137 | m_interrupt_flags |= 4; | |
138 | } | |
139 | else | |
140 | { | |
141 | update<boundary, exterior, '0', TransposeResult>(m_result); | |
142 | m_interrupt_flags |= 8; | |
143 | } | |
144 | } | |
145 | ||
146 | return m_interrupt_flags != 0xF | |
147 | && ! m_result.interrupt; | |
148 | } | |
149 | ||
150 | private: | |
151 | Geometry2 const& m_geometry2; | |
152 | Result & m_result; | |
b32b8144 | 153 | PointInArealStrategy const& m_point_in_areal_strategy; |
7c673cae FG |
154 | BoundaryChecker const& m_boundary_checker; |
155 | unsigned m_interrupt_flags; | |
156 | }; | |
157 | ||
158 | // may be used to set EI and EB for an Areal geometry for which no turns were generated | |
159 | template <typename Result, bool TransposeResult> | |
160 | class no_turns_la_areal_pred | |
161 | { | |
162 | public: | |
163 | no_turns_la_areal_pred(Result & res) | |
164 | : m_result(res) | |
165 | , interrupt(! may_update<interior, exterior, '2', TransposeResult>(m_result) | |
166 | && ! may_update<boundary, exterior, '1', TransposeResult>(m_result) ) | |
167 | {} | |
168 | ||
169 | template <typename Areal> | |
170 | bool operator()(Areal const& areal) | |
171 | { | |
172 | if ( interrupt ) | |
173 | { | |
174 | return false; | |
175 | } | |
176 | ||
177 | // TODO: | |
178 | // handle empty/invalid geometries in a different way than below? | |
179 | ||
180 | typedef typename geometry::point_type<Areal>::type point_type; | |
181 | point_type dummy; | |
182 | bool const ok = boost::geometry::point_on_border(dummy, areal); | |
183 | ||
184 | // TODO: for now ignore, later throw an exception? | |
185 | if ( !ok ) | |
186 | { | |
187 | return true; | |
188 | } | |
189 | ||
190 | update<interior, exterior, '2', TransposeResult>(m_result); | |
191 | update<boundary, exterior, '1', TransposeResult>(m_result); | |
192 | ||
193 | return false; | |
194 | } | |
195 | ||
196 | private: | |
197 | Result & m_result; | |
198 | bool const interrupt; | |
199 | }; | |
200 | ||
201 | // The implementation of an algorithm calculating relate() for L/A | |
202 | template <typename Geometry1, typename Geometry2, bool TransposeResult = false> | |
203 | struct linear_areal | |
204 | { | |
205 | // check Linear / Areal | |
206 | BOOST_STATIC_ASSERT(topological_dimension<Geometry1>::value == 1 | |
207 | && topological_dimension<Geometry2>::value == 2); | |
208 | ||
209 | static const bool interruption_enabled = true; | |
210 | ||
211 | typedef typename geometry::point_type<Geometry1>::type point1_type; | |
212 | typedef typename geometry::point_type<Geometry2>::type point2_type; | |
213 | ||
92f5a8d4 | 214 | template <typename Geom1, typename Geom2, typename Strategy> |
7c673cae | 215 | struct multi_turn_info |
92f5a8d4 | 216 | : turns::get_turns<Geom1, Geom2>::template turn_info_type<Strategy>::type |
7c673cae FG |
217 | { |
218 | multi_turn_info() : priority(0) {} | |
219 | int priority; // single-geometry sorting priority | |
220 | }; | |
221 | ||
92f5a8d4 | 222 | template <typename Geom1, typename Geom2, typename Strategy> |
7c673cae | 223 | struct turn_info_type |
20effc67 | 224 | : std::conditional |
7c673cae | 225 | < |
20effc67 | 226 | util::is_multi<Geometry2>::value, |
92f5a8d4 TL |
227 | multi_turn_info<Geom1, Geom2, Strategy>, |
228 | typename turns::get_turns<Geom1, Geom2>::template turn_info_type<Strategy>::type | |
7c673cae FG |
229 | > |
230 | {}; | |
231 | ||
1e59de90 | 232 | template <typename Result, typename Strategy> |
b32b8144 FG |
233 | static inline void apply(Geometry1 const& geometry1, Geometry2 const& geometry2, |
234 | Result & result, | |
1e59de90 | 235 | Strategy const& strategy) |
7c673cae FG |
236 | { |
237 | // TODO: If Areal geometry may have infinite size, change the following line: | |
238 | ||
239 | // The result should be FFFFFFFFF | |
240 | relate::set<exterior, exterior, result_dimension<Geometry2>::value, TransposeResult>(result);// FFFFFFFFd, d in [1,9] or T | |
241 | ||
242 | if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) | |
243 | return; | |
244 | ||
245 | // get and analyse turns | |
1e59de90 | 246 | typedef typename turn_info_type<Geometry1, Geometry2, Strategy>::type turn_type; |
7c673cae FG |
247 | std::vector<turn_type> turns; |
248 | ||
249 | interrupt_policy_linear_areal<Geometry2, Result> interrupt_policy(geometry2, result); | |
250 | ||
1e59de90 | 251 | turns::get_turns<Geometry1, Geometry2>::apply(turns, geometry1, geometry2, interrupt_policy, strategy); |
7c673cae FG |
252 | if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) |
253 | return; | |
254 | ||
1e59de90 | 255 | typedef typename Strategy::cs_tag cs_tag; |
92f5a8d4 TL |
256 | |
257 | typedef boundary_checker | |
258 | < | |
259 | Geometry1, | |
1e59de90 | 260 | Strategy |
92f5a8d4 | 261 | > boundary_checker1_type; |
1e59de90 | 262 | boundary_checker1_type boundary_checker1(geometry1, strategy); |
92f5a8d4 | 263 | |
7c673cae FG |
264 | no_turns_la_linestring_pred |
265 | < | |
266 | Geometry2, | |
267 | Result, | |
1e59de90 | 268 | Strategy, |
92f5a8d4 | 269 | boundary_checker1_type, |
7c673cae | 270 | TransposeResult |
b32b8144 FG |
271 | > pred1(geometry2, |
272 | result, | |
1e59de90 | 273 | strategy, |
b32b8144 | 274 | boundary_checker1); |
7c673cae FG |
275 | for_each_disjoint_geometry_if<0, Geometry1>::apply(turns.begin(), turns.end(), geometry1, pred1); |
276 | if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) | |
277 | return; | |
278 | ||
279 | no_turns_la_areal_pred<Result, !TransposeResult> pred2(result); | |
280 | for_each_disjoint_geometry_if<1, Geometry2>::apply(turns.begin(), turns.end(), geometry2, pred2); | |
281 | if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) | |
282 | return; | |
283 | ||
284 | if ( turns.empty() ) | |
285 | return; | |
286 | ||
287 | // This is set here because in the case if empty Areal geometry were passed | |
288 | // those shouldn't be set | |
289 | relate::set<exterior, interior, '2', TransposeResult>(result);// FFFFFF2Fd | |
290 | if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) | |
291 | return; | |
292 | ||
293 | { | |
20effc67 | 294 | sort_dispatch<cs_tag>(turns.begin(), turns.end(), util::is_multi<Geometry2>()); |
7c673cae FG |
295 | |
296 | turns_analyser<turn_type> analyser; | |
297 | analyse_each_turn(result, analyser, | |
298 | turns.begin(), turns.end(), | |
299 | geometry1, geometry2, | |
b32b8144 | 300 | boundary_checker1, |
1e59de90 | 301 | strategy); |
7c673cae FG |
302 | |
303 | if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) ) | |
304 | return; | |
305 | } | |
306 | ||
307 | // If 'c' (insersection_boundary) was not found we know that any Ls isn't equal to one of the Rings | |
308 | if ( !interrupt_policy.is_boundary_found ) | |
309 | { | |
310 | relate::set<exterior, boundary, '1', TransposeResult>(result); | |
311 | } | |
312 | // Don't calculate it if it's required | |
313 | else if ( may_update<exterior, boundary, '1', TransposeResult>(result) ) | |
314 | { | |
315 | // TODO: REVISE THIS CODE AND PROBABLY REWRITE SOME PARTS TO BE MORE HUMAN-READABLE | |
316 | // IN GENERAL IT ANALYSES THE RINGS OF AREAL GEOMETRY AND DETECTS THE ONES THAT | |
317 | // MAY OVERLAP THE INTERIOR OF LINEAR GEOMETRY (NO IPs OR NON-FAKE 'u' OPERATION) | |
318 | // NOTE: For one case std::sort may be called again to sort data by operations for data already sorted by ring index | |
319 | // In the worst case scenario the complexity will be O( NlogN + R*(N/R)log(N/R) ) | |
320 | // So always should remain O(NlogN) -> for R==1 <-> 1(N/1)log(N/1), for R==N <-> N(N/N)log(N/N) | |
321 | // Some benchmarking should probably be done to check if only one std::sort should be used | |
322 | ||
323 | // sort by multi_index and rind_index | |
324 | std::sort(turns.begin(), turns.end(), less_ring()); | |
325 | ||
326 | typedef typename std::vector<turn_type>::iterator turn_iterator; | |
327 | ||
328 | turn_iterator it = turns.begin(); | |
329 | segment_identifier * prev_seg_id_ptr = NULL; | |
330 | // for each ring | |
331 | for ( ; it != turns.end() ; ) | |
332 | { | |
333 | // it's the next single geometry | |
334 | if ( prev_seg_id_ptr == NULL | |
335 | || prev_seg_id_ptr->multi_index != it->operations[1].seg_id.multi_index ) | |
336 | { | |
337 | // if the first ring has no IPs | |
338 | if ( it->operations[1].seg_id.ring_index > -1 ) | |
339 | { | |
340 | // we can be sure that the exterior overlaps the boundary | |
341 | relate::set<exterior, boundary, '1', TransposeResult>(result); | |
342 | break; | |
343 | } | |
344 | // if there was some previous ring | |
345 | if ( prev_seg_id_ptr != NULL ) | |
346 | { | |
347 | signed_size_type const next_ring_index = prev_seg_id_ptr->ring_index + 1; | |
348 | BOOST_GEOMETRY_ASSERT(next_ring_index >= 0); | |
349 | ||
350 | // if one of the last rings of previous single geometry was ommited | |
351 | if ( static_cast<std::size_t>(next_ring_index) | |
352 | < geometry::num_interior_rings( | |
353 | single_geometry(geometry2, *prev_seg_id_ptr)) ) | |
354 | { | |
355 | // we can be sure that the exterior overlaps the boundary | |
356 | relate::set<exterior, boundary, '1', TransposeResult>(result); | |
357 | break; | |
358 | } | |
359 | } | |
360 | } | |
361 | // if it's the same single geometry | |
362 | else /*if ( previous_multi_index == it->operations[1].seg_id.multi_index )*/ | |
363 | { | |
364 | // and we jumped over one of the rings | |
365 | if ( prev_seg_id_ptr != NULL // just in case | |
366 | && prev_seg_id_ptr->ring_index + 1 < it->operations[1].seg_id.ring_index ) | |
367 | { | |
368 | // we can be sure that the exterior overlaps the boundary | |
369 | relate::set<exterior, boundary, '1', TransposeResult>(result); | |
370 | break; | |
371 | } | |
372 | } | |
373 | ||
374 | prev_seg_id_ptr = boost::addressof(it->operations[1].seg_id); | |
375 | ||
376 | // find the next ring first iterator and check if the analysis should be performed | |
377 | has_boundary_intersection has_boundary_inters; | |
378 | turn_iterator next = find_next_ring(it, turns.end(), has_boundary_inters); | |
379 | ||
380 | // if there is no 1d overlap with the boundary | |
381 | if ( !has_boundary_inters.result ) | |
382 | { | |
383 | // we can be sure that the exterior overlaps the boundary | |
384 | relate::set<exterior, boundary, '1', TransposeResult>(result); | |
385 | break; | |
386 | } | |
387 | // else there is 1d overlap with the boundary so we must analyse the boundary | |
388 | else | |
389 | { | |
390 | // u, c | |
92f5a8d4 | 391 | typedef turns::less<1, turns::less_op_areal_linear<1>, cs_tag> less; |
7c673cae FG |
392 | std::sort(it, next, less()); |
393 | ||
394 | // analyse | |
395 | areal_boundary_analyser<turn_type> analyser; | |
396 | for ( turn_iterator rit = it ; rit != next ; ++rit ) | |
397 | { | |
398 | // if the analyser requests, break the search | |
1e59de90 | 399 | if ( !analyser.apply(it, rit, next, strategy) ) |
7c673cae FG |
400 | break; |
401 | } | |
402 | ||
403 | // if the boundary of Areal goes out of the Linear | |
404 | if ( analyser.is_union_detected ) | |
405 | { | |
406 | // we can be sure that the boundary of Areal overlaps the exterior of Linear | |
407 | relate::set<exterior, boundary, '1', TransposeResult>(result); | |
408 | break; | |
409 | } | |
410 | } | |
411 | ||
412 | it = next; | |
413 | } | |
414 | ||
415 | // if there was some previous ring | |
416 | if ( prev_seg_id_ptr != NULL ) | |
417 | { | |
418 | signed_size_type const next_ring_index = prev_seg_id_ptr->ring_index + 1; | |
419 | BOOST_GEOMETRY_ASSERT(next_ring_index >= 0); | |
420 | ||
421 | // if one of the last rings of previous single geometry was ommited | |
422 | if ( static_cast<std::size_t>(next_ring_index) | |
423 | < geometry::num_interior_rings( | |
424 | single_geometry(geometry2, *prev_seg_id_ptr)) ) | |
425 | { | |
426 | // we can be sure that the exterior overlaps the boundary | |
427 | relate::set<exterior, boundary, '1', TransposeResult>(result); | |
428 | } | |
429 | } | |
430 | } | |
431 | } | |
432 | ||
433 | template <typename It, typename Pred, typename Comp> | |
434 | static void for_each_equal_range(It first, It last, Pred pred, Comp comp) | |
435 | { | |
436 | if ( first == last ) | |
437 | return; | |
438 | ||
439 | It first_equal = first; | |
440 | It prev = first; | |
441 | for ( ++first ; ; ++first, ++prev ) | |
442 | { | |
443 | if ( first == last || !comp(*prev, *first) ) | |
444 | { | |
445 | pred(first_equal, first); | |
446 | first_equal = first; | |
447 | } | |
448 | ||
449 | if ( first == last ) | |
450 | break; | |
451 | } | |
452 | } | |
453 | ||
454 | struct same_ip | |
455 | { | |
456 | template <typename Turn> | |
457 | bool operator()(Turn const& left, Turn const& right) const | |
458 | { | |
459 | return left.operations[0].seg_id == right.operations[0].seg_id | |
460 | && left.operations[0].fraction == right.operations[0].fraction; | |
461 | } | |
462 | }; | |
463 | ||
464 | struct same_ip_and_multi_index | |
465 | { | |
466 | template <typename Turn> | |
467 | bool operator()(Turn const& left, Turn const& right) const | |
468 | { | |
469 | return same_ip()(left, right) | |
470 | && left.operations[1].seg_id.multi_index == right.operations[1].seg_id.multi_index; | |
471 | } | |
472 | }; | |
473 | ||
474 | template <typename OpToPriority> | |
475 | struct set_turns_group_priority | |
476 | { | |
477 | template <typename TurnIt> | |
478 | void operator()(TurnIt first, TurnIt last) const | |
479 | { | |
480 | BOOST_GEOMETRY_ASSERT(first != last); | |
481 | static OpToPriority op_to_priority; | |
482 | // find the operation with the least priority | |
483 | int least_priority = op_to_priority(first->operations[0]); | |
484 | for ( TurnIt it = first + 1 ; it != last ; ++it ) | |
485 | { | |
486 | int priority = op_to_priority(it->operations[0]); | |
487 | if ( priority < least_priority ) | |
488 | least_priority = priority; | |
489 | } | |
490 | // set the least priority for all turns of the group | |
491 | for ( TurnIt it = first ; it != last ; ++it ) | |
492 | { | |
493 | it->priority = least_priority; | |
494 | } | |
495 | } | |
496 | }; | |
497 | ||
498 | template <typename SingleLess> | |
499 | struct sort_turns_group | |
500 | { | |
501 | struct less | |
502 | { | |
503 | template <typename Turn> | |
504 | bool operator()(Turn const& left, Turn const& right) const | |
505 | { | |
506 | return left.operations[1].seg_id.multi_index == right.operations[1].seg_id.multi_index ? | |
507 | SingleLess()(left, right) : | |
508 | left.priority < right.priority; | |
509 | } | |
510 | }; | |
511 | ||
512 | template <typename TurnIt> | |
513 | void operator()(TurnIt first, TurnIt last) const | |
514 | { | |
515 | std::sort(first, last, less()); | |
516 | } | |
517 | }; | |
518 | ||
92f5a8d4 | 519 | template <typename CSTag, typename TurnIt> |
20effc67 | 520 | static void sort_dispatch(TurnIt first, TurnIt last, std::true_type const& /*is_multi*/) |
7c673cae FG |
521 | { |
522 | // sort turns by Linear seg_id, then by fraction, then by other multi_index | |
92f5a8d4 | 523 | typedef turns::less<0, turns::less_other_multi_index<0>, CSTag> less; |
7c673cae FG |
524 | std::sort(first, last, less()); |
525 | ||
526 | // For the same IP and multi_index - the same other's single geometry | |
527 | // set priorities as the least operation found for the whole single geometry | |
528 | // so e.g. single geometries containing 'u' will always be before those only containing 'i' | |
529 | typedef turns::op_to_int<0,2,3,1,4,0> op_to_int_xuic; | |
530 | for_each_equal_range(first, last, | |
531 | set_turns_group_priority<op_to_int_xuic>(), // least operation in xuic order | |
532 | same_ip_and_multi_index()); // other's multi_index | |
533 | ||
534 | // When priorities for single geometries are set now sort turns for the same IP | |
535 | // if multi_index is the same sort them according to the single-less | |
536 | // else use priority of the whole single-geometry set earlier | |
92f5a8d4 | 537 | typedef turns::less<0, turns::less_op_linear_areal_single<0>, CSTag> single_less; |
7c673cae FG |
538 | for_each_equal_range(first, last, |
539 | sort_turns_group<single_less>(), | |
540 | same_ip()); | |
541 | } | |
542 | ||
92f5a8d4 | 543 | template <typename CSTag, typename TurnIt> |
20effc67 | 544 | static void sort_dispatch(TurnIt first, TurnIt last, std::false_type const& /*is_multi*/) |
7c673cae FG |
545 | { |
546 | // sort turns by Linear seg_id, then by fraction, then | |
547 | // for same ring id: x, u, i, c | |
548 | // for different ring id: c, i, u, x | |
92f5a8d4 | 549 | typedef turns::less<0, turns::less_op_linear_areal_single<0>, CSTag> less; |
7c673cae FG |
550 | std::sort(first, last, less()); |
551 | } | |
552 | ||
553 | ||
554 | // interrupt policy which may be passed to get_turns to interrupt the analysis | |
555 | // based on the info in the passed result/mask | |
556 | template <typename Areal, typename Result> | |
557 | class interrupt_policy_linear_areal | |
558 | { | |
559 | public: | |
560 | static bool const enabled = true; | |
561 | ||
562 | interrupt_policy_linear_areal(Areal const& areal, Result & result) | |
563 | : m_result(result), m_areal(areal) | |
564 | , is_boundary_found(false) | |
565 | {} | |
566 | ||
567 | // TODO: since we update result for some operations here, we may not do it in the analyser! | |
568 | ||
569 | template <typename Range> | |
570 | inline bool apply(Range const& turns) | |
571 | { | |
572 | typedef typename boost::range_iterator<Range const>::type iterator; | |
573 | ||
574 | for (iterator it = boost::begin(turns) ; it != boost::end(turns) ; ++it) | |
575 | { | |
576 | if ( it->operations[0].operation == overlay::operation_intersection ) | |
577 | { | |
578 | bool const no_interior_rings | |
579 | = geometry::num_interior_rings( | |
580 | single_geometry(m_areal, it->operations[1].seg_id)) == 0; | |
581 | ||
582 | // WARNING! THIS IS TRUE ONLY IF THE POLYGON IS SIMPLE! | |
583 | // OR WITHOUT INTERIOR RINGS (AND OF COURSE VALID) | |
584 | if ( no_interior_rings ) | |
585 | update<interior, interior, '1', TransposeResult>(m_result); | |
586 | } | |
587 | else if ( it->operations[0].operation == overlay::operation_continue ) | |
588 | { | |
589 | update<interior, boundary, '1', TransposeResult>(m_result); | |
590 | is_boundary_found = true; | |
591 | } | |
592 | else if ( ( it->operations[0].operation == overlay::operation_union | |
593 | || it->operations[0].operation == overlay::operation_blocked ) | |
594 | && it->operations[0].position == overlay::position_middle ) | |
595 | { | |
596 | // TODO: here we could also check the boundaries and set BB at this point | |
597 | update<interior, boundary, '0', TransposeResult>(m_result); | |
598 | } | |
599 | } | |
600 | ||
601 | return m_result.interrupt; | |
602 | } | |
603 | ||
604 | private: | |
605 | Result & m_result; | |
606 | Areal const& m_areal; | |
607 | ||
608 | public: | |
609 | bool is_boundary_found; | |
610 | }; | |
611 | ||
612 | // This analyser should be used like Input or SinglePass Iterator | |
613 | // IMPORTANT! It should be called also for the end iterator - last | |
614 | template <typename TurnInfo> | |
615 | class turns_analyser | |
616 | { | |
617 | typedef typename TurnInfo::point_type turn_point_type; | |
618 | ||
619 | static const std::size_t op_id = 0; | |
620 | static const std::size_t other_op_id = 1; | |
621 | ||
92f5a8d4 | 622 | template <typename TurnPointCSTag, typename PointP, typename PointQ, |
1e59de90 | 623 | typename Strategy, |
92f5a8d4 TL |
624 | typename Pi = PointP, typename Pj = PointP, typename Pk = PointP, |
625 | typename Qi = PointQ, typename Qj = PointQ, typename Qk = PointQ | |
626 | > | |
627 | struct la_side_calculator | |
628 | { | |
1e59de90 TL |
629 | typedef decltype(std::declval<Strategy>().side()) side_strategy_type; |
630 | ||
92f5a8d4 | 631 | inline la_side_calculator(Pi const& pi, Pj const& pj, Pk const& pk, |
1e59de90 TL |
632 | Qi const& qi, Qj const& qj, Qk const& qk, |
633 | Strategy const& strategy) | |
92f5a8d4 TL |
634 | : m_pi(pi), m_pj(pj), m_pk(pk) |
635 | , m_qi(qi), m_qj(qj), m_qk(qk) | |
1e59de90 | 636 | , m_side_strategy(strategy.side()) |
92f5a8d4 TL |
637 | {} |
638 | ||
639 | inline int pk_wrt_p1() const { return m_side_strategy.apply(m_pi, m_pj, m_pk); } | |
640 | inline int qk_wrt_p1() const { return m_side_strategy.apply(m_pi, m_pj, m_qk); } | |
641 | inline int pk_wrt_q2() const { return m_side_strategy.apply(m_qj, m_qk, m_pk); } | |
642 | ||
643 | private : | |
644 | Pi const& m_pi; | |
645 | Pj const& m_pj; | |
646 | Pk const& m_pk; | |
647 | Qi const& m_qi; | |
648 | Qj const& m_qj; | |
649 | Qk const& m_qk; | |
650 | ||
1e59de90 | 651 | side_strategy_type m_side_strategy; |
92f5a8d4 TL |
652 | }; |
653 | ||
654 | ||
7c673cae FG |
655 | public: |
656 | turns_analyser() | |
657 | : m_previous_turn_ptr(NULL) | |
658 | , m_previous_operation(overlay::operation_none) | |
659 | , m_boundary_counter(0) | |
660 | , m_interior_detected(false) | |
661 | , m_first_interior_other_id_ptr(NULL) | |
662 | , m_first_from_unknown(false) | |
663 | , m_first_from_unknown_boundary_detected(false) | |
664 | {} | |
665 | ||
666 | template <typename Result, | |
667 | typename TurnIt, | |
668 | typename Geometry, | |
669 | typename OtherGeometry, | |
b32b8144 | 670 | typename BoundaryChecker, |
1e59de90 | 671 | typename Strategy> |
7c673cae FG |
672 | void apply(Result & res, TurnIt it, |
673 | Geometry const& geometry, | |
674 | OtherGeometry const& other_geometry, | |
b32b8144 | 675 | BoundaryChecker const& boundary_checker, |
1e59de90 | 676 | Strategy const& strategy) |
7c673cae FG |
677 | { |
678 | overlay::operation_type op = it->operations[op_id].operation; | |
679 | ||
680 | if ( op != overlay::operation_union | |
681 | && op != overlay::operation_intersection | |
682 | && op != overlay::operation_blocked | |
683 | && op != overlay::operation_continue ) // operation_boundary / operation_boundary_intersection | |
684 | { | |
685 | return; | |
686 | } | |
687 | ||
688 | segment_identifier const& seg_id = it->operations[op_id].seg_id; | |
689 | segment_identifier const& other_id = it->operations[other_op_id].seg_id; | |
690 | ||
691 | const bool first_in_range = m_seg_watcher.update(seg_id); | |
692 | ||
693 | // TODO: should apply() for the post-last ip be called if first_in_range ? | |
694 | // this would unify how last points in ranges are handled | |
695 | // possibly replacing parts of the code below | |
696 | // e.g. for is_multi and m_interior_detected | |
697 | ||
698 | // handle possible exit | |
699 | bool fake_enter_detected = false; | |
700 | if ( m_exit_watcher.get_exit_operation() == overlay::operation_union ) | |
701 | { | |
702 | // real exit point - may be multiple | |
703 | // we know that we entered and now we exit | |
92f5a8d4 | 704 | if ( ! turn_on_the_same_ip<op_id>(m_exit_watcher.get_exit_turn(), *it, |
1e59de90 | 705 | strategy) ) |
7c673cae FG |
706 | { |
707 | m_exit_watcher.reset_detected_exit(); | |
708 | ||
709 | update<interior, exterior, '1', TransposeResult>(res); | |
710 | ||
711 | // next single geometry | |
712 | if ( first_in_range && m_previous_turn_ptr ) | |
713 | { | |
714 | // NOTE: similar code is in the post-last-ip-apply() | |
715 | segment_identifier const& prev_seg_id = m_previous_turn_ptr->operations[op_id].seg_id; | |
716 | ||
717 | bool const prev_back_b = is_endpoint_on_boundary<boundary_back>( | |
718 | range::back(sub_range(geometry, prev_seg_id)), | |
719 | boundary_checker); | |
720 | ||
721 | // if there is a boundary on the last point | |
722 | if ( prev_back_b ) | |
723 | { | |
724 | update<boundary, exterior, '0', TransposeResult>(res); | |
725 | } | |
726 | } | |
727 | } | |
728 | // fake exit point, reset state | |
729 | else if ( op == overlay::operation_intersection | |
730 | || op == overlay::operation_continue ) // operation_boundary | |
731 | { | |
732 | m_exit_watcher.reset_detected_exit(); | |
733 | fake_enter_detected = true; | |
734 | } | |
735 | } | |
736 | else if ( m_exit_watcher.get_exit_operation() == overlay::operation_blocked ) | |
737 | { | |
738 | // ignore multiple BLOCKs for this same single geometry1 | |
739 | if ( op == overlay::operation_blocked | |
740 | && seg_id.multi_index == m_previous_turn_ptr->operations[op_id].seg_id.multi_index ) | |
741 | { | |
742 | return; | |
743 | } | |
744 | ||
745 | if ( ( op == overlay::operation_intersection | |
746 | || op == overlay::operation_continue ) | |
92f5a8d4 | 747 | && turn_on_the_same_ip<op_id>(m_exit_watcher.get_exit_turn(), *it, |
1e59de90 | 748 | strategy) ) |
7c673cae FG |
749 | { |
750 | fake_enter_detected = true; | |
751 | } | |
752 | ||
753 | m_exit_watcher.reset_detected_exit(); | |
754 | } | |
755 | ||
20effc67 | 756 | if ( BOOST_GEOMETRY_CONDITION( util::is_multi<OtherGeometry>::value ) |
7c673cae FG |
757 | && m_first_from_unknown ) |
758 | { | |
759 | // For MultiPolygon many x/u operations may be generated as a first IP | |
760 | // if for all turns x/u was generated and any of the Polygons doesn't contain the LineString | |
761 | // then we know that the LineString is outside | |
762 | // Similar with the u/u turns, if it was the first one it doesn't mean that the | |
763 | // Linestring came from the exterior | |
764 | if ( ( m_previous_operation == overlay::operation_blocked | |
765 | && ( op != overlay::operation_blocked // operation different than block | |
766 | || seg_id.multi_index != m_previous_turn_ptr->operations[op_id].seg_id.multi_index ) ) // or the next single-geometry | |
767 | || ( m_previous_operation == overlay::operation_union | |
92f5a8d4 | 768 | && ! turn_on_the_same_ip<op_id>(*m_previous_turn_ptr, *it, |
1e59de90 | 769 | strategy) ) |
7c673cae FG |
770 | ) |
771 | { | |
772 | update<interior, exterior, '1', TransposeResult>(res); | |
773 | if ( m_first_from_unknown_boundary_detected ) | |
774 | { | |
775 | update<boundary, exterior, '0', TransposeResult>(res); | |
776 | } | |
777 | ||
778 | m_first_from_unknown = false; | |
779 | m_first_from_unknown_boundary_detected = false; | |
780 | } | |
781 | } | |
782 | ||
783 | // NOTE: THE WHOLE m_interior_detected HANDLING IS HERE BECAUSE WE CAN'T EFFICIENTLY SORT TURNS (CORRECTLY) | |
784 | // BECAUSE THE SAME IP MAY BE REPRESENTED BY TWO SEGMENTS WITH DIFFERENT DISTANCES | |
785 | // IT WOULD REQUIRE THE CALCULATION OF MAX DISTANCE | |
786 | // TODO: WE COULD GET RID OF THE TEST IF THE DISTANCES WERE NORMALIZED | |
787 | ||
788 | // UPDATE: THEY SHOULD BE NORMALIZED NOW | |
789 | ||
790 | // TODO: THIS IS POTENTIALLY ERROREOUS! | |
791 | // THIS ALGORITHM DEPENDS ON SOME SPECIFIC SEQUENCE OF OPERATIONS | |
792 | // IT WOULD GIVE WRONG RESULTS E.G. | |
793 | // IN THE CASE OF SELF-TOUCHING POINT WHEN 'i' WOULD BE BEFORE 'u' | |
794 | ||
795 | // handle the interior overlap | |
796 | if ( m_interior_detected ) | |
797 | { | |
798 | BOOST_GEOMETRY_ASSERT_MSG(m_previous_turn_ptr, "non-NULL ptr expected"); | |
799 | ||
800 | // real interior overlap | |
92f5a8d4 | 801 | if ( ! turn_on_the_same_ip<op_id>(*m_previous_turn_ptr, *it, |
1e59de90 | 802 | strategy) ) |
7c673cae FG |
803 | { |
804 | update<interior, interior, '1', TransposeResult>(res); | |
805 | m_interior_detected = false; | |
806 | ||
807 | // new range detected - reset previous state and check the boundary | |
808 | if ( first_in_range ) | |
809 | { | |
810 | segment_identifier const& prev_seg_id = m_previous_turn_ptr->operations[op_id].seg_id; | |
811 | ||
812 | bool const prev_back_b = is_endpoint_on_boundary<boundary_back>( | |
813 | range::back(sub_range(geometry, prev_seg_id)), | |
814 | boundary_checker); | |
815 | ||
816 | // if there is a boundary on the last point | |
817 | if ( prev_back_b ) | |
818 | { | |
819 | update<boundary, interior, '0', TransposeResult>(res); | |
820 | } | |
821 | ||
822 | // The exit_watcher is reset below | |
823 | // m_exit_watcher.reset(); | |
824 | } | |
825 | } | |
826 | // fake interior overlap | |
827 | else if ( op == overlay::operation_continue ) | |
828 | { | |
829 | m_interior_detected = false; | |
830 | } | |
831 | else if ( op == overlay::operation_union ) | |
832 | { | |
833 | // TODO: this probably is not a good way of handling the interiors/enters | |
834 | // the solution similar to exit_watcher would be more robust | |
835 | // all enters should be kept and handled. | |
836 | // maybe integrate it with the exit_watcher -> enter_exit_watcher | |
837 | if ( m_first_interior_other_id_ptr | |
838 | && m_first_interior_other_id_ptr->multi_index == other_id.multi_index ) | |
839 | { | |
840 | m_interior_detected = false; | |
841 | } | |
842 | } | |
843 | } | |
844 | ||
845 | // NOTE: If post-last-ip apply() was called this wouldn't be needed | |
846 | if ( first_in_range ) | |
847 | { | |
848 | m_exit_watcher.reset(); | |
849 | m_boundary_counter = 0; | |
850 | m_first_from_unknown = false; | |
851 | m_first_from_unknown_boundary_detected = false; | |
852 | } | |
853 | ||
854 | // i/u, c/u | |
855 | if ( op == overlay::operation_intersection | |
856 | || op == overlay::operation_continue ) // operation_boundary/operation_boundary_intersection | |
857 | { | |
858 | bool const first_point = first_in_range || m_first_from_unknown; | |
859 | bool no_enters_detected = m_exit_watcher.is_outside(); | |
860 | m_exit_watcher.enter(*it); | |
861 | ||
862 | if ( op == overlay::operation_intersection ) | |
863 | { | |
864 | if ( m_boundary_counter > 0 && it->operations[op_id].is_collinear ) | |
865 | --m_boundary_counter; | |
866 | ||
867 | if ( m_boundary_counter == 0 ) | |
868 | { | |
869 | // interiors overlaps | |
870 | //update<interior, interior, '1', TransposeResult>(res); | |
871 | ||
872 | // TODO: think about the implementation of the more robust version | |
873 | // this way only the first enter will be handled | |
874 | if ( !m_interior_detected ) | |
875 | { | |
876 | // don't update now | |
877 | // we might enter a boundary of some other ring on the same IP | |
878 | m_interior_detected = true; | |
879 | m_first_interior_other_id_ptr = boost::addressof(other_id); | |
880 | } | |
881 | } | |
882 | } | |
883 | else // operation_boundary | |
884 | { | |
885 | // don't add to the count for all met boundaries | |
886 | // only if this is the "new" boundary | |
887 | if ( first_point || !it->operations[op_id].is_collinear ) | |
888 | ++m_boundary_counter; | |
889 | ||
890 | update<interior, boundary, '1', TransposeResult>(res); | |
891 | } | |
892 | ||
893 | bool const this_b | |
894 | = is_ip_on_boundary<boundary_front>(it->point, | |
895 | it->operations[op_id], | |
896 | boundary_checker, | |
897 | seg_id); | |
898 | // going inside on boundary point | |
899 | if ( this_b ) | |
900 | { | |
901 | update<boundary, boundary, '0', TransposeResult>(res); | |
902 | } | |
903 | // going inside on non-boundary point | |
904 | else | |
905 | { | |
906 | update<interior, boundary, '0', TransposeResult>(res); | |
907 | ||
908 | // if we didn't enter in the past, we were outside | |
909 | if ( no_enters_detected | |
910 | && ! fake_enter_detected | |
911 | && it->operations[op_id].position != overlay::position_front ) | |
912 | { | |
913 | // TODO: calculate_from_inside() is only needed if the current Linestring is not closed | |
914 | bool const from_inside = first_point | |
915 | && calculate_from_inside(geometry, | |
916 | other_geometry, | |
b32b8144 | 917 | *it, |
1e59de90 | 918 | strategy); |
7c673cae FG |
919 | |
920 | if ( from_inside ) | |
921 | update<interior, interior, '1', TransposeResult>(res); | |
922 | else | |
923 | update<interior, exterior, '1', TransposeResult>(res); | |
924 | ||
925 | // if it's the first IP then the first point is outside | |
926 | if ( first_point ) | |
927 | { | |
928 | bool const front_b = is_endpoint_on_boundary<boundary_front>( | |
929 | range::front(sub_range(geometry, seg_id)), | |
930 | boundary_checker); | |
931 | ||
932 | // if there is a boundary on the first point | |
933 | if ( front_b ) | |
934 | { | |
935 | if ( from_inside ) | |
936 | update<boundary, interior, '0', TransposeResult>(res); | |
937 | else | |
938 | update<boundary, exterior, '0', TransposeResult>(res); | |
939 | } | |
940 | } | |
941 | } | |
942 | } | |
943 | ||
20effc67 | 944 | if ( BOOST_GEOMETRY_CONDITION( util::is_multi<OtherGeometry>::value ) ) |
7c673cae FG |
945 | { |
946 | m_first_from_unknown = false; | |
947 | m_first_from_unknown_boundary_detected = false; | |
948 | } | |
949 | } | |
950 | // u/u, x/u | |
951 | else if ( op == overlay::operation_union || op == overlay::operation_blocked ) | |
952 | { | |
953 | bool const op_blocked = op == overlay::operation_blocked; | |
954 | bool const no_enters_detected = m_exit_watcher.is_outside() | |
955 | // TODO: is this condition ok? | |
956 | // TODO: move it into the exit_watcher? | |
957 | && m_exit_watcher.get_exit_operation() == overlay::operation_none; | |
958 | ||
959 | if ( op == overlay::operation_union ) | |
960 | { | |
961 | if ( m_boundary_counter > 0 && it->operations[op_id].is_collinear ) | |
962 | --m_boundary_counter; | |
963 | } | |
964 | else // overlay::operation_blocked | |
965 | { | |
966 | m_boundary_counter = 0; | |
967 | } | |
968 | ||
969 | // we're inside, possibly going out right now | |
970 | if ( ! no_enters_detected ) | |
971 | { | |
972 | if ( op_blocked | |
973 | && it->operations[op_id].position == overlay::position_back ) // ignore spikes! | |
974 | { | |
975 | // check if this is indeed the boundary point | |
976 | // NOTE: is_ip_on_boundary<>() should be called here but the result will be the same | |
977 | if ( is_endpoint_on_boundary<boundary_back>(it->point, boundary_checker) ) | |
978 | { | |
979 | update<boundary, boundary, '0', TransposeResult>(res); | |
980 | } | |
981 | } | |
982 | // union, inside, but no exit -> collinear on self-intersection point | |
983 | // not needed since we're already inside the boundary | |
984 | /*else if ( !exit_detected ) | |
985 | { | |
986 | update<interior, boundary, '0', TransposeResult>(res); | |
987 | }*/ | |
988 | } | |
989 | // we're outside or inside and this is the first turn | |
990 | else | |
991 | { | |
992 | bool const this_b = is_ip_on_boundary<boundary_any>(it->point, | |
993 | it->operations[op_id], | |
994 | boundary_checker, | |
995 | seg_id); | |
996 | // if current IP is on boundary of the geometry | |
997 | if ( this_b ) | |
998 | { | |
999 | update<boundary, boundary, '0', TransposeResult>(res); | |
1000 | } | |
1001 | // if current IP is not on boundary of the geometry | |
1002 | else | |
1003 | { | |
1004 | update<interior, boundary, '0', TransposeResult>(res); | |
1005 | } | |
1006 | ||
1007 | // TODO: very similar code is used in the handling of intersection | |
1008 | if ( it->operations[op_id].position != overlay::position_front ) | |
1009 | { | |
1010 | // TODO: calculate_from_inside() is only needed if the current Linestring is not closed | |
1011 | // NOTE: this is not enough for MultiPolygon and operation_blocked | |
1012 | // For LS/MultiPolygon multiple x/u turns may be generated | |
1013 | // the first checked Polygon may be the one which LS is outside for. | |
1014 | bool const first_point = first_in_range || m_first_from_unknown; | |
1015 | bool const first_from_inside = first_point | |
1016 | && calculate_from_inside(geometry, | |
1017 | other_geometry, | |
b32b8144 | 1018 | *it, |
1e59de90 | 1019 | strategy); |
7c673cae FG |
1020 | if ( first_from_inside ) |
1021 | { | |
1022 | update<interior, interior, '1', TransposeResult>(res); | |
1023 | ||
1024 | // notify the exit_watcher that we started inside | |
1025 | m_exit_watcher.enter(*it); | |
1026 | // and reset unknown flags since we know that we started inside | |
1027 | m_first_from_unknown = false; | |
1028 | m_first_from_unknown_boundary_detected = false; | |
1029 | } | |
1030 | else | |
1031 | { | |
20effc67 | 1032 | if ( BOOST_GEOMETRY_CONDITION( util::is_multi<OtherGeometry>::value ) |
7c673cae FG |
1033 | /*&& ( op == overlay::operation_blocked |
1034 | || op == overlay::operation_union )*/ ) // if we're here it's u or x | |
1035 | { | |
1036 | m_first_from_unknown = true; | |
1037 | } | |
1038 | else | |
1039 | { | |
1040 | update<interior, exterior, '1', TransposeResult>(res); | |
1041 | } | |
1042 | } | |
1043 | ||
1044 | // first IP on the last segment point - this means that the first point is outside or inside | |
1045 | if ( first_point && ( !this_b || op_blocked ) ) | |
1046 | { | |
1047 | bool const front_b = is_endpoint_on_boundary<boundary_front>( | |
1048 | range::front(sub_range(geometry, seg_id)), | |
1049 | boundary_checker); | |
1050 | ||
1051 | // if there is a boundary on the first point | |
1052 | if ( front_b ) | |
1053 | { | |
1054 | if ( first_from_inside ) | |
1055 | { | |
1056 | update<boundary, interior, '0', TransposeResult>(res); | |
1057 | } | |
1058 | else | |
1059 | { | |
20effc67 | 1060 | if ( BOOST_GEOMETRY_CONDITION( util::is_multi<OtherGeometry>::value ) |
7c673cae FG |
1061 | /*&& ( op == overlay::operation_blocked |
1062 | || op == overlay::operation_union )*/ ) // if we're here it's u or x | |
1063 | { | |
1064 | BOOST_GEOMETRY_ASSERT(m_first_from_unknown); | |
1065 | m_first_from_unknown_boundary_detected = true; | |
1066 | } | |
1067 | else | |
1068 | { | |
1069 | update<boundary, exterior, '0', TransposeResult>(res); | |
1070 | } | |
1071 | } | |
1072 | } | |
1073 | } | |
1074 | } | |
1075 | } | |
1076 | ||
1077 | // if we're going along a boundary, we exit only if the linestring was collinear | |
1078 | if ( m_boundary_counter == 0 | |
1079 | || it->operations[op_id].is_collinear ) | |
1080 | { | |
1081 | // notify the exit watcher about the possible exit | |
1082 | m_exit_watcher.exit(*it); | |
1083 | } | |
1084 | } | |
1085 | ||
1086 | // store ref to previously analysed (valid) turn | |
1087 | m_previous_turn_ptr = boost::addressof(*it); | |
1088 | // and previously analysed (valid) operation | |
1089 | m_previous_operation = op; | |
1090 | } | |
1091 | ||
1092 | // it == last | |
1093 | template <typename Result, | |
1094 | typename TurnIt, | |
1095 | typename Geometry, | |
1096 | typename OtherGeometry, | |
1097 | typename BoundaryChecker> | |
1098 | void apply(Result & res, | |
1099 | TurnIt first, TurnIt last, | |
1100 | Geometry const& geometry, | |
1101 | OtherGeometry const& /*other_geometry*/, | |
1102 | BoundaryChecker const& boundary_checker) | |
1103 | { | |
1104 | boost::ignore_unused(first, last); | |
1105 | //BOOST_GEOMETRY_ASSERT( first != last ); | |
1106 | ||
1107 | // For MultiPolygon many x/u operations may be generated as a first IP | |
1108 | // if for all turns x/u was generated and any of the Polygons doesn't contain the LineString | |
1109 | // then we know that the LineString is outside | |
20effc67 | 1110 | if ( BOOST_GEOMETRY_CONDITION( util::is_multi<OtherGeometry>::value ) |
7c673cae FG |
1111 | && m_first_from_unknown ) |
1112 | { | |
1113 | update<interior, exterior, '1', TransposeResult>(res); | |
1114 | if ( m_first_from_unknown_boundary_detected ) | |
1115 | { | |
1116 | update<boundary, exterior, '0', TransposeResult>(res); | |
1117 | } | |
1118 | ||
1119 | // done below | |
1120 | //m_first_from_unknown = false; | |
1121 | //m_first_from_unknown_boundary_detected = false; | |
1122 | } | |
1123 | ||
1124 | // here, the possible exit is the real one | |
1125 | // we know that we entered and now we exit | |
1126 | if ( /*m_exit_watcher.get_exit_operation() == overlay::operation_union // THIS CHECK IS REDUNDANT | |
1127 | ||*/ m_previous_operation == overlay::operation_union | |
1128 | && !m_interior_detected ) | |
1129 | { | |
1130 | // for sure | |
1131 | update<interior, exterior, '1', TransposeResult>(res); | |
1132 | ||
1133 | BOOST_GEOMETRY_ASSERT(first != last); | |
1134 | BOOST_GEOMETRY_ASSERT(m_previous_turn_ptr); | |
1135 | ||
1136 | segment_identifier const& prev_seg_id = m_previous_turn_ptr->operations[op_id].seg_id; | |
1137 | ||
1138 | bool const prev_back_b = is_endpoint_on_boundary<boundary_back>( | |
1139 | range::back(sub_range(geometry, prev_seg_id)), | |
1140 | boundary_checker); | |
1141 | ||
1142 | // if there is a boundary on the last point | |
1143 | if ( prev_back_b ) | |
1144 | { | |
1145 | update<boundary, exterior, '0', TransposeResult>(res); | |
1146 | } | |
1147 | } | |
1148 | // we might enter some Areal and didn't go out, | |
1149 | else if ( m_previous_operation == overlay::operation_intersection | |
1150 | || m_interior_detected ) | |
1151 | { | |
1152 | // just in case | |
1153 | update<interior, interior, '1', TransposeResult>(res); | |
1154 | m_interior_detected = false; | |
1155 | ||
1156 | BOOST_GEOMETRY_ASSERT(first != last); | |
1157 | BOOST_GEOMETRY_ASSERT(m_previous_turn_ptr); | |
1158 | ||
1159 | segment_identifier const& prev_seg_id = m_previous_turn_ptr->operations[op_id].seg_id; | |
1160 | ||
1161 | bool const prev_back_b = is_endpoint_on_boundary<boundary_back>( | |
1162 | range::back(sub_range(geometry, prev_seg_id)), | |
1163 | boundary_checker); | |
1164 | ||
1165 | // if there is a boundary on the last point | |
1166 | if ( prev_back_b ) | |
1167 | { | |
1168 | update<boundary, interior, '0', TransposeResult>(res); | |
1169 | } | |
1170 | } | |
1171 | ||
1172 | // This condition may be false if the Linestring is lying on the Polygon's collinear spike | |
1173 | // if Polygon's spikes are not handled in get_turns() or relate() (they currently aren't) | |
1174 | //BOOST_GEOMETRY_ASSERT_MSG(m_previous_operation != overlay::operation_continue, | |
1175 | // "Unexpected operation! Probably the error in get_turns(L,A) or relate(L,A)"); | |
1176 | // Currently one c/c turn is generated for the exit | |
1177 | // when a Linestring is going out on a collinear spike | |
1178 | // When a Linestring is going in on a collinear spike | |
1179 | // the turn is not generated for the entry | |
1180 | // So assume it's the former | |
1181 | if ( m_previous_operation == overlay::operation_continue ) | |
1182 | { | |
1183 | update<interior, exterior, '1', TransposeResult>(res); | |
1184 | ||
1185 | segment_identifier const& prev_seg_id = m_previous_turn_ptr->operations[op_id].seg_id; | |
1186 | ||
1187 | bool const prev_back_b = is_endpoint_on_boundary<boundary_back>( | |
1188 | range::back(sub_range(geometry, prev_seg_id)), | |
1189 | boundary_checker); | |
1190 | ||
1191 | // if there is a boundary on the last point | |
1192 | if ( prev_back_b ) | |
1193 | { | |
1194 | update<boundary, exterior, '0', TransposeResult>(res); | |
1195 | } | |
1196 | } | |
1197 | ||
1198 | // Reset exit watcher before the analysis of the next Linestring | |
1199 | m_exit_watcher.reset(); | |
1200 | m_boundary_counter = 0; | |
1201 | m_first_from_unknown = false; | |
1202 | m_first_from_unknown_boundary_detected = false; | |
1203 | } | |
1204 | ||
1205 | // check if the passed turn's segment of Linear geometry arrived | |
1206 | // from the inside or the outside of the Areal geometry | |
1e59de90 | 1207 | template <typename Turn, typename Strategy> |
7c673cae FG |
1208 | static inline bool calculate_from_inside(Geometry1 const& geometry1, |
1209 | Geometry2 const& geometry2, | |
b32b8144 | 1210 | Turn const& turn, |
1e59de90 | 1211 | Strategy const& strategy) |
7c673cae FG |
1212 | { |
1213 | typedef typename cs_tag<typename Turn::point_type>::type cs_tag; | |
1214 | ||
1215 | if ( turn.operations[op_id].position == overlay::position_front ) | |
1216 | return false; | |
1217 | ||
1218 | typename sub_range_return_type<Geometry1 const>::type | |
1219 | range1 = sub_range(geometry1, turn.operations[op_id].seg_id); | |
1220 | ||
1e59de90 TL |
1221 | using range2_view = detail::closed_clockwise_view<typename ring_type<Geometry2>::type const>; |
1222 | using range2_iterator = typename boost::range_iterator<range2_view const>::type; | |
1223 | range2_view const range2(sub_range(geometry2, turn.operations[other_op_id].seg_id)); | |
7c673cae FG |
1224 | |
1225 | BOOST_GEOMETRY_ASSERT(boost::size(range1)); | |
1226 | std::size_t const s2 = boost::size(range2); | |
1227 | BOOST_GEOMETRY_ASSERT(s2 > 2); | |
1228 | std::size_t const seg_count2 = s2 - 1; | |
1229 | ||
1230 | std::size_t const p_seg_ij = static_cast<std::size_t>(turn.operations[op_id].seg_id.segment_index); | |
1231 | std::size_t const q_seg_ij = static_cast<std::size_t>(turn.operations[other_op_id].seg_id.segment_index); | |
1232 | ||
1233 | BOOST_GEOMETRY_ASSERT(p_seg_ij + 1 < boost::size(range1)); | |
1234 | BOOST_GEOMETRY_ASSERT(q_seg_ij + 1 < s2); | |
1235 | ||
1236 | point1_type const& pi = range::at(range1, p_seg_ij); | |
1237 | point2_type const& qi = range::at(range2, q_seg_ij); | |
1238 | point2_type const& qj = range::at(range2, q_seg_ij + 1); | |
1239 | point1_type qi_conv; | |
1240 | geometry::convert(qi, qi_conv); | |
1e59de90 | 1241 | bool const is_ip_qj = equals::equals_point_point(turn.point, qj, strategy); |
7c673cae FG |
1242 | // TODO: test this! |
1243 | // BOOST_GEOMETRY_ASSERT(!equals::equals_point_point(turn.point, pi)); | |
1244 | // BOOST_GEOMETRY_ASSERT(!equals::equals_point_point(turn.point, qi)); | |
1245 | point1_type new_pj; | |
1246 | geometry::convert(turn.point, new_pj); | |
1247 | ||
1248 | if ( is_ip_qj ) | |
1249 | { | |
1250 | std::size_t const q_seg_jk = (q_seg_ij + 1) % seg_count2; | |
1251 | // TODO: the following function should return immediately, however the worst case complexity is O(N) | |
1252 | // It would be good to replace it with some O(1) mechanism | |
1253 | range2_iterator qk_it = find_next_non_duplicated(boost::begin(range2), | |
1254 | range::pos(range2, q_seg_jk), | |
92f5a8d4 | 1255 | boost::end(range2), |
1e59de90 | 1256 | strategy); |
7c673cae FG |
1257 | |
1258 | // Will this sequence of points be always correct? | |
1e59de90 TL |
1259 | la_side_calculator<cs_tag, point1_type, point2_type, Strategy> |
1260 | side_calc(qi_conv, new_pj, pi, qi, qj, *qk_it, strategy); | |
7c673cae FG |
1261 | |
1262 | return calculate_from_inside_sides(side_calc); | |
1263 | } | |
1264 | else | |
1265 | { | |
b32b8144 | 1266 | point2_type new_qj; |
7c673cae FG |
1267 | geometry::convert(turn.point, new_qj); |
1268 | ||
1e59de90 TL |
1269 | la_side_calculator<cs_tag, point1_type, point2_type, Strategy> |
1270 | side_calc(qi_conv, new_pj, pi, qi, new_qj, qj, strategy); | |
7c673cae FG |
1271 | |
1272 | return calculate_from_inside_sides(side_calc); | |
1273 | } | |
1274 | } | |
1275 | ||
1e59de90 | 1276 | template <typename It, typename Strategy> |
92f5a8d4 | 1277 | static inline It find_next_non_duplicated(It first, It current, It last, |
1e59de90 | 1278 | Strategy const& strategy) |
7c673cae FG |
1279 | { |
1280 | BOOST_GEOMETRY_ASSERT( current != last ); | |
1281 | ||
1282 | It it = current; | |
1283 | ||
1284 | for ( ++it ; it != last ; ++it ) | |
1285 | { | |
92f5a8d4 | 1286 | if ( !equals::equals_point_point(*current, *it, strategy) ) |
7c673cae FG |
1287 | return it; |
1288 | } | |
1289 | ||
1290 | // if not found start from the beginning | |
1291 | for ( it = first ; it != current ; ++it ) | |
1292 | { | |
92f5a8d4 | 1293 | if ( !equals::equals_point_point(*current, *it, strategy) ) |
7c673cae FG |
1294 | return it; |
1295 | } | |
1296 | ||
1297 | return current; | |
1298 | } | |
1299 | ||
1300 | // calculate inside or outside based on side_calc | |
1301 | // this is simplified version of a check from equal<> | |
1302 | template <typename SideCalc> | |
1303 | static inline bool calculate_from_inside_sides(SideCalc const& side_calc) | |
1304 | { | |
1305 | int const side_pk_p = side_calc.pk_wrt_p1(); | |
1306 | int const side_qk_p = side_calc.qk_wrt_p1(); | |
1307 | // If they turn to same side (not opposite sides) | |
1308 | if (! overlay::base_turn_handler::opposite(side_pk_p, side_qk_p)) | |
1309 | { | |
1310 | int const side_pk_q2 = side_calc.pk_wrt_q2(); | |
1311 | return side_pk_q2 == -1; | |
1312 | } | |
1313 | else | |
1314 | { | |
1315 | return side_pk_p == -1; | |
1316 | } | |
1317 | } | |
1318 | ||
1319 | private: | |
1320 | exit_watcher<TurnInfo, op_id> m_exit_watcher; | |
1321 | segment_watcher<same_single> m_seg_watcher; | |
1322 | TurnInfo * m_previous_turn_ptr; | |
1323 | overlay::operation_type m_previous_operation; | |
1324 | unsigned m_boundary_counter; | |
1325 | bool m_interior_detected; | |
1326 | const segment_identifier * m_first_interior_other_id_ptr; | |
1327 | bool m_first_from_unknown; | |
1328 | bool m_first_from_unknown_boundary_detected; | |
1329 | }; | |
1330 | ||
1331 | // call analyser.apply() for each turn in range | |
1332 | // IMPORTANT! The analyser is also called for the end iterator - last | |
1333 | template <typename Result, | |
1334 | typename TurnIt, | |
1335 | typename Analyser, | |
1336 | typename Geometry, | |
1337 | typename OtherGeometry, | |
b32b8144 | 1338 | typename BoundaryChecker, |
1e59de90 | 1339 | typename Strategy> |
7c673cae FG |
1340 | static inline void analyse_each_turn(Result & res, |
1341 | Analyser & analyser, | |
1342 | TurnIt first, TurnIt last, | |
1343 | Geometry const& geometry, | |
1344 | OtherGeometry const& other_geometry, | |
b32b8144 | 1345 | BoundaryChecker const& boundary_checker, |
1e59de90 | 1346 | Strategy const& strategy) |
7c673cae FG |
1347 | { |
1348 | if ( first == last ) | |
1349 | return; | |
1350 | ||
1351 | for ( TurnIt it = first ; it != last ; ++it ) | |
1352 | { | |
1353 | analyser.apply(res, it, | |
1354 | geometry, other_geometry, | |
b32b8144 | 1355 | boundary_checker, |
1e59de90 | 1356 | strategy); |
7c673cae FG |
1357 | |
1358 | if ( BOOST_GEOMETRY_CONDITION( res.interrupt ) ) | |
1359 | return; | |
1360 | } | |
1361 | ||
1362 | analyser.apply(res, first, last, | |
1363 | geometry, other_geometry, | |
1364 | boundary_checker); | |
1365 | } | |
1366 | ||
1367 | // less comparator comparing multi_index then ring_index | |
1368 | // may be used to sort turns by ring | |
1369 | struct less_ring | |
1370 | { | |
1371 | template <typename Turn> | |
1372 | inline bool operator()(Turn const& left, Turn const& right) const | |
1373 | { | |
1374 | return left.operations[1].seg_id.multi_index < right.operations[1].seg_id.multi_index | |
1375 | || ( left.operations[1].seg_id.multi_index == right.operations[1].seg_id.multi_index | |
1376 | && left.operations[1].seg_id.ring_index < right.operations[1].seg_id.ring_index ); | |
1377 | } | |
1378 | }; | |
1379 | ||
1380 | // policy/functor checking if a turn's operation is operation_continue | |
1381 | struct has_boundary_intersection | |
1382 | { | |
1383 | has_boundary_intersection() | |
1384 | : result(false) {} | |
1385 | ||
1386 | template <typename Turn> | |
1387 | inline void operator()(Turn const& turn) | |
1388 | { | |
1389 | if ( turn.operations[1].operation == overlay::operation_continue ) | |
1390 | result = true; | |
1391 | } | |
1392 | ||
1393 | bool result; | |
1394 | }; | |
1395 | ||
1396 | // iterate through the range and search for the different multi_index or ring_index | |
1397 | // also call fun for each turn in the current range | |
1398 | template <typename It, typename Fun> | |
1399 | static inline It find_next_ring(It first, It last, Fun & fun) | |
1400 | { | |
1401 | if ( first == last ) | |
1402 | return last; | |
1403 | ||
1404 | signed_size_type const multi_index = first->operations[1].seg_id.multi_index; | |
1405 | signed_size_type const ring_index = first->operations[1].seg_id.ring_index; | |
1406 | ||
1407 | fun(*first); | |
1408 | ++first; | |
1409 | ||
1410 | for ( ; first != last ; ++first ) | |
1411 | { | |
1412 | if ( multi_index != first->operations[1].seg_id.multi_index | |
1413 | || ring_index != first->operations[1].seg_id.ring_index ) | |
1414 | { | |
1415 | return first; | |
1416 | } | |
1417 | ||
1418 | fun(*first); | |
1419 | } | |
1420 | ||
1421 | return last; | |
1422 | } | |
1423 | ||
1424 | // analyser which called for turns sorted by seg/distance/operation | |
1425 | // checks if the boundary of Areal geometry really got out | |
1426 | // into the exterior of Linear geometry | |
1427 | template <typename TurnInfo> | |
1428 | class areal_boundary_analyser | |
1429 | { | |
1430 | public: | |
1431 | areal_boundary_analyser() | |
1432 | : is_union_detected(false) | |
1433 | , m_previous_turn_ptr(NULL) | |
1434 | {} | |
1435 | ||
1e59de90 | 1436 | template <typename TurnIt, typename Strategy> |
92f5a8d4 | 1437 | bool apply(TurnIt /*first*/, TurnIt it, TurnIt last, |
1e59de90 | 1438 | Strategy const& strategy) |
7c673cae FG |
1439 | { |
1440 | overlay::operation_type op = it->operations[1].operation; | |
1441 | ||
1442 | if ( it != last ) | |
1443 | { | |
1444 | if ( op != overlay::operation_union | |
1445 | && op != overlay::operation_continue ) | |
1446 | { | |
1447 | return true; | |
1448 | } | |
1449 | ||
1450 | if ( is_union_detected ) | |
1451 | { | |
1452 | BOOST_GEOMETRY_ASSERT(m_previous_turn_ptr != NULL); | |
92f5a8d4 | 1453 | if ( !detail::equals::equals_point_point(it->point, m_previous_turn_ptr->point, strategy) ) |
7c673cae FG |
1454 | { |
1455 | // break | |
1456 | return false; | |
1457 | } | |
1458 | else if ( op == overlay::operation_continue ) // operation_boundary | |
1459 | { | |
1460 | is_union_detected = false; | |
1461 | } | |
1462 | } | |
1463 | ||
1464 | if ( op == overlay::operation_union ) | |
1465 | { | |
1466 | is_union_detected = true; | |
1467 | m_previous_turn_ptr = boost::addressof(*it); | |
1468 | } | |
1469 | ||
1470 | return true; | |
1471 | } | |
1472 | else | |
1473 | { | |
1474 | return false; | |
1475 | } | |
1476 | } | |
1477 | ||
1478 | bool is_union_detected; | |
1479 | ||
1480 | private: | |
1481 | const TurnInfo * m_previous_turn_ptr; | |
1482 | }; | |
1483 | }; | |
1484 | ||
1485 | template <typename Geometry1, typename Geometry2> | |
1486 | struct areal_linear | |
1487 | { | |
1488 | typedef linear_areal<Geometry2, Geometry1, true> linear_areal_type; | |
1489 | ||
1490 | static const bool interruption_enabled = linear_areal_type::interruption_enabled; | |
1491 | ||
1e59de90 | 1492 | template <typename Result, typename Strategy> |
b32b8144 FG |
1493 | static inline void apply(Geometry1 const& geometry1, Geometry2 const& geometry2, |
1494 | Result & result, | |
1e59de90 | 1495 | Strategy const& strategy) |
7c673cae | 1496 | { |
1e59de90 | 1497 | linear_areal_type::apply(geometry2, geometry1, result, strategy); |
7c673cae FG |
1498 | } |
1499 | }; | |
1500 | ||
1501 | }} // namespace detail::relate | |
1502 | #endif // DOXYGEN_NO_DETAIL | |
1503 | ||
1504 | }} // namespace boost::geometry | |
1505 | ||
1506 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LINEAR_AREAL_HPP |