detail/relate/point_point.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // This file was modified by Oracle on 2013-2022.
0006 // Modifications copyright (c) 2013-2023, Oracle and/or its affiliates.
0007
0008 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010
0011 // Use, modification and distribution is subject to the Boost Software License,
0012 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0013 // http://www.boost.org/LICENSE_1_0.txt)
0014
0015 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_POINT_POINT_HPP
0016 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_POINT_POINT_HPP
0017
0018 #include <algorithm>
0019 #include <vector>
0020
0021 #include <boost/range/empty.hpp>
0022 #include <boost/range/size.hpp>
0023
0024 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
0025 #include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp>
0026 #include <boost/geometry/algorithms/detail/relate/result.hpp>
0027
0028 #include <boost/geometry/policies/compare.hpp>
0029
0030 namespace boost { namespace geometry
0031 {
0032
0033 #ifndef DOXYGEN_NO_DETAIL
0034 namespace detail { namespace relate {
0035
0036 template <typename Point1, typename Point2>
0037 struct point_point
0038 {
0039     static const bool interruption_enabled = false;
0040
0041     template <typename Result, typename Strategy>
0042     static inline void apply(Point1 const& point1, Point2 const& point2,
0043                              Result & result,
0044                              Strategy const& strategy)
0045     {
0046         bool equal = detail::equals::equals_point_point(point1, point2, strategy);
0047         if ( equal )
0048         {
0049             update<interior, interior, '0'>(result);
0050         }
0051         else
0052         {
0053             update<interior, exterior, '0'>(result);
0054             update<exterior, interior, '0'>(result);
0055         }
0056
0057         update<exterior, exterior, result_dimension<Point1>::value>(result);
0058     }
0059 };
0060
0061 template <typename Point, typename MultiPoint, typename EqPPStrategy>
0062 std::pair<bool, bool> point_multipoint_check(Point const& point,
0063                                              MultiPoint const& multi_point,
0064                                              EqPPStrategy const& strategy)
0065 {
0066     bool found_inside = false;
0067     bool found_outside = false;
0068
0069     // point_in_geometry could be used here but why iterate over MultiPoint twice?
0070     // we must search for a point in the exterior because all points in MultiPoint can be equal
0071
0072
0073     auto const end = boost::end(multi_point);
0074     for (auto it = boost::begin(multi_point); it != end; ++it)
0075     {
0076         bool ii = detail::equals::equals_point_point(point, *it, strategy);
0077
0078         if (ii)
0079         {
0080             found_inside = true;
0081         }
0082         else
0083         {
0084             found_outside = true;
0085         }
0086
0087         if (found_inside && found_outside)
0088         {
0089             break;
0090         }
0091     }
0092
0093     return std::make_pair(found_inside, found_outside);
0094 }
0095
0096 template <typename Point, typename MultiPoint, bool Transpose = false>
0097 struct point_multipoint
0098 {
0099     static const bool interruption_enabled = false;
0100
0101     template <typename Result, typename Strategy>
0102     static inline void apply(Point const& point, MultiPoint const& multi_point,
0103                              Result & result,
0104                              Strategy const& strategy)
0105     {
0106         if ( boost::empty(multi_point) )
0107         {
0108             // TODO: throw on empty input?
0109             update<interior, exterior, '0', Transpose>(result);
0110             return;
0111         }
0112
0113         std::pair<bool, bool> rel = point_multipoint_check(point, multi_point, strategy);
0114
0115         if ( rel.first ) // some point of MP is equal to P
0116         {
0117             update<interior, interior, '0', Transpose>(result);
0118
0119             if ( rel.second ) // a point of MP was found outside P
0120             {
0121                 update<exterior, interior, '0', Transpose>(result);
0122             }
0123         }
0124         else
0125         {
0126             update<interior, exterior, '0', Transpose>(result);
0127             update<exterior, interior, '0', Transpose>(result);
0128         }
0129
0130         update<exterior, exterior, result_dimension<Point>::value, Transpose>(result);
0131     }
0132 };
0133
0134 template <typename MultiPoint, typename Point>
0135 struct multipoint_point
0136 {
0137     static const bool interruption_enabled = false;
0138
0139     template <typename Result, typename Strategy>
0140     static inline void apply(MultiPoint const& multi_point, Point const& point,
0141                              Result & result,
0142                              Strategy const& strategy)
0143     {
0144         point_multipoint<Point, MultiPoint, true>::apply(point, multi_point, result, strategy);
0145     }
0146 };
0147
0148 template <typename MultiPoint1, typename MultiPoint2>
0149 struct multipoint_multipoint
0150 {
0151     static const bool interruption_enabled = true;
0152
0153     template <typename Result, typename Strategy>
0154     static inline void apply(MultiPoint1 const& multi_point1, MultiPoint2 const& multi_point2,
0155                              Result & result,
0156                              Strategy const& /*strategy*/)
0157     {
0158         {
0159             // TODO: throw on empty input?
0160             bool empty1 = boost::empty(multi_point1);
0161             bool empty2 = boost::empty(multi_point2);
0162             if ( empty1 && empty2 )
0163             {
0164                 return;
0165             }
0166             else if ( empty1 )
0167             {
0168                 update<exterior, interior, '0'>(result);
0169                 return;
0170             }
0171             else if ( empty2 )
0172             {
0173                 update<interior, exterior, '0'>(result);
0174                 return;
0175             }
0176         }
0177
0178         // The geometry containing smaller number of points will be analysed first
0179         if ( boost::size(multi_point1) < boost::size(multi_point2) )
0180         {
0181             search_both<false, Strategy>(multi_point1, multi_point2, result);
0182         }
0183         else
0184         {
0185             search_both<true, Strategy>(multi_point2, multi_point1, result);
0186         }
0187
0188         update<exterior, exterior, result_dimension<MultiPoint1>::value>(result);
0189     }
0190
0191     template <bool Transpose, typename Strategy, typename MPt1, typename MPt2, typename Result>
0192     static inline void search_both(MPt1 const& first_sorted_mpt, MPt2 const& first_iterated_mpt,
0193                                    Result & result)
0194     {
0195         if ( relate::may_update<interior, interior, '0'>(result)
0196           || relate::may_update<interior, exterior, '0'>(result)
0197           || relate::may_update<exterior, interior, '0'>(result) )
0198         {
0199             // NlogN + MlogN
0200             bool is_disjoint = search<Transpose, Strategy>(first_sorted_mpt, first_iterated_mpt, result);
0201
0202             if ( BOOST_GEOMETRY_CONDITION(is_disjoint || result.interrupt) )
0203                 return;
0204         }
0205
0206         if ( relate::may_update<interior, interior, '0'>(result)
0207           || relate::may_update<interior, exterior, '0'>(result)
0208           || relate::may_update<exterior, interior, '0'>(result) )
0209         {
0210             // MlogM + NlogM
0211             search<! Transpose, Strategy>(first_iterated_mpt, first_sorted_mpt, result);
0212         }
0213     }
0214
0215     template <bool Transpose,
0216               typename Strategy,
0217               typename SortedMultiPoint,
0218               typename IteratedMultiPoint,
0219               typename Result>
0220     static inline bool search(SortedMultiPoint const& sorted_mpt,
0221                               IteratedMultiPoint const& iterated_mpt,
0222                               Result & result)
0223     {
0224         // sort points from the 1 MPt
0225         typedef typename geometry::point_type<SortedMultiPoint>::type point_type;
0226         typedef geometry::less<void, -1, Strategy> less_type;
0227
0228         std::vector<point_type> points(boost::begin(sorted_mpt), boost::end(sorted_mpt));
0229
0230         less_type const less = less_type();
0231         std::sort(points.begin(), points.end(), less);
0232
0233         bool found_inside = false;
0234         bool found_outside = false;
0235
0236         // for each point in the second MPt
0237         for (auto it = boost::begin(iterated_mpt); it != boost::end(iterated_mpt); ++it)
0238         {
0239             bool ii = std::binary_search(points.begin(), points.end(), *it, less);
0240             if (ii)
0241             {
0242                 found_inside = true;
0243             }
0244             else
0245             {
0246                 found_outside = true;
0247             }
0248
0249             if (found_inside && found_outside)
0250             {
0251                 break;
0252             }
0253         }
0254
0255         if ( found_inside ) // some point of MP2 is equal to some of MP1
0256         {
0257 // TODO: if I/I is set for one MPt, this won't be changed when the other one in analysed
0258 //       so if e.g. only I/I must be analysed we musn't check the other MPt
0259
0260             update<interior, interior, '0', Transpose>(result);
0261
0262             if ( found_outside ) // some point of MP2 was found outside of MP1
0263             {
0264                 update<exterior, interior, '0', Transpose>(result);
0265             }
0266         }
0267         else
0268         {
0269             update<interior, exterior, '0', Transpose>(result);
0270             update<exterior, interior, '0', Transpose>(result);
0271         }
0272
0273         // if no point is intersecting the other MPt then we musn't analyse the reversed case
0274         return ! found_inside;
0275     }
0276 };
0277
0278 }} // namespace detail::relate
0279 #endif // DOXYGEN_NO_DETAIL
0280
0281 }} // namespace boost::geometry
0282
0283 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_POINT_POINT_HPP