1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2014-2017, Oracle and/or its affiliates. 4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. 5 6 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle 7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 8 9 // Licensed under the Boost Software License version 1.0. 10 // http://www.boost.org/users/license.html 11 12 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP 13 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP 14 15 #include <algorithm> 16 #include <vector> 17 18 #include <boost/range.hpp> 19 #include <boost/mpl/assert.hpp> 20 21 #include <boost/geometry/core/assert.hpp> 22 #include <boost/geometry/core/tag.hpp> 23 #include <boost/geometry/core/tags.hpp> 24 25 #include <boost/geometry/geometries/box.hpp> 26 27 #include <boost/geometry/iterators/segment_iterator.hpp> 28 29 #include <boost/geometry/algorithms/envelope.hpp> 30 #include <boost/geometry/algorithms/expand.hpp> 31 32 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp> 33 #include <boost/geometry/algorithms/detail/partition.hpp> 34 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> 35 #include <boost/geometry/algorithms/detail/disjoint/multirange_geometry.hpp> 36 #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> 37 #include <boost/geometry/algorithms/detail/disjoint/point_point.hpp> 38 #include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp> 39 #include <boost/geometry/algorithms/detail/relate/less.hpp> 40 41 #include <boost/geometry/algorithms/dispatch/disjoint.hpp> 42 43 44 namespace boost { namespace geometry 45 { 46 47 48 #ifndef DOXYGEN_NO_DETAIL 49 namespace detail { namespace disjoint 50 { 51 52 53 template <typename MultiPoint1, typename MultiPoint2> 54 class multipoint_multipoint 55 { 56 private: 57 template <typename Iterator> 58 class unary_disjoint_predicate 59 : detail::relate::less 60 { 61 private: 62 typedef detail::relate::less base_type; 63 64 public: unary_disjoint_predicate(Iterator first,Iterator last)65 unary_disjoint_predicate(Iterator first, Iterator last) 66 : base_type(), m_first(first), m_last(last) 67 {} 68 69 template <typename Point> apply(Point const & point) const70 inline bool apply(Point const& point) const 71 { 72 return !std::binary_search(m_first, 73 m_last, 74 point, 75 static_cast<base_type const&>(*this)); 76 } 77 78 private: 79 Iterator m_first, m_last; 80 }; 81 82 public: apply(MultiPoint1 const & multipoint1,MultiPoint2 const & multipoint2)83 static inline bool apply(MultiPoint1 const& multipoint1, 84 MultiPoint2 const& multipoint2) 85 { 86 BOOST_GEOMETRY_ASSERT( boost::size(multipoint1) <= boost::size(multipoint2) ); 87 88 typedef typename boost::range_value<MultiPoint1>::type point1_type; 89 90 std::vector<point1_type> points1(boost::begin(multipoint1), 91 boost::end(multipoint1)); 92 93 std::sort(points1.begin(), points1.end(), detail::relate::less()); 94 95 typedef unary_disjoint_predicate 96 < 97 typename std::vector<point1_type>::const_iterator 98 > predicate_type; 99 100 return check_iterator_range 101 < 102 predicate_type 103 >::apply(boost::begin(multipoint2), 104 boost::end(multipoint2), 105 predicate_type(points1.begin(), points1.end())); 106 } 107 }; 108 109 110 template <typename MultiPoint, typename Linear> 111 class multipoint_linear 112 { 113 private: 114 struct expand_box_point 115 { 116 template <typename Box, typename Point> applyboost::geometry::detail::disjoint::multipoint_linear::expand_box_point117 static inline void apply(Box& total, Point const& point) 118 { 119 geometry::expand(total, point); 120 } 121 }; 122 123 template <typename EnvelopeStrategy> 124 struct expand_box_segment 125 { expand_box_segmentboost::geometry::detail::disjoint::multipoint_linear::expand_box_segment126 explicit expand_box_segment(EnvelopeStrategy const& strategy) 127 : m_strategy(strategy) 128 {} 129 130 template <typename Box, typename Segment> applyboost::geometry::detail::disjoint::multipoint_linear::expand_box_segment131 inline void apply(Box& total, Segment const& segment) const 132 { 133 geometry::expand(total, 134 geometry::return_envelope<Box>(segment, m_strategy)); 135 } 136 137 EnvelopeStrategy const& m_strategy; 138 }; 139 140 struct overlaps_box_point 141 { 142 template <typename Box, typename Point> applyboost::geometry::detail::disjoint::multipoint_linear::overlaps_box_point143 static inline bool apply(Box const& box, Point const& point) 144 { 145 // The default strategy is enough in this case 146 return ! detail::disjoint::disjoint_point_box(point, box); 147 } 148 }; 149 150 template <typename DisjointStrategy> 151 struct overlaps_box_segment 152 { overlaps_box_segmentboost::geometry::detail::disjoint::multipoint_linear::overlaps_box_segment153 explicit overlaps_box_segment(DisjointStrategy const& strategy) 154 : m_strategy(strategy) 155 {} 156 157 template <typename Box, typename Segment> applyboost::geometry::detail::disjoint::multipoint_linear::overlaps_box_segment158 inline bool apply(Box const& box, Segment const& segment) const 159 { 160 return ! dispatch::disjoint<Segment, Box>::apply(segment, box, m_strategy); 161 } 162 163 DisjointStrategy const& m_strategy; 164 }; 165 166 template <typename PtSegStrategy> 167 class item_visitor_type 168 { 169 public: item_visitor_type(PtSegStrategy const & strategy)170 item_visitor_type(PtSegStrategy const& strategy) 171 : m_intersection_found(false) 172 , m_strategy(strategy) 173 {} 174 175 template <typename Item1, typename Item2> apply(Item1 const & item1,Item2 const & item2)176 inline bool apply(Item1 const& item1, Item2 const& item2) 177 { 178 if (! m_intersection_found 179 && ! dispatch::disjoint<Item1, Item2>::apply(item1, item2, m_strategy)) 180 { 181 m_intersection_found = true; 182 return false; 183 } 184 return true; 185 } 186 intersection_found() const187 inline bool intersection_found() const { return m_intersection_found; } 188 189 private: 190 bool m_intersection_found; 191 PtSegStrategy const& m_strategy; 192 }; 193 // structs for partition -- end 194 195 class segment_range 196 { 197 public: 198 typedef geometry::segment_iterator<Linear const> const_iterator; 199 typedef const_iterator iterator; 200 segment_range(Linear const & linear)201 segment_range(Linear const& linear) 202 : m_linear(linear) 203 {} 204 begin() const205 const_iterator begin() const 206 { 207 return geometry::segments_begin(m_linear); 208 } 209 end() const210 const_iterator end() const 211 { 212 return geometry::segments_end(m_linear); 213 } 214 215 private: 216 Linear const& m_linear; 217 }; 218 219 public: 220 template <typename Strategy> apply(MultiPoint const & multipoint,Linear const & linear,Strategy const & strategy)221 static inline bool apply(MultiPoint const& multipoint, Linear const& linear, Strategy const& strategy) 222 { 223 item_visitor_type<Strategy> visitor(strategy); 224 225 typedef typename Strategy::envelope_strategy_type envelope_strategy_type; 226 typedef typename Strategy::disjoint_strategy_type disjoint_strategy_type; 227 228 // TODO: disjoint Segment/Box may be called in partition multiple times 229 // possibly for non-cartesian segments which could be slow. We should consider 230 // passing a range of bounding boxes of segments after calculating them once. 231 // Alternatively instead of a range of segments a range of Segment/Envelope pairs 232 // should be passed, where envelope would be lazily calculated when needed the first time 233 geometry::partition 234 < 235 geometry::model::box<typename point_type<MultiPoint>::type> 236 >::apply(multipoint, segment_range(linear), visitor, 237 expand_box_point(), 238 overlaps_box_point(), 239 expand_box_segment<envelope_strategy_type>(strategy.get_envelope_strategy()), 240 overlaps_box_segment<disjoint_strategy_type>(strategy.get_disjoint_strategy())); 241 242 return ! visitor.intersection_found(); 243 } 244 245 template <typename Strategy> apply(Linear const & linear,MultiPoint const & multipoint,Strategy const & strategy)246 static inline bool apply(Linear const& linear, MultiPoint const& multipoint, Strategy const& strategy) 247 { 248 return apply(multipoint, linear, strategy); 249 } 250 }; 251 252 253 template <typename MultiPoint, typename SingleGeometry> 254 class multi_point_single_geometry 255 { 256 public: 257 template <typename Strategy> apply(MultiPoint const & multi_point,SingleGeometry const & single_geometry,Strategy const & strategy)258 static inline bool apply(MultiPoint const& multi_point, SingleGeometry const& single_geometry, Strategy const& strategy) 259 { 260 typedef typename point_type<MultiPoint>::type point1_type; 261 typedef typename point_type<SingleGeometry>::type point2_type; 262 typedef model::box<point2_type> box2_type; 263 264 box2_type box2; 265 geometry::envelope(single_geometry, box2, strategy.get_envelope_strategy()); 266 geometry::detail::expand_by_epsilon(box2); 267 268 typedef typename boost::range_const_iterator<MultiPoint>::type iterator; 269 for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it ) 270 { 271 // The default strategy is enough for Point/Box 272 if (! detail::disjoint::disjoint_point_box(*it, box2) 273 && ! dispatch::disjoint<point1_type, SingleGeometry>::apply(*it, single_geometry, strategy)) 274 { 275 return false; 276 } 277 } 278 279 return true; 280 } 281 282 template <typename Strategy> apply(SingleGeometry const & single_geometry,MultiPoint const & multi_point,Strategy const & strategy)283 static inline bool apply(SingleGeometry const& single_geometry, MultiPoint const& multi_point, Strategy const& strategy) 284 { 285 return apply(multi_point, single_geometry, strategy); 286 } 287 }; 288 289 290 template <typename MultiPoint, typename MultiGeometry> 291 class multi_point_multi_geometry 292 { 293 private: 294 struct expand_box_point 295 { 296 template <typename Box, typename Point> applyboost::geometry::detail::disjoint::multi_point_multi_geometry::expand_box_point297 static inline void apply(Box& total, Point const& point) 298 { 299 geometry::expand(total, point); 300 } 301 }; 302 303 struct expand_box_box_pair 304 { 305 template <typename Box, typename BoxPair> applyboost::geometry::detail::disjoint::multi_point_multi_geometry::expand_box_box_pair306 inline void apply(Box& total, BoxPair const& box_pair) const 307 { 308 geometry::expand(total, box_pair.first); 309 } 310 }; 311 312 struct overlaps_box_point 313 { 314 template <typename Box, typename Point> applyboost::geometry::detail::disjoint::multi_point_multi_geometry::overlaps_box_point315 static inline bool apply(Box const& box, Point const& point) 316 { 317 // The default strategy is enough for Point/Box 318 return ! detail::disjoint::disjoint_point_box(point, box); 319 } 320 }; 321 322 struct overlaps_box_box_pair 323 { 324 template <typename Box, typename BoxPair> applyboost::geometry::detail::disjoint::multi_point_multi_geometry::overlaps_box_box_pair325 inline bool apply(Box const& box, BoxPair const& box_pair) const 326 { 327 // The default strategy is enough for Box/Box 328 return ! detail::disjoint::disjoint_box_box(box_pair.first, box); 329 } 330 }; 331 332 template <typename PtSegStrategy> 333 class item_visitor_type 334 { 335 public: item_visitor_type(MultiGeometry const & multi_geometry,PtSegStrategy const & strategy)336 item_visitor_type(MultiGeometry const& multi_geometry, 337 PtSegStrategy const& strategy) 338 : m_intersection_found(false) 339 , m_multi_geometry(multi_geometry) 340 , m_strategy(strategy) 341 {} 342 343 template <typename Point, typename BoxPair> apply(Point const & point,BoxPair const & box_pair)344 inline bool apply(Point const& point, BoxPair const& box_pair) 345 { 346 typedef typename boost::range_value<MultiGeometry>::type single_type; 347 348 // The default strategy is enough for Point/Box 349 if (! m_intersection_found 350 && ! detail::disjoint::disjoint_point_box(point, box_pair.first) 351 && ! dispatch::disjoint<Point, single_type>::apply(point, range::at(m_multi_geometry, box_pair.second), m_strategy)) 352 { 353 m_intersection_found = true; 354 return false; 355 } 356 return true; 357 } 358 intersection_found() const359 inline bool intersection_found() const { return m_intersection_found; } 360 361 private: 362 bool m_intersection_found; 363 MultiGeometry const& m_multi_geometry; 364 PtSegStrategy const& m_strategy; 365 }; 366 // structs for partition -- end 367 368 public: 369 template <typename Strategy> apply(MultiPoint const & multi_point,MultiGeometry const & multi_geometry,Strategy const & strategy)370 static inline bool apply(MultiPoint const& multi_point, MultiGeometry const& multi_geometry, Strategy const& strategy) 371 { 372 typedef typename point_type<MultiPoint>::type point1_type; 373 typedef typename point_type<MultiGeometry>::type point2_type; 374 typedef model::box<point1_type> box1_type; 375 typedef model::box<point2_type> box2_type; 376 typedef std::pair<box2_type, std::size_t> box_pair_type; 377 378 typename Strategy::envelope_strategy_type const 379 envelope_strategy = strategy.get_envelope_strategy(); 380 381 std::size_t count2 = boost::size(multi_geometry); 382 std::vector<box_pair_type> boxes(count2); 383 for (std::size_t i = 0 ; i < count2 ; ++i) 384 { 385 geometry::envelope(range::at(multi_geometry, i), boxes[i].first, envelope_strategy); 386 geometry::detail::expand_by_epsilon(boxes[i].first); 387 boxes[i].second = i; 388 } 389 390 item_visitor_type<Strategy> visitor(multi_geometry, strategy); 391 392 geometry::partition 393 < 394 box1_type 395 >::apply(multi_point, boxes, visitor, 396 expand_box_point(), 397 overlaps_box_point(), 398 expand_box_box_pair(), 399 overlaps_box_box_pair()); 400 401 return ! visitor.intersection_found(); 402 } 403 404 template <typename Strategy> apply(MultiGeometry const & multi_geometry,MultiPoint const & multi_point,Strategy const & strategy)405 static inline bool apply(MultiGeometry const& multi_geometry, MultiPoint const& multi_point, Strategy const& strategy) 406 { 407 return apply(multi_point, multi_geometry, strategy); 408 } 409 }; 410 411 412 template <typename MultiPoint, typename Areal, typename Tag = typename tag<Areal>::type> 413 struct multipoint_areal 414 : multi_point_single_geometry<MultiPoint, Areal> 415 {}; 416 417 template <typename MultiPoint, typename Areal> 418 struct multipoint_areal<MultiPoint, Areal, multi_polygon_tag> 419 : multi_point_multi_geometry<MultiPoint, Areal> 420 {}; 421 422 423 }} // namespace detail::disjoint 424 #endif // DOXYGEN_NO_DETAIL 425 426 427 428 429 #ifndef DOXYGEN_NO_DISPATCH 430 namespace dispatch 431 { 432 433 434 template <typename Point, typename MultiPoint, std::size_t DimensionCount> 435 struct disjoint 436 < 437 Point, MultiPoint, DimensionCount, point_tag, multi_point_tag, false 438 > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Point> 439 {}; 440 441 442 template <typename MultiPoint, typename Segment, std::size_t DimensionCount> 443 struct disjoint 444 < 445 MultiPoint, Segment, DimensionCount, multi_point_tag, segment_tag, false 446 > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Segment> 447 {}; 448 449 450 template <typename MultiPoint, typename Box, std::size_t DimensionCount> 451 struct disjoint 452 < 453 MultiPoint, Box, DimensionCount, multi_point_tag, box_tag, false 454 > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Box> 455 {}; 456 457 458 template 459 < 460 typename MultiPoint1, 461 typename MultiPoint2, 462 std::size_t DimensionCount 463 > 464 struct disjoint 465 < 466 MultiPoint1, MultiPoint2, DimensionCount, 467 multi_point_tag, multi_point_tag, false 468 > 469 { 470 template <typename Strategy> applyboost::geometry::dispatch::disjoint471 static inline bool apply(MultiPoint1 const& multipoint1, 472 MultiPoint2 const& multipoint2, 473 Strategy const& ) 474 { 475 if ( boost::size(multipoint2) < boost::size(multipoint1) ) 476 { 477 return detail::disjoint::multipoint_multipoint 478 < 479 MultiPoint2, MultiPoint1 480 >::apply(multipoint2, multipoint1); 481 } 482 483 return detail::disjoint::multipoint_multipoint 484 < 485 MultiPoint1, MultiPoint2 486 >::apply(multipoint1, multipoint2); 487 } 488 }; 489 490 491 template <typename Linear, typename MultiPoint, std::size_t DimensionCount> 492 struct disjoint 493 < 494 Linear, MultiPoint, DimensionCount, linear_tag, multi_point_tag, false 495 > : detail::disjoint::multipoint_linear<MultiPoint, Linear> 496 {}; 497 498 499 template <typename MultiPoint, typename Linear, std::size_t DimensionCount> 500 struct disjoint 501 < 502 MultiPoint, Linear, DimensionCount, multi_point_tag, linear_tag, false 503 > : detail::disjoint::multipoint_linear<MultiPoint, Linear> 504 {}; 505 506 507 template <typename Areal, typename MultiPoint, std::size_t DimensionCount> 508 struct disjoint 509 < 510 Areal, MultiPoint, DimensionCount, areal_tag, multi_point_tag, false 511 > : detail::disjoint::multipoint_areal<MultiPoint, Areal> 512 {}; 513 514 515 template <typename MultiPoint, typename Areal, std::size_t DimensionCount> 516 struct disjoint 517 < 518 MultiPoint, Areal, DimensionCount, multi_point_tag, areal_tag, false 519 > : detail::disjoint::multipoint_areal<MultiPoint, Areal> 520 {}; 521 522 523 } // namespace dispatch 524 #endif // DOXYGEN_NO_DISPATCH 525 526 527 }} // namespace boost::geometry 528 529 530 531 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP 532