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

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