Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:35:15 

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 = typename tag<Geometry>::type
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         typedef typename point_type<SingleGeometry>::type point2_type;
0186         typedef model::box<point2_type> box2_type;
0187 
0188         box2_type box2;
0189         geometry::envelope(single_geometry, box2, strategy);
0190         geometry::detail::expand_by_epsilon(box2);
0191 
0192         for (auto it = boost::begin(multi_point); it != boost::end(multi_point); ++it)
0193         {
0194             if (! (relate::may_update<interior, interior, '0', Transpose>(result)
0195                 || relate::may_update<interior, boundary, '0', Transpose>(result)
0196                 || relate::may_update<interior, exterior, '0', Transpose>(result) ) )
0197             {
0198                 break;
0199             }
0200 
0201             // The default strategy is enough for Point/Box
0202             if (detail::disjoint::disjoint_point_box(*it, box2, strategy))
0203             {
0204                 update<interior, exterior, '0', Transpose>(result);
0205             }
0206             else
0207             {
0208                 int in_val = detail::within::point_in_geometry(*it, single_geometry, strategy);
0209 
0210                 if (in_val > 0) // within
0211                 {
0212                     update<interior, interior, '0', Transpose>(result);
0213                 }
0214                 else if (in_val == 0)
0215                 {
0216                     update<interior, boundary, '0', Transpose>(result);
0217                 }
0218                 else // in_val < 0 - not within
0219                 {
0220                     update<interior, exterior, '0', Transpose>(result);
0221                 }
0222             }
0223 
0224             if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
0225             {
0226                 return;
0227             }
0228         }
0229 
0230         typedef detail::relate::topology_check<SingleGeometry, Strategy> tc_t;
0231 
0232         if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result)
0233           || relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) )
0234         {
0235             tc_t tc(single_geometry, strategy);
0236 
0237             if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result)
0238               && tc.has_interior() )
0239             {
0240                 // TODO: this is not true if a linestring is degenerated to a point
0241                 // then the interior has topological dimension = 0, not 1
0242                 update<exterior, interior, tc_t::interior, Transpose>(result);
0243             }
0244 
0245             if ( relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result)
0246               && tc.has_boundary() )
0247             {
0248                 if (multi_point_geometry_eb<SingleGeometry>::apply(multi_point, tc))
0249                 {
0250                     update<exterior, boundary, tc_t::boundary, Transpose>(result);
0251                 }
0252             }
0253         }
0254 
0255         update<exterior, exterior, result_dimension<MultiPoint>::value, Transpose>(result);
0256     }
0257 };
0258 
0259 
0260 // MultiGeometry - Linear or Areal
0261 // part of the algorithm calculating II and IB when no IE has to be calculated
0262 // using partition()
0263 template <typename MultiPoint, typename MultiGeometry, bool Transpose>
0264 class multi_point_multi_geometry_ii_ib
0265 {
0266     template <typename Strategy>
0267     struct expand_box_point
0268     {
0269         expand_box_point(Strategy const& strategy)
0270             : m_strategy(strategy)
0271         {}
0272 
0273         template <typename Box, typename Point>
0274         inline void apply(Box& total, Point const& point) const
0275         {
0276             geometry::expand(total, point, m_strategy);
0277         }
0278 
0279     private:
0280         Strategy const& m_strategy;
0281     };
0282 
0283     template <typename Strategy>
0284     struct expand_box_box_pair
0285     {
0286         expand_box_box_pair(Strategy const& strategy)
0287             : m_strategy(strategy)
0288         {}
0289 
0290         template <typename Box, typename BoxPair>
0291         inline void apply(Box& total, BoxPair const& box_pair) const
0292         {
0293             geometry::expand(total, box_pair.first, m_strategy);
0294         }
0295 
0296     private:
0297         Strategy const& m_strategy;
0298     };
0299 
0300     template <typename Strategy>
0301     struct overlaps_box_point
0302     {
0303         overlaps_box_point(Strategy const& strategy)
0304             : m_strategy(strategy)
0305         {}
0306 
0307         template <typename Box, typename Point>
0308         inline bool apply(Box const& box, Point const& point) const
0309         {
0310             // The default strategy is enough for Point/Box
0311             return ! detail::disjoint::disjoint_point_box(point, box,
0312                                                           m_strategy);
0313         }
0314 
0315     private:
0316         Strategy const& m_strategy;
0317     };
0318 
0319     template <typename Strategy>
0320     struct overlaps_box_box_pair
0321     {
0322         overlaps_box_box_pair(Strategy const& strategy)
0323             : m_strategy(strategy)
0324         {}
0325 
0326         template <typename Box, typename BoxPair>
0327         inline bool apply(Box const& box, BoxPair const& box_pair) const
0328         {
0329             // The default strategy is enough for Box/Box
0330             return ! detail::disjoint::disjoint_box_box(box_pair.first, box,
0331                                                         m_strategy);
0332         }
0333 
0334     private:
0335         Strategy const& m_strategy;
0336     };
0337 
0338     template <typename Result, typename Strategy>
0339     class item_visitor_type
0340     {
0341         typedef detail::relate::topology_check<MultiGeometry, Strategy> topology_check_type;
0342 
0343     public:
0344         item_visitor_type(MultiGeometry const& multi_geometry,
0345                           topology_check_type const& tc,
0346                           Result & result,
0347                           Strategy const& strategy)
0348             : m_multi_geometry(multi_geometry)
0349             , m_tc(tc)
0350             , m_result(result)
0351             , m_strategy(strategy)
0352         {}
0353 
0354         template <typename Point, typename BoxPair>
0355         inline bool apply(Point const& point, BoxPair const& box_pair)
0356         {
0357             // The default strategy is enough for Point/Box
0358             if (! detail::disjoint::disjoint_point_box(point, box_pair.first, m_strategy) )
0359             {
0360                 typename boost::range_value<MultiGeometry>::type const&
0361                     single = range::at(m_multi_geometry, box_pair.second);
0362 
0363                 int in_val = detail::within::point_in_geometry(point, single, m_strategy);
0364 
0365                 if (in_val > 0) // within
0366                 {
0367                     update<interior, interior, '0', Transpose>(m_result);
0368                 }
0369                 else if (in_val == 0)
0370                 {
0371                     if (m_tc.check_boundary_point(point))
0372                     {
0373                         update<interior, boundary, '0', Transpose>(m_result);
0374                     }
0375                     else
0376                     {
0377                         update<interior, interior, '0', Transpose>(m_result);
0378                     }
0379                 }
0380             }
0381 
0382             if ( BOOST_GEOMETRY_CONDITION(m_result.interrupt) )
0383             {
0384                 return false;
0385             }
0386 
0387             if (! (relate::may_update<interior, interior, '0', Transpose>(m_result)
0388                 || relate::may_update<interior, boundary, '0', Transpose>(m_result) ) )
0389             {
0390                 return false;
0391             }
0392 
0393             return true;
0394         }
0395 
0396 
0397     private:
0398         MultiGeometry const& m_multi_geometry;
0399         topology_check_type const& m_tc;
0400         Result & m_result;
0401         Strategy const& m_strategy;
0402     };
0403 
0404 public:
0405     typedef typename point_type<MultiPoint>::type point1_type;
0406     typedef typename point_type<MultiGeometry>::type point2_type;
0407     typedef model::box<point1_type> box1_type;
0408     typedef model::box<point2_type> box2_type;
0409     typedef std::pair<box2_type, std::size_t> box_pair_type;
0410 
0411     template <typename Result, typename Strategy>
0412     static inline void apply(MultiPoint const& multi_point,
0413                              MultiGeometry const& multi_geometry,
0414                              std::vector<box_pair_type> const& boxes,
0415                              detail::relate::topology_check
0416                                 <
0417                                     MultiGeometry, Strategy
0418                                 > const& tc,
0419                              Result & result,
0420                              Strategy const& strategy)
0421     {
0422         item_visitor_type<Result, Strategy> visitor(multi_geometry, tc, result, strategy);
0423 
0424         geometry::partition
0425             <
0426                 box1_type
0427             >::apply(multi_point, boxes, visitor,
0428                      expand_box_point<Strategy>(strategy),
0429                      overlaps_box_point<Strategy>(strategy),
0430                      expand_box_box_pair<Strategy>(strategy),
0431                      overlaps_box_box_pair<Strategy>(strategy));
0432     }
0433 
0434 };
0435 
0436 // MultiGeometry - Linear or Areal
0437 // part of the algorithm calculating II, IB and IE
0438 // using rtree
0439 template <typename MultiPoint, typename MultiGeometry, bool Transpose>
0440 struct multi_point_multi_geometry_ii_ib_ie
0441 {
0442     typedef typename point_type<MultiPoint>::type point1_type;
0443     typedef typename point_type<MultiGeometry>::type point2_type;
0444     typedef model::box<point1_type> box1_type;
0445     typedef model::box<point2_type> box2_type;
0446     typedef std::pair<box2_type, std::size_t> box_pair_type;
0447     typedef std::vector<box_pair_type> boxes_type;
0448 
0449     template <typename Result, typename Strategy>
0450     static inline void apply(MultiPoint const& multi_point,
0451                              MultiGeometry const& multi_geometry,
0452                              std::vector<box_pair_type> const& boxes,
0453                              detail::relate::topology_check
0454                                 <
0455                                     MultiGeometry, Strategy
0456                                 > const& tc,
0457                              Result & result,
0458                              Strategy const& strategy)
0459     {
0460         typedef index::parameters
0461             <
0462                 index::rstar<4>, Strategy
0463             > index_parameters_type;
0464         index::rtree<box_pair_type, index_parameters_type>
0465             rtree(boxes.begin(), boxes.end(),
0466                   index_parameters_type(index::rstar<4>(), strategy));
0467 
0468         for (auto it = boost::begin(multi_point); it != boost::end(multi_point); ++it)
0469         {
0470             if (! (relate::may_update<interior, interior, '0', Transpose>(result)
0471                 || relate::may_update<interior, boundary, '0', Transpose>(result)
0472                 || relate::may_update<interior, exterior, '0', Transpose>(result) ) )
0473             {
0474                 return;
0475             }
0476 
0477             typename boost::range_value<MultiPoint>::type const& point = *it;
0478 
0479             boxes_type boxes_found;
0480             rtree.query(index::intersects(point), std::back_inserter(boxes_found));
0481 
0482             bool found_ii_or_ib = false;
0483             for (auto const& box_found : boxes_found)
0484             {
0485                 typename boost::range_value<MultiGeometry>::type const&
0486                     single = range::at(multi_geometry, box_found.second);
0487 
0488                 int in_val = detail::within::point_in_geometry(point, single, strategy);
0489 
0490                 if (in_val > 0) // within
0491                 {
0492                     update<interior, interior, '0', Transpose>(result);
0493                     found_ii_or_ib = true;
0494                 }
0495                 else if (in_val == 0) // on boundary of single
0496                 {
0497                     if (tc.check_boundary_point(point))
0498                     {
0499                         update<interior, boundary, '0', Transpose>(result);
0500                     }
0501                     else
0502                     {
0503                         update<interior, interior, '0', Transpose>(result);
0504                     }
0505                     found_ii_or_ib = true;
0506                 }
0507             }
0508 
0509             // neither interior nor boundary found -> exterior
0510             if (found_ii_or_ib == false)
0511             {
0512                 update<interior, exterior, '0', Transpose>(result);
0513             }
0514 
0515             if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
0516             {
0517                 return;
0518             }
0519         }
0520     }
0521 };
0522 
0523 // MultiGeometry - Linear or Areal
0524 template <typename MultiPoint, typename MultiGeometry, bool Transpose = false>
0525 struct multi_point_multi_geometry
0526 {
0527     static const bool interruption_enabled = true;
0528 
0529     template <typename Result, typename Strategy>
0530     static inline void apply(MultiPoint const& multi_point,
0531                              MultiGeometry const& multi_geometry,
0532                              Result & result,
0533                              Strategy const& strategy)
0534     {
0535         typedef typename point_type<MultiGeometry>::type point2_type;
0536         typedef model::box<point2_type> box2_type;
0537         typedef std::pair<box2_type, std::size_t> box_pair_type;
0538 
0539         std::size_t count2 = boost::size(multi_geometry);
0540         std::vector<box_pair_type> boxes(count2);
0541         for (std::size_t i = 0 ; i < count2 ; ++i)
0542         {
0543             geometry::envelope(range::at(multi_geometry, i), boxes[i].first, strategy);
0544             geometry::detail::expand_by_epsilon(boxes[i].first);
0545             boxes[i].second = i;
0546         }
0547 
0548         typedef detail::relate::topology_check<MultiGeometry, Strategy> tc_t;
0549         tc_t tc(multi_geometry, strategy);
0550 
0551         if ( relate::may_update<interior, interior, '0', Transpose>(result)
0552           || relate::may_update<interior, boundary, '0', Transpose>(result)
0553           || relate::may_update<interior, exterior, '0', Transpose>(result) )
0554         {
0555             // If there is no need to calculate IE, use partition
0556             if (! relate::may_update<interior, exterior, '0', Transpose>(result) )
0557             {
0558                 multi_point_multi_geometry_ii_ib<MultiPoint, MultiGeometry, Transpose>
0559                     ::apply(multi_point, multi_geometry, boxes, tc, result, strategy);
0560             }
0561             else // otherwise use rtree
0562             {
0563                 multi_point_multi_geometry_ii_ib_ie<MultiPoint, MultiGeometry, Transpose>
0564                     ::apply(multi_point, multi_geometry, boxes, tc, result, strategy);
0565             }
0566         }
0567 
0568         if ( BOOST_GEOMETRY_CONDITION(result.interrupt) )
0569         {
0570             return;
0571         }
0572 
0573         if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result)
0574           || relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) )
0575         {
0576             if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result)
0577               && tc.has_interior() )
0578             {
0579                 // TODO: this is not true if a linestring is degenerated to a point
0580                 // then the interior has topological dimension = 0, not 1
0581                 update<exterior, interior, tc_t::interior, Transpose>(result);
0582             }
0583 
0584             if ( relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result)
0585               && tc.has_boundary() )
0586             {
0587                 if (multi_point_geometry_eb<MultiGeometry>::apply(multi_point, tc))
0588                 {
0589                     update<exterior, boundary, tc_t::boundary, Transpose>(result);
0590                 }
0591             }
0592         }
0593 
0594         update<exterior, exterior, result_dimension<MultiPoint>::value, Transpose>(result);
0595     }
0596 
0597 };
0598 
0599 
0600 template
0601 <
0602     typename MultiPoint, typename Geometry,
0603     bool Transpose = false,
0604     bool isMulti = util::is_multi<Geometry>::value
0605 >
0606 struct multi_point_geometry
0607     : multi_point_single_geometry<MultiPoint, Geometry, Transpose>
0608 {};
0609 
0610 template <typename MultiPoint, typename Geometry, bool Transpose>
0611 struct multi_point_geometry<MultiPoint, Geometry, Transpose, true>
0612     : multi_point_multi_geometry<MultiPoint, Geometry, Transpose>
0613 {};
0614 
0615 
0616 // transposed result of multi_point_geometry
0617 template <typename Geometry, typename MultiPoint>
0618 struct geometry_multi_point
0619 {
0620     static const bool interruption_enabled = true;
0621 
0622     template <typename Result, typename Strategy>
0623     static inline void apply(Geometry const& geometry, MultiPoint const& multi_point,
0624                              Result & result, Strategy const& strategy)
0625     {
0626         multi_point_geometry<MultiPoint, Geometry, true>::apply(multi_point, geometry, result, strategy);
0627     }
0628 };
0629 
0630 }} // namespace detail::relate
0631 #endif // DOXYGEN_NO_DETAIL
0632 
0633 }} // namespace boost::geometry
0634 
0635 #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!