Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-10-18 08:45:21 

0001 // Boost.Geometry
0002 
0003 // Copyright (c) 2014-2023, Oracle and/or its affiliates.
0004 
0005 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0006 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0007 
0008 // Use, modification and distribution is subject to the Boost Software License,
0009 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0010 // http://www.boost.org/LICENSE_1_0.txt)
0011 
0012 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_MULTI_POINT_GEOMETRY_HPP
0013 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_MULTI_POINT_GEOMETRY_HPP
0014 
0015 
0016 #include <boost/range/begin.hpp>
0017 #include <boost/range/end.hpp>
0018 #include <boost/range/size.hpp>
0019 #include <boost/range/value_type.hpp>
0020 
0021 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
0022 #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
0023 #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp>
0024 #include <boost/geometry/algorithms/detail/partition.hpp>
0025 #include <boost/geometry/algorithms/detail/relate/result.hpp>
0026 #include <boost/geometry/algorithms/detail/relate/topology_check.hpp>
0027 #include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp>
0028 #include <boost/geometry/algorithms/envelope.hpp>
0029 
0030 #include <boost/geometry/core/point_type.hpp>
0031 
0032 #include <boost/geometry/geometries/box.hpp>
0033 
0034 #include <boost/geometry/index/rtree.hpp>
0035 
0036 // TEMP
0037 #include <boost/geometry/strategies/envelope/cartesian.hpp>
0038 #include <boost/geometry/strategies/envelope/geographic.hpp>
0039 #include <boost/geometry/strategies/envelope/spherical.hpp>
0040 
0041 #include <boost/geometry/util/type_traits.hpp>
0042 
0043 
0044 namespace boost { namespace geometry
0045 {
0046 
0047 #ifndef DOXYGEN_NO_DETAIL
0048 namespace detail { namespace relate
0049 {
0050 
0051 template
0052 <
0053     typename Geometry,
0054     typename Tag = tag_t<Geometry>
0055 >
0056 struct multi_point_geometry_eb
0057 {
0058     template <typename MultiPoint, typename Strategy>
0059     static inline bool apply(MultiPoint const& ,
0060                              detail::relate::topology_check<Geometry, Strategy> const& )
0061     {
0062         return true;
0063     }
0064 };
0065 
0066 template <typename Geometry>
0067 struct multi_point_geometry_eb<Geometry, linestring_tag>
0068 {
0069     template <typename Points>
0070     struct boundary_visitor
0071     {
0072         boundary_visitor(Points const& points)
0073             : m_points(points)
0074             , m_boundary_found(false)
0075         {}
0076 
0077         template <typename Point, typename Strategy>
0078         struct find_pred
0079         {
0080             find_pred(Point const& point, Strategy const& strategy)
0081                 : m_point(point)
0082                 , m_strategy(strategy)
0083             {}
0084 
0085             template <typename Pt>
0086             bool operator()(Pt const& pt) const
0087             {
0088                 return detail::equals::equals_point_point(pt, m_point, m_strategy);
0089             }
0090 
0091             Point const& m_point;
0092             Strategy const& m_strategy;
0093         };
0094 
0095         template <typename Point, typename Strategy>
0096         bool apply(Point const& boundary_point, Strategy const& strategy)
0097         {
0098             if ( std::none_of(m_points.begin(), m_points.end(),
0099                               find_pred<Point, Strategy>(boundary_point, strategy)))
0100             {
0101                 m_boundary_found = true;
0102                 return false;
0103             }
0104             return true;
0105         }
0106 
0107         bool result() const { return m_boundary_found; }
0108 
0109     private:
0110         Points const& m_points;
0111         bool m_boundary_found;
0112     };
0113 
0114     template <typename MultiPoint, typename Strategy>
0115     static inline bool apply(MultiPoint const& multi_point,
0116                              detail::relate::topology_check<Geometry, Strategy> const& tc)
0117     {
0118         boundary_visitor<MultiPoint> visitor(multi_point);
0119         tc.for_each_boundary_point(visitor);
0120         return visitor.result();
0121     }
0122 };
0123 
0124 template <typename Geometry>
0125 struct multi_point_geometry_eb<Geometry, multi_linestring_tag>
0126 {
0127     template <typename Points>
0128     struct boundary_visitor
0129     {
0130         boundary_visitor(Points const& points)
0131             : m_points(points)
0132             , m_boundary_found(false)
0133         {}
0134 
0135         template <typename Point, typename Strategy>
0136         bool apply(Point const& boundary_point, Strategy const&)
0137         {
0138             typedef geometry::less<void, -1, Strategy> less_type;
0139 
0140             if (! std::binary_search(m_points.begin(), m_points.end(),
0141                                      boundary_point, less_type()) )
0142             {
0143                 m_boundary_found = true;
0144                 return false;
0145             }
0146             return true;
0147         }
0148 
0149         bool result() const { return m_boundary_found; }
0150 
0151     private:
0152         Points const& m_points;
0153         bool m_boundary_found;
0154     };
0155 
0156     template <typename MultiPoint, typename Strategy>
0157     static inline bool apply(MultiPoint const& multi_point,
0158                              detail::relate::topology_check<Geometry, Strategy> const& tc)
0159     {
0160         typedef typename boost::range_value<MultiPoint>::type point_type;
0161         typedef std::vector<point_type> points_type;
0162         typedef geometry::less<void, -1, Strategy> less_type;
0163 
0164         points_type points(boost::begin(multi_point), boost::end(multi_point));
0165         std::sort(points.begin(), points.end(), less_type());
0166 
0167         boundary_visitor<points_type> visitor(points);
0168         tc.for_each_boundary_point(visitor);
0169         return visitor.result();
0170     }
0171 };
0172 
0173 // SingleGeometry - Linear or Areal
0174 template <typename MultiPoint, typename SingleGeometry, bool Transpose = false>
0175 struct multi_point_single_geometry
0176 {
0177     static const bool interruption_enabled = true;
0178 
0179     template <typename Result, typename Strategy>
0180     static inline void apply(MultiPoint const& multi_point,
0181                              SingleGeometry const& single_geometry,
0182                              Result & result,
0183                              Strategy const& strategy)
0184     {
0185         using box2_type = model::box<point_type_t<SingleGeometry>> ;
0186 
0187         box2_type box2;
0188         geometry::envelope(single_geometry, box2, strategy);
0189         geometry::detail::expand_by_epsilon(box2);
0190 
0191         for (auto it = boost::begin(multi_point); it != boost::end(multi_point); ++it)
0192         {
0193             if (! (relate::may_update<interior, interior, '0', Transpose>(result)
0194                 || relate::may_update<interior, boundary, '0', Transpose>(result)
0195                 || relate::may_update<interior, exterior, '0', Transpose>(result) ) )
0196             {
0197                 break;
0198             }
0199 
0200             // The default strategy is enough for Point/Box
0201             if (detail::disjoint::disjoint_point_box(*it, box2, strategy))
0202             {
0203                 update<interior, exterior, '0', Transpose>(result);
0204             }
0205             else
0206             {
0207                 int in_val = detail::within::point_in_geometry(*it, single_geometry, strategy);
0208 
0209                 if (in_val > 0) // within
0210                 {
0211                     update<interior, interior, '0', Transpose>(result);
0212                 }
0213                 else if (in_val == 0)
0214                 {
0215                     update<interior, boundary, '0', Transpose>(result);
0216                 }
0217                 else // in_val < 0 - not within
0218                 {
0219                     update<interior, exterior, '0', Transpose>(result);
0220                 }
0221             }
0222 
0223             if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
0224             {
0225                 return;
0226             }
0227         }
0228 
0229         typedef detail::relate::topology_check<SingleGeometry, Strategy> tc_t;
0230 
0231         if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result)
0232           || relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) )
0233         {
0234             tc_t tc(single_geometry, strategy);
0235 
0236             if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result)
0237               && tc.has_interior() )
0238             {
0239                 // TODO: this is not true if a linestring is degenerated to a point
0240                 // then the interior has topological dimension = 0, not 1
0241                 update<exterior, interior, tc_t::interior, Transpose>(result);
0242             }
0243 
0244             if ( relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result)
0245               && tc.has_boundary() )
0246             {
0247                 if (multi_point_geometry_eb<SingleGeometry>::apply(multi_point, tc))
0248                 {
0249                     update<exterior, boundary, tc_t::boundary, Transpose>(result);
0250                 }
0251             }
0252         }
0253 
0254         update<exterior, exterior, result_dimension<MultiPoint>::value, Transpose>(result);
0255     }
0256 };
0257 
0258 
0259 // MultiGeometry - Linear or Areal
0260 // part of the algorithm calculating II and IB when no IE has to be calculated
0261 // using partition()
0262 template <typename MultiPoint, typename MultiGeometry, bool Transpose>
0263 class multi_point_multi_geometry_ii_ib
0264 {
0265     template <typename Strategy>
0266     struct expand_box_point
0267     {
0268         expand_box_point(Strategy const& strategy)
0269             : m_strategy(strategy)
0270         {}
0271 
0272         template <typename Box, typename Point>
0273         inline void apply(Box& total, Point const& point) const
0274         {
0275             geometry::expand(total, point, m_strategy);
0276         }
0277 
0278     private:
0279         Strategy const& m_strategy;
0280     };
0281 
0282     template <typename Strategy>
0283     struct expand_box_box_pair
0284     {
0285         expand_box_box_pair(Strategy const& strategy)
0286             : m_strategy(strategy)
0287         {}
0288 
0289         template <typename Box, typename BoxPair>
0290         inline void apply(Box& total, BoxPair const& box_pair) const
0291         {
0292             geometry::expand(total, box_pair.first, m_strategy);
0293         }
0294 
0295     private:
0296         Strategy const& m_strategy;
0297     };
0298 
0299     template <typename Strategy>
0300     struct overlaps_box_point
0301     {
0302         overlaps_box_point(Strategy const& strategy)
0303             : m_strategy(strategy)
0304         {}
0305 
0306         template <typename Box, typename Point>
0307         inline bool apply(Box const& box, Point const& point) const
0308         {
0309             // The default strategy is enough for Point/Box
0310             return ! detail::disjoint::disjoint_point_box(point, box,
0311                                                           m_strategy);
0312         }
0313 
0314     private:
0315         Strategy const& m_strategy;
0316     };
0317 
0318     template <typename Strategy>
0319     struct overlaps_box_box_pair
0320     {
0321         overlaps_box_box_pair(Strategy const& strategy)
0322             : m_strategy(strategy)
0323         {}
0324 
0325         template <typename Box, typename BoxPair>
0326         inline bool apply(Box const& box, BoxPair const& box_pair) const
0327         {
0328             // The default strategy is enough for Box/Box
0329             return ! detail::disjoint::disjoint_box_box(box_pair.first, box,
0330                                                         m_strategy);
0331         }
0332 
0333     private:
0334         Strategy const& m_strategy;
0335     };
0336 
0337     template <typename Result, typename Strategy>
0338     class item_visitor_type
0339     {
0340         typedef detail::relate::topology_check<MultiGeometry, Strategy> topology_check_type;
0341 
0342     public:
0343         item_visitor_type(MultiGeometry const& multi_geometry,
0344                           topology_check_type const& tc,
0345                           Result & result,
0346                           Strategy const& strategy)
0347             : m_multi_geometry(multi_geometry)
0348             , m_tc(tc)
0349             , m_result(result)
0350             , m_strategy(strategy)
0351         {}
0352 
0353         template <typename Point, typename BoxPair>
0354         inline bool apply(Point const& point, BoxPair const& box_pair)
0355         {
0356             // The default strategy is enough for Point/Box
0357             if (! detail::disjoint::disjoint_point_box(point, box_pair.first, m_strategy) )
0358             {
0359                 typename boost::range_value<MultiGeometry>::type const&
0360                     single = range::at(m_multi_geometry, box_pair.second);
0361 
0362                 int in_val = detail::within::point_in_geometry(point, single, m_strategy);
0363 
0364                 if (in_val > 0) // within
0365                 {
0366                     update<interior, interior, '0', Transpose>(m_result);
0367                 }
0368                 else if (in_val == 0)
0369                 {
0370                     if (m_tc.check_boundary_point(point))
0371                     {
0372                         update<interior, boundary, '0', Transpose>(m_result);
0373                     }
0374                     else
0375                     {
0376                         update<interior, interior, '0', Transpose>(m_result);
0377                     }
0378                 }
0379             }
0380 
0381             if ( BOOST_GEOMETRY_CONDITION(m_result.interrupt) )
0382             {
0383                 return false;
0384             }
0385 
0386             if (! (relate::may_update<interior, interior, '0', Transpose>(m_result)
0387                 || relate::may_update<interior, boundary, '0', Transpose>(m_result) ) )
0388             {
0389                 return false;
0390             }
0391 
0392             return true;
0393         }
0394 
0395 
0396     private:
0397         MultiGeometry const& m_multi_geometry;
0398         topology_check_type const& m_tc;
0399         Result & m_result;
0400         Strategy const& m_strategy;
0401     };
0402 
0403 public:
0404     using box1_type = model::box<point_type_t<MultiPoint>>;
0405     using box2_type = model::box<point_type_t<MultiGeometry>>;
0406     using box_pair_type = std::pair<box2_type, std::size_t>;
0407 
0408     template <typename Result, typename Strategy>
0409     static inline void apply(MultiPoint const& multi_point,
0410                              MultiGeometry const& multi_geometry,
0411                              std::vector<box_pair_type> const& boxes,
0412                              detail::relate::topology_check
0413                                 <
0414                                     MultiGeometry, Strategy
0415                                 > const& tc,
0416                              Result & result,
0417                              Strategy const& strategy)
0418     {
0419         item_visitor_type<Result, Strategy> visitor(multi_geometry, tc, result, strategy);
0420 
0421         geometry::partition
0422             <
0423                 box1_type
0424             >::apply(multi_point, boxes, visitor,
0425                      expand_box_point<Strategy>(strategy),
0426                      overlaps_box_point<Strategy>(strategy),
0427                      expand_box_box_pair<Strategy>(strategy),
0428                      overlaps_box_box_pair<Strategy>(strategy));
0429     }
0430 
0431 };
0432 
0433 // MultiGeometry - Linear or Areal
0434 // part of the algorithm calculating II, IB and IE
0435 // using rtree
0436 template <typename MultiPoint, typename MultiGeometry, bool Transpose>
0437 struct multi_point_multi_geometry_ii_ib_ie
0438 {
0439     using box1_type = model::box<point_type_t<MultiPoint>>;
0440     using box2_type = model::box<point_type_t<MultiGeometry>>;
0441     using box_pair_type = std::pair<box2_type, std::size_t>;
0442     using boxes_type = std::vector<box_pair_type>;
0443 
0444     template <typename Result, typename Strategy>
0445     static inline void apply(MultiPoint const& multi_point,
0446                              MultiGeometry const& multi_geometry,
0447                              std::vector<box_pair_type> const& boxes,
0448                              detail::relate::topology_check
0449                                 <
0450                                     MultiGeometry, Strategy
0451                                 > const& tc,
0452                              Result & result,
0453                              Strategy const& strategy)
0454     {
0455         typedef index::parameters
0456             <
0457                 index::rstar<4>, Strategy
0458             > index_parameters_type;
0459         index::rtree<box_pair_type, index_parameters_type>
0460             rtree(boxes.begin(), boxes.end(),
0461                   index_parameters_type(index::rstar<4>(), strategy));
0462 
0463         for (auto it = boost::begin(multi_point); it != boost::end(multi_point); ++it)
0464         {
0465             if (! (relate::may_update<interior, interior, '0', Transpose>(result)
0466                 || relate::may_update<interior, boundary, '0', Transpose>(result)
0467                 || relate::may_update<interior, exterior, '0', Transpose>(result) ) )
0468             {
0469                 return;
0470             }
0471 
0472             typename boost::range_value<MultiPoint>::type const& point = *it;
0473 
0474             boxes_type boxes_found;
0475             rtree.query(index::intersects(point), std::back_inserter(boxes_found));
0476 
0477             bool found_ii_or_ib = false;
0478             for (auto const& box_found : boxes_found)
0479             {
0480                 typename boost::range_value<MultiGeometry>::type const&
0481                     single = range::at(multi_geometry, box_found.second);
0482 
0483                 int in_val = detail::within::point_in_geometry(point, single, strategy);
0484 
0485                 if (in_val > 0) // within
0486                 {
0487                     update<interior, interior, '0', Transpose>(result);
0488                     found_ii_or_ib = true;
0489                 }
0490                 else if (in_val == 0) // on boundary of single
0491                 {
0492                     if (tc.check_boundary_point(point))
0493                     {
0494                         update<interior, boundary, '0', Transpose>(result);
0495                     }
0496                     else
0497                     {
0498                         update<interior, interior, '0', Transpose>(result);
0499                     }
0500                     found_ii_or_ib = true;
0501                 }
0502             }
0503 
0504             // neither interior nor boundary found -> exterior
0505             if (found_ii_or_ib == false)
0506             {
0507                 update<interior, exterior, '0', Transpose>(result);
0508             }
0509 
0510             if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
0511             {
0512                 return;
0513             }
0514         }
0515     }
0516 };
0517 
0518 // MultiGeometry - Linear or Areal
0519 template <typename MultiPoint, typename MultiGeometry, bool Transpose = false>
0520 struct multi_point_multi_geometry
0521 {
0522     static const bool interruption_enabled = true;
0523 
0524     template <typename Result, typename Strategy>
0525     static inline void apply(MultiPoint const& multi_point,
0526                              MultiGeometry const& multi_geometry,
0527                              Result & result,
0528                              Strategy const& strategy)
0529     {
0530         using box_pair_type = std::pair<model::box<point_type_t<MultiGeometry>>, std::size_t>;
0531 
0532         std::size_t count2 = boost::size(multi_geometry);
0533         std::vector<box_pair_type> boxes(count2);
0534         for (std::size_t i = 0 ; i < count2 ; ++i)
0535         {
0536             geometry::envelope(range::at(multi_geometry, i), boxes[i].first, strategy);
0537             geometry::detail::expand_by_epsilon(boxes[i].first);
0538             boxes[i].second = i;
0539         }
0540 
0541         typedef detail::relate::topology_check<MultiGeometry, Strategy> tc_t;
0542         tc_t tc(multi_geometry, strategy);
0543 
0544         if ( relate::may_update<interior, interior, '0', Transpose>(result)
0545           || relate::may_update<interior, boundary, '0', Transpose>(result)
0546           || relate::may_update<interior, exterior, '0', Transpose>(result) )
0547         {
0548             // If there is no need to calculate IE, use partition
0549             if (! relate::may_update<interior, exterior, '0', Transpose>(result) )
0550             {
0551                 multi_point_multi_geometry_ii_ib<MultiPoint, MultiGeometry, Transpose>
0552                     ::apply(multi_point, multi_geometry, boxes, tc, result, strategy);
0553             }
0554             else // otherwise use rtree
0555             {
0556                 multi_point_multi_geometry_ii_ib_ie<MultiPoint, MultiGeometry, Transpose>
0557                     ::apply(multi_point, multi_geometry, boxes, tc, result, strategy);
0558             }
0559         }
0560 
0561         if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
0562         {
0563             return;
0564         }
0565 
0566         if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result)
0567           || relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) )
0568         {
0569             if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result)
0570               && tc.has_interior() )
0571             {
0572                 // TODO: this is not true if a linestring is degenerated to a point
0573                 // then the interior has topological dimension = 0, not 1
0574                 update<exterior, interior, tc_t::interior, Transpose>(result);
0575             }
0576 
0577             if ( relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result)
0578               && tc.has_boundary() )
0579             {
0580                 if (multi_point_geometry_eb<MultiGeometry>::apply(multi_point, tc))
0581                 {
0582                     update<exterior, boundary, tc_t::boundary, Transpose>(result);
0583                 }
0584             }
0585         }
0586 
0587         update<exterior, exterior, result_dimension<MultiPoint>::value, Transpose>(result);
0588     }
0589 
0590 };
0591 
0592 
0593 template
0594 <
0595     typename MultiPoint, typename Geometry,
0596     bool Transpose = false,
0597     bool isMulti = util::is_multi<Geometry>::value
0598 >
0599 struct multi_point_geometry
0600     : multi_point_single_geometry<MultiPoint, Geometry, Transpose>
0601 {};
0602 
0603 template <typename MultiPoint, typename Geometry, bool Transpose>
0604 struct multi_point_geometry<MultiPoint, Geometry, Transpose, true>
0605     : multi_point_multi_geometry<MultiPoint, Geometry, Transpose>
0606 {};
0607 
0608 
0609 // transposed result of multi_point_geometry
0610 template <typename Geometry, typename MultiPoint>
0611 struct geometry_multi_point
0612 {
0613     static const bool interruption_enabled = true;
0614 
0615     template <typename Result, typename Strategy>
0616     static inline void apply(Geometry const& geometry, MultiPoint const& multi_point,
0617                              Result & result, Strategy const& strategy)
0618     {
0619         multi_point_geometry<MultiPoint, Geometry, true>::apply(multi_point, geometry, result, strategy);
0620     }
0621 };
0622 
0623 }} // namespace detail::relate
0624 #endif // DOXYGEN_NO_DETAIL
0625 
0626 }} // namespace boost::geometry
0627 
0628 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_MULTI_POINT_GEOMETRY_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!