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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2014-2017, Oracle and/or its affiliates.
   4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   5
   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:
  66         unary_disjoint_predicate(Iterator first, Iterator last)
  67             : base_type(), m_first(first), m_last(last)
  68         {}
  69
  70         template <typename Point>
  71         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:
  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>
 118         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     {
 127         explicit expand_box_segment(EnvelopeStrategy const& strategy)
 128             : m_strategy(strategy)
 129         {}
 130
 131         template <typename Box, typename Segment>
 132         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     struct overlaps_box_point
 142     {
 143         template <typename Box, typename Point>
 144         static inline bool apply(Box const& box, Point const& point)
 145         {
 146             // The default strategy is enough in this case
 147             return ! detail::disjoint::disjoint_point_box(point, box);
 148         }
 149     };
 150
 151     template <typename DisjointStrategy>
 152     struct overlaps_box_segment
 153     {
 154         explicit overlaps_box_segment(DisjointStrategy const& strategy)
 155             : m_strategy(strategy)
 156         {}
 157
 158         template <typename Box, typename Segment>
 159         inline bool apply(Box const& box, Segment const& segment) const
 160         {
 161             return ! dispatch::disjoint<Segment, Box>::apply(segment, box, m_strategy);
 162         }
 163
 164         DisjointStrategy const& m_strategy;
 165     };
 166
 167     template <typename PtSegStrategy>
 168     class item_visitor_type
 169     {
 170     public:
 171         item_visitor_type(PtSegStrategy const& strategy)
 172             : m_intersection_found(false)
 173             , m_strategy(strategy)
 174         {}
 175
 176         template <typename Item1, typename Item2>
 177         inline bool apply(Item1 const& item1, Item2 const& item2)
 178         {
 179             if (! m_intersection_found
 180                 && ! dispatch::disjoint<Item1, Item2>::apply(item1, item2, m_strategy))
 181             {
 182                 m_intersection_found = true;
 183                 return false;
 184             }
 185             return true;
 186         }
 187
 188         inline bool intersection_found() const { return m_intersection_found; }
 189
 190     private:
 191         bool m_intersection_found;
 192         PtSegStrategy const& m_strategy;
 193     };
 194     // structs for partition -- end
 195
 196     class segment_range
 197     {
 198     public:
 199         typedef geometry::segment_iterator<Linear const> const_iterator;
 200         typedef const_iterator iterator;
 201
 202         segment_range(Linear const& linear)
 203             : m_linear(linear)
 204         {}
 205
 206         const_iterator begin() const
 207         {
 208             return geometry::segments_begin(m_linear);
 209         }
 210
 211         const_iterator end() const
 212         {
 213             return geometry::segments_end(m_linear);
 214         }
 215
 216     private:
 217         Linear const& m_linear;
 218     };
 219
 220 public:
 221     template <typename Strategy>
 222     static inline bool apply(MultiPoint const& multipoint, Linear const& linear, Strategy const& strategy)
 223     {
 224         item_visitor_type<Strategy> visitor(strategy);
 225
 226         typedef typename Strategy::envelope_strategy_type envelope_strategy_type;
 227         typedef typename Strategy::disjoint_strategy_type disjoint_strategy_type;
 228
 229         // TODO: disjoint Segment/Box may be called in partition multiple times
 230         // possibly for non-cartesian segments which could be slow. We should consider
 231         // passing a range of bounding boxes of segments after calculating them once.
 232         // Alternatively instead of a range of segments a range of Segment/Envelope pairs
 233         // should be passed, where envelope would be lazily calculated when needed the first time
 234         geometry::partition
 235             <
 236                 geometry::model::box<typename point_type<MultiPoint>::type>
 237             >::apply(multipoint, segment_range(linear), visitor,
 238                      expand_box_point(),
 239                      overlaps_box_point(),
 240                      expand_box_segment<envelope_strategy_type>(strategy.get_envelope_strategy()),
 241                      overlaps_box_segment<disjoint_strategy_type>(strategy.get_disjoint_strategy()));
 242
 243         return ! visitor.intersection_found();
 244     }
 245
 246     template <typename Strategy>
 247     static inline bool apply(Linear const& linear, MultiPoint const& multipoint, Strategy const& strategy)
 248     {
 249         return apply(multipoint, linear, strategy);
 250     }
 251 };
 252
 253
 254 template <typename MultiPoint, typename SingleGeometry>
 255 class multi_point_single_geometry
 256 {
 257 public:
 258     template <typename Strategy>
 259     static inline bool apply(MultiPoint const& multi_point, SingleGeometry const& single_geometry, Strategy const& strategy)
 260     {
 261         typedef typename point_type<MultiPoint>::type point1_type;
 262         typedef typename point_type<SingleGeometry>::type point2_type;
 263         typedef model::box<point2_type> box2_type;
 264
 265         box2_type box2;
 266         geometry::envelope(single_geometry, box2, strategy.get_envelope_strategy());
 267         geometry::detail::expand_by_epsilon(box2);
 268
 269         typedef typename boost::range_const_iterator<MultiPoint>::type iterator;
 270         for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it )
 271         {
 272             // The default strategy is enough for Point/Box
 273             if (! detail::disjoint::disjoint_point_box(*it, box2)
 274                 && ! dispatch::disjoint<point1_type, SingleGeometry>::apply(*it, single_geometry, strategy))
 275             {
 276                 return false;
 277             }
 278         }
 279
 280         return true;
 281     }
 282
 283     template <typename Strategy>
 284     static inline bool apply(SingleGeometry const& single_geometry, MultiPoint const& multi_point, Strategy const& strategy)
 285     {
 286         return apply(multi_point, single_geometry, strategy);
 287     }
 288 };
 289
 290
 291 template <typename MultiPoint, typename MultiGeometry>
 292 class multi_point_multi_geometry
 293 {
 294 private:
 295     struct expand_box_point
 296     {
 297         template <typename Box, typename Point>
 298         static inline void apply(Box& total, Point const& point)
 299         {
 300             geometry::expand(total, point);
 301         }
 302     };
 303
 304     struct expand_box_box_pair
 305     {
 306         template <typename Box, typename BoxPair>
 307         inline void apply(Box& total, BoxPair const& box_pair) const
 308         {
 309             geometry::expand(total, box_pair.first);
 310         }
 311     };
 312
 313     struct overlaps_box_point
 314     {
 315         template <typename Box, typename Point>
 316         static inline bool apply(Box const& box, Point const& point)
 317         {
 318             // The default strategy is enough for Point/Box
 319             return ! detail::disjoint::disjoint_point_box(point, box);
 320         }
 321     };
 322
 323     struct overlaps_box_box_pair
 324     {
 325         template <typename Box, typename BoxPair>
 326         inline bool apply(Box const& box, BoxPair const& box_pair) const
 327         {
 328             // The default strategy is enough for Box/Box
 329             return ! detail::disjoint::disjoint_box_box(box_pair.first, box);
 330         }
 331     };
 332
 333     template <typename PtSegStrategy>
 334     class item_visitor_type
 335     {
 336     public:
 337         item_visitor_type(MultiGeometry const& multi_geometry,
 338                           PtSegStrategy const& strategy)
 339             : m_intersection_found(false)
 340             , m_multi_geometry(multi_geometry)
 341             , m_strategy(strategy)
 342         {}
 343
 344         template <typename Point, typename BoxPair>
 345         inline bool apply(Point const& point, BoxPair const& box_pair)
 346         {
 347             typedef typename boost::range_value<MultiGeometry>::type single_type;
 348
 349             // The default strategy is enough for Point/Box
 350             if (! m_intersection_found
 351                 && ! detail::disjoint::disjoint_point_box(point, box_pair.first)
 352                 && ! dispatch::disjoint<Point, single_type>::apply(point, range::at(m_multi_geometry, box_pair.second), m_strategy))
 353             {
 354                 m_intersection_found = true;
 355                 return false;
 356             }
 357             return true;
 358         }
 359
 360         inline bool intersection_found() const { return m_intersection_found; }
 361
 362     private:
 363         bool m_intersection_found;
 364         MultiGeometry const& m_multi_geometry;
 365         PtSegStrategy const& m_strategy;
 366     };
 367     // structs for partition -- end
 368
 369 public:
 370     template <typename Strategy>
 371     static inline bool apply(MultiPoint const& multi_point, MultiGeometry const& multi_geometry, Strategy const& strategy)
 372     {
 373         typedef typename point_type<MultiPoint>::type point1_type;
 374         typedef typename point_type<MultiGeometry>::type point2_type;
 375         typedef model::box<point1_type> box1_type;
 376         typedef model::box<point2_type> box2_type;
 377         typedef std::pair<box2_type, std::size_t> box_pair_type;
 378
 379         typename Strategy::envelope_strategy_type const
 380             envelope_strategy = strategy.get_envelope_strategy();
 381
 382         std::size_t count2 = boost::size(multi_geometry);
 383         std::vector<box_pair_type> boxes(count2);
 384         for (std::size_t i = 0 ; i < count2 ; ++i)
 385         {
 386             geometry::envelope(range::at(multi_geometry, i), boxes[i].first, envelope_strategy);
 387             geometry::detail::expand_by_epsilon(boxes[i].first);
 388             boxes[i].second = i;
 389         }
 390
 391         item_visitor_type<Strategy> visitor(multi_geometry, strategy);
 392
 393         geometry::partition
 394             <
 395                 box1_type
 396             >::apply(multi_point, boxes, visitor,
 397                      expand_box_point(),
 398                      overlaps_box_point(),
 399                      expand_box_box_pair(),
 400                      overlaps_box_box_pair());
 401
 402         return ! visitor.intersection_found();
 403     }
 404
 405     template <typename Strategy>
 406     static inline bool apply(MultiGeometry const& multi_geometry, MultiPoint const& multi_point, Strategy const& strategy)
 407     {
 408         return apply(multi_point, multi_geometry, strategy);
 409     }
 410 };
 411
 412
 413 template <typename MultiPoint, typename Areal, typename Tag = typename tag<Areal>::type>
 414 struct multipoint_areal
 415     : multi_point_single_geometry<MultiPoint, Areal>
 416 {};
 417
 418 template <typename MultiPoint, typename Areal>
 419 struct multipoint_areal<MultiPoint, Areal, multi_polygon_tag>
 420     : multi_point_multi_geometry<MultiPoint, Areal>
 421 {};
 422
 423
 424 }} // namespace detail::disjoint
 425 #endif // DOXYGEN_NO_DETAIL
 426
 427
 428
 429
 430 #ifndef DOXYGEN_NO_DISPATCH
 431 namespace dispatch
 432 {
 433
 434
 435 template <typename Point, typename MultiPoint, std::size_t DimensionCount>
 436 struct disjoint
 437     <
 438         Point, MultiPoint, DimensionCount, point_tag, multi_point_tag, false
 439     > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Point>
 440 {};
 441
 442
 443 template <typename MultiPoint, typename Segment, std::size_t DimensionCount>
 444 struct disjoint
 445     <
 446         MultiPoint, Segment, DimensionCount, multi_point_tag, segment_tag, false
 447     > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Segment>
 448 {};
 449
 450
 451 template <typename MultiPoint, typename Box, std::size_t DimensionCount>
 452 struct disjoint
 453     <
 454         MultiPoint, Box, DimensionCount, multi_point_tag, box_tag, false
 455     > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Box>
 456 {};
 457
 458
 459 template
 460 <
 461     typename MultiPoint1,
 462     typename MultiPoint2,
 463     std::size_t DimensionCount
 464 >
 465 struct disjoint
 466     <
 467         MultiPoint1, MultiPoint2, DimensionCount,
 468         multi_point_tag, multi_point_tag, false
 469     >
 470 {
 471     template <typename Strategy>
 472     static inline bool apply(MultiPoint1 const& multipoint1,
 473                              MultiPoint2 const& multipoint2,
 474                              Strategy const& )
 475     {
 476         if ( boost::size(multipoint2) < boost::size(multipoint1) )
 477         {
 478             return detail::disjoint::multipoint_multipoint
 479                 <
 480                     MultiPoint2, MultiPoint1
 481                 >::apply(multipoint2, multipoint1);
 482         }
 483
 484         return detail::disjoint::multipoint_multipoint
 485             <
 486                 MultiPoint1, MultiPoint2
 487             >::apply(multipoint1, multipoint2);
 488    }
 489 };
 490
 491
 492 template <typename Linear, typename MultiPoint, std::size_t DimensionCount>
 493 struct disjoint
 494     <
 495         Linear, MultiPoint, DimensionCount, linear_tag, multi_point_tag, false
 496     > : detail::disjoint::multipoint_linear<MultiPoint, Linear>
 497 {};
 498
 499
 500 template <typename MultiPoint, typename Linear, std::size_t DimensionCount>
 501 struct disjoint
 502     <
 503         MultiPoint, Linear, DimensionCount, multi_point_tag, linear_tag, false
 504     > : detail::disjoint::multipoint_linear<MultiPoint, Linear>
 505 {};
 506
 507
 508 template <typename Areal, typename MultiPoint, std::size_t DimensionCount>
 509 struct disjoint
 510     <
 511         Areal, MultiPoint, DimensionCount, areal_tag, multi_point_tag, false
 512     > : detail::disjoint::multipoint_areal<MultiPoint, Areal>
 513 {};
 514
 515
 516 template <typename MultiPoint, typename Areal, std::size_t DimensionCount>
 517 struct disjoint
 518     <
 519         MultiPoint, Areal, DimensionCount, multi_point_tag, areal_tag, false
 520     > : detail::disjoint::multipoint_areal<MultiPoint, Areal>
 521 {};
 522
 523
 524 } // namespace dispatch
 525 #endif // DOXYGEN_NO_DISPATCH
 526
 527
 528 }} // namespace boost::geometry
 529
 530
 531
 532 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP