1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
4 
5 // This file was modified by Oracle on 2014, 2017.
6 // Modifications copyright (c) 2014-2017 Oracle and/or its affiliates.
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 // Use, modification and distribution is subject to the Boost Software License,
11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
12 // http://www.boost.org/LICENSE_1_0.txt)
13 
14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP
16 
17 #include <cstddef>
18 
19 #include <boost/range.hpp>
20 #include <boost/mpl/assert.hpp>
21 
22 #include <boost/geometry/algorithms/detail/point_on_border.hpp>
23 #include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp>
24 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
25 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
26 
27 #include <boost/geometry/algorithms/covered_by.hpp>
28 #include <boost/geometry/algorithms/clear.hpp>
29 
30 
31 namespace boost { namespace geometry
32 {
33 
34 
35 #ifndef DOXYGEN_NO_DETAIL
36 namespace detail { namespace overlay
37 {
38 
39 namespace following
40 {
41 
42 template <typename Turn, typename Operation>
is_entering(Turn const &,Operation const & op)43 static inline bool is_entering(Turn const& /* TODO remove this parameter */, Operation const& op)
44 {
45     // (Blocked means: blocked for polygon/polygon intersection, because
46     // they are reversed. But for polygon/line it is similar to continue)
47     return op.operation == operation_intersection
48         || op.operation == operation_continue
49         || op.operation == operation_blocked
50         ;
51 }
52 
53 template
54 <
55     typename Turn,
56     typename Operation,
57     typename LineString,
58     typename Polygon,
59     typename PtInPolyStrategy
60 >
last_covered_by(Turn const & turn,Operation const & op,LineString const & linestring,Polygon const & polygon,PtInPolyStrategy const & strategy)61 static inline bool last_covered_by(Turn const& turn, Operation const& op,
62                 LineString const& linestring, Polygon const& polygon,
63                 PtInPolyStrategy const& strategy)
64 {
65     return geometry::covered_by(range::at(linestring, op.seg_id.segment_index), polygon, strategy);
66 }
67 
68 
69 template
70 <
71     typename Turn,
72     typename Operation,
73     typename LineString,
74     typename Polygon,
75     typename PtInPolyStrategy
76 >
is_leaving(Turn const & turn,Operation const & op,bool entered,bool first,LineString const & linestring,Polygon const & polygon,PtInPolyStrategy const & strategy)77 static inline bool is_leaving(Turn const& turn, Operation const& op,
78                 bool entered, bool first,
79                 LineString const& linestring, Polygon const& polygon,
80                 PtInPolyStrategy const& strategy)
81 {
82     if (op.operation == operation_union)
83     {
84         return entered
85             || turn.method == method_crosses
86             || (first && last_covered_by(turn, op, linestring, polygon, strategy))
87             ;
88     }
89     return false;
90 }
91 
92 
93 template
94 <
95     typename Turn,
96     typename Operation,
97     typename LineString,
98     typename Polygon,
99     typename PtInPolyStrategy
100 >
is_staying_inside(Turn const & turn,Operation const & op,bool entered,bool first,LineString const & linestring,Polygon const & polygon,PtInPolyStrategy const & strategy)101 static inline bool is_staying_inside(Turn const& turn, Operation const& op,
102                 bool entered, bool first,
103                 LineString const& linestring, Polygon const& polygon,
104                 PtInPolyStrategy const& strategy)
105 {
106     if (turn.method == method_crosses)
107     {
108         // The normal case, this is completely covered with entering/leaving
109         // so stay out of this time consuming "covered_by"
110         return false;
111     }
112 
113     if (is_entering(turn, op))
114     {
115         return entered || (first && last_covered_by(turn, op, linestring, polygon, strategy));
116     }
117 
118     return false;
119 }
120 
121 template
122 <
123     typename Turn,
124     typename Operation,
125     typename Linestring,
126     typename Polygon,
127     typename PtInPolyStrategy
128 >
was_entered(Turn const & turn,Operation const & op,bool first,Linestring const & linestring,Polygon const & polygon,PtInPolyStrategy const & strategy)129 static inline bool was_entered(Turn const& turn, Operation const& op, bool first,
130                 Linestring const& linestring, Polygon const& polygon,
131                 PtInPolyStrategy const& strategy)
132 {
133     if (first && (turn.method == method_collinear || turn.method == method_equal))
134     {
135         return last_covered_by(turn, op, linestring, polygon, strategy);
136     }
137     return false;
138 }
139 
140 
141 // Template specialization structure to call the right actions for the right type
142 template <overlay_type OverlayType, bool RemoveSpikes = true>
143 struct action_selector
144 {
145     // If you get here the overlay type is not intersection or difference
146     // BOOST_MPL_ASSERT(false);
147 };
148 
149 // Specialization for intersection, containing the implementation
150 template <bool RemoveSpikes>
151 struct action_selector<overlay_intersection, RemoveSpikes>
152 {
153     template
154     <
155         typename OutputIterator,
156         typename LineStringOut,
157         typename LineString,
158         typename Point,
159         typename Operation,
160         typename SideStrategy,
161         typename RobustPolicy
162     >
enterboost::geometry::detail::overlay::following::action_selector163     static inline void enter(LineStringOut& current_piece,
164                 LineString const& ,
165                 segment_identifier& segment_id,
166                 signed_size_type , Point const& point,
167                 Operation const& operation,
168                 SideStrategy const& ,
169                 RobustPolicy const& ,
170                 OutputIterator& )
171     {
172         // On enter, append the intersection point and remember starting point
173         // TODO: we don't check on spikes for linestrings (?). Consider this.
174         detail::overlay::append_no_duplicates(current_piece, point);
175         segment_id = operation.seg_id;
176     }
177 
178     template
179     <
180         typename OutputIterator,
181         typename LineStringOut,
182         typename LineString,
183         typename Point,
184         typename Operation,
185         typename SideStrategy,
186         typename RobustPolicy
187     >
leaveboost::geometry::detail::overlay::following::action_selector188     static inline void leave(LineStringOut& current_piece,
189                 LineString const& linestring,
190                 segment_identifier& segment_id,
191                 signed_size_type index, Point const& point,
192                 Operation const& ,
193                 SideStrategy const& strategy,
194                 RobustPolicy const& robust_policy,
195                 OutputIterator& out)
196     {
197         // On leave, copy all segments from starting point, append the intersection point
198         // and add the output piece
199         detail::copy_segments::copy_segments_linestring
200             <
201                 false, RemoveSpikes
202             >::apply(linestring, segment_id, index, strategy, robust_policy, current_piece);
203         detail::overlay::append_no_duplicates(current_piece, point);
204         if (::boost::size(current_piece) > 1)
205         {
206             *out++ = current_piece;
207         }
208 
209         geometry::clear(current_piece);
210     }
211 
212     template
213     <
214         typename OutputIterator,
215         typename LineStringOut,
216         typename LineString,
217         typename Point,
218         typename Operation
219     >
isolated_pointboost::geometry::detail::overlay::following::action_selector220     static inline void isolated_point(LineStringOut&,
221                 LineString const&,
222                 segment_identifier&,
223                 signed_size_type, Point const& point,
224                 Operation const& , OutputIterator& out)
225     {
226         LineStringOut isolated_point_ls;
227         geometry::append(isolated_point_ls, point);
228 
229 #ifndef BOOST_GEOMETRY_ALLOW_ONE_POINT_LINESTRINGS
230         geometry::append(isolated_point_ls, point);
231 #endif // BOOST_GEOMETRY_ALLOW_ONE_POINT_LINESTRINGS
232 
233         *out++ = isolated_point_ls;
234     }
235 
is_enteredboost::geometry::detail::overlay::following::action_selector236     static inline bool is_entered(bool entered)
237     {
238         return entered;
239     }
240 
includedboost::geometry::detail::overlay::following::action_selector241     static inline bool included(int inside_value)
242     {
243         return inside_value >= 0; // covered_by
244     }
245 
246 };
247 
248 // Specialization for difference, which reverses these actions
249 template <bool RemoveSpikes>
250 struct action_selector<overlay_difference, RemoveSpikes>
251 {
252     typedef action_selector<overlay_intersection, RemoveSpikes> normal_action;
253 
254     template
255     <
256         typename OutputIterator,
257         typename LineStringOut,
258         typename LineString,
259         typename Point,
260         typename Operation,
261         typename SideStrategy,
262         typename RobustPolicy
263     >
enterboost::geometry::detail::overlay::following::action_selector264     static inline void enter(LineStringOut& current_piece,
265                 LineString const& linestring,
266                 segment_identifier& segment_id,
267                 signed_size_type index, Point const& point,
268                 Operation const& operation,
269                 SideStrategy const& strategy,
270                 RobustPolicy const& robust_policy,
271                 OutputIterator& out)
272     {
273         normal_action::leave(current_piece, linestring, segment_id, index,
274                     point, operation, strategy, robust_policy, out);
275     }
276 
277     template
278     <
279         typename OutputIterator,
280         typename LineStringOut,
281         typename LineString,
282         typename Point,
283         typename Operation,
284         typename SideStrategy,
285         typename RobustPolicy
286     >
leaveboost::geometry::detail::overlay::following::action_selector287     static inline void leave(LineStringOut& current_piece,
288                 LineString const& linestring,
289                 segment_identifier& segment_id,
290                 signed_size_type index, Point const& point,
291                 Operation const& operation,
292                 SideStrategy const& strategy,
293                 RobustPolicy const& robust_policy,
294                 OutputIterator& out)
295     {
296         normal_action::enter(current_piece, linestring, segment_id, index,
297                     point, operation, strategy, robust_policy, out);
298     }
299 
300     template
301     <
302         typename OutputIterator,
303         typename LineStringOut,
304         typename LineString,
305         typename Point,
306         typename Operation
307     >
isolated_pointboost::geometry::detail::overlay::following::action_selector308     static inline void isolated_point(LineStringOut&,
309                 LineString const&,
310                 segment_identifier&,
311                 signed_size_type, Point const&,
312                 Operation const&, OutputIterator&)
313     {
314     }
315 
is_enteredboost::geometry::detail::overlay::following::action_selector316     static inline bool is_entered(bool entered)
317     {
318         return ! normal_action::is_entered(entered);
319     }
320 
includedboost::geometry::detail::overlay::following::action_selector321     static inline bool included(int inside_value)
322     {
323         return ! normal_action::included(inside_value);
324     }
325 
326 };
327 
328 }
329 
330 /*!
331 \brief Follows a linestring from intersection point to intersection point, outputting which
332     is inside, or outside, a ring or polygon
333 \ingroup overlay
334  */
335 template
336 <
337     typename LineStringOut,
338     typename LineString,
339     typename Polygon,
340     overlay_type OverlayType,
341     bool RemoveSpikes = true
342 >
343 class follow
344 {
345 
346     template <typename Turn>
347     struct sort_on_segment
348     {
349         // In case of turn point at the same location, we want to have continue/blocked LAST
350         // because that should be followed (intersection) or skipped (difference).
operation_orderboost::geometry::detail::overlay::follow::sort_on_segment351         inline int operation_order(Turn const& turn) const
352         {
353             operation_type const& operation = turn.operations[0].operation;
354             switch(operation)
355             {
356                 case operation_opposite : return 0;
357                 case operation_none : return 0;
358                 case operation_union : return 1;
359                 case operation_intersection : return 2;
360                 case operation_blocked : return 3;
361                 case operation_continue : return 4;
362             }
363             return -1;
364         };
365 
use_operationboost::geometry::detail::overlay::follow::sort_on_segment366         inline bool use_operation(Turn const& left, Turn const& right) const
367         {
368             // If they are the same, OK.
369             return operation_order(left) < operation_order(right);
370         }
371 
use_distanceboost::geometry::detail::overlay::follow::sort_on_segment372         inline bool use_distance(Turn const& left, Turn const& right) const
373         {
374             return left.operations[0].fraction == right.operations[0].fraction
375                 ? use_operation(left, right)
376                 : left.operations[0].fraction < right.operations[0].fraction
377                 ;
378         }
379 
operator ()boost::geometry::detail::overlay::follow::sort_on_segment380         inline bool operator()(Turn const& left, Turn const& right) const
381         {
382             segment_identifier const& sl = left.operations[0].seg_id;
383             segment_identifier const& sr = right.operations[0].seg_id;
384 
385             return sl == sr
386                 ? use_distance(left, right)
387                 : sl < sr
388                 ;
389 
390         }
391     };
392 
393 
394 
395 public :
396 
included(int inside_value)397     static inline bool included(int inside_value)
398     {
399         return following::action_selector
400             <
401                 OverlayType, RemoveSpikes
402             >::included(inside_value);
403     }
404 
405     template
406     <
407         typename Turns,
408         typename OutputIterator,
409         typename RobustPolicy,
410         typename Strategy
411     >
apply(LineString const & linestring,Polygon const & polygon,detail::overlay::operation_type,Turns & turns,RobustPolicy const & robust_policy,OutputIterator out,Strategy const & strategy)412     static inline OutputIterator apply(LineString const& linestring, Polygon const& polygon,
413                 detail::overlay::operation_type ,  // TODO: this parameter might be redundant
414                 Turns& turns,
415                 RobustPolicy const& robust_policy,
416                 OutputIterator out,
417                 Strategy const& strategy)
418     {
419         typedef typename boost::range_iterator<Turns>::type turn_iterator;
420         typedef typename boost::range_value<Turns>::type turn_type;
421         typedef typename boost::range_iterator
422             <
423                 typename turn_type::container_type
424             >::type turn_operation_iterator_type;
425 
426         typedef following::action_selector<OverlayType, RemoveSpikes> action;
427 
428         typename Strategy::template point_in_geometry_strategy
429             <
430                 LineString, Polygon
431             >::type const pt_in_poly_strategy
432             = strategy.template get_point_in_geometry_strategy<LineString, Polygon>();
433 
434         // Sort intersection points on segments-along-linestring, and distance
435         // (like in enrich is done for poly/poly)
436         std::sort(boost::begin(turns), boost::end(turns), sort_on_segment<turn_type>());
437 
438         LineStringOut current_piece;
439         geometry::segment_identifier current_segment_id(0, -1, -1, -1);
440 
441         // Iterate through all intersection points (they are ordered along the line)
442         bool entered = false;
443         bool first = true;
444         for (turn_iterator it = boost::begin(turns); it != boost::end(turns); ++it)
445         {
446             turn_operation_iterator_type iit = boost::begin(it->operations);
447 
448             if (following::was_entered(*it, *iit, first, linestring, polygon, pt_in_poly_strategy))
449             {
450                 debug_traverse(*it, *iit, "-> Was entered");
451                 entered = true;
452             }
453 
454             if (following::is_staying_inside(*it, *iit, entered, first, linestring, polygon, pt_in_poly_strategy))
455             {
456                 debug_traverse(*it, *iit, "-> Staying inside");
457 
458                 entered = true;
459             }
460             else if (following::is_entering(*it, *iit))
461             {
462                 debug_traverse(*it, *iit, "-> Entering");
463 
464                 entered = true;
465                 action::enter(current_piece, linestring, current_segment_id,
466                     iit->seg_id.segment_index, it->point, *iit,
467                     strategy, robust_policy,
468                     out);
469             }
470             else if (following::is_leaving(*it, *iit, entered, first, linestring, polygon, pt_in_poly_strategy))
471             {
472                 debug_traverse(*it, *iit, "-> Leaving");
473 
474                 entered = false;
475                 action::leave(current_piece, linestring, current_segment_id,
476                     iit->seg_id.segment_index, it->point, *iit,
477                     strategy, robust_policy,
478                     out);
479             }
480             first = false;
481         }
482 
483         if (action::is_entered(entered))
484         {
485             detail::copy_segments::copy_segments_linestring
486                 <
487                     false, RemoveSpikes
488                 >::apply(linestring,
489                          current_segment_id,
490                          static_cast<signed_size_type>(boost::size(linestring) - 1),
491                          strategy, robust_policy,
492                          current_piece);
493         }
494 
495         // Output the last one, if applicable
496         if (::boost::size(current_piece) > 1)
497         {
498             *out++ = current_piece;
499         }
500         return out;
501     }
502 
503 };
504 
505 
506 }} // namespace detail::overlay
507 #endif // DOXYGEN_NO_DETAIL
508 
509 
510 }} // namespace boost::geometry
511 
512 
513 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP
514