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