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 // Copyright (c) 2023-2024 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2013-2022.
0007 // Modifications copyright (c) 2013-2023, Oracle and/or its affiliates.
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 const is_disjoint = search<Transpose, Strategy>(first_sorted_mpt, first_iterated_mpt, result);
0201
0202             if (is_disjoint || BOOST_GEOMETRY_CONDITION(result.interrupt) )
0203             {
0204                 return;
0205             }
0206         }
0207
0208         if ( relate::may_update<interior, interior, '0'>(result)
0209           || relate::may_update<interior, exterior, '0'>(result)
0210           || relate::may_update<exterior, interior, '0'>(result) )
0211         {
0212             // MlogM + NlogM
0213             search<! Transpose, Strategy>(first_iterated_mpt, first_sorted_mpt, result);
0214         }
0215     }
0216
0217     template <bool Transpose,
0218               typename Strategy,
0219               typename SortedMultiPoint,
0220               typename IteratedMultiPoint,
0221               typename Result>
0222     static inline bool search(SortedMultiPoint const& sorted_mpt,
0223                               IteratedMultiPoint const& iterated_mpt,
0224                               Result & result)
0225     {
0226         // sort points from the 1 MPt
0227         typedef typename geometry::point_type<SortedMultiPoint>::type point_type;
0228         typedef geometry::less<void, -1, Strategy> less_type;
0229
0230         std::vector<point_type> points(boost::begin(sorted_mpt), boost::end(sorted_mpt));
0231
0232         less_type const less = less_type();
0233         std::sort(points.begin(), points.end(), less);
0234
0235         bool found_inside = false;
0236         bool found_outside = false;
0237
0238         // for each point in the second MPt
0239         for (auto it = boost::begin(iterated_mpt); it != boost::end(iterated_mpt); ++it)
0240         {
0241             bool ii = std::binary_search(points.begin(), points.end(), *it, less);
0242             if (ii)
0243             {
0244                 found_inside = true;
0245             }
0246             else
0247             {
0248                 found_outside = true;
0249             }
0250
0251             if (found_inside && found_outside)
0252             {
0253                 break;
0254             }
0255         }
0256
0257         if ( found_inside ) // some point of MP2 is equal to some of MP1
0258         {
0259 // TODO: if I/I is set for one MPt, this won't be changed when the other one in analysed
0260 //       so if e.g. only I/I must be analysed we musn't check the other MPt
0261
0262             update<interior, interior, '0', Transpose>(result);
0263
0264             if ( found_outside ) // some point of MP2 was found outside of MP1
0265             {
0266                 update<exterior, interior, '0', Transpose>(result);
0267             }
0268         }
0269         else
0270         {
0271             update<interior, exterior, '0', Transpose>(result);
0272             update<exterior, interior, '0', Transpose>(result);
0273         }
0274
0275         // if no point is intersecting the other MPt then we musn't analyse the reversed case
0276         return ! found_inside;
0277     }
0278 };
0279
0280 }} // namespace detail::relate
0281 #endif // DOXYGEN_NO_DETAIL
0282
0283 }} // namespace boost::geometry
0284
0285 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_POINT_POINT_HPP