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