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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // This file was modified by Oracle on 2013, 2014, 2017.
   6 // Modifications copyright (c) 2013-2017, Oracle and/or its affiliates.
   7
   8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   9
  10 // Use, modification and distribution is subject to the Boost Software License,
  11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  12 // http://www.boost.org/LICENSE_1_0.txt)
  13
  14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_POINT_POINT_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_POINT_POINT_HPP
  16
  17 #include <algorithm>
  18 #include <vector>
  19
  20 #include <boost/range/empty.hpp>
  21
  22 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
  23 #include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp>
  24 #include <boost/geometry/algorithms/detail/relate/result.hpp>
  25
  26 #include <boost/geometry/policies/compare.hpp>
  27
  28 namespace boost { namespace geometry
  29 {
  30
  31 #ifndef DOXYGEN_NO_DETAIL
  32 namespace detail { namespace relate {
  33
  34 template <typename Point1, typename Point2>
  35 struct point_point
  36 {
  37     static const bool interruption_enabled = false;
  38
  39     template <typename Result, typename Strategy>
  40     static inline void apply(Point1 const& point1, Point2 const& point2,
  41                              Result & result,
  42                              Strategy const& /*strategy*/)
  43     {
  44         bool equal = detail::equals::equals_point_point(point1, point2);
  45         if ( equal )
  46         {
  47             relate::set<interior, interior, '0'>(result);
  48         }
  49         else
  50         {
  51             relate::set<interior, exterior, '0'>(result);
  52             relate::set<exterior, interior, '0'>(result);
  53         }
  54
  55         relate::set<exterior, exterior, result_dimension<Point1>::value>(result);
  56     }
  57 };
  58
  59 template <typename Point, typename MultiPoint>
  60 std::pair<bool, bool> point_multipoint_check(Point const& point, MultiPoint const& multi_point)
  61 {
  62     bool found_inside = false;
  63     bool found_outside = false;
  64
  65     // point_in_geometry could be used here but why iterate over MultiPoint twice?
  66     // we must search for a point in the exterior because all points in MultiPoint can be equal
  67
  68     typedef typename boost::range_iterator<MultiPoint const>::type iterator;
  69     iterator it = boost::begin(multi_point);
  70     iterator last = boost::end(multi_point);
  71     for ( ; it != last ; ++it )
  72     {
  73         bool ii = detail::equals::equals_point_point(point, *it);
  74
  75         if ( ii )
  76             found_inside = true;
  77         else
  78             found_outside = true;
  79
  80         if ( found_inside && found_outside )
  81             break;
  82     }
  83
  84     return std::make_pair(found_inside, found_outside);
  85 }
  86
  87 template <typename Point, typename MultiPoint, bool Transpose = false>
  88 struct point_multipoint
  89 {
  90     static const bool interruption_enabled = false;
  91
  92     template <typename Result, typename Strategy>
  93     static inline void apply(Point const& point, MultiPoint const& multi_point,
  94                              Result & result,
  95                              Strategy const& /*strategy*/)
  96     {
  97         if ( boost::empty(multi_point) )
  98         {
  99             // TODO: throw on empty input?
 100             relate::set<interior, exterior, '0', Transpose>(result);
 101             return;
 102         }
 103
 104         std::pair<bool, bool> rel = point_multipoint_check(point, multi_point);
 105
 106         if ( rel.first ) // some point of MP is equal to P
 107         {
 108             relate::set<interior, interior, '0', Transpose>(result);
 109
 110             if ( rel.second ) // a point of MP was found outside P
 111             {
 112                 relate::set<exterior, interior, '0', Transpose>(result);
 113             }
 114         }
 115         else
 116         {
 117             relate::set<interior, exterior, '0', Transpose>(result);
 118             relate::set<exterior, interior, '0', Transpose>(result);
 119         }
 120
 121         relate::set<exterior, exterior, result_dimension<Point>::value, Transpose>(result);
 122     }
 123 };
 124
 125 template <typename MultiPoint, typename Point>
 126 struct multipoint_point
 127 {
 128     static const bool interruption_enabled = false;
 129
 130     template <typename Result, typename Strategy>
 131     static inline void apply(MultiPoint const& multi_point, Point const& point,
 132                              Result & result,
 133                              Strategy const& strategy)
 134     {
 135         point_multipoint<Point, MultiPoint, true>::apply(point, multi_point, result, strategy);
 136     }
 137 };
 138
 139 template <typename MultiPoint1, typename MultiPoint2>
 140 struct multipoint_multipoint
 141 {
 142     static const bool interruption_enabled = true;
 143
 144     template <typename Result, typename Strategy>
 145     static inline void apply(MultiPoint1 const& multi_point1, MultiPoint2 const& multi_point2,
 146                              Result & result,
 147                              Strategy const& /*strategy*/)
 148     {
 149         {
 150             // TODO: throw on empty input?
 151             bool empty1 = boost::empty(multi_point1);
 152             bool empty2 = boost::empty(multi_point2);
 153             if ( empty1 && empty2 )
 154             {
 155                 return;
 156             }
 157             else if ( empty1 )
 158             {
 159                 relate::set<exterior, interior, '0'>(result);
 160                 return;
 161             }
 162             else if ( empty2 )
 163             {
 164                 relate::set<interior, exterior, '0'>(result);
 165                 return;
 166             }
 167         }
 168
 169         // The geometry containing smaller number of points will be analysed first
 170         if ( boost::size(multi_point1) < boost::size(multi_point2) )
 171         {
 172             search_both<false>(multi_point1, multi_point2, result);
 173         }
 174         else
 175         {
 176             search_both<true>(multi_point2, multi_point1, result);
 177         }
 178
 179         relate::set<exterior, exterior, result_dimension<MultiPoint1>::value>(result);
 180     }
 181
 182     template <bool Transpose, typename MPt1, typename MPt2, typename Result>
 183     static inline void search_both(MPt1 const& first_sorted_mpt, MPt2 const& first_iterated_mpt,
 184                                    Result & result)
 185     {
 186         if ( relate::may_update<interior, interior, '0'>(result)
 187           || relate::may_update<interior, exterior, '0'>(result)
 188           || relate::may_update<exterior, interior, '0'>(result) )
 189         {
 190             // NlogN + MlogN
 191             bool is_disjoint = search<Transpose>(first_sorted_mpt, first_iterated_mpt, result);
 192
 193             if ( BOOST_GEOMETRY_CONDITION(is_disjoint || result.interrupt) )
 194                 return;
 195         }
 196
 197         if ( relate::may_update<interior, interior, '0'>(result)
 198           || relate::may_update<interior, exterior, '0'>(result)
 199           || relate::may_update<exterior, interior, '0'>(result) )
 200         {
 201             // MlogM + NlogM
 202             search<! Transpose>(first_iterated_mpt, first_sorted_mpt, result);
 203         }
 204     }
 205
 206     template <bool Transpose,
 207               typename SortedMultiPoint,
 208               typename IteratedMultiPoint,
 209               typename Result>
 210     static inline bool search(SortedMultiPoint const& sorted_mpt,
 211                               IteratedMultiPoint const& iterated_mpt,
 212                               Result & result)
 213     {
 214         // sort points from the 1 MPt
 215         typedef typename geometry::point_type<SortedMultiPoint>::type point_type;
 216         std::vector<point_type> points(boost::begin(sorted_mpt), boost::end(sorted_mpt));
 217
 218         geometry::less<> const less = geometry::less<>();
 219         std::sort(points.begin(), points.end(), less);
 220
 221         bool found_inside = false;
 222         bool found_outside = false;
 223
 224         // for each point in the second MPt
 225         typedef typename boost::range_iterator<IteratedMultiPoint const>::type iterator;
 226         for ( iterator it = boost::begin(iterated_mpt) ;
 227               it != boost::end(iterated_mpt) ; ++it )
 228         {
 229             bool ii =
 230                 std::binary_search(points.begin(), points.end(), *it, less);
 231             if ( ii )
 232                 found_inside = true;
 233             else
 234                 found_outside = true;
 235
 236             if ( found_inside && found_outside )
 237                 break;
 238         }
 239
 240         if ( found_inside ) // some point of MP2 is equal to some of MP1
 241         {
 242 // TODO: if I/I is set for one MPt, this won't be changed when the other one in analysed
 243 //       so if e.g. only I/I must be analysed we musn't check the other MPt
 244
 245             relate::set<interior, interior, '0', Transpose>(result);
 246
 247             if ( found_outside ) // some point of MP2 was found outside of MP1
 248             {
 249                 relate::set<exterior, interior, '0', Transpose>(result);
 250             }
 251         }
 252         else
 253         {
 254             relate::set<interior, exterior, '0', Transpose>(result);
 255             relate::set<exterior, interior, '0', Transpose>(result);
 256         }
 257
 258         // if no point is intersecting the other MPt then we musn't analyse the reversed case
 259         return ! found_inside;
 260     }
 261 };
 262
 263 }} // namespace detail::relate
 264 #endif // DOXYGEN_NO_DETAIL
 265
 266 }} // namespace boost::geometry
 267
 268 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_POINT_POINT_HPP