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, 2018.
   6 // Modifications copyright (c) 2013-2018, 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, strategy);
  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, typename EqPPStrategy>
  60 std::pair<bool, bool> point_multipoint_check(Point const& point,
  61                                              MultiPoint const& multi_point,
  62                                              EqPPStrategy const& strategy)
  63 {
  64     bool found_inside = false;
  65     bool found_outside = false;
  66
  67     // point_in_geometry could be used here but why iterate over MultiPoint twice?
  68     // we must search for a point in the exterior because all points in MultiPoint can be equal
  69
  70     typedef typename boost::range_iterator<MultiPoint const>::type iterator;
  71     iterator it = boost::begin(multi_point);
  72     iterator last = boost::end(multi_point);
  73     for ( ; it != last ; ++it )
  74     {
  75         bool ii = detail::equals::equals_point_point(point, *it, strategy);
  76
  77         if ( ii )
  78             found_inside = true;
  79         else
  80             found_outside = true;
  81
  82         if ( found_inside && found_outside )
  83             break;
  84     }
  85
  86     return std::make_pair(found_inside, found_outside);
  87 }
  88
  89 template <typename Point, typename MultiPoint, bool Transpose = false>
  90 struct point_multipoint
  91 {
  92     static const bool interruption_enabled = false;
  93
  94     template <typename Result, typename Strategy>
  95     static inline void apply(Point const& point, MultiPoint const& multi_point,
  96                              Result & result,
  97                              Strategy const& strategy)
  98     {
  99         if ( boost::empty(multi_point) )
 100         {
 101             // TODO: throw on empty input?
 102             relate::set<interior, exterior, '0', Transpose>(result);
 103             return;
 104         }
 105
 106         std::pair<bool, bool> rel = point_multipoint_check(point, multi_point, strategy);
 107
 108         if ( rel.first ) // some point of MP is equal to P
 109         {
 110             relate::set<interior, interior, '0', Transpose>(result);
 111
 112             if ( rel.second ) // a point of MP was found outside P
 113             {
 114                 relate::set<exterior, interior, '0', Transpose>(result);
 115             }
 116         }
 117         else
 118         {
 119             relate::set<interior, exterior, '0', Transpose>(result);
 120             relate::set<exterior, interior, '0', Transpose>(result);
 121         }
 122
 123         relate::set<exterior, exterior, result_dimension<Point>::value, Transpose>(result);
 124     }
 125 };
 126
 127 template <typename MultiPoint, typename Point>
 128 struct multipoint_point
 129 {
 130     static const bool interruption_enabled = false;
 131
 132     template <typename Result, typename Strategy>
 133     static inline void apply(MultiPoint const& multi_point, Point const& point,
 134                              Result & result,
 135                              Strategy const& strategy)
 136     {
 137         point_multipoint<Point, MultiPoint, true>::apply(point, multi_point, result, strategy);
 138     }
 139 };
 140
 141 template <typename MultiPoint1, typename MultiPoint2>
 142 struct multipoint_multipoint
 143 {
 144     static const bool interruption_enabled = true;
 145
 146     template <typename Result, typename Strategy>
 147     static inline void apply(MultiPoint1 const& multi_point1, MultiPoint2 const& multi_point2,
 148                              Result & result,
 149                              Strategy const& /*strategy*/)
 150     {
 151         typedef typename Strategy::cs_tag cs_tag;
 152
 153         {
 154             // TODO: throw on empty input?
 155             bool empty1 = boost::empty(multi_point1);
 156             bool empty2 = boost::empty(multi_point2);
 157             if ( empty1 && empty2 )
 158             {
 159                 return;
 160             }
 161             else if ( empty1 )
 162             {
 163                 relate::set<exterior, interior, '0'>(result);
 164                 return;
 165             }
 166             else if ( empty2 )
 167             {
 168                 relate::set<interior, exterior, '0'>(result);
 169                 return;
 170             }
 171         }
 172
 173         // The geometry containing smaller number of points will be analysed first
 174         if ( boost::size(multi_point1) < boost::size(multi_point2) )
 175         {
 176             search_both<false, cs_tag>(multi_point1, multi_point2, result);
 177         }
 178         else
 179         {
 180             search_both<true, cs_tag>(multi_point2, multi_point1, result);
 181         }
 182
 183         relate::set<exterior, exterior, result_dimension<MultiPoint1>::value>(result);
 184     }
 185
 186     template <bool Transpose, typename CSTag, typename MPt1, typename MPt2, typename Result>
 187     static inline void search_both(MPt1 const& first_sorted_mpt, MPt2 const& first_iterated_mpt,
 188                                    Result & result)
 189     {
 190         if ( relate::may_update<interior, interior, '0'>(result)
 191           || relate::may_update<interior, exterior, '0'>(result)
 192           || relate::may_update<exterior, interior, '0'>(result) )
 193         {
 194             // NlogN + MlogN
 195             bool is_disjoint = search<Transpose, CSTag>(first_sorted_mpt, first_iterated_mpt, result);
 196
 197             if ( BOOST_GEOMETRY_CONDITION(is_disjoint || result.interrupt) )
 198                 return;
 199         }
 200
 201         if ( relate::may_update<interior, interior, '0'>(result)
 202           || relate::may_update<interior, exterior, '0'>(result)
 203           || relate::may_update<exterior, interior, '0'>(result) )
 204         {
 205             // MlogM + NlogM
 206             search<! Transpose, CSTag>(first_iterated_mpt, first_sorted_mpt, result);
 207         }
 208     }
 209
 210     template <bool Transpose,
 211               typename CSTag,
 212               typename SortedMultiPoint,
 213               typename IteratedMultiPoint,
 214               typename Result>
 215     static inline bool search(SortedMultiPoint const& sorted_mpt,
 216                               IteratedMultiPoint const& iterated_mpt,
 217                               Result & result)
 218     {
 219         // sort points from the 1 MPt
 220         typedef typename geometry::point_type<SortedMultiPoint>::type point_type;
 221         typedef geometry::less<void, -1, CSTag> less_type;
 222
 223         std::vector<point_type> points(boost::begin(sorted_mpt), boost::end(sorted_mpt));
 224
 225         less_type const less = less_type();
 226         std::sort(points.begin(), points.end(), less);
 227
 228         bool found_inside = false;
 229         bool found_outside = false;
 230
 231         // for each point in the second MPt
 232         typedef typename boost::range_iterator<IteratedMultiPoint const>::type iterator;
 233         for ( iterator it = boost::begin(iterated_mpt) ;
 234               it != boost::end(iterated_mpt) ; ++it )
 235         {
 236             bool ii =
 237                 std::binary_search(points.begin(), points.end(), *it, less);
 238             if ( ii )
 239                 found_inside = true;
 240             else
 241                 found_outside = true;
 242
 243             if ( found_inside && found_outside )
 244                 break;
 245         }
 246
 247         if ( found_inside ) // some point of MP2 is equal to some of MP1
 248         {
 249 // TODO: if I/I is set for one MPt, this won't be changed when the other one in analysed
 250 //       so if e.g. only I/I must be analysed we musn't check the other MPt
 251
 252             relate::set<interior, interior, '0', Transpose>(result);
 253
 254             if ( found_outside ) // some point of MP2 was found outside of MP1
 255             {
 256                 relate::set<exterior, interior, '0', Transpose>(result);
 257             }
 258         }
 259         else
 260         {
 261             relate::set<interior, exterior, '0', Transpose>(result);
 262             relate::set<exterior, interior, '0', Transpose>(result);
 263         }
 264
 265         // if no point is intersecting the other MPt then we musn't analyse the reversed case
 266         return ! found_inside;
 267     }
 268 };
 269
 270 }} // namespace detail::relate
 271 #endif // DOXYGEN_NO_DETAIL
 272
 273 }} // namespace boost::geometry
 274
 275 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_POINT_POINT_HPP