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> applyboost::geometry::detail::within::multi_point_point49 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> applyboost::geometry::detail::within::multi_point_multi_point71 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> applyboost::geometry::detail::within::multi_point_single_geometry115 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> applyboost::geometry::detail::within::multi_point_multi_geometry164 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 289