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

   1 // Boost.Geometry
   2
   3 // Copyright (c) 2017 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
  77         geometry::less<> const less = geometry::less<>();
  78
  79         std::vector<point2_type> points2(boost::begin(multi_point2), boost::end(multi_point2));
  80         std::sort(points2.begin(), points2.end(), less);
  81
  82         bool result = false;
  83
  84         typedef typename boost::range_const_iterator<MultiPoint1>::type iterator;
  85         for ( iterator it = boost::begin(multi_point1) ; it != boost::end(multi_point1) ; ++it )
  86         {
  87             if (! std::binary_search(points2.begin(), points2.end(), *it, less))
  88             {
  89                 return false;
  90             }
  91             else
  92             {
  93                 result = true;
  94             }
  95         }
  96
  97         return result;
  98     }
  99 };
 100
 101
 102 // TODO: the complexity could be lesser
 103 //   the second geometry could be "prepared"/sorted
 104 // For Linear geometries partition could be used
 105 // For Areal geometries point_in_geometry() would have to call the winding
 106 //   strategy differently, currently it linearly calls the strategy for each
 107 //   segment. So the segments would have to be sorted in a way consistent with
 108 //   the strategy and then the strategy called only for the segments in range.
 109 template <bool Within>
 110 struct multi_point_single_geometry
 111 {
 112     template <typename MultiPoint, typename LinearOrAreal, typename Strategy>
 113     static inline bool apply(MultiPoint const& multi_point,
 114                              LinearOrAreal const& linear_or_areal,
 115                              Strategy const& strategy)
 116     {
 117         typedef typename boost::range_value<MultiPoint>::type point1_type;
 118         typedef typename point_type<LinearOrAreal>::type point2_type;
 119         typedef model::box<point2_type> box2_type;
 120
 121         // Create envelope of geometry
 122         box2_type box;
 123         geometry::envelope(linear_or_areal, box, strategy.get_envelope_strategy());
 124         geometry::detail::expand_by_epsilon(box);
 125
 126         typedef typename strategy::covered_by::services::default_strategy
 127             <
 128                 point1_type, box2_type
 129             >::type point_in_box_type;
 130
 131         // Test each Point with envelope and then geometry if needed
 132         // If in the exterior, break
 133         bool result = false;
 134
 135         typedef typename boost::range_const_iterator<MultiPoint>::type iterator;
 136         for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it )
 137         {
 138             int in_val = 0;
 139
 140             // exterior of box and of geometry
 141             if (! point_in_box_type::apply(*it, box)
 142                 || (in_val = point_in_geometry(*it, linear_or_areal, strategy)) < 0)
 143             {
 144                 result = false;
 145                 break;
 146             }
 147
 148             // interior : interior/boundary
 149             if (Within ? in_val > 0 : in_val >= 0)
 150             {
 151                 result = true;
 152             }
 153         }
 154
 155         return result;
 156     }
 157 };
 158
 159
 160 // TODO: same here, probably the complexity could be lesser
 161 template <bool Within>
 162 struct multi_point_multi_geometry
 163 {
 164     template <typename MultiPoint, typename LinearOrAreal, typename Strategy>
 165     static inline bool apply(MultiPoint const& multi_point,
 166                              LinearOrAreal const& linear_or_areal,
 167                              Strategy const& strategy)
 168     {
 169         typedef typename point_type<LinearOrAreal>::type point2_type;
 170         typedef model::box<point2_type> box2_type;
 171         static const bool is_linear = is_same
 172             <
 173                 typename tag_cast
 174                     <
 175                         typename tag<LinearOrAreal>::type,
 176                         linear_tag
 177                     >::type,
 178                 linear_tag
 179             >::value;
 180
 181         typename Strategy::envelope_strategy_type const
 182             envelope_strategy = strategy.get_envelope_strategy();
 183
 184         // TODO: box pairs could be constructed on the fly, inside the rtree
 185
 186         // Prepare range of envelopes and ids
 187         std::size_t count2 = boost::size(linear_or_areal);
 188         typedef std::pair<box2_type, std::size_t> box_pair_type;
 189         typedef std::vector<box_pair_type> box_pair_vector;
 190         box_pair_vector boxes(count2);
 191         for (std::size_t i = 0 ; i < count2 ; ++i)
 192         {
 193             geometry::envelope(linear_or_areal, boxes[i].first, envelope_strategy);
 194             geometry::detail::expand_by_epsilon(boxes[i].first);
 195             boxes[i].second = i;
 196         }
 197
 198         // Create R-tree
 199         index::rtree<box_pair_type, index::rstar<4> > rtree(boxes.begin(), boxes.end());
 200
 201         // For each point find overlapping envelopes and test corresponding single geometries
 202         // If a point is in the exterior break
 203         bool result = false;
 204
 205         typedef typename boost::range_const_iterator<MultiPoint>::type iterator;
 206         for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it )
 207         {
 208             // TODO: investigate the possibility of using satisfies
 209             // TODO: investigate the possibility of using iterative queries (optimization below)
 210             box_pair_vector inters_boxes;
 211             rtree.query(index::intersects(*it), std::back_inserter(inters_boxes));
 212
 213             bool found_interior = false;
 214             bool found_boundary = false;
 215             int boundaries = 0;
 216
 217             typedef typename box_pair_vector::const_iterator iterator;
 218             for ( iterator box_it = inters_boxes.begin() ; box_it != inters_boxes.end() ; ++box_it )
 219             {
 220                 int in_val = point_in_geometry(*it, range::at(linear_or_areal, box_it->second), strategy);
 221
 222                 if (in_val > 0)
 223                     found_interior = true;
 224                 else if (in_val == 0)
 225                     ++boundaries;
 226
 227                 // If the result was set previously (interior or
 228                 // interior/boundary found) the only thing that needs to be
 229                 // done for other points is to make sure they're not
 230                 // overlapping the exterior no need to analyse boundaries.
 231                 if (result && in_val >= 0)
 232                 {
 233                     break;
 234                 }
 235             }
 236
 237             if ( boundaries > 0)
 238             {
 239                 if (is_linear && boundaries % 2 == 0)
 240                     found_interior = true;
 241                 else
 242                     found_boundary = true;
 243             }
 244
 245             // exterior
 246             if (! found_interior && ! found_boundary)
 247             {
 248                 result = false;
 249                 break;
 250             }
 251
 252             // interior : interior/boundary
 253             if (Within ? found_interior : (found_interior || found_boundary))
 254             {
 255                 result = true;
 256             }
 257         }
 258
 259         return result;
 260     }
 261 };
 262
 263 }} // namespace detail::within
 264 #endif // DOXYGEN_NO_DETAIL
 265
 266 }} // namespace boost::geometry
 267
 268
 269 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_MULTI_POINT_HPP