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