1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. 4 5 // Copyright (c) 2015-2019, Oracle and/or its affiliates. 6 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 // Licensed under the Boost Software License version 1.0. 11 // http://www.boost.org/users/license.html 12 13 14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP 15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP 16 17 #include <iterator> 18 #include <vector> 19 20 #include <boost/range.hpp> 21 22 #include <boost/geometry/core/tags.hpp> 23 24 #include <boost/geometry/geometries/box.hpp> 25 26 #include <boost/geometry/iterators/segment_iterator.hpp> 27 28 #include <boost/geometry/algorithms/disjoint.hpp> 29 #include <boost/geometry/algorithms/envelope.hpp> 30 #include <boost/geometry/algorithms/expand.hpp> 31 #include <boost/geometry/algorithms/not_implemented.hpp> 32 33 #include <boost/geometry/algorithms/detail/not.hpp> 34 #include <boost/geometry/algorithms/detail/partition.hpp> 35 #include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp> 36 #include <boost/geometry/algorithms/detail/equals/point_point.hpp> 37 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> 38 #include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp> 39 40 41 namespace boost { namespace geometry 42 { 43 44 45 #ifndef DOXYGEN_NO_DETAIL 46 namespace detail { namespace overlay 47 { 48 49 50 // action struct for pointlike-linear difference/intersection 51 // it works the same as its pointlike-pointlike counterpart, hence the 52 // derivation 53 template <typename PointOut, overlay_type OverlayType> 54 struct action_selector_pl_l 55 : action_selector_pl_pl<PointOut, OverlayType> 56 {}; 57 58 // difference/intersection of point-linear 59 template 60 < 61 typename Point, 62 typename Linear, 63 typename PointOut, 64 overlay_type OverlayType, 65 typename Policy 66 > 67 struct point_linear_point 68 { 69 template <typename RobustPolicy, typename OutputIterator, typename Strategy> applyboost::geometry::detail::overlay::point_linear_point70 static inline OutputIterator apply(Point const& point, 71 Linear const& linear, 72 RobustPolicy const&, 73 OutputIterator oit, 74 Strategy const& strategy) 75 { 76 action_selector_pl_l 77 < 78 PointOut, OverlayType 79 >::apply(point, Policy::apply(point, linear, strategy), oit); 80 return oit; 81 } 82 }; 83 84 // difference/intersection of multipoint-segment 85 template 86 < 87 typename MultiPoint, 88 typename Segment, 89 typename PointOut, 90 overlay_type OverlayType, 91 typename Policy 92 > 93 struct multipoint_segment_point 94 { 95 template <typename RobustPolicy, typename OutputIterator, typename Strategy> applyboost::geometry::detail::overlay::multipoint_segment_point96 static inline OutputIterator apply(MultiPoint const& multipoint, 97 Segment const& segment, 98 RobustPolicy const&, 99 OutputIterator oit, 100 Strategy const& strategy) 101 { 102 for (typename boost::range_iterator<MultiPoint const>::type 103 it = boost::begin(multipoint); 104 it != boost::end(multipoint); 105 ++it) 106 { 107 action_selector_pl_l 108 < 109 PointOut, OverlayType 110 >::apply(*it, Policy::apply(*it, segment, strategy), oit); 111 } 112 113 return oit; 114 } 115 }; 116 117 118 // difference/intersection of multipoint-linear 119 template 120 < 121 typename MultiPoint, 122 typename Linear, 123 typename PointOut, 124 overlay_type OverlayType, 125 typename Policy 126 > 127 class multipoint_linear_point 128 { 129 private: 130 // structs for partition -- start 131 template <typename ExpandPointStrategy> 132 struct expand_box_point 133 { 134 template <typename Box, typename Point> applyboost::geometry::detail::overlay::multipoint_linear_point::expand_box_point135 static inline void apply(Box& total, Point const& point) 136 { 137 geometry::expand(total, point, ExpandPointStrategy()); 138 } 139 }; 140 141 template <typename EnvelopeStrategy> 142 struct expand_box_segment 143 { expand_box_segmentboost::geometry::detail::overlay::multipoint_linear_point::expand_box_segment144 explicit expand_box_segment(EnvelopeStrategy const& strategy) 145 : m_strategy(strategy) 146 {} 147 148 template <typename Box, typename Segment> applyboost::geometry::detail::overlay::multipoint_linear_point::expand_box_segment149 inline void apply(Box& total, Segment const& segment) const 150 { 151 geometry::expand(total, 152 geometry::return_envelope<Box>(segment, m_strategy), 153 m_strategy.get_box_expand_strategy()); 154 } 155 156 EnvelopeStrategy const& m_strategy; 157 }; 158 159 template <typename DisjointPointBoxStrategy> 160 struct overlaps_box_point 161 { 162 template <typename Box, typename Point> applyboost::geometry::detail::overlay::multipoint_linear_point::overlaps_box_point163 static inline bool apply(Box const& box, Point const& point) 164 { 165 return ! geometry::disjoint(point, box, DisjointPointBoxStrategy()); 166 } 167 }; 168 169 template <typename DisjointStrategy> 170 struct overlaps_box_segment 171 { overlaps_box_segmentboost::geometry::detail::overlay::multipoint_linear_point::overlaps_box_segment172 explicit overlaps_box_segment(DisjointStrategy const& strategy) 173 : m_strategy(strategy) 174 {} 175 176 template <typename Box, typename Segment> applyboost::geometry::detail::overlay::multipoint_linear_point::overlaps_box_segment177 inline bool apply(Box const& box, Segment const& segment) const 178 { 179 return ! geometry::disjoint(segment, box, m_strategy); 180 } 181 182 DisjointStrategy const& m_strategy; 183 }; 184 185 template <typename OutputIterator, typename Strategy> 186 class item_visitor_type 187 { 188 public: item_visitor_type(OutputIterator & oit,Strategy const & strategy)189 item_visitor_type(OutputIterator& oit, Strategy const& strategy) 190 : m_oit(oit) 191 , m_strategy(strategy) 192 {} 193 194 template <typename Item1, typename Item2> apply(Item1 const & item1,Item2 const & item2)195 inline bool apply(Item1 const& item1, Item2 const& item2) 196 { 197 action_selector_pl_l 198 < 199 PointOut, overlay_intersection 200 >::apply(item1, Policy::apply(item1, item2, m_strategy), m_oit); 201 202 return true; 203 } 204 205 private: 206 OutputIterator& m_oit; 207 Strategy const& m_strategy; 208 }; 209 // structs for partition -- end 210 211 class segment_range 212 { 213 public: 214 typedef geometry::segment_iterator<Linear const> const_iterator; 215 typedef const_iterator iterator; 216 segment_range(Linear const & linear)217 segment_range(Linear const& linear) 218 : m_linear(linear) 219 {} 220 begin() const221 const_iterator begin() const 222 { 223 return geometry::segments_begin(m_linear); 224 } 225 end() const226 const_iterator end() const 227 { 228 return geometry::segments_end(m_linear); 229 } 230 231 private: 232 Linear const& m_linear; 233 }; 234 235 template <typename OutputIterator, typename Strategy> get_common_points(MultiPoint const & multipoint,Linear const & linear,OutputIterator oit,Strategy const & strategy)236 static inline OutputIterator get_common_points(MultiPoint const& multipoint, 237 Linear const& linear, 238 OutputIterator oit, 239 Strategy const& strategy) 240 { 241 item_visitor_type<OutputIterator, Strategy> item_visitor(oit, strategy); 242 243 typedef typename Strategy::envelope_strategy_type envelope_strategy_type; 244 typedef typename Strategy::disjoint_strategy_type disjoint_strategy_type; 245 typedef typename Strategy::disjoint_point_box_strategy_type disjoint_point_box_strategy_type; 246 typedef typename Strategy::expand_point_strategy_type expand_point_strategy_type; 247 248 // TODO: disjoint Segment/Box may be called in partition multiple times 249 // possibly for non-cartesian segments which could be slow. We should consider 250 // passing a range of bounding boxes of segments after calculating them once. 251 // Alternatively instead of a range of segments a range of Segment/Envelope pairs 252 // should be passed, where envelope would be lazily calculated when needed the first time 253 geometry::partition 254 < 255 geometry::model::box 256 < 257 typename boost::range_value<MultiPoint>::type 258 > 259 >::apply(multipoint, segment_range(linear), item_visitor, 260 expand_box_point<expand_point_strategy_type>(), 261 overlaps_box_point<disjoint_point_box_strategy_type>(), 262 expand_box_segment<envelope_strategy_type>(strategy.get_envelope_strategy()), 263 overlaps_box_segment<disjoint_strategy_type>(strategy.get_disjoint_strategy())); 264 265 return oit; 266 } 267 268 public: 269 template <typename RobustPolicy, typename OutputIterator, typename Strategy> apply(MultiPoint const & multipoint,Linear const & linear,RobustPolicy const & robust_policy,OutputIterator oit,Strategy const & strategy)270 static inline OutputIterator apply(MultiPoint const& multipoint, 271 Linear const& linear, 272 RobustPolicy const& robust_policy, 273 OutputIterator oit, 274 Strategy const& strategy) 275 { 276 typedef std::vector 277 < 278 typename boost::range_value<MultiPoint>::type 279 > point_vector_type; 280 281 point_vector_type common_points; 282 283 // compute the common points 284 get_common_points(multipoint, linear, 285 std::back_inserter(common_points), 286 strategy); 287 288 return multipoint_multipoint_point 289 < 290 MultiPoint, point_vector_type, PointOut, OverlayType 291 >::apply(multipoint, common_points, robust_policy, oit, strategy); 292 } 293 }; 294 295 296 }} // namespace detail::overlay 297 #endif // DOXYGEN_NO_DETAIL 298 299 300 #ifndef DOXYGEN_NO_DISPATCH 301 namespace detail_dispatch { namespace overlay 302 { 303 304 // dispatch struct for pointlike-linear difference/intersection computation 305 template 306 < 307 typename PointLike, 308 typename Linear, 309 typename PointOut, 310 overlay_type OverlayType, 311 typename Tag1, 312 typename Tag2 313 > 314 struct pointlike_linear_point 315 : not_implemented<PointLike, Linear, PointOut> 316 {}; 317 318 319 template 320 < 321 typename Point, 322 typename Linear, 323 typename PointOut, 324 overlay_type OverlayType 325 > 326 struct pointlike_linear_point 327 < 328 Point, Linear, PointOut, OverlayType, point_tag, linear_tag 329 > : detail::overlay::point_linear_point 330 < 331 Point, Linear, PointOut, OverlayType, 332 detail::not_<detail::disjoint::reverse_covered_by> 333 > 334 {}; 335 336 337 template 338 < 339 typename Point, 340 typename Segment, 341 typename PointOut, 342 overlay_type OverlayType 343 > 344 struct pointlike_linear_point 345 < 346 Point, Segment, PointOut, OverlayType, point_tag, segment_tag 347 > : detail::overlay::point_linear_point 348 < 349 Point, Segment, PointOut, OverlayType, 350 detail::not_<detail::disjoint::reverse_covered_by> 351 > 352 {}; 353 354 355 template 356 < 357 typename MultiPoint, 358 typename Linear, 359 typename PointOut, 360 overlay_type OverlayType 361 > 362 struct pointlike_linear_point 363 < 364 MultiPoint, Linear, PointOut, OverlayType, multi_point_tag, linear_tag 365 > : detail::overlay::multipoint_linear_point 366 < 367 MultiPoint, Linear, PointOut, OverlayType, 368 detail::not_<detail::disjoint::reverse_covered_by> 369 > 370 {}; 371 372 373 template 374 < 375 typename MultiPoint, 376 typename Segment, 377 typename PointOut, 378 overlay_type OverlayType 379 > 380 struct pointlike_linear_point 381 < 382 MultiPoint, Segment, PointOut, OverlayType, multi_point_tag, segment_tag 383 > : detail::overlay::multipoint_segment_point 384 < 385 MultiPoint, Segment, PointOut, OverlayType, 386 detail::not_<detail::disjoint::reverse_covered_by> 387 > 388 {}; 389 390 391 }} // namespace detail_dispatch::overlay 392 #endif // DOXYGEN_NO_DISPATCH 393 394 395 }} // namespace boost::geometry 396 397 398 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP 399