]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
b32b8144 FG |
3 | // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. |
4 | ||
f67539c2 | 5 | // Copyright (c) 2014-2020, Oracle and/or its affiliates. |
b32b8144 FG |
6 | |
7 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle | |
8 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
7c673cae FG |
9 | |
10 | // Licensed under the Boost Software License version 1.0. | |
11 | // http://www.boost.org/users/license.html | |
12 | ||
7c673cae FG |
13 | |
14 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_LINEAR_LINEAR_HPP | |
15 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_LINEAR_LINEAR_HPP | |
16 | ||
17 | #include <cstddef> | |
18 | #include <algorithm> | |
19 | #include <iterator> | |
20 | ||
21 | #include <boost/range.hpp> | |
b32b8144 | 22 | #include <boost/throw_exception.hpp> |
7c673cae FG |
23 | |
24 | #include <boost/geometry/core/assert.hpp> | |
25 | #include <boost/geometry/core/tag.hpp> | |
26 | #include <boost/geometry/core/tags.hpp> | |
27 | ||
28 | #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp> | |
29 | #include <boost/geometry/algorithms/detail/overlay/follow.hpp> | |
30 | #include <boost/geometry/algorithms/detail/overlay/inconsistent_turns_exception.hpp> | |
31 | #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> | |
32 | #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp> | |
33 | #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> | |
34 | ||
35 | #include <boost/geometry/algorithms/detail/turns/debug_turn.hpp> | |
36 | ||
f67539c2 TL |
37 | #include <boost/geometry/algorithms/detail/tupled_output.hpp> |
38 | ||
7c673cae FG |
39 | #include <boost/geometry/algorithms/convert.hpp> |
40 | #include <boost/geometry/algorithms/not_implemented.hpp> | |
41 | ||
42 | ||
43 | namespace boost { namespace geometry | |
44 | { | |
45 | ||
46 | #ifndef DOXYGEN_NO_DETAIL | |
47 | namespace detail { namespace overlay | |
48 | { | |
49 | ||
50 | namespace following { namespace linear | |
51 | { | |
52 | ||
53 | ||
54 | ||
55 | ||
56 | // follower for linear/linear geometries set operations | |
57 | ||
58 | template <typename Turn, typename Operation> | |
59 | static inline bool is_entering(Turn const& turn, | |
60 | Operation const& operation) | |
61 | { | |
62 | if ( turn.method != method_touch && turn.method != method_touch_interior ) | |
63 | { | |
64 | return false; | |
65 | } | |
66 | return operation.operation == operation_intersection; | |
67 | } | |
68 | ||
69 | ||
70 | ||
71 | template <typename Turn, typename Operation> | |
72 | static inline bool is_staying_inside(Turn const& turn, | |
73 | Operation const& operation, | |
74 | bool entered) | |
75 | { | |
76 | if ( !entered ) | |
77 | { | |
78 | return false; | |
79 | } | |
80 | ||
81 | if ( turn.method != method_equal && turn.method != method_collinear ) | |
82 | { | |
83 | return false; | |
84 | } | |
85 | return operation.operation == operation_continue; | |
86 | } | |
87 | ||
88 | ||
89 | ||
90 | template <typename Turn, typename Operation> | |
91 | static inline bool is_leaving(Turn const& turn, | |
92 | Operation const& operation, | |
93 | bool entered) | |
94 | { | |
95 | if ( !entered ) | |
96 | { | |
97 | return false; | |
98 | } | |
99 | ||
100 | if ( turn.method != method_touch | |
101 | && turn.method != method_touch_interior | |
102 | && turn.method != method_equal | |
103 | && turn.method != method_collinear ) | |
104 | { | |
105 | return false; | |
106 | } | |
107 | ||
108 | if ( operation.operation == operation_blocked ) | |
109 | { | |
110 | return true; | |
111 | } | |
112 | ||
113 | if ( operation.operation != operation_union ) | |
114 | { | |
115 | return false; | |
116 | } | |
117 | ||
118 | return operation.is_collinear; | |
119 | } | |
120 | ||
121 | ||
122 | ||
123 | template <typename Turn, typename Operation> | |
124 | static inline bool is_isolated_point(Turn const& turn, | |
125 | Operation const& operation, | |
126 | bool entered) | |
127 | { | |
128 | if ( entered ) | |
129 | { | |
130 | return false; | |
131 | } | |
132 | ||
133 | if ( turn.method == method_none ) | |
134 | { | |
135 | BOOST_GEOMETRY_ASSERT( operation.operation == operation_continue ); | |
136 | return true; | |
137 | } | |
138 | ||
139 | if ( turn.method == method_crosses ) | |
140 | { | |
141 | return true; | |
142 | } | |
143 | ||
144 | if ( turn.method != method_touch && turn.method != method_touch_interior ) | |
145 | { | |
146 | return false; | |
147 | } | |
148 | ||
149 | if ( operation.operation == operation_blocked ) | |
150 | { | |
151 | return true; | |
152 | } | |
153 | ||
154 | if ( operation.operation != operation_union ) | |
155 | { | |
156 | return false; | |
157 | } | |
158 | ||
159 | return !operation.is_collinear; | |
160 | } | |
161 | ||
162 | ||
163 | ||
164 | ||
165 | ||
f67539c2 | 166 | // GeometryOut - linestring or tuple of at least point and linestring |
7c673cae FG |
167 | template |
168 | < | |
f67539c2 | 169 | typename GeometryOut, |
7c673cae FG |
170 | typename Linestring, |
171 | typename Linear, | |
172 | overlay_type OverlayType, | |
173 | bool FollowIsolatedPoints, | |
174 | bool FollowContinueTurns | |
175 | > | |
f67539c2 | 176 | class follow_linestring_linear |
7c673cae FG |
177 | { |
178 | protected: | |
179 | // allow spikes (false indicates: do not remove spikes) | |
180 | typedef following::action_selector<OverlayType, false> action; | |
181 | ||
f67539c2 TL |
182 | typedef geometry::detail::output_geometry_access |
183 | < | |
184 | GeometryOut, linestring_tag, linestring_tag | |
185 | > linear; | |
186 | typedef geometry::detail::output_geometry_access | |
187 | < | |
188 | GeometryOut, point_tag, linestring_tag | |
189 | > pointlike; | |
190 | ||
7c673cae FG |
191 | template |
192 | < | |
193 | typename TurnIterator, | |
194 | typename TurnOperationIterator, | |
f67539c2 | 195 | typename LinestringOut, |
7c673cae | 196 | typename SegmentIdentifier, |
b32b8144 FG |
197 | typename OutputIterator, |
198 | typename SideStrategy | |
7c673cae FG |
199 | > |
200 | static inline OutputIterator | |
201 | process_turn(TurnIterator it, | |
202 | TurnOperationIterator op_it, | |
203 | bool& entered, | |
204 | std::size_t& enter_count, | |
205 | Linestring const& linestring, | |
206 | LinestringOut& current_piece, | |
207 | SegmentIdentifier& current_segment_id, | |
b32b8144 FG |
208 | OutputIterator oit, |
209 | SideStrategy const& strategy) | |
7c673cae FG |
210 | { |
211 | // We don't rescale linear/linear | |
212 | detail::no_rescale_policy robust_policy; | |
213 | ||
214 | if ( is_entering(*it, *op_it) ) | |
215 | { | |
216 | detail::turns::debug_turn(*it, *op_it, "-> Entering"); | |
217 | ||
218 | entered = true; | |
219 | if ( enter_count == 0 ) | |
220 | { | |
f67539c2 TL |
221 | action::enter(current_piece, |
222 | linestring, | |
7c673cae FG |
223 | current_segment_id, |
224 | op_it->seg_id.segment_index, | |
f67539c2 TL |
225 | it->point, *op_it, strategy, robust_policy, |
226 | linear::get(oit)); | |
7c673cae FG |
227 | } |
228 | ++enter_count; | |
229 | } | |
230 | else if ( is_leaving(*it, *op_it, entered) ) | |
231 | { | |
232 | detail::turns::debug_turn(*it, *op_it, "-> Leaving"); | |
233 | ||
234 | --enter_count; | |
235 | if ( enter_count == 0 ) | |
236 | { | |
237 | entered = false; | |
f67539c2 TL |
238 | action::leave(current_piece, |
239 | linestring, | |
7c673cae FG |
240 | current_segment_id, |
241 | op_it->seg_id.segment_index, | |
f67539c2 TL |
242 | it->point, *op_it, strategy, robust_policy, |
243 | linear::get(oit)); | |
7c673cae FG |
244 | } |
245 | } | |
246 | else if ( FollowIsolatedPoints | |
247 | && is_isolated_point(*it, *op_it, entered) ) | |
248 | { | |
249 | detail::turns::debug_turn(*it, *op_it, "-> Isolated point"); | |
250 | ||
f67539c2 TL |
251 | action::template isolated_point |
252 | < | |
253 | typename pointlike::type | |
254 | >(it->point, pointlike::get(oit)); | |
7c673cae FG |
255 | } |
256 | else if ( FollowContinueTurns | |
257 | && is_staying_inside(*it, *op_it, entered) ) | |
258 | { | |
259 | detail::turns::debug_turn(*it, *op_it, "-> Staying inside"); | |
260 | ||
261 | entered = true; | |
262 | } | |
263 | return oit; | |
264 | } | |
265 | ||
266 | template | |
267 | < | |
268 | typename SegmentIdentifier, | |
f67539c2 | 269 | typename LinestringOut, |
b32b8144 FG |
270 | typename OutputIterator, |
271 | typename SideStrategy | |
7c673cae FG |
272 | > |
273 | static inline OutputIterator | |
274 | process_end(bool entered, | |
275 | Linestring const& linestring, | |
276 | SegmentIdentifier const& current_segment_id, | |
277 | LinestringOut& current_piece, | |
b32b8144 FG |
278 | OutputIterator oit, |
279 | SideStrategy const& strategy) | |
7c673cae FG |
280 | { |
281 | if ( action::is_entered(entered) ) | |
282 | { | |
283 | // We don't rescale linear/linear | |
284 | detail::no_rescale_policy robust_policy; | |
285 | ||
286 | detail::copy_segments::copy_segments_linestring | |
287 | < | |
288 | false, false // do not reverse; do not remove spikes | |
289 | >::apply(linestring, | |
290 | current_segment_id, | |
291 | static_cast<signed_size_type>(boost::size(linestring) - 1), | |
b32b8144 | 292 | strategy, |
7c673cae FG |
293 | robust_policy, |
294 | current_piece); | |
295 | } | |
296 | ||
297 | // Output the last one, if applicable | |
298 | if (::boost::size(current_piece) > 1) | |
299 | { | |
f67539c2 | 300 | *linear::get(oit)++ = current_piece; |
7c673cae FG |
301 | } |
302 | ||
303 | return oit; | |
304 | } | |
305 | ||
306 | public: | |
b32b8144 | 307 | template <typename TurnIterator, typename OutputIterator, typename SideStrategy> |
7c673cae FG |
308 | static inline OutputIterator |
309 | apply(Linestring const& linestring, Linear const&, | |
310 | TurnIterator first, TurnIterator beyond, | |
b32b8144 FG |
311 | OutputIterator oit, |
312 | SideStrategy const& strategy) | |
7c673cae FG |
313 | { |
314 | // Iterate through all intersection points (they are | |
315 | // ordered along the each line) | |
316 | ||
f67539c2 | 317 | typename linear::type current_piece; |
7c673cae FG |
318 | geometry::segment_identifier current_segment_id(0, -1, -1, -1); |
319 | ||
320 | bool entered = false; | |
321 | std::size_t enter_count = 0; | |
322 | ||
323 | for (TurnIterator it = first; it != beyond; ++it) | |
324 | { | |
325 | oit = process_turn(it, boost::begin(it->operations), | |
326 | entered, enter_count, | |
327 | linestring, | |
328 | current_piece, current_segment_id, | |
b32b8144 FG |
329 | oit, |
330 | strategy); | |
7c673cae FG |
331 | } |
332 | ||
333 | #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW) | |
334 | if (enter_count != 0) | |
335 | { | |
b32b8144 | 336 | BOOST_THROW_EXCEPTION(inconsistent_turns_exception()); |
7c673cae FG |
337 | } |
338 | #else | |
339 | BOOST_GEOMETRY_ASSERT(enter_count == 0); | |
340 | #endif | |
341 | ||
342 | return process_end(entered, linestring, | |
343 | current_segment_id, current_piece, | |
b32b8144 FG |
344 | oit, |
345 | strategy); | |
7c673cae FG |
346 | } |
347 | }; | |
348 | ||
349 | ||
350 | ||
351 | ||
352 | template | |
353 | < | |
354 | typename LinestringOut, | |
355 | typename MultiLinestring, | |
356 | typename Linear, | |
357 | overlay_type OverlayType, | |
358 | bool FollowIsolatedPoints, | |
359 | bool FollowContinueTurns | |
360 | > | |
f67539c2 TL |
361 | class follow_multilinestring_linear |
362 | : follow_linestring_linear | |
7c673cae FG |
363 | < |
364 | LinestringOut, | |
365 | typename boost::range_value<MultiLinestring>::type, | |
366 | Linear, | |
367 | OverlayType, | |
368 | FollowIsolatedPoints, | |
369 | FollowContinueTurns | |
370 | > | |
371 | { | |
372 | protected: | |
373 | typedef typename boost::range_value<MultiLinestring>::type Linestring; | |
374 | ||
f67539c2 | 375 | typedef follow_linestring_linear |
7c673cae FG |
376 | < |
377 | LinestringOut, Linestring, Linear, | |
378 | OverlayType, FollowIsolatedPoints, FollowContinueTurns | |
379 | > Base; | |
380 | ||
381 | typedef following::action_selector<OverlayType> action; | |
382 | ||
383 | typedef typename boost::range_iterator | |
384 | < | |
385 | MultiLinestring const | |
386 | >::type linestring_iterator; | |
387 | ||
388 | ||
389 | template <typename OutputIt, overlay_type OT> | |
390 | struct copy_linestrings_in_range | |
391 | { | |
392 | static inline OutputIt | |
393 | apply(linestring_iterator, linestring_iterator, OutputIt oit) | |
394 | { | |
395 | return oit; | |
396 | } | |
397 | }; | |
398 | ||
399 | template <typename OutputIt> | |
400 | struct copy_linestrings_in_range<OutputIt, overlay_difference> | |
401 | { | |
402 | static inline OutputIt | |
403 | apply(linestring_iterator first, linestring_iterator beyond, | |
404 | OutputIt oit) | |
405 | { | |
406 | for (linestring_iterator ls_it = first; ls_it != beyond; ++ls_it) | |
407 | { | |
408 | LinestringOut line_out; | |
409 | geometry::convert(*ls_it, line_out); | |
410 | *oit++ = line_out; | |
411 | } | |
412 | return oit; | |
413 | } | |
414 | }; | |
415 | ||
416 | template <typename TurnIterator> | |
417 | static inline signed_size_type get_multi_index(TurnIterator it) | |
418 | { | |
419 | return boost::begin(it->operations)->seg_id.multi_index; | |
420 | } | |
421 | ||
422 | class has_other_multi_id | |
423 | { | |
424 | private: | |
425 | signed_size_type m_multi_id; | |
426 | ||
427 | public: | |
428 | has_other_multi_id(signed_size_type multi_id) | |
429 | : m_multi_id(multi_id) {} | |
430 | ||
431 | template <typename Turn> | |
432 | bool operator()(Turn const& turn) const | |
433 | { | |
434 | return boost::begin(turn.operations)->seg_id.multi_index | |
435 | != m_multi_id; | |
436 | } | |
437 | }; | |
438 | ||
439 | public: | |
b32b8144 | 440 | template <typename TurnIterator, typename OutputIterator, typename SideStrategy> |
7c673cae FG |
441 | static inline OutputIterator |
442 | apply(MultiLinestring const& multilinestring, Linear const& linear, | |
443 | TurnIterator first, TurnIterator beyond, | |
b32b8144 FG |
444 | OutputIterator oit, |
445 | SideStrategy const& strategy) | |
7c673cae FG |
446 | { |
447 | BOOST_GEOMETRY_ASSERT( first != beyond ); | |
448 | ||
449 | typedef copy_linestrings_in_range | |
450 | < | |
451 | OutputIterator, OverlayType | |
452 | > copy_linestrings; | |
453 | ||
454 | linestring_iterator ls_first = boost::begin(multilinestring); | |
455 | linestring_iterator ls_beyond = boost::end(multilinestring); | |
456 | ||
457 | // Iterate through all intersection points (they are | |
458 | // ordered along the each linestring) | |
459 | ||
460 | signed_size_type current_multi_id = get_multi_index(first); | |
461 | ||
462 | oit = copy_linestrings::apply(ls_first, | |
463 | ls_first + current_multi_id, | |
464 | oit); | |
465 | ||
466 | TurnIterator per_ls_next = first; | |
467 | do { | |
468 | TurnIterator per_ls_current = per_ls_next; | |
469 | ||
470 | // find turn with different multi-index | |
471 | per_ls_next = std::find_if(per_ls_current, beyond, | |
472 | has_other_multi_id(current_multi_id)); | |
473 | ||
474 | oit = Base::apply(*(ls_first + current_multi_id), | |
b32b8144 | 475 | linear, per_ls_current, per_ls_next, oit, strategy); |
7c673cae FG |
476 | |
477 | signed_size_type next_multi_id = -1; | |
478 | linestring_iterator ls_next = ls_beyond; | |
479 | if ( per_ls_next != beyond ) | |
480 | { | |
481 | next_multi_id = get_multi_index(per_ls_next); | |
482 | ls_next = ls_first + next_multi_id; | |
483 | } | |
484 | oit = copy_linestrings::apply(ls_first + current_multi_id + 1, | |
485 | ls_next, | |
486 | oit); | |
487 | ||
488 | current_multi_id = next_multi_id; | |
489 | } | |
490 | while ( per_ls_next != beyond ); | |
491 | ||
492 | return oit; | |
493 | } | |
494 | }; | |
495 | ||
496 | ||
497 | ||
498 | ||
499 | ||
500 | ||
501 | template | |
502 | < | |
503 | typename LinestringOut, | |
504 | typename Geometry1, | |
505 | typename Geometry2, | |
506 | overlay_type OverlayType, | |
507 | bool FollowIsolatedPoints, | |
508 | bool FollowContinueTurns, | |
7c673cae FG |
509 | typename TagIn1 = typename tag<Geometry1>::type |
510 | > | |
511 | struct follow | |
f67539c2 | 512 | : not_implemented<Geometry1> |
7c673cae FG |
513 | {}; |
514 | ||
515 | ||
516 | ||
517 | template | |
518 | < | |
519 | typename LinestringOut, | |
520 | typename Linestring, | |
521 | typename Linear, | |
522 | overlay_type OverlayType, | |
523 | bool FollowIsolatedPoints, | |
524 | bool FollowContinueTurns | |
525 | > | |
526 | struct follow | |
527 | < | |
528 | LinestringOut, Linestring, Linear, | |
529 | OverlayType, FollowIsolatedPoints, FollowContinueTurns, | |
f67539c2 TL |
530 | linestring_tag |
531 | > : follow_linestring_linear | |
7c673cae FG |
532 | < |
533 | LinestringOut, Linestring, Linear, | |
534 | OverlayType, FollowIsolatedPoints, FollowContinueTurns | |
535 | > | |
536 | {}; | |
537 | ||
538 | ||
539 | template | |
540 | < | |
541 | typename LinestringOut, | |
542 | typename MultiLinestring, | |
543 | typename Linear, | |
544 | overlay_type OverlayType, | |
545 | bool FollowIsolatedPoints, | |
546 | bool FollowContinueTurns | |
547 | > | |
548 | struct follow | |
549 | < | |
550 | LinestringOut, MultiLinestring, Linear, | |
551 | OverlayType, FollowIsolatedPoints, FollowContinueTurns, | |
f67539c2 TL |
552 | multi_linestring_tag |
553 | > : follow_multilinestring_linear | |
7c673cae FG |
554 | < |
555 | LinestringOut, MultiLinestring, Linear, | |
556 | OverlayType, FollowIsolatedPoints, FollowContinueTurns | |
557 | > | |
558 | {}; | |
559 | ||
560 | ||
561 | ||
562 | }} // namespace following::linear | |
563 | ||
564 | }} // namespace detail::overlay | |
565 | #endif // DOXYGEN_NO_DETAIL | |
566 | ||
567 | }} // namespace boost::geometry | |
568 | ||
569 | ||
570 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_LINEAR_LINEAR_HPP |