1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. 4 5 // Copyright (c) 2014-2019, Oracle and/or its affiliates. 6 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle 7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 8 9 // Licensed under the Boost Software License version 1.0. 10 // http://www.boost.org/users/license.html 11 12 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP 13 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP 14 15 #include <algorithm> 16 #include <vector> 17 18 #include <boost/range.hpp> 19 #include <boost/mpl/assert.hpp> 20 21 #include <boost/geometry/core/assert.hpp> 22 #include <boost/geometry/core/tag.hpp> 23 #include <boost/geometry/core/tags.hpp> 24 25 #include <boost/geometry/geometries/box.hpp> 26 27 #include <boost/geometry/iterators/segment_iterator.hpp> 28 29 #include <boost/geometry/algorithms/envelope.hpp> 30 #include <boost/geometry/algorithms/expand.hpp> 31 32 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp> 33 #include <boost/geometry/algorithms/detail/partition.hpp> 34 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> 35 #include <boost/geometry/algorithms/detail/disjoint/multirange_geometry.hpp> 36 #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> 37 #include <boost/geometry/algorithms/detail/disjoint/point_point.hpp> 38 #include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp> 39 40 #include <boost/geometry/algorithms/dispatch/disjoint.hpp> 41 42 #include <boost/geometry/policies/compare.hpp> 43 44 45 namespace boost { namespace geometry 46 { 47 48 49 #ifndef DOXYGEN_NO_DETAIL 50 namespace detail { namespace disjoint 51 { 52 53 54 class multipoint_multipoint 55 { 56 private: 57 template <typename Iterator, typename CSTag> 58 class unary_disjoint_predicate 59 : geometry::less<void, -1, CSTag> 60 { 61 private: 62 typedef geometry::less<void, -1, CSTag> base_type; 63 64 public: unary_disjoint_predicate(Iterator first,Iterator last)65 unary_disjoint_predicate(Iterator first, Iterator last) 66 : base_type(), m_first(first), m_last(last) 67 {} 68 69 template <typename Point> apply(Point const & point) const70 inline bool apply(Point const& point) const 71 { 72 return !std::binary_search(m_first, 73 m_last, 74 point, 75 static_cast<base_type const&>(*this)); 76 } 77 78 private: 79 Iterator m_first, m_last; 80 }; 81 82 public: 83 template <typename MultiPoint1, typename MultiPoint2, typename Strategy> apply(MultiPoint1 const & multipoint1,MultiPoint2 const & multipoint2,Strategy const &)84 static inline bool apply(MultiPoint1 const& multipoint1, 85 MultiPoint2 const& multipoint2, 86 Strategy const&) 87 { 88 typedef typename Strategy::cs_tag cs_tag; 89 typedef geometry::less<void, -1, cs_tag> less_type; 90 91 BOOST_GEOMETRY_ASSERT( boost::size(multipoint1) <= boost::size(multipoint2) ); 92 93 typedef typename boost::range_value<MultiPoint1>::type point1_type; 94 95 std::vector<point1_type> points1(boost::begin(multipoint1), 96 boost::end(multipoint1)); 97 98 std::sort(points1.begin(), points1.end(), less_type()); 99 100 typedef unary_disjoint_predicate 101 < 102 typename std::vector<point1_type>::const_iterator, 103 cs_tag 104 > predicate_type; 105 106 return check_iterator_range 107 < 108 predicate_type 109 >::apply(boost::begin(multipoint2), 110 boost::end(multipoint2), 111 predicate_type(points1.begin(), points1.end())); 112 } 113 }; 114 115 116 template <typename MultiPoint, typename Linear> 117 class multipoint_linear 118 { 119 private: 120 template <typename ExpandPointBoxStrategy> 121 struct expand_box_point 122 { 123 template <typename Box, typename Point> applyboost::geometry::detail::disjoint::multipoint_linear::expand_box_point124 static inline void apply(Box& total, Point const& point) 125 { 126 geometry::expand(total, point, ExpandPointBoxStrategy()); 127 } 128 }; 129 130 template <typename EnvelopeStrategy> 131 struct expand_box_segment 132 { expand_box_segmentboost::geometry::detail::disjoint::multipoint_linear::expand_box_segment133 explicit expand_box_segment(EnvelopeStrategy const& strategy) 134 : m_strategy(strategy) 135 {} 136 137 template <typename Box, typename Segment> applyboost::geometry::detail::disjoint::multipoint_linear::expand_box_segment138 inline void apply(Box& total, Segment const& segment) const 139 { 140 geometry::expand(total, 141 geometry::return_envelope<Box>(segment, m_strategy), 142 typename EnvelopeStrategy::box_expand_strategy_type()); 143 } 144 145 EnvelopeStrategy const& m_strategy; 146 }; 147 148 template <typename DisjointPointBoxStrategy> 149 struct overlaps_box_point 150 { 151 template <typename Box, typename Point> applyboost::geometry::detail::disjoint::multipoint_linear::overlaps_box_point152 static inline bool apply(Box const& box, Point const& point) 153 { 154 // The default strategy is enough in this case 155 return ! detail::disjoint::disjoint_point_box(point, box, 156 DisjointPointBoxStrategy()); 157 } 158 }; 159 160 template <typename DisjointStrategy> 161 struct overlaps_box_segment 162 { overlaps_box_segmentboost::geometry::detail::disjoint::multipoint_linear::overlaps_box_segment163 explicit overlaps_box_segment(DisjointStrategy const& strategy) 164 : m_strategy(strategy) 165 {} 166 167 template <typename Box, typename Segment> applyboost::geometry::detail::disjoint::multipoint_linear::overlaps_box_segment168 inline bool apply(Box const& box, Segment const& segment) const 169 { 170 return ! dispatch::disjoint<Segment, Box>::apply(segment, box, m_strategy); 171 } 172 173 DisjointStrategy const& m_strategy; 174 }; 175 176 template <typename PtSegStrategy> 177 class item_visitor_type 178 { 179 public: item_visitor_type(PtSegStrategy const & strategy)180 item_visitor_type(PtSegStrategy const& strategy) 181 : m_intersection_found(false) 182 , m_strategy(strategy) 183 {} 184 185 template <typename Item1, typename Item2> apply(Item1 const & item1,Item2 const & item2)186 inline bool apply(Item1 const& item1, Item2 const& item2) 187 { 188 if (! m_intersection_found 189 && ! dispatch::disjoint<Item1, Item2>::apply(item1, item2, m_strategy)) 190 { 191 m_intersection_found = true; 192 return false; 193 } 194 return true; 195 } 196 intersection_found() const197 inline bool intersection_found() const { return m_intersection_found; } 198 199 private: 200 bool m_intersection_found; 201 PtSegStrategy const& m_strategy; 202 }; 203 // structs for partition -- end 204 205 class segment_range 206 { 207 public: 208 typedef geometry::segment_iterator<Linear const> const_iterator; 209 typedef const_iterator iterator; 210 segment_range(Linear const & linear)211 segment_range(Linear const& linear) 212 : m_linear(linear) 213 {} 214 begin() const215 const_iterator begin() const 216 { 217 return geometry::segments_begin(m_linear); 218 } 219 end() const220 const_iterator end() const 221 { 222 return geometry::segments_end(m_linear); 223 } 224 225 private: 226 Linear const& m_linear; 227 }; 228 229 public: 230 template <typename Strategy> apply(MultiPoint const & multipoint,Linear const & linear,Strategy const & strategy)231 static inline bool apply(MultiPoint const& multipoint, Linear const& linear, Strategy const& strategy) 232 { 233 item_visitor_type<Strategy> visitor(strategy); 234 235 typedef typename Strategy::expand_point_strategy_type expand_point_strategy_type; 236 typedef typename Strategy::envelope_strategy_type envelope_strategy_type; 237 typedef typename Strategy::disjoint_strategy_type disjoint_strategy_type; 238 typedef typename Strategy::disjoint_point_box_strategy_type disjoint_pb_strategy_type; 239 240 // TODO: disjoint Segment/Box may be called in partition multiple times 241 // possibly for non-cartesian segments which could be slow. We should consider 242 // passing a range of bounding boxes of segments after calculating them once. 243 // Alternatively instead of a range of segments a range of Segment/Envelope pairs 244 // should be passed, where envelope would be lazily calculated when needed the first time 245 geometry::partition 246 < 247 geometry::model::box<typename point_type<MultiPoint>::type> 248 >::apply(multipoint, segment_range(linear), visitor, 249 expand_box_point<expand_point_strategy_type>(), 250 overlaps_box_point<disjoint_pb_strategy_type>(), 251 expand_box_segment<envelope_strategy_type>(strategy.get_envelope_strategy()), 252 overlaps_box_segment<disjoint_strategy_type>(strategy.get_disjoint_strategy())); 253 254 return ! visitor.intersection_found(); 255 } 256 257 template <typename Strategy> apply(Linear const & linear,MultiPoint const & multipoint,Strategy const & strategy)258 static inline bool apply(Linear const& linear, MultiPoint const& multipoint, Strategy const& strategy) 259 { 260 return apply(multipoint, linear, strategy); 261 } 262 }; 263 264 265 template <typename MultiPoint, typename SingleGeometry> 266 class multi_point_single_geometry 267 { 268 public: 269 template <typename Strategy> apply(MultiPoint const & multi_point,SingleGeometry const & single_geometry,Strategy const & strategy)270 static inline bool apply(MultiPoint const& multi_point, 271 SingleGeometry const& single_geometry, 272 Strategy const& strategy) 273 { 274 typedef typename Strategy::disjoint_point_box_strategy_type d_pb_strategy_type; 275 276 typedef typename point_type<MultiPoint>::type point1_type; 277 typedef typename point_type<SingleGeometry>::type point2_type; 278 typedef model::box<point2_type> box2_type; 279 280 box2_type box2; 281 geometry::envelope(single_geometry, box2, strategy.get_envelope_strategy()); 282 geometry::detail::expand_by_epsilon(box2); 283 284 typedef typename boost::range_const_iterator<MultiPoint>::type iterator; 285 for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it ) 286 { 287 // The default strategy is enough for Point/Box 288 if (! detail::disjoint::disjoint_point_box(*it, box2, d_pb_strategy_type()) 289 && ! dispatch::disjoint<point1_type, SingleGeometry>::apply(*it, single_geometry, strategy)) 290 { 291 return false; 292 } 293 } 294 295 return true; 296 } 297 298 template <typename Strategy> apply(SingleGeometry const & single_geometry,MultiPoint const & multi_point,Strategy const & strategy)299 static inline bool apply(SingleGeometry const& single_geometry, MultiPoint const& multi_point, Strategy const& strategy) 300 { 301 return apply(multi_point, single_geometry, strategy); 302 } 303 }; 304 305 306 template <typename MultiPoint, typename MultiGeometry> 307 class multi_point_multi_geometry 308 { 309 private: 310 template <typename ExpandPointStrategy> 311 struct expand_box_point 312 { 313 template <typename Box, typename Point> applyboost::geometry::detail::disjoint::multi_point_multi_geometry::expand_box_point314 static inline void apply(Box& total, Point const& point) 315 { 316 geometry::expand(total, point, ExpandPointStrategy()); 317 } 318 }; 319 320 template <typename ExpandBoxStrategy> 321 struct expand_box_box_pair 322 { 323 template <typename Box, typename BoxPair> applyboost::geometry::detail::disjoint::multi_point_multi_geometry::expand_box_box_pair324 inline void apply(Box& total, BoxPair const& box_pair) const 325 { 326 geometry::expand(total, box_pair.first, ExpandBoxStrategy()); 327 } 328 }; 329 330 template <typename DisjointPointBoxStrategy> 331 struct overlaps_box_point 332 { 333 template <typename Box, typename Point> applyboost::geometry::detail::disjoint::multi_point_multi_geometry::overlaps_box_point334 static inline bool apply(Box const& box, Point const& point) 335 { 336 // The default strategy is enough for Point/Box 337 return ! detail::disjoint::disjoint_point_box(point, box, 338 DisjointPointBoxStrategy()); 339 } 340 }; 341 342 template <typename DisjointBoxBoxStrategy> 343 struct overlaps_box_box_pair 344 { 345 template <typename Box, typename BoxPair> applyboost::geometry::detail::disjoint::multi_point_multi_geometry::overlaps_box_box_pair346 inline bool apply(Box const& box, BoxPair const& box_pair) const 347 { 348 // The default strategy is enough for Box/Box 349 return ! detail::disjoint::disjoint_box_box(box_pair.first, box, 350 DisjointBoxBoxStrategy()); 351 } 352 }; 353 354 template <typename PtSegStrategy> 355 class item_visitor_type 356 { 357 public: item_visitor_type(MultiGeometry const & multi_geometry,PtSegStrategy const & strategy)358 item_visitor_type(MultiGeometry const& multi_geometry, 359 PtSegStrategy const& strategy) 360 : m_intersection_found(false) 361 , m_multi_geometry(multi_geometry) 362 , m_strategy(strategy) 363 {} 364 365 template <typename Point, typename BoxPair> apply(Point const & point,BoxPair const & box_pair)366 inline bool apply(Point const& point, BoxPair const& box_pair) 367 { 368 typedef typename PtSegStrategy::disjoint_point_box_strategy_type d_pb_strategy_type; 369 370 typedef typename boost::range_value<MultiGeometry>::type single_type; 371 372 // The default strategy is enough for Point/Box 373 if (! m_intersection_found 374 && ! detail::disjoint::disjoint_point_box(point, box_pair.first, d_pb_strategy_type()) 375 && ! dispatch::disjoint<Point, single_type>::apply(point, range::at(m_multi_geometry, box_pair.second), m_strategy)) 376 { 377 m_intersection_found = true; 378 return false; 379 } 380 return true; 381 } 382 intersection_found() const383 inline bool intersection_found() const { return m_intersection_found; } 384 385 private: 386 bool m_intersection_found; 387 MultiGeometry const& m_multi_geometry; 388 PtSegStrategy const& m_strategy; 389 }; 390 // structs for partition -- end 391 392 public: 393 template <typename Strategy> apply(MultiPoint const & multi_point,MultiGeometry const & multi_geometry,Strategy const & strategy)394 static inline bool apply(MultiPoint const& multi_point, MultiGeometry const& multi_geometry, Strategy const& strategy) 395 { 396 typedef typename point_type<MultiPoint>::type point1_type; 397 typedef typename point_type<MultiGeometry>::type point2_type; 398 typedef model::box<point1_type> box1_type; 399 typedef model::box<point2_type> box2_type; 400 typedef std::pair<box2_type, std::size_t> box_pair_type; 401 402 typename Strategy::envelope_strategy_type const 403 envelope_strategy = strategy.get_envelope_strategy(); 404 405 std::size_t count2 = boost::size(multi_geometry); 406 std::vector<box_pair_type> boxes(count2); 407 for (std::size_t i = 0 ; i < count2 ; ++i) 408 { 409 geometry::envelope(range::at(multi_geometry, i), boxes[i].first, envelope_strategy); 410 geometry::detail::expand_by_epsilon(boxes[i].first); 411 boxes[i].second = i; 412 } 413 414 item_visitor_type<Strategy> visitor(multi_geometry, strategy); 415 416 typedef expand_box_point 417 < 418 typename Strategy::expand_point_strategy_type 419 > expand_box_point_type; 420 typedef overlaps_box_point 421 < 422 typename Strategy::disjoint_point_box_strategy_type 423 > overlaps_box_point_type; 424 typedef expand_box_box_pair 425 < 426 typename Strategy::envelope_strategy_type::box_expand_strategy_type 427 > expand_box_box_pair_type; 428 typedef overlaps_box_box_pair 429 < 430 typename Strategy::disjoint_box_box_strategy_type 431 > overlaps_box_box_pair_type; 432 433 geometry::partition 434 < 435 box1_type 436 >::apply(multi_point, boxes, visitor, 437 expand_box_point_type(), 438 overlaps_box_point_type(), 439 expand_box_box_pair_type(), 440 overlaps_box_box_pair_type()); 441 442 return ! visitor.intersection_found(); 443 } 444 445 template <typename Strategy> apply(MultiGeometry const & multi_geometry,MultiPoint const & multi_point,Strategy const & strategy)446 static inline bool apply(MultiGeometry const& multi_geometry, MultiPoint const& multi_point, Strategy const& strategy) 447 { 448 return apply(multi_point, multi_geometry, strategy); 449 } 450 }; 451 452 453 template <typename MultiPoint, typename Areal, typename Tag = typename tag<Areal>::type> 454 struct multipoint_areal 455 : multi_point_single_geometry<MultiPoint, Areal> 456 {}; 457 458 template <typename MultiPoint, typename Areal> 459 struct multipoint_areal<MultiPoint, Areal, multi_polygon_tag> 460 : multi_point_multi_geometry<MultiPoint, Areal> 461 {}; 462 463 464 }} // namespace detail::disjoint 465 #endif // DOXYGEN_NO_DETAIL 466 467 468 469 470 #ifndef DOXYGEN_NO_DISPATCH 471 namespace dispatch 472 { 473 474 475 template <typename Point, typename MultiPoint, std::size_t DimensionCount> 476 struct disjoint 477 < 478 Point, MultiPoint, DimensionCount, point_tag, multi_point_tag, false 479 > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Point> 480 {}; 481 482 483 template <typename MultiPoint, typename Segment, std::size_t DimensionCount> 484 struct disjoint 485 < 486 MultiPoint, Segment, DimensionCount, multi_point_tag, segment_tag, false 487 > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Segment> 488 {}; 489 490 491 template <typename MultiPoint, typename Box, std::size_t DimensionCount> 492 struct disjoint 493 < 494 MultiPoint, Box, DimensionCount, multi_point_tag, box_tag, false 495 > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Box> 496 {}; 497 498 499 template 500 < 501 typename MultiPoint1, 502 typename MultiPoint2, 503 std::size_t DimensionCount 504 > 505 struct disjoint 506 < 507 MultiPoint1, MultiPoint2, DimensionCount, 508 multi_point_tag, multi_point_tag, false 509 > 510 { 511 template <typename Strategy> applyboost::geometry::dispatch::disjoint512 static inline bool apply(MultiPoint1 const& multipoint1, 513 MultiPoint2 const& multipoint2, 514 Strategy const& strategy) 515 { 516 if ( boost::size(multipoint2) < boost::size(multipoint1) ) 517 { 518 return detail::disjoint::multipoint_multipoint 519 ::apply(multipoint2, multipoint1, strategy); 520 } 521 522 return detail::disjoint::multipoint_multipoint 523 ::apply(multipoint1, multipoint2, strategy); 524 } 525 }; 526 527 528 template <typename Linear, typename MultiPoint, std::size_t DimensionCount> 529 struct disjoint 530 < 531 Linear, MultiPoint, DimensionCount, linear_tag, multi_point_tag, false 532 > : detail::disjoint::multipoint_linear<MultiPoint, Linear> 533 {}; 534 535 536 template <typename MultiPoint, typename Linear, std::size_t DimensionCount> 537 struct disjoint 538 < 539 MultiPoint, Linear, DimensionCount, multi_point_tag, linear_tag, false 540 > : detail::disjoint::multipoint_linear<MultiPoint, Linear> 541 {}; 542 543 544 template <typename Areal, typename MultiPoint, std::size_t DimensionCount> 545 struct disjoint 546 < 547 Areal, MultiPoint, DimensionCount, areal_tag, multi_point_tag, false 548 > : detail::disjoint::multipoint_areal<MultiPoint, Areal> 549 {}; 550 551 552 template <typename MultiPoint, typename Areal, std::size_t DimensionCount> 553 struct disjoint 554 < 555 MultiPoint, Areal, DimensionCount, multi_point_tag, areal_tag, false 556 > : detail::disjoint::multipoint_areal<MultiPoint, Areal> 557 {}; 558 559 560 } // namespace dispatch 561 #endif // DOXYGEN_NO_DISPATCH 562 563 564 }} // namespace boost::geometry 565 566 567 568 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP 569