ceph/src/boost/boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp

   1 // Boost.Geometry
   2
   3 // Copyright (c) 2017-2020 Oracle and/or its affiliates.
   4
   5 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   6
   7 // Use, modification and distribution is subject to the Boost Software License,
   8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   9 // http://www.boost.org/LICENSE_1_0.txt)
  10
  11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_MULTI_POINT_GEOMETRY_HPP
  12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_MULTI_POINT_GEOMETRY_HPP
  13
  14
  15 #include <boost/range/begin.hpp>
  16 #include <boost/range/end.hpp>
  17 #include <boost/range/size.hpp>
  18 #include <boost/range/value_type.hpp>
  19
  20 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
  21 #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
  22 #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp>
  23 #include <boost/geometry/algorithms/detail/partition.hpp>
  24 #include <boost/geometry/algorithms/detail/relate/result.hpp>
  25 #include <boost/geometry/algorithms/detail/relate/topology_check.hpp>
  26 #include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp>
  27 #include <boost/geometry/algorithms/envelope.hpp>
  28
  29 #include <boost/geometry/core/point_type.hpp>
  30
  31 #include <boost/geometry/geometries/box.hpp>
  32
  33 #include <boost/geometry/index/rtree.hpp>
  34
  35 // TEMP
  36 #include <boost/geometry/strategies/envelope/cartesian.hpp>
  37 #include <boost/geometry/strategies/envelope/geographic.hpp>
  38 #include <boost/geometry/strategies/envelope/spherical.hpp>
  39
  40 #include <boost/geometry/util/type_traits.hpp>
  41
  42
  43 namespace boost { namespace geometry
  44 {
  45
  46 #ifndef DOXYGEN_NO_DETAIL
  47 namespace detail { namespace relate
  48 {
  49
  50 template
  51 <
  52     typename Geometry,
  53     typename Tag = typename tag<Geometry>::type
  54 >
  55 struct multi_point_geometry_eb
  56 {
  57     template <typename MultiPoint, typename Strategy>
  58     static inline bool apply(MultiPoint const& ,
  59                              detail::relate::topology_check<Geometry, Strategy> const& )
  60     {
  61         return true;
  62     }
  63 };
  64
  65 template <typename Geometry>
  66 struct multi_point_geometry_eb<Geometry, linestring_tag>
  67 {
  68     template <typename Points>
  69     struct boundary_visitor
  70     {
  71         boundary_visitor(Points const& points)
  72             : m_points(points)
  73             , m_boundary_found(false)
  74         {}
  75
  76         template <typename Point, typename Strategy>
  77         struct find_pred
  78         {
  79             find_pred(Point const& point, Strategy const& strategy)
  80                 : m_point(point)
  81                 , m_strategy(strategy)
  82             {}
  83
  84             template <typename Pt>
  85             bool operator()(Pt const& pt) const
  86             {
  87                 return detail::equals::equals_point_point(pt, m_point, m_strategy);
  88             }
  89
  90             Point const& m_point;
  91             Strategy const& m_strategy;
  92         };
  93
  94         template <typename Point, typename Strategy>
  95         bool apply(Point const& boundary_point, Strategy const& strategy)
  96         {
  97             if ( std::none_of(m_points.begin(), m_points.end(),
  98                               find_pred<Point, Strategy>(boundary_point, strategy)))
  99             {
 100                 m_boundary_found = true;
 101                 return false;
 102             }
 103             return true;
 104         }
 105
 106         bool result() const { return m_boundary_found; }
 107
 108     private:
 109         Points const& m_points;
 110         bool m_boundary_found;
 111     };
 112
 113     template <typename MultiPoint, typename Strategy>
 114     static inline bool apply(MultiPoint const& multi_point,
 115                              detail::relate::topology_check<Geometry, Strategy> const& tc)
 116     {
 117         boundary_visitor<MultiPoint> visitor(multi_point);
 118         tc.for_each_boundary_point(visitor);
 119         return visitor.result();
 120     }
 121 };
 122
 123 template <typename Geometry>
 124 struct multi_point_geometry_eb<Geometry, multi_linestring_tag>
 125 {
 126     template <typename Points>
 127     struct boundary_visitor
 128     {
 129         boundary_visitor(Points const& points)
 130             : m_points(points)
 131             , m_boundary_found(false)
 132         {}
 133
 134         template <typename Point, typename Strategy>
 135         bool apply(Point const& boundary_point, Strategy const&)
 136         {
 137             typedef geometry::less<void, -1, typename Strategy::cs_tag> less_type;
 138
 139             if (! std::binary_search(m_points.begin(), m_points.end(),
 140                                      boundary_point, less_type()) )
 141             {
 142                 m_boundary_found = true;
 143                 return false;
 144             }
 145             return true;
 146         }
 147
 148         bool result() const { return m_boundary_found; }
 149
 150     private:
 151         Points const& m_points;
 152         bool m_boundary_found;
 153     };
 154
 155     template <typename MultiPoint, typename Strategy>
 156     static inline bool apply(MultiPoint const& multi_point,
 157                              detail::relate::topology_check<Geometry, Strategy> const& tc)
 158     {
 159         typedef typename boost::range_value<MultiPoint>::type point_type;
 160         typedef std::vector<point_type> points_type;
 161         typedef geometry::less<void, -1, typename Strategy::cs_tag> less_type;
 162
 163         points_type points(boost::begin(multi_point), boost::end(multi_point));
 164         std::sort(points.begin(), points.end(), less_type());
 165
 166         boundary_visitor<points_type> visitor(points);
 167         tc.for_each_boundary_point(visitor);
 168         return visitor.result();
 169     }
 170 };
 171
 172 // SingleGeometry - Linear or Areal
 173 template <typename MultiPoint, typename SingleGeometry, bool Transpose = false>
 174 struct multi_point_single_geometry
 175 {
 176     static const bool interruption_enabled = true;
 177
 178     template <typename Result, typename Strategy>
 179     static inline void apply(MultiPoint const& multi_point,
 180                              SingleGeometry const& single_geometry,
 181                              Result & result,
 182                              Strategy const& strategy)
 183     {
 184         typedef typename point_type<SingleGeometry>::type point2_type;
 185         typedef model::box<point2_type> box2_type;
 186
 187         box2_type box2;
 188         geometry::envelope(single_geometry, box2, strategy);
 189         geometry::detail::expand_by_epsilon(box2);
 190
 191         typedef typename boost::range_const_iterator<MultiPoint>::type iterator;
 192         for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it )
 193         {
 194             if (! (relate::may_update<interior, interior, '0', Transpose>(result)
 195                 || relate::may_update<interior, boundary, '0', Transpose>(result)
 196                 || relate::may_update<interior, exterior, '0', Transpose>(result) ) )
 197             {
 198                 break;
 199             }
 200
 201             // The default strategy is enough for Point/Box
 202             if (detail::disjoint::disjoint_point_box(*it, box2, strategy))
 203             {
 204                 relate::set<interior, exterior, '0', Transpose>(result);
 205             }
 206             else
 207             {
 208                 int in_val = detail::within::point_in_geometry(*it, single_geometry, strategy);
 209
 210                 if (in_val > 0) // within
 211                 {
 212                     relate::set<interior, interior, '0', Transpose>(result);
 213                 }
 214                 else if (in_val == 0)
 215                 {
 216                     relate::set<interior, boundary, '0', Transpose>(result);
 217                 }
 218                 else // in_val < 0 - not within
 219                 {
 220                     relate::set<interior, exterior, '0', Transpose>(result);
 221                 }
 222             }
 223
 224             if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
 225             {
 226                 return;
 227             }
 228         }
 229
 230         typedef detail::relate::topology_check<SingleGeometry, Strategy> tc_t;
 231
 232         if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result)
 233           || relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) )
 234         {
 235             tc_t tc(single_geometry, strategy);
 236
 237             if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result)
 238               && tc.has_interior() )
 239             {
 240                 // TODO: this is not true if a linestring is degenerated to a point
 241                 // then the interior has topological dimension = 0, not 1
 242                 relate::set<exterior, interior, tc_t::interior, Transpose>(result);
 243             }
 244
 245             if ( relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result)
 246               && tc.has_boundary() )
 247             {
 248                 if (multi_point_geometry_eb<SingleGeometry>::apply(multi_point, tc))
 249                 {
 250                     relate::set<exterior, boundary, tc_t::boundary, Transpose>(result);
 251                 }
 252             }
 253         }
 254
 255         relate::set<exterior, exterior, result_dimension<MultiPoint>::value, Transpose>(result);
 256     }
 257 };
 258
 259
 260 // MultiGeometry - Linear or Areal
 261 // part of the algorithm calculating II and IB when no IE has to be calculated
 262 // using partition()
 263 template <typename MultiPoint, typename MultiGeometry, bool Transpose>
 264 class multi_point_multi_geometry_ii_ib
 265 {
 266     template <typename Strategy>
 267     struct expand_box_point
 268     {
 269         expand_box_point(Strategy const& strategy)
 270             : m_strategy(strategy)
 271         {}
 272
 273         template <typename Box, typename Point>
 274         inline void apply(Box& total, Point const& point) const
 275         {
 276             geometry::expand(total, point, m_strategy);
 277         }
 278
 279     private:
 280         Strategy const& m_strategy;
 281     };
 282
 283     template <typename Strategy>
 284     struct expand_box_box_pair
 285     {
 286         expand_box_box_pair(Strategy const& strategy)
 287             : m_strategy(strategy)
 288         {}
 289
 290         template <typename Box, typename BoxPair>
 291         inline void apply(Box& total, BoxPair const& box_pair) const
 292         {
 293             geometry::expand(total, box_pair.first, m_strategy);
 294         }
 295
 296     private:
 297         Strategy const& m_strategy;
 298     };
 299
 300     template <typename Strategy>
 301     struct overlaps_box_point
 302     {
 303         overlaps_box_point(Strategy const& strategy)
 304             : m_strategy(strategy)
 305         {}
 306
 307         template <typename Box, typename Point>
 308         inline bool apply(Box const& box, Point const& point) const
 309         {
 310             // The default strategy is enough for Point/Box
 311             return ! detail::disjoint::disjoint_point_box(point, box,
 312                                                           m_strategy);
 313         }
 314
 315     private:
 316         Strategy const& m_strategy;
 317     };
 318
 319     template <typename Strategy>
 320     struct overlaps_box_box_pair
 321     {
 322         overlaps_box_box_pair(Strategy const& strategy)
 323             : m_strategy(strategy)
 324         {}
 325
 326         template <typename Box, typename BoxPair>
 327         inline bool apply(Box const& box, BoxPair const& box_pair) const
 328         {
 329             // The default strategy is enough for Box/Box
 330             return ! detail::disjoint::disjoint_box_box(box_pair.first, box,
 331                                                         m_strategy);
 332         }
 333
 334     private:
 335         Strategy const& m_strategy;
 336     };
 337
 338     template <typename Result, typename Strategy>
 339     class item_visitor_type
 340     {
 341         typedef detail::relate::topology_check<MultiGeometry, Strategy> topology_check_type;
 342
 343     public:
 344         item_visitor_type(MultiGeometry const& multi_geometry,
 345                           topology_check_type const& tc,
 346                           Result & result,
 347                           Strategy const& strategy)
 348             : m_multi_geometry(multi_geometry)
 349             , m_tc(tc)
 350             , m_result(result)
 351             , m_strategy(strategy)
 352         {}
 353
 354         template <typename Point, typename BoxPair>
 355         inline bool apply(Point const& point, BoxPair const& box_pair)
 356         {
 357             // The default strategy is enough for Point/Box
 358             if (! detail::disjoint::disjoint_point_box(point, box_pair.first, m_strategy) )
 359             {
 360                 typename boost::range_value<MultiGeometry>::type const&
 361                     single = range::at(m_multi_geometry, box_pair.second);
 362
 363                 int in_val = detail::within::point_in_geometry(point, single, m_strategy);
 364
 365                 if (in_val > 0) // within
 366                 {
 367                     relate::set<interior, interior, '0', Transpose>(m_result);
 368                 }
 369                 else if (in_val == 0)
 370                 {
 371                     if (m_tc.check_boundary_point(point))
 372                         relate::set<interior, boundary, '0', Transpose>(m_result);
 373                     else
 374                         relate::set<interior, interior, '0', Transpose>(m_result);
 375                 }
 376             }
 377
 378             if ( BOOST_GEOMETRY_CONDITION(m_result.interrupt) )
 379             {
 380                 return false;
 381             }
 382
 383             if (! (relate::may_update<interior, interior, '0', Transpose>(m_result)
 384                 || relate::may_update<interior, boundary, '0', Transpose>(m_result) ) )
 385             {
 386                 return false;
 387             }
 388
 389             return true;
 390         }
 391
 392
 393     private:
 394         MultiGeometry const& m_multi_geometry;
 395         topology_check_type const& m_tc;
 396         Result & m_result;
 397         Strategy const& m_strategy;
 398     };
 399
 400 public:
 401     typedef typename point_type<MultiPoint>::type point1_type;
 402     typedef typename point_type<MultiGeometry>::type point2_type;
 403     typedef model::box<point1_type> box1_type;
 404     typedef model::box<point2_type> box2_type;
 405     typedef std::pair<box2_type, std::size_t> box_pair_type;
 406
 407     template <typename Result, typename Strategy>
 408     static inline void apply(MultiPoint const& multi_point,
 409                              MultiGeometry const& multi_geometry,
 410                              std::vector<box_pair_type> const& boxes,
 411                              detail::relate::topology_check
 412                                 <
 413                                     MultiGeometry, Strategy
 414                                 > const& tc,
 415                              Result & result,
 416                              Strategy const& strategy)
 417     {
 418         item_visitor_type<Result, Strategy> visitor(multi_geometry, tc, result, strategy);
 419
 420         geometry::partition
 421             <
 422                 box1_type
 423             >::apply(multi_point, boxes, visitor,
 424                      expand_box_point<Strategy>(strategy),
 425                      overlaps_box_point<Strategy>(strategy),
 426                      expand_box_box_pair<Strategy>(strategy),
 427                      overlaps_box_box_pair<Strategy>(strategy));
 428     }
 429
 430 };
 431
 432 // MultiGeometry - Linear or Areal
 433 // part of the algorithm calculating II, IB and IE
 434 // using rtree
 435 template <typename MultiPoint, typename MultiGeometry, bool Transpose>
 436 struct multi_point_multi_geometry_ii_ib_ie
 437 {
 438     typedef typename point_type<MultiPoint>::type point1_type;
 439     typedef typename point_type<MultiGeometry>::type point2_type;
 440     typedef model::box<point1_type> box1_type;
 441     typedef model::box<point2_type> box2_type;
 442     typedef std::pair<box2_type, std::size_t> box_pair_type;
 443     typedef std::vector<box_pair_type> boxes_type;
 444     typedef typename boxes_type::const_iterator boxes_iterator;
 445
 446     template <typename Result, typename Strategy>
 447     static inline void apply(MultiPoint const& multi_point,
 448                              MultiGeometry const& multi_geometry,
 449                              std::vector<box_pair_type> const& boxes,
 450                              detail::relate::topology_check
 451                                 <
 452                                     MultiGeometry, Strategy
 453                                 > const& tc,
 454                              Result & result,
 455                              Strategy const& strategy)
 456     {
 457         typedef index::parameters
 458             <
 459                 index::rstar<4>, Strategy
 460             > index_parameters_type;
 461         index::rtree<box_pair_type, index_parameters_type>
 462             rtree(boxes.begin(), boxes.end(),
 463                   index_parameters_type(index::rstar<4>(), strategy));
 464
 465         typedef typename boost::range_const_iterator<MultiPoint>::type iterator;
 466         for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it )
 467         {
 468             if (! (relate::may_update<interior, interior, '0', Transpose>(result)
 469                 || relate::may_update<interior, boundary, '0', Transpose>(result)
 470                 || relate::may_update<interior, exterior, '0', Transpose>(result) ) )
 471             {
 472                 return;
 473             }
 474
 475             typename boost::range_value<MultiPoint>::type const& point = *it;
 476
 477             boxes_type boxes_found;
 478             rtree.query(index::intersects(point), std::back_inserter(boxes_found));
 479
 480             bool found_ii_or_ib = false;
 481             for (boxes_iterator bi = boxes_found.begin() ; bi != boxes_found.end() ; ++bi)
 482             {
 483                 typename boost::range_value<MultiGeometry>::type const&
 484                     single = range::at(multi_geometry, bi->second);
 485
 486                 int in_val = detail::within::point_in_geometry(point, single, strategy);
 487
 488                 if (in_val > 0) // within
 489                 {
 490                     relate::set<interior, interior, '0', Transpose>(result);
 491                     found_ii_or_ib = true;
 492                 }
 493                 else if (in_val == 0) // on boundary of single
 494                 {
 495                     if (tc.check_boundary_point(point))
 496                         relate::set<interior, boundary, '0', Transpose>(result);
 497                     else
 498                         relate::set<interior, interior, '0', Transpose>(result);
 499                     found_ii_or_ib = true;
 500                 }
 501             }
 502
 503             // neither interior nor boundary found -> exterior
 504             if (found_ii_or_ib == false)
 505             {
 506                 relate::set<interior, exterior, '0', Transpose>(result);
 507             }
 508
 509             if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
 510             {
 511                 return;
 512             }
 513         }
 514     }
 515 };
 516
 517 // MultiGeometry - Linear or Areal
 518 template <typename MultiPoint, typename MultiGeometry, bool Transpose = false>
 519 struct multi_point_multi_geometry
 520 {
 521     static const bool interruption_enabled = true;
 522
 523     template <typename Result, typename Strategy>
 524     static inline void apply(MultiPoint const& multi_point,
 525                              MultiGeometry const& multi_geometry,
 526                              Result & result,
 527                              Strategy const& strategy)
 528     {
 529         typedef typename point_type<MultiGeometry>::type point2_type;
 530         typedef model::box<point2_type> box2_type;
 531         typedef std::pair<box2_type, std::size_t> box_pair_type;
 532
 533         std::size_t count2 = boost::size(multi_geometry);
 534         std::vector<box_pair_type> boxes(count2);
 535         for (std::size_t i = 0 ; i < count2 ; ++i)
 536         {
 537             geometry::envelope(range::at(multi_geometry, i), boxes[i].first, strategy);
 538             geometry::detail::expand_by_epsilon(boxes[i].first);
 539             boxes[i].second = i;
 540         }
 541
 542         typedef detail::relate::topology_check<MultiGeometry, Strategy> tc_t;
 543         tc_t tc(multi_geometry, strategy);
 544
 545         if ( relate::may_update<interior, interior, '0', Transpose>(result)
 546           || relate::may_update<interior, boundary, '0', Transpose>(result)
 547           || relate::may_update<interior, exterior, '0', Transpose>(result) )
 548         {
 549             // If there is no need to calculate IE, use partition
 550             if (! relate::may_update<interior, exterior, '0', Transpose>(result) )
 551             {
 552                 multi_point_multi_geometry_ii_ib<MultiPoint, MultiGeometry, Transpose>
 553                     ::apply(multi_point, multi_geometry, boxes, tc, result, strategy);
 554             }
 555             else // otherwise use rtree
 556             {
 557                 multi_point_multi_geometry_ii_ib_ie<MultiPoint, MultiGeometry, Transpose>
 558                     ::apply(multi_point, multi_geometry, boxes, tc, result, strategy);
 559             }
 560         }
 561
 562         if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
 563         {
 564             return;
 565         }
 566
 567         if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result)
 568           || relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) )
 569         {
 570             if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result)
 571               && tc.has_interior() )
 572             {
 573                 // TODO: this is not true if a linestring is degenerated to a point
 574                 // then the interior has topological dimension = 0, not 1
 575                 relate::set<exterior, interior, tc_t::interior, Transpose>(result);
 576             }
 577
 578             if ( relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result)
 579               && tc.has_boundary() )
 580             {
 581                 if (multi_point_geometry_eb<MultiGeometry>::apply(multi_point, tc))
 582                 {
 583                     relate::set<exterior, boundary, tc_t::boundary, Transpose>(result);
 584                 }
 585             }
 586         }
 587
 588         relate::set<exterior, exterior, result_dimension<MultiPoint>::value, Transpose>(result);
 589     }
 590
 591 };
 592
 593
 594 template
 595 <
 596     typename MultiPoint, typename Geometry,
 597     bool Transpose = false,
 598     bool isMulti = util::is_multi<Geometry>::value
 599 >
 600 struct multi_point_geometry
 601     : multi_point_single_geometry<MultiPoint, Geometry, Transpose>
 602 {};
 603
 604 template <typename MultiPoint, typename Geometry, bool Transpose>
 605 struct multi_point_geometry<MultiPoint, Geometry, Transpose, true>
 606     : multi_point_multi_geometry<MultiPoint, Geometry, Transpose>
 607 {};
 608
 609
 610 // transposed result of multi_point_geometry
 611 template <typename Geometry, typename MultiPoint>
 612 struct geometry_multi_point
 613 {
 614     static const bool interruption_enabled = true;
 615
 616     template <typename Result, typename Strategy>
 617     static inline void apply(Geometry const& geometry, MultiPoint const& multi_point,
 618                              Result & result, Strategy const& strategy)
 619     {
 620         multi_point_geometry<MultiPoint, Geometry, true>::apply(multi_point, geometry, result, strategy);
 621     }
 622 };
 623
 624 }} // namespace detail::relate
 625 #endif // DOXYGEN_NO_DETAIL
 626
 627 }} // namespace boost::geometry
 628
 629 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_MULTI_POINT_GEOMETRY_HPP