ceph/src/boost/boost/geometry/algorithms/detail/within/multi_point.hpp

   1 // Boost.Geometry
   2
   3 // Copyright (c) 2017, 2019 Oracle and/or its affiliates.
   4
   5 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   6
   7 // Use, modification and distribution is subject to the Boost Software License,
   8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   9 // http://www.boost.org/LICENSE_1_0.txt)
  10
  11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_MULTI_POINT_HPP
  12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_MULTI_POINT_HPP
  13
  14
  15 #include <algorithm>
  16 #include <vector>
  17
  18 #include <boost/range.hpp>
  19 #include <boost/type_traits/is_same.hpp>
  20
  21 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
  22 #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
  23 #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp>
  24 #include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp>
  25 #include <boost/geometry/algorithms/envelope.hpp>
  26 #include <boost/geometry/algorithms/detail/partition.hpp>
  27 #include <boost/geometry/core/tag.hpp>
  28 #include <boost/geometry/core/tag_cast.hpp>
  29 #include <boost/geometry/core/tags.hpp>
  30
  31 #include <boost/geometry/geometries/box.hpp>
  32
  33 #include <boost/geometry/index/rtree.hpp>
  34
  35 #include <boost/geometry/policies/compare.hpp>
  36
  37 #include <boost/geometry/strategies/covered_by.hpp>
  38 #include <boost/geometry/strategies/disjoint.hpp>
  39
  40
  41 namespace boost { namespace geometry {
  42
  43 #ifndef DOXYGEN_NO_DETAIL
  44 namespace detail { namespace within {
  45
  46 struct multi_point_point
  47 {
  48     template <typename MultiPoint, typename Point, typename Strategy>
  49     static inline bool apply(MultiPoint const& multi_point,
  50                              Point const& point,
  51                              Strategy const& strategy)
  52     {
  53         typedef typename boost::range_const_iterator<MultiPoint>::type iterator;
  54         for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it )
  55         {
  56             if (! strategy.apply(*it, point))
  57             {
  58                 return false;
  59             }
  60         }
  61
  62         // all points of MultiPoint inside Point
  63         return true;
  64     }
  65 };
  66
  67 // NOTE: currently the strategy is ignored, math::equals() is used inside geometry::less<>
  68 struct multi_point_multi_point
  69 {
  70     template <typename MultiPoint1, typename MultiPoint2, typename Strategy>
  71     static inline bool apply(MultiPoint1 const& multi_point1,
  72                              MultiPoint2 const& multi_point2,
  73                              Strategy const& /*strategy*/)
  74     {
  75         typedef typename boost::range_value<MultiPoint2>::type point2_type;
  76         typedef typename Strategy::cs_tag cs_tag;
  77         typedef geometry::less<void, -1, cs_tag> less_type;
  78
  79         less_type const less = less_type();
  80
  81         std::vector<point2_type> points2(boost::begin(multi_point2), boost::end(multi_point2));
  82         std::sort(points2.begin(), points2.end(), less);
  83
  84         bool result = false;
  85
  86         typedef typename boost::range_const_iterator<MultiPoint1>::type iterator;
  87         for ( iterator it = boost::begin(multi_point1) ; it != boost::end(multi_point1) ; ++it )
  88         {
  89             if (! std::binary_search(points2.begin(), points2.end(), *it, less))
  90             {
  91                 return false;
  92             }
  93             else
  94             {
  95                 result = true;
  96             }
  97         }
  98
  99         return result;
 100     }
 101 };
 102
 103
 104 // TODO: the complexity could be lesser
 105 //   the second geometry could be "prepared"/sorted
 106 // For Linear geometries partition could be used
 107 // For Areal geometries point_in_geometry() would have to call the winding
 108 //   strategy differently, currently it linearly calls the strategy for each
 109 //   segment. So the segments would have to be sorted in a way consistent with
 110 //   the strategy and then the strategy called only for the segments in range.
 111 template <bool Within>
 112 struct multi_point_single_geometry
 113 {
 114     template <typename MultiPoint, typename LinearOrAreal, typename Strategy>
 115     static inline bool apply(MultiPoint const& multi_point,
 116                              LinearOrAreal const& linear_or_areal,
 117                              Strategy const& strategy)
 118     {
 119         //typedef typename boost::range_value<MultiPoint>::type point1_type;
 120         typedef typename point_type<LinearOrAreal>::type point2_type;
 121         typedef model::box<point2_type> box2_type;
 122
 123         // Create envelope of geometry
 124         box2_type box;
 125         geometry::envelope(linear_or_areal, box, strategy.get_envelope_strategy());
 126         geometry::detail::expand_by_epsilon(box);
 127
 128         typedef typename Strategy::disjoint_point_box_strategy_type point_in_box_type;
 129
 130         // Test each Point with envelope and then geometry if needed
 131         // If in the exterior, break
 132         bool result = false;
 133
 134         typedef typename boost::range_const_iterator<MultiPoint>::type iterator;
 135         for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it )
 136         {
 137             int in_val = 0;
 138
 139             // exterior of box and of geometry
 140             if (! point_in_box_type::apply(*it, box)
 141                 || (in_val = point_in_geometry(*it, linear_or_areal, strategy)) < 0)
 142             {
 143                 result = false;
 144                 break;
 145             }
 146
 147             // interior : interior/boundary
 148             if (Within ? in_val > 0 : in_val >= 0)
 149             {
 150                 result = true;
 151             }
 152         }
 153
 154         return result;
 155     }
 156 };
 157
 158
 159 // TODO: same here, probably the complexity could be lesser
 160 template <bool Within>
 161 struct multi_point_multi_geometry
 162 {
 163     template <typename MultiPoint, typename LinearOrAreal, typename Strategy>
 164     static inline bool apply(MultiPoint const& multi_point,
 165                              LinearOrAreal const& linear_or_areal,
 166                              Strategy const& strategy)
 167     {
 168         typedef typename point_type<LinearOrAreal>::type point2_type;
 169         typedef model::box<point2_type> box2_type;
 170         static const bool is_linear = is_same
 171             <
 172                 typename tag_cast
 173                     <
 174                         typename tag<LinearOrAreal>::type,
 175                         linear_tag
 176                     >::type,
 177                 linear_tag
 178             >::value;
 179
 180         typename Strategy::envelope_strategy_type const
 181             envelope_strategy = strategy.get_envelope_strategy();
 182
 183         // TODO: box pairs could be constructed on the fly, inside the rtree
 184
 185         // Prepare range of envelopes and ids
 186         std::size_t count2 = boost::size(linear_or_areal);
 187         typedef std::pair<box2_type, std::size_t> box_pair_type;
 188         typedef std::vector<box_pair_type> box_pair_vector;
 189         box_pair_vector boxes(count2);
 190         for (std::size_t i = 0 ; i < count2 ; ++i)
 191         {
 192             geometry::envelope(linear_or_areal, boxes[i].first, envelope_strategy);
 193             geometry::detail::expand_by_epsilon(boxes[i].first);
 194             boxes[i].second = i;
 195         }
 196
 197         // Create R-tree
 198         typedef strategy::index::services::from_strategy
 199             <
 200                 Strategy
 201             > index_strategy_from;
 202         typedef index::parameters
 203             <
 204                 index::rstar<4>, typename index_strategy_from::type
 205             > index_parameters_type;
 206         index::rtree<box_pair_type, index_parameters_type>
 207             rtree(boxes.begin(), boxes.end(),
 208                   index_parameters_type(index::rstar<4>(), index_strategy_from::get(strategy)));
 209
 210         // For each point find overlapping envelopes and test corresponding single geometries
 211         // If a point is in the exterior break
 212         bool result = false;
 213
 214         typedef typename boost::range_const_iterator<MultiPoint>::type iterator;
 215         for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it )
 216         {
 217             // TODO: investigate the possibility of using satisfies
 218             // TODO: investigate the possibility of using iterative queries (optimization below)
 219             box_pair_vector inters_boxes;
 220             rtree.query(index::intersects(*it), std::back_inserter(inters_boxes));
 221
 222             bool found_interior = false;
 223             bool found_boundary = false;
 224             int boundaries = 0;
 225
 226             typedef typename box_pair_vector::const_iterator box_iterator;
 227             for (box_iterator box_it = inters_boxes.begin() ;
 228                  box_it != inters_boxes.end() ; ++box_it )
 229             {
 230                 int const in_val = point_in_geometry(*it,
 231                     range::at(linear_or_areal, box_it->second), strategy);
 232
 233                 if (in_val > 0)
 234                 {
 235                     found_interior = true;
 236                 }
 237                 else if (in_val == 0)
 238                 {
 239                     ++boundaries;
 240                 }
 241
 242                 // If the result was set previously (interior or
 243                 // interior/boundary found) the only thing that needs to be
 244                 // done for other points is to make sure they're not
 245                 // overlapping the exterior no need to analyse boundaries.
 246                 if (result && in_val >= 0)
 247                 {
 248                     break;
 249                 }
 250             }
 251
 252             if (boundaries > 0)
 253             {
 254                 if (is_linear && boundaries % 2 == 0)
 255                 {
 256                     found_interior = true;
 257                 }
 258                 else
 259                 {
 260                     found_boundary = true;
 261                 }
 262             }
 263
 264             // exterior
 265             if (! found_interior && ! found_boundary)
 266             {
 267                 result = false;
 268                 break;
 269             }
 270
 271             // interior : interior/boundary
 272             if (Within ? found_interior : (found_interior || found_boundary))
 273             {
 274                 result = true;
 275             }
 276         }
 277
 278         return result;
 279     }
 280 };
 281
 282 }} // namespace detail::within
 283 #endif // DOXYGEN_NO_DETAIL
 284
 285 }} // namespace boost::geometry
 286
 287
 288 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_MULTI_POINT_HPP