ceph/src/boost/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp

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