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