1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2014-2020, Oracle and/or its affiliates.
4 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
5 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
7 // Licensed under the Boost Software License version 1.0.
8 // http://www.boost.org/users/license.html
10 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
16 #include <boost/range/begin.hpp>
17 #include <boost/range/end.hpp>
19 #include <boost/geometry/core/tag.hpp>
20 #include <boost/geometry/core/tags.hpp>
22 #include <boost/geometry/algorithms/detail/relate/turns.hpp>
24 #include <boost/geometry/algorithms/detail/turns/compare_turns.hpp>
25 #include <boost/geometry/algorithms/detail/turns/filter_continue_turns.hpp>
26 #include <boost/geometry/algorithms/detail/turns/remove_duplicate_turns.hpp>
28 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
29 #include <boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp>
31 #include <boost/geometry/algorithms/convert.hpp>
35 namespace boost { namespace geometry
39 #ifndef DOXYGEN_NO_DETAIL
40 namespace detail { namespace overlay
46 typename LineStringOut,
47 overlay_type OverlayType,
51 struct linear_linear_no_intersections;
54 template <typename LineStringOut, typename LineString>
55 struct linear_linear_no_intersections
57 LineStringOut, overlay_difference, LineString, linestring_tag
60 template <typename OutputIterator>
61 static inline OutputIterator apply(LineString const& linestring,
65 geometry::convert(linestring, ls_out);
72 template <typename LineStringOut, typename MultiLineString>
73 struct linear_linear_no_intersections
81 template <typename OutputIterator>
82 static inline OutputIterator apply(MultiLineString const& multilinestring,
85 for (typename boost::range_iterator<MultiLineString const>::type
86 it = boost::begin(multilinestring);
87 it != boost::end(multilinestring); ++it)
90 geometry::convert(*it, ls_out);
98 template <typename LineStringOut, typename Geometry, typename GeometryTag>
99 struct linear_linear_no_intersections
101 LineStringOut, overlay_intersection, Geometry, GeometryTag
104 template <typename OutputIterator>
105 static inline OutputIterator apply(Geometry const&,
122 typename LinestringOut,
123 overlay_type OverlayType,
124 bool EnableFilterContinueTurns = false,
125 bool EnableRemoveDuplicateTurns = false,
126 bool EnableDegenerateTurns = true,
127 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
128 bool EnableFollowIsolatedPoints = false
130 bool EnableFollowIsolatedPoints = true
133 class linear_linear_linestring
138 static bool const include_no_turn = false;
139 static bool const include_degenerate = EnableDegenerateTurns;
140 static bool const include_opposite = false;
141 static bool const include_start_turn = false;
148 typename LinearGeometry1,
149 typename LinearGeometry2,
150 typename IntersectionStrategy,
151 typename RobustPolicy
153 static inline void compute_turns(Turns& turns,
154 LinearGeometry1 const& linear1,
155 LinearGeometry2 const& linear2,
156 IntersectionStrategy const& strategy,
157 RobustPolicy const& robust_policy)
161 detail::get_turns::no_interrupt_policy interrupt_policy;
163 geometry::detail::relate::turns::get_turns
167 detail::get_turns::get_turn_info_type
173 >::apply(turns, linear1, linear2, interrupt_policy, strategy, robust_policy);
179 overlay_type OverlayTypeForFollow,
180 bool FollowIsolatedPoints,
182 typename LinearGeometry1,
183 typename LinearGeometry2,
184 typename OutputIterator,
185 typename IntersectionStrategy
187 static inline OutputIterator
188 sort_and_follow_turns(Turns& turns,
189 LinearGeometry1 const& linear1,
190 LinearGeometry2 const& linear2,
192 IntersectionStrategy const& strategy)
194 // remove turns that have no added value
195 turns::filter_continue_turns
198 EnableFilterContinueTurns && OverlayType != overlay_intersection
201 // sort by seg_id, distance, and operation
202 std::sort(boost::begin(turns), boost::end(turns),
203 detail::turns::less_seg_fraction_other_op<>());
205 // remove duplicate turns
206 turns::remove_duplicate_turns
208 Turns, EnableRemoveDuplicateTurns
211 return detail::overlay::following::linear::follow
216 OverlayTypeForFollow,
217 FollowIsolatedPoints,
218 !EnableFilterContinueTurns || OverlayType == overlay_intersection
219 >::apply(linear1, linear2, boost::begin(turns), boost::end(turns),
220 oit, strategy.get_side_strategy());
226 typename RobustPolicy, typename OutputIterator, typename Strategy
228 static inline OutputIterator apply(Linear1 const& linear1,
229 Linear2 const& linear2,
230 RobustPolicy const& robust_policy,
232 Strategy const& strategy)
234 typedef typename detail::relate::turns::get_turns
238 detail::get_turns::get_turn_info_type
244 >::template turn_info_type<Strategy, RobustPolicy>::type turn_info;
246 typedef std::vector<turn_info> turns_container;
248 turns_container turns;
249 compute_turns(turns, linear1, linear2, strategy, robust_policy);
253 // the two linear geometries are disjoint
254 return linear_linear_no_intersections
259 typename tag<Linear1>::type
260 >::apply(linear1, oit);
263 return sort_and_follow_turns
266 EnableFollowIsolatedPoints
267 && OverlayType == overlay_intersection
268 >(turns, linear1, linear2, oit, strategy);
279 typename LinestringOut,
280 bool EnableFilterContinueTurns,
281 bool EnableRemoveDuplicateTurns,
282 bool EnableDegenerateTurns,
283 bool EnableFollowIsolatedPoints
285 struct linear_linear_linestring
287 Linear1, Linear2, LinestringOut, overlay_union,
288 EnableFilterContinueTurns, EnableRemoveDuplicateTurns,
289 EnableDegenerateTurns, EnableFollowIsolatedPoints
294 typename RobustPolicy, typename OutputIterator, typename Strategy
296 static inline OutputIterator apply(Linear1 const& linear1,
297 Linear2 const& linear2,
298 RobustPolicy const& robust_policy,
300 Strategy const& strategy)
302 oit = linear_linear_no_intersections
307 typename tag<Linear1>::type
308 >::apply(linear1, oit);
310 return linear_linear_linestring
312 Linear2, Linear1, LinestringOut, overlay_difference,
313 EnableFilterContinueTurns, EnableRemoveDuplicateTurns,
314 EnableDegenerateTurns, EnableFollowIsolatedPoints
315 >::apply(linear2, linear1, robust_policy, oit, strategy);
322 }} // namespace detail::overlay
323 #endif // DOXYGEN_NO_DETAIL
326 }} // namespace boost::geometry
330 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP