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