1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2014-2019, 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 144 145 template 146 < 147 typename Turns, 148 typename LinearGeometry1, 149 typename LinearGeometry2, 150 typename IntersectionStrategy, 151 typename RobustPolicy 152 > compute_turns(Turns & turns,LinearGeometry1 const & linear1,LinearGeometry2 const & linear2,IntersectionStrategy const & strategy,RobustPolicy const & robust_policy)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) 158 { 159 turns.clear(); 160 161 detail::get_turns::no_interrupt_policy interrupt_policy; 162 163 geometry::detail::relate::turns::get_turns 164 < 165 LinearGeometry1, 166 LinearGeometry2, 167 detail::get_turns::get_turn_info_type 168 < 169 LinearGeometry1, 170 LinearGeometry2, 171 assign_policy 172 > 173 >::apply(turns, linear1, linear2, interrupt_policy, strategy, robust_policy); 174 } 175 176 177 template 178 < 179 overlay_type OverlayTypeForFollow, 180 bool FollowIsolatedPoints, 181 typename Turns, 182 typename LinearGeometry1, 183 typename LinearGeometry2, 184 typename OutputIterator, 185 typename IntersectionStrategy 186 > 187 static inline OutputIterator sort_and_follow_turns(Turns & turns,LinearGeometry1 const & linear1,LinearGeometry2 const & linear2,OutputIterator oit,IntersectionStrategy const & strategy)188 sort_and_follow_turns(Turns& turns, 189 LinearGeometry1 const& linear1, 190 LinearGeometry2 const& linear2, 191 OutputIterator oit, 192 IntersectionStrategy const& strategy) 193 { 194 // remove turns that have no added value 195 turns::filter_continue_turns 196 < 197 Turns, 198 EnableFilterContinueTurns && OverlayType != overlay_intersection 199 >::apply(turns); 200 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<>()); 204 205 // remove duplicate turns 206 turns::remove_duplicate_turns 207 < 208 Turns, EnableRemoveDuplicateTurns 209 >::apply(turns); 210 211 return detail::overlay::following::linear::follow 212 < 213 LinestringOut, 214 LinearGeometry1, 215 LinearGeometry2, 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()); 221 } 222 223 public: 224 template 225 < 226 typename RobustPolicy, typename OutputIterator, typename Strategy 227 > apply(Linear1 const & linear1,Linear2 const & linear2,RobustPolicy const & robust_policy,OutputIterator oit,Strategy const & strategy)228 static inline OutputIterator apply(Linear1 const& linear1, 229 Linear2 const& linear2, 230 RobustPolicy const& robust_policy, 231 OutputIterator oit, 232 Strategy const& strategy) 233 { 234 typedef typename detail::relate::turns::get_turns 235 < 236 Linear1, 237 Linear2, 238 detail::get_turns::get_turn_info_type 239 < 240 Linear1, 241 Linear2, 242 assign_policy 243 > 244 >::template turn_info_type<Strategy, RobustPolicy>::type turn_info; 245 246 typedef std::vector<turn_info> turns_container; 247 248 turns_container turns; 249 compute_turns(turns, linear1, linear2, strategy, robust_policy); 250 251 if ( turns.empty() ) 252 { 253 // the two linear geometries are disjoint 254 return linear_linear_no_intersections 255 < 256 LinestringOut, 257 OverlayType, 258 Linear1, 259 typename tag<Linear1>::type 260 >::apply(linear1, oit); 261 } 262 263 return sort_and_follow_turns 264 < 265 OverlayType, 266 EnableFollowIsolatedPoints 267 && OverlayType == overlay_intersection 268 >(turns, linear1, linear2, oit, strategy); 269 } 270 }; 271 272 273 274 275 template 276 < 277 typename Linear1, 278 typename Linear2, 279 typename LinestringOut, 280 bool EnableFilterContinueTurns, 281 bool EnableRemoveDuplicateTurns, 282 bool EnableDegenerateTurns, 283 bool EnableFollowIsolatedPoints 284 > 285 struct linear_linear_linestring 286 < 287 Linear1, Linear2, LinestringOut, overlay_union, 288 EnableFilterContinueTurns, EnableRemoveDuplicateTurns, 289 EnableDegenerateTurns, EnableFollowIsolatedPoints 290 > 291 { 292 template 293 < 294 typename RobustPolicy, typename OutputIterator, typename Strategy 295 > applyboost::geometry::detail::overlay::linear_linear_linestring296 static inline OutputIterator apply(Linear1 const& linear1, 297 Linear2 const& linear2, 298 RobustPolicy const& robust_policy, 299 OutputIterator oit, 300 Strategy const& strategy) 301 { 302 oit = linear_linear_no_intersections 303 < 304 LinestringOut, 305 overlay_difference, 306 Linear1, 307 typename tag<Linear1>::type 308 >::apply(linear1, oit); 309 310 return linear_linear_linestring 311 < 312 Linear2, Linear1, LinestringOut, overlay_difference, 313 EnableFilterContinueTurns, EnableRemoveDuplicateTurns, 314 EnableDegenerateTurns, EnableFollowIsolatedPoints 315 >::apply(linear2, linear1, robust_policy, oit, strategy); 316 } 317 }; 318 319 320 321 322 }} // namespace detail::overlay 323 #endif // DOXYGEN_NO_DETAIL 324 325 326 }} // namespace boost::geometry 327 328 329 330 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP 331