1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. 4 5 // Copyright (c) 2014-2018, 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 template <typename MultiPoint1, typename MultiPoint2> 55 class multipoint_multipoint 56 { 57 private: 58 template <typename Iterator> 59 class unary_disjoint_predicate 60 : geometry::less<> 61 { 62 private: 63 typedef geometry::less<> base_type; 64 65 public: unary_disjoint_predicate(Iterator first,Iterator last)66 unary_disjoint_predicate(Iterator first, Iterator last) 67 : base_type(), m_first(first), m_last(last) 68 {} 69 70 template <typename Point> apply(Point const & point) const71 inline bool apply(Point const& point) const 72 { 73 return !std::binary_search(m_first, 74 m_last, 75 point, 76 static_cast<base_type const&>(*this)); 77 } 78 79 private: 80 Iterator m_first, m_last; 81 }; 82 83 public: apply(MultiPoint1 const & multipoint1,MultiPoint2 const & multipoint2)84 static inline bool apply(MultiPoint1 const& multipoint1, 85 MultiPoint2 const& multipoint2) 86 { 87 BOOST_GEOMETRY_ASSERT( boost::size(multipoint1) <= boost::size(multipoint2) ); 88 89 typedef typename boost::range_value<MultiPoint1>::type point1_type; 90 91 std::vector<point1_type> points1(boost::begin(multipoint1), 92 boost::end(multipoint1)); 93 94 std::sort(points1.begin(), points1.end(), geometry::less<>()); 95 96 typedef unary_disjoint_predicate 97 < 98 typename std::vector<point1_type>::const_iterator 99 > predicate_type; 100 101 return check_iterator_range 102 < 103 predicate_type 104 >::apply(boost::begin(multipoint2), 105 boost::end(multipoint2), 106 predicate_type(points1.begin(), points1.end())); 107 } 108 }; 109 110 111 template <typename MultiPoint, typename Linear> 112 class multipoint_linear 113 { 114 private: 115 struct expand_box_point 116 { 117 template <typename Box, typename Point> applyboost::geometry::detail::disjoint::multipoint_linear::expand_box_point118 static inline void apply(Box& total, Point const& point) 119 { 120 geometry::expand(total, point); 121 } 122 }; 123 124 template <typename EnvelopeStrategy> 125 struct expand_box_segment 126 { expand_box_segmentboost::geometry::detail::disjoint::multipoint_linear::expand_box_segment127 explicit expand_box_segment(EnvelopeStrategy const& strategy) 128 : m_strategy(strategy) 129 {} 130 131 template <typename Box, typename Segment> applyboost::geometry::detail::disjoint::multipoint_linear::expand_box_segment132 inline void apply(Box& total, Segment const& segment) const 133 { 134 geometry::expand(total, 135 geometry::return_envelope<Box>(segment, m_strategy)); 136 } 137 138 EnvelopeStrategy const& m_strategy; 139 }; 140 141 template <typename DisjointPointBoxStrategy> 142 struct overlaps_box_point 143 { 144 template <typename Box, typename Point> applyboost::geometry::detail::disjoint::multipoint_linear::overlaps_box_point145 static inline bool apply(Box const& box, Point const& point) 146 { 147 // The default strategy is enough in this case 148 return ! detail::disjoint::disjoint_point_box(point, box, 149 DisjointPointBoxStrategy()); 150 } 151 }; 152 153 template <typename DisjointStrategy> 154 struct overlaps_box_segment 155 { overlaps_box_segmentboost::geometry::detail::disjoint::multipoint_linear::overlaps_box_segment156 explicit overlaps_box_segment(DisjointStrategy const& strategy) 157 : m_strategy(strategy) 158 {} 159 160 template <typename Box, typename Segment> applyboost::geometry::detail::disjoint::multipoint_linear::overlaps_box_segment161 inline bool apply(Box const& box, Segment const& segment) const 162 { 163 return ! dispatch::disjoint<Segment, Box>::apply(segment, box, m_strategy); 164 } 165 166 DisjointStrategy const& m_strategy; 167 }; 168 169 template <typename PtSegStrategy> 170 class item_visitor_type 171 { 172 public: item_visitor_type(PtSegStrategy const & strategy)173 item_visitor_type(PtSegStrategy const& strategy) 174 : m_intersection_found(false) 175 , m_strategy(strategy) 176 {} 177 178 template <typename Item1, typename Item2> apply(Item1 const & item1,Item2 const & item2)179 inline bool apply(Item1 const& item1, Item2 const& item2) 180 { 181 if (! m_intersection_found 182 && ! dispatch::disjoint<Item1, Item2>::apply(item1, item2, m_strategy)) 183 { 184 m_intersection_found = true; 185 return false; 186 } 187 return true; 188 } 189 intersection_found() const190 inline bool intersection_found() const { return m_intersection_found; } 191 192 private: 193 bool m_intersection_found; 194 PtSegStrategy const& m_strategy; 195 }; 196 // structs for partition -- end 197 198 class segment_range 199 { 200 public: 201 typedef geometry::segment_iterator<Linear const> const_iterator; 202 typedef const_iterator iterator; 203 segment_range(Linear const & linear)204 segment_range(Linear const& linear) 205 : m_linear(linear) 206 {} 207 begin() const208 const_iterator begin() const 209 { 210 return geometry::segments_begin(m_linear); 211 } 212 end() const213 const_iterator end() const 214 { 215 return geometry::segments_end(m_linear); 216 } 217 218 private: 219 Linear const& m_linear; 220 }; 221 222 public: 223 template <typename Strategy> apply(MultiPoint const & multipoint,Linear const & linear,Strategy const & strategy)224 static inline bool apply(MultiPoint const& multipoint, Linear const& linear, Strategy const& strategy) 225 { 226 item_visitor_type<Strategy> visitor(strategy); 227 228 typedef typename Strategy::envelope_strategy_type envelope_strategy_type; 229 typedef typename Strategy::disjoint_strategy_type disjoint_strategy_type; 230 typedef typename Strategy::disjoint_point_box_strategy_type disjoint_pb_strategy_type; 231 232 // TODO: disjoint Segment/Box may be called in partition multiple times 233 // possibly for non-cartesian segments which could be slow. We should consider 234 // passing a range of bounding boxes of segments after calculating them once. 235 // Alternatively instead of a range of segments a range of Segment/Envelope pairs 236 // should be passed, where envelope would be lazily calculated when needed the first time 237 geometry::partition 238 < 239 geometry::model::box<typename point_type<MultiPoint>::type> 240 >::apply(multipoint, segment_range(linear), visitor, 241 expand_box_point(), 242 overlaps_box_point<disjoint_pb_strategy_type>(), 243 expand_box_segment<envelope_strategy_type>(strategy.get_envelope_strategy()), 244 overlaps_box_segment<disjoint_strategy_type>(strategy.get_disjoint_strategy())); 245 246 return ! visitor.intersection_found(); 247 } 248 249 template <typename Strategy> apply(Linear const & linear,MultiPoint const & multipoint,Strategy const & strategy)250 static inline bool apply(Linear const& linear, MultiPoint const& multipoint, Strategy const& strategy) 251 { 252 return apply(multipoint, linear, strategy); 253 } 254 }; 255 256 257 template <typename MultiPoint, typename SingleGeometry> 258 class multi_point_single_geometry 259 { 260 public: 261 template <typename Strategy> apply(MultiPoint const & multi_point,SingleGeometry const & single_geometry,Strategy const & strategy)262 static inline bool apply(MultiPoint const& multi_point, 263 SingleGeometry const& single_geometry, 264 Strategy const& strategy) 265 { 266 typedef typename Strategy::disjoint_point_box_strategy_type d_pb_strategy_type; 267 268 typedef typename point_type<MultiPoint>::type point1_type; 269 typedef typename point_type<SingleGeometry>::type point2_type; 270 typedef model::box<point2_type> box2_type; 271 272 box2_type box2; 273 geometry::envelope(single_geometry, box2, strategy.get_envelope_strategy()); 274 geometry::detail::expand_by_epsilon(box2); 275 276 typedef typename boost::range_const_iterator<MultiPoint>::type iterator; 277 for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it ) 278 { 279 // The default strategy is enough for Point/Box 280 if (! detail::disjoint::disjoint_point_box(*it, box2, d_pb_strategy_type()) 281 && ! dispatch::disjoint<point1_type, SingleGeometry>::apply(*it, single_geometry, strategy)) 282 { 283 return false; 284 } 285 } 286 287 return true; 288 } 289 290 template <typename Strategy> apply(SingleGeometry const & single_geometry,MultiPoint const & multi_point,Strategy const & strategy)291 static inline bool apply(SingleGeometry const& single_geometry, MultiPoint const& multi_point, Strategy const& strategy) 292 { 293 return apply(multi_point, single_geometry, strategy); 294 } 295 }; 296 297 298 template <typename MultiPoint, typename MultiGeometry> 299 class multi_point_multi_geometry 300 { 301 private: 302 struct expand_box_point 303 { 304 template <typename Box, typename Point> applyboost::geometry::detail::disjoint::multi_point_multi_geometry::expand_box_point305 static inline void apply(Box& total, Point const& point) 306 { 307 geometry::expand(total, point); 308 } 309 }; 310 311 struct expand_box_box_pair 312 { 313 template <typename Box, typename BoxPair> applyboost::geometry::detail::disjoint::multi_point_multi_geometry::expand_box_box_pair314 inline void apply(Box& total, BoxPair const& box_pair) const 315 { 316 geometry::expand(total, box_pair.first); 317 } 318 }; 319 320 template <typename DisjointPointBoxStrategy> 321 struct overlaps_box_point 322 { 323 template <typename Box, typename Point> applyboost::geometry::detail::disjoint::multi_point_multi_geometry::overlaps_box_point324 static inline bool apply(Box const& box, Point const& point) 325 { 326 // The default strategy is enough for Point/Box 327 return ! detail::disjoint::disjoint_point_box(point, box, 328 DisjointPointBoxStrategy()); 329 } 330 }; 331 332 template <typename DisjointBoxBoxStrategy> 333 struct overlaps_box_box_pair 334 { 335 template <typename Box, typename BoxPair> applyboost::geometry::detail::disjoint::multi_point_multi_geometry::overlaps_box_box_pair336 inline bool apply(Box const& box, BoxPair const& box_pair) const 337 { 338 // The default strategy is enough for Box/Box 339 return ! detail::disjoint::disjoint_box_box(box_pair.first, box, 340 DisjointBoxBoxStrategy()); 341 } 342 }; 343 344 template <typename PtSegStrategy> 345 class item_visitor_type 346 { 347 public: item_visitor_type(MultiGeometry const & multi_geometry,PtSegStrategy const & strategy)348 item_visitor_type(MultiGeometry const& multi_geometry, 349 PtSegStrategy const& strategy) 350 : m_intersection_found(false) 351 , m_multi_geometry(multi_geometry) 352 , m_strategy(strategy) 353 {} 354 355 template <typename Point, typename BoxPair> apply(Point const & point,BoxPair const & box_pair)356 inline bool apply(Point const& point, BoxPair const& box_pair) 357 { 358 typedef typename PtSegStrategy::disjoint_point_box_strategy_type d_pb_strategy_type; 359 360 typedef typename boost::range_value<MultiGeometry>::type single_type; 361 362 // The default strategy is enough for Point/Box 363 if (! m_intersection_found 364 && ! detail::disjoint::disjoint_point_box(point, box_pair.first, d_pb_strategy_type()) 365 && ! dispatch::disjoint<Point, single_type>::apply(point, range::at(m_multi_geometry, box_pair.second), m_strategy)) 366 { 367 m_intersection_found = true; 368 return false; 369 } 370 return true; 371 } 372 intersection_found() const373 inline bool intersection_found() const { return m_intersection_found; } 374 375 private: 376 bool m_intersection_found; 377 MultiGeometry const& m_multi_geometry; 378 PtSegStrategy const& m_strategy; 379 }; 380 // structs for partition -- end 381 382 public: 383 template <typename Strategy> apply(MultiPoint const & multi_point,MultiGeometry const & multi_geometry,Strategy const & strategy)384 static inline bool apply(MultiPoint const& multi_point, MultiGeometry const& multi_geometry, Strategy const& strategy) 385 { 386 typedef typename point_type<MultiPoint>::type point1_type; 387 typedef typename point_type<MultiGeometry>::type point2_type; 388 typedef model::box<point1_type> box1_type; 389 typedef model::box<point2_type> box2_type; 390 typedef std::pair<box2_type, std::size_t> box_pair_type; 391 392 typename Strategy::envelope_strategy_type const 393 envelope_strategy = strategy.get_envelope_strategy(); 394 395 std::size_t count2 = boost::size(multi_geometry); 396 std::vector<box_pair_type> boxes(count2); 397 for (std::size_t i = 0 ; i < count2 ; ++i) 398 { 399 geometry::envelope(range::at(multi_geometry, i), boxes[i].first, envelope_strategy); 400 geometry::detail::expand_by_epsilon(boxes[i].first); 401 boxes[i].second = i; 402 } 403 404 item_visitor_type<Strategy> visitor(multi_geometry, strategy); 405 406 typedef overlaps_box_point 407 < 408 typename Strategy::disjoint_point_box_strategy_type 409 > overlaps_box_point_type; 410 typedef overlaps_box_box_pair 411 < 412 typename Strategy::disjoint_box_box_strategy_type 413 > overlaps_box_box_pair_type; 414 415 geometry::partition 416 < 417 box1_type 418 >::apply(multi_point, boxes, visitor, 419 expand_box_point(), 420 overlaps_box_point_type(), 421 expand_box_box_pair(), 422 overlaps_box_box_pair_type()); 423 424 return ! visitor.intersection_found(); 425 } 426 427 template <typename Strategy> apply(MultiGeometry const & multi_geometry,MultiPoint const & multi_point,Strategy const & strategy)428 static inline bool apply(MultiGeometry const& multi_geometry, MultiPoint const& multi_point, Strategy const& strategy) 429 { 430 return apply(multi_point, multi_geometry, strategy); 431 } 432 }; 433 434 435 template <typename MultiPoint, typename Areal, typename Tag = typename tag<Areal>::type> 436 struct multipoint_areal 437 : multi_point_single_geometry<MultiPoint, Areal> 438 {}; 439 440 template <typename MultiPoint, typename Areal> 441 struct multipoint_areal<MultiPoint, Areal, multi_polygon_tag> 442 : multi_point_multi_geometry<MultiPoint, Areal> 443 {}; 444 445 446 }} // namespace detail::disjoint 447 #endif // DOXYGEN_NO_DETAIL 448 449 450 451 452 #ifndef DOXYGEN_NO_DISPATCH 453 namespace dispatch 454 { 455 456 457 template <typename Point, typename MultiPoint, std::size_t DimensionCount> 458 struct disjoint 459 < 460 Point, MultiPoint, DimensionCount, point_tag, multi_point_tag, false 461 > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Point> 462 {}; 463 464 465 template <typename MultiPoint, typename Segment, std::size_t DimensionCount> 466 struct disjoint 467 < 468 MultiPoint, Segment, DimensionCount, multi_point_tag, segment_tag, false 469 > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Segment> 470 {}; 471 472 473 template <typename MultiPoint, typename Box, std::size_t DimensionCount> 474 struct disjoint 475 < 476 MultiPoint, Box, DimensionCount, multi_point_tag, box_tag, false 477 > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Box> 478 {}; 479 480 481 template 482 < 483 typename MultiPoint1, 484 typename MultiPoint2, 485 std::size_t DimensionCount 486 > 487 struct disjoint 488 < 489 MultiPoint1, MultiPoint2, DimensionCount, 490 multi_point_tag, multi_point_tag, false 491 > 492 { 493 template <typename Strategy> applyboost::geometry::dispatch::disjoint494 static inline bool apply(MultiPoint1 const& multipoint1, 495 MultiPoint2 const& multipoint2, 496 Strategy const& ) 497 { 498 if ( boost::size(multipoint2) < boost::size(multipoint1) ) 499 { 500 return detail::disjoint::multipoint_multipoint 501 < 502 MultiPoint2, MultiPoint1 503 >::apply(multipoint2, multipoint1); 504 } 505 506 return detail::disjoint::multipoint_multipoint 507 < 508 MultiPoint1, MultiPoint2 509 >::apply(multipoint1, multipoint2); 510 } 511 }; 512 513 514 template <typename Linear, typename MultiPoint, std::size_t DimensionCount> 515 struct disjoint 516 < 517 Linear, MultiPoint, DimensionCount, linear_tag, multi_point_tag, false 518 > : detail::disjoint::multipoint_linear<MultiPoint, Linear> 519 {}; 520 521 522 template <typename MultiPoint, typename Linear, std::size_t DimensionCount> 523 struct disjoint 524 < 525 MultiPoint, Linear, DimensionCount, multi_point_tag, linear_tag, false 526 > : detail::disjoint::multipoint_linear<MultiPoint, Linear> 527 {}; 528 529 530 template <typename Areal, typename MultiPoint, std::size_t DimensionCount> 531 struct disjoint 532 < 533 Areal, MultiPoint, DimensionCount, areal_tag, multi_point_tag, false 534 > : detail::disjoint::multipoint_areal<MultiPoint, Areal> 535 {}; 536 537 538 template <typename MultiPoint, typename Areal, std::size_t DimensionCount> 539 struct disjoint 540 < 541 MultiPoint, Areal, DimensionCount, multi_point_tag, areal_tag, false 542 > : detail::disjoint::multipoint_areal<MultiPoint, Areal> 543 {}; 544 545 546 } // namespace dispatch 547 #endif // DOXYGEN_NO_DISPATCH 548 549 550 }} // namespace boost::geometry 551 552 553 554 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP 555