1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2014-2017, 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 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
10 
11 
12 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
13 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
14 
15 #include <algorithm>
16 #include <vector>
17 
18 #include <boost/range.hpp>
19 
20 #include <boost/geometry/core/tag.hpp>
21 #include <boost/geometry/core/tags.hpp>
22 
23 #include <boost/geometry/algorithms/detail/relate/turns.hpp>
24 
25 #include <boost/geometry/algorithms/detail/turns/compare_turns.hpp>
26 #include <boost/geometry/algorithms/detail/turns/filter_continue_turns.hpp>
27 #include <boost/geometry/algorithms/detail/turns/remove_duplicate_turns.hpp>
28 
29 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
30 #include <boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp>
31 
32 #include <boost/geometry/algorithms/convert.hpp>
33 
34 
35 
36 namespace boost { namespace geometry
37 {
38 
39 
40 #ifndef DOXYGEN_NO_DETAIL
41 namespace detail { namespace overlay
42 {
43 
44 
45 template
46 <
47     typename LineStringOut,
48     overlay_type OverlayType,
49     typename Geometry,
50     typename GeometryTag
51 >
52 struct linear_linear_no_intersections;
53 
54 
55 template <typename LineStringOut, typename LineString>
56 struct linear_linear_no_intersections
57     <
58         LineStringOut, overlay_difference, LineString, linestring_tag
59     >
60 {
61     template <typename OutputIterator>
applyboost::geometry::detail::overlay::linear_linear_no_intersections62     static inline OutputIterator apply(LineString const& linestring,
63                                        OutputIterator oit)
64     {
65         LineStringOut ls_out;
66         geometry::convert(linestring, ls_out);
67         *oit++ = ls_out;
68         return oit;
69     }
70 };
71 
72 
73 template <typename LineStringOut, typename MultiLineString>
74 struct linear_linear_no_intersections
75     <
76         LineStringOut,
77         overlay_difference,
78         MultiLineString,
79         multi_linestring_tag
80     >
81 {
82     template <typename OutputIterator>
applyboost::geometry::detail::overlay::linear_linear_no_intersections83     static inline OutputIterator apply(MultiLineString const& multilinestring,
84                                        OutputIterator oit)
85     {
86         for (typename boost::range_iterator<MultiLineString const>::type
87                  it = boost::begin(multilinestring);
88              it != boost::end(multilinestring); ++it)
89         {
90             LineStringOut ls_out;
91             geometry::convert(*it, ls_out);
92             *oit++ = ls_out;
93         }
94         return oit;
95     }
96 };
97 
98 
99 template <typename LineStringOut, typename Geometry, typename GeometryTag>
100 struct linear_linear_no_intersections
101     <
102         LineStringOut, overlay_intersection, Geometry, GeometryTag
103     >
104 {
105     template <typename OutputIterator>
applyboost::geometry::detail::overlay::linear_linear_no_intersections106     static inline OutputIterator apply(Geometry const&,
107                                        OutputIterator oit)
108     {
109         return oit;
110     }
111 };
112 
113 
114 
115 
116 
117 
118 
119 template
120 <
121     typename Linear1,
122     typename Linear2,
123     typename LinestringOut,
124     overlay_type OverlayType,
125     bool EnableFilterContinueTurns = false,
126     bool EnableRemoveDuplicateTurns = false,
127     bool EnableDegenerateTurns = true,
128 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
129     bool EnableFollowIsolatedPoints = false
130 #else
131     bool EnableFollowIsolatedPoints = true
132 #endif
133 >
134 class linear_linear_linestring
135 {
136 protected:
137     struct assign_policy
138     {
139         static bool const include_no_turn = false;
140         static bool const include_degenerate = EnableDegenerateTurns;
141         static bool const include_opposite = false;
142 
143         template
144         <
145             typename Info,
146             typename Point1,
147             typename Point2,
148             typename IntersectionInfo
149         >
applyboost::geometry::detail::overlay::linear_linear_linestring::assign_policy150         static inline void apply(Info& , Point1 const& , Point2 const& ,
151                                  IntersectionInfo const& )
152         {
153         }
154     };
155 
156 
157     template
158     <
159         typename Turns,
160         typename LinearGeometry1,
161         typename LinearGeometry2,
162         typename IntersectionStrategy,
163         typename RobustPolicy
164     >
compute_turns(Turns & turns,LinearGeometry1 const & linear1,LinearGeometry2 const & linear2,IntersectionStrategy const & strategy,RobustPolicy const & robust_policy)165     static inline void compute_turns(Turns& turns,
166                                      LinearGeometry1 const& linear1,
167                                      LinearGeometry2 const& linear2,
168                                      IntersectionStrategy const& strategy,
169                                      RobustPolicy const& robust_policy)
170     {
171         turns.clear();
172 
173         detail::get_turns::no_interrupt_policy interrupt_policy;
174 
175         geometry::detail::relate::turns::get_turns
176             <
177                 LinearGeometry1,
178                 LinearGeometry2,
179                 detail::get_turns::get_turn_info_type
180                 <
181                     LinearGeometry1,
182                     LinearGeometry2,
183                     assign_policy
184                 >,
185                 RobustPolicy
186             >::apply(turns, linear1, linear2, interrupt_policy, strategy, robust_policy);
187     }
188 
189 
190     template
191     <
192         overlay_type OverlayTypeForFollow,
193         bool FollowIsolatedPoints,
194         typename Turns,
195         typename LinearGeometry1,
196         typename LinearGeometry2,
197         typename OutputIterator,
198         typename IntersectionStrategy
199     >
200     static inline OutputIterator
sort_and_follow_turns(Turns & turns,LinearGeometry1 const & linear1,LinearGeometry2 const & linear2,OutputIterator oit,IntersectionStrategy const & strategy)201     sort_and_follow_turns(Turns& turns,
202                           LinearGeometry1 const& linear1,
203                           LinearGeometry2 const& linear2,
204                           OutputIterator oit,
205                           IntersectionStrategy const& strategy)
206     {
207         // remove turns that have no added value
208         turns::filter_continue_turns
209             <
210                 Turns,
211                 EnableFilterContinueTurns && OverlayType != overlay_intersection
212             >::apply(turns);
213 
214         // sort by seg_id, distance, and operation
215         std::sort(boost::begin(turns), boost::end(turns),
216                   detail::turns::less_seg_fraction_other_op<>());
217 
218         // remove duplicate turns
219         turns::remove_duplicate_turns
220             <
221                 Turns, EnableRemoveDuplicateTurns
222             >::apply(turns);
223 
224         return detail::overlay::following::linear::follow
225             <
226                 LinestringOut,
227                 LinearGeometry1,
228                 LinearGeometry2,
229                 OverlayTypeForFollow,
230                 FollowIsolatedPoints,
231                 !EnableFilterContinueTurns || OverlayType == overlay_intersection
232             >::apply(linear1, linear2, boost::begin(turns), boost::end(turns),
233                      oit, strategy.get_side_strategy());
234     }
235 
236 public:
237     template
238     <
239         typename RobustPolicy, typename OutputIterator, typename Strategy
240     >
apply(Linear1 const & linear1,Linear2 const & linear2,RobustPolicy const & robust_policy,OutputIterator oit,Strategy const & strategy)241     static inline OutputIterator apply(Linear1 const& linear1,
242                                        Linear2 const& linear2,
243                                        RobustPolicy const& robust_policy,
244                                        OutputIterator oit,
245                                        Strategy const& strategy)
246     {
247         typedef typename detail::relate::turns::get_turns
248             <
249                 Linear1,
250                 Linear2,
251                 detail::get_turns::get_turn_info_type
252                 <
253                     Linear1,
254                     Linear2,
255                     assign_policy
256                 >,
257                 RobustPolicy
258             >::turn_info turn_info;
259 
260         typedef std::vector<turn_info> turns_container;
261 
262         turns_container turns;
263         compute_turns(turns, linear1, linear2, strategy, robust_policy);
264 
265         if ( turns.empty() )
266         {
267             // the two linear geometries are disjoint
268             return linear_linear_no_intersections
269                 <
270                     LinestringOut,
271                     OverlayType,
272                     Linear1,
273                     typename tag<Linear1>::type
274                 >::apply(linear1, oit);
275         }
276 
277         return sort_and_follow_turns
278             <
279                 OverlayType,
280                 EnableFollowIsolatedPoints
281                 && OverlayType == overlay_intersection
282             >(turns, linear1, linear2, oit, strategy);
283     }
284 };
285 
286 
287 
288 
289 template
290 <
291     typename Linear1,
292     typename Linear2,
293     typename LinestringOut,
294     bool EnableFilterContinueTurns,
295     bool EnableRemoveDuplicateTurns,
296     bool EnableDegenerateTurns,
297     bool EnableFollowIsolatedPoints
298 >
299 struct linear_linear_linestring
300     <
301         Linear1, Linear2, LinestringOut, overlay_union,
302         EnableFilterContinueTurns, EnableRemoveDuplicateTurns,
303         EnableDegenerateTurns, EnableFollowIsolatedPoints
304     >
305 {
306     template
307     <
308         typename RobustPolicy, typename OutputIterator, typename Strategy
309     >
applyboost::geometry::detail::overlay::linear_linear_linestring310     static inline OutputIterator apply(Linear1 const& linear1,
311                                        Linear2 const& linear2,
312                                        RobustPolicy const& robust_policy,
313                                        OutputIterator oit,
314                                        Strategy const& strategy)
315     {
316         oit = linear_linear_no_intersections
317             <
318                 LinestringOut,
319                 overlay_difference,
320                 Linear1,
321                 typename tag<Linear1>::type
322             >::apply(linear1, oit);
323 
324         return linear_linear_linestring
325             <
326                 Linear2, Linear1, LinestringOut, overlay_difference,
327                 EnableFilterContinueTurns, EnableRemoveDuplicateTurns,
328                 EnableDegenerateTurns, EnableFollowIsolatedPoints
329             >::apply(linear2, linear1, robust_policy, oit, strategy);
330     }
331 };
332 
333 
334 
335 
336 }} // namespace detail::overlay
337 #endif // DOXYGEN_NO_DETAIL
338 
339 
340 }} // namespace boost::geometry
341 
342 
343 
344 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
345