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_RELATE_MULTI_POINT_GEOMETRY_HPP 12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_MULTI_POINT_GEOMETRY_HPP 13 14 15 #include <boost/range.hpp> 16 17 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> 18 #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> 19 #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp> 20 #include <boost/geometry/algorithms/detail/partition.hpp> 21 #include <boost/geometry/algorithms/detail/relate/result.hpp> 22 #include <boost/geometry/algorithms/detail/relate/topology_check.hpp> 23 #include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp> 24 #include <boost/geometry/algorithms/envelope.hpp> 25 26 #include <boost/geometry/core/is_areal.hpp> 27 #include <boost/geometry/core/point_type.hpp> 28 29 #include <boost/geometry/geometries/box.hpp> 30 31 #include <boost/geometry/index/rtree.hpp> 32 33 34 namespace boost { namespace geometry 35 { 36 37 #ifndef DOXYGEN_NO_DETAIL 38 namespace detail { namespace relate 39 { 40 41 template 42 < 43 typename Geometry, 44 typename EqPPStrategy, 45 typename Tag = typename tag<Geometry>::type 46 > 47 struct multi_point_geometry_eb 48 { 49 template <typename MultiPoint> applyboost::geometry::detail::relate::multi_point_geometry_eb50 static inline bool apply(MultiPoint const& , 51 detail::relate::topology_check<Geometry, EqPPStrategy> const& ) 52 { 53 return true; 54 } 55 }; 56 57 template <typename Geometry, typename EqPPStrategy> 58 struct multi_point_geometry_eb<Geometry, EqPPStrategy, linestring_tag> 59 { 60 template <typename Points> 61 struct boundary_visitor 62 { boundary_visitorboost::geometry::detail::relate::multi_point_geometry_eb::boundary_visitor63 boundary_visitor(Points const& points) 64 : m_points(points) 65 , m_boundary_found(false) 66 {} 67 68 template <typename Point> 69 struct find_pred 70 { find_predboost::geometry::detail::relate::multi_point_geometry_eb::boundary_visitor::find_pred71 find_pred(Point const& point) 72 : m_point(point) 73 {} 74 75 template <typename Pt> operator ()boost::geometry::detail::relate::multi_point_geometry_eb::boundary_visitor::find_pred76 bool operator()(Pt const& pt) const 77 { 78 return detail::equals::equals_point_point(pt, m_point, EqPPStrategy()); 79 } 80 81 Point const& m_point; 82 }; 83 84 template <typename Point> applyboost::geometry::detail::relate::multi_point_geometry_eb::boundary_visitor85 bool apply(Point const& boundary_point) 86 { 87 if (std::find_if(m_points.begin(), m_points.end(), find_pred<Point>(boundary_point)) == m_points.end()) 88 { 89 m_boundary_found = true; 90 return false; 91 } 92 return true; 93 } 94 resultboost::geometry::detail::relate::multi_point_geometry_eb::boundary_visitor95 bool result() const { return m_boundary_found; } 96 97 private: 98 Points const& m_points; 99 bool m_boundary_found; 100 }; 101 102 template <typename MultiPoint> applyboost::geometry::detail::relate::multi_point_geometry_eb103 static inline bool apply(MultiPoint const& multi_point, 104 detail::relate::topology_check<Geometry, EqPPStrategy> const& tc) 105 { 106 boundary_visitor<MultiPoint> visitor(multi_point); 107 tc.for_each_boundary_point(visitor); 108 return visitor.result(); 109 } 110 }; 111 112 template <typename Geometry, typename EqPPStrategy> 113 struct multi_point_geometry_eb<Geometry, EqPPStrategy, multi_linestring_tag> 114 { 115 // TODO: CS-specific less compare strategy derived from EqPPStrategy 116 typedef geometry::less<void, -1, typename EqPPStrategy::cs_tag> less_type; 117 118 template <typename Points> 119 struct boundary_visitor 120 { boundary_visitorboost::geometry::detail::relate::multi_point_geometry_eb::boundary_visitor121 boundary_visitor(Points const& points) 122 : m_points(points) 123 , m_boundary_found(false) 124 {} 125 126 template <typename Point> applyboost::geometry::detail::relate::multi_point_geometry_eb::boundary_visitor127 bool apply(Point const& boundary_point) 128 { 129 if (! std::binary_search(m_points.begin(), m_points.end(), boundary_point, less_type())) 130 { 131 m_boundary_found = true; 132 return false; 133 } 134 return true; 135 } 136 resultboost::geometry::detail::relate::multi_point_geometry_eb::boundary_visitor137 bool result() const { return m_boundary_found; } 138 139 private: 140 Points const& m_points; 141 bool m_boundary_found; 142 }; 143 144 template <typename MultiPoint> applyboost::geometry::detail::relate::multi_point_geometry_eb145 static inline bool apply(MultiPoint const& multi_point, 146 detail::relate::topology_check<Geometry, EqPPStrategy> const& tc) 147 { 148 typedef typename boost::range_value<MultiPoint>::type point_type; 149 typedef std::vector<point_type> points_type; 150 points_type points(boost::begin(multi_point), boost::end(multi_point)); 151 std::sort(points.begin(), points.end(), less_type()); 152 153 boundary_visitor<points_type> visitor(points); 154 tc.for_each_boundary_point(visitor); 155 return visitor.result(); 156 } 157 }; 158 159 // SingleGeometry - Linear or Areal 160 template <typename MultiPoint, typename SingleGeometry, bool Transpose = false> 161 struct multi_point_single_geometry 162 { 163 static const bool interruption_enabled = true; 164 165 template <typename Result, typename Strategy> applyboost::geometry::detail::relate::multi_point_single_geometry166 static inline void apply(MultiPoint const& multi_point, 167 SingleGeometry const& single_geometry, 168 Result & result, 169 Strategy const& strategy) 170 { 171 typedef typename point_type<SingleGeometry>::type point2_type; 172 typedef model::box<point2_type> box2_type; 173 typedef typename Strategy::equals_point_point_strategy_type eq_pp_strategy_type; 174 typedef typename Strategy::disjoint_point_box_strategy_type d_pb_strategy_type; 175 176 box2_type box2; 177 geometry::envelope(single_geometry, box2, strategy.get_envelope_strategy()); 178 geometry::detail::expand_by_epsilon(box2); 179 180 typedef typename boost::range_const_iterator<MultiPoint>::type iterator; 181 for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it ) 182 { 183 if (! (relate::may_update<interior, interior, '0', Transpose>(result) 184 || relate::may_update<interior, boundary, '0', Transpose>(result) 185 || relate::may_update<interior, exterior, '0', Transpose>(result) ) ) 186 { 187 break; 188 } 189 190 // The default strategy is enough for Point/Box 191 if (detail::disjoint::disjoint_point_box(*it, box2, d_pb_strategy_type())) 192 { 193 relate::set<interior, exterior, '0', Transpose>(result); 194 } 195 else 196 { 197 int in_val = detail::within::point_in_geometry(*it, single_geometry, strategy); 198 199 if (in_val > 0) // within 200 { 201 relate::set<interior, interior, '0', Transpose>(result); 202 } 203 else if (in_val == 0) 204 { 205 relate::set<interior, boundary, '0', Transpose>(result); 206 } 207 else // in_val < 0 - not within 208 { 209 relate::set<interior, exterior, '0', Transpose>(result); 210 } 211 } 212 213 if ( BOOST_GEOMETRY_CONDITION(result.interrupt) ) 214 { 215 return; 216 } 217 } 218 219 typedef detail::relate::topology_check 220 < 221 SingleGeometry, eq_pp_strategy_type 222 > tc_t; 223 if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result) 224 || relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) ) 225 { 226 tc_t tc(single_geometry); 227 228 if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result) 229 && tc.has_interior() ) 230 { 231 // TODO: this is not true if a linestring is degenerated to a point 232 // then the interior has topological dimension = 0, not 1 233 relate::set<exterior, interior, tc_t::interior, Transpose>(result); 234 } 235 236 if ( relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) 237 && tc.has_boundary() ) 238 { 239 if (multi_point_geometry_eb 240 < 241 SingleGeometry, eq_pp_strategy_type 242 >::apply(multi_point, tc)) 243 { 244 relate::set<exterior, boundary, tc_t::boundary, Transpose>(result); 245 } 246 } 247 } 248 249 relate::set<exterior, exterior, result_dimension<MultiPoint>::value, Transpose>(result); 250 } 251 }; 252 253 254 // MultiGeometry - Linear or Areal 255 // part of the algorithm calculating II and IB when no IE has to be calculated 256 // using partition() 257 template <typename MultiPoint, typename MultiGeometry, bool Transpose> 258 class multi_point_multi_geometry_ii_ib 259 { 260 template <typename ExpandPointStrategy> 261 struct expand_box_point 262 { 263 template <typename Box, typename Point> applyboost::geometry::detail::relate::multi_point_multi_geometry_ii_ib::expand_box_point264 static inline void apply(Box& total, Point const& point) 265 { 266 geometry::expand(total, point, ExpandPointStrategy()); 267 } 268 }; 269 270 template <typename ExpandBoxStrategy> 271 struct expand_box_box_pair 272 { 273 template <typename Box, typename BoxPair> applyboost::geometry::detail::relate::multi_point_multi_geometry_ii_ib::expand_box_box_pair274 static inline void apply(Box& total, BoxPair const& box_pair) 275 { 276 geometry::expand(total, box_pair.first, ExpandBoxStrategy()); 277 } 278 }; 279 280 template <typename DisjointPointBoxStrategy> 281 struct overlaps_box_point 282 { 283 template <typename Box, typename Point> applyboost::geometry::detail::relate::multi_point_multi_geometry_ii_ib::overlaps_box_point284 static inline bool apply(Box const& box, Point const& point) 285 { 286 // The default strategy is enough for Point/Box 287 return ! detail::disjoint::disjoint_point_box(point, box, 288 DisjointPointBoxStrategy()); 289 } 290 }; 291 292 template <typename DisjointBoxBoxStrategy> 293 struct overlaps_box_box_pair 294 { 295 template <typename Box, typename BoxPair> applyboost::geometry::detail::relate::multi_point_multi_geometry_ii_ib::overlaps_box_box_pair296 static inline bool apply(Box const& box, BoxPair const& box_pair) 297 { 298 // The default strategy is enough for Box/Box 299 return ! detail::disjoint::disjoint_box_box(box_pair.first, box, 300 DisjointBoxBoxStrategy()); 301 } 302 }; 303 304 template <typename Result, typename PtSegStrategy> 305 class item_visitor_type 306 { 307 typedef typename PtSegStrategy::equals_point_point_strategy_type pp_strategy_type; 308 typedef typename PtSegStrategy::disjoint_point_box_strategy_type d_pp_strategy_type; 309 typedef detail::relate::topology_check<MultiGeometry, pp_strategy_type> topology_check_type; 310 311 public: item_visitor_type(MultiGeometry const & multi_geometry,topology_check_type const & tc,Result & result,PtSegStrategy const & strategy)312 item_visitor_type(MultiGeometry const& multi_geometry, 313 topology_check_type const& tc, 314 Result & result, 315 PtSegStrategy const& strategy) 316 : m_multi_geometry(multi_geometry) 317 , m_tc(tc) 318 , m_result(result) 319 , m_strategy(strategy) 320 {} 321 322 template <typename Point, typename BoxPair> apply(Point const & point,BoxPair const & box_pair)323 inline bool apply(Point const& point, BoxPair const& box_pair) 324 { 325 // The default strategy is enough for Point/Box 326 if (! detail::disjoint::disjoint_point_box(point, box_pair.first, d_pp_strategy_type())) 327 { 328 typename boost::range_value<MultiGeometry>::type const& 329 single = range::at(m_multi_geometry, box_pair.second); 330 331 int in_val = detail::within::point_in_geometry(point, single, m_strategy); 332 333 if (in_val > 0) // within 334 { 335 relate::set<interior, interior, '0', Transpose>(m_result); 336 } 337 else if (in_val == 0) 338 { 339 if (m_tc.check_boundary_point(point)) 340 relate::set<interior, boundary, '0', Transpose>(m_result); 341 else 342 relate::set<interior, interior, '0', Transpose>(m_result); 343 } 344 } 345 346 if ( BOOST_GEOMETRY_CONDITION(m_result.interrupt) ) 347 { 348 return false; 349 } 350 351 if (! (relate::may_update<interior, interior, '0', Transpose>(m_result) 352 || relate::may_update<interior, boundary, '0', Transpose>(m_result) ) ) 353 { 354 return false; 355 } 356 357 return true; 358 } 359 360 361 private: 362 MultiGeometry const& m_multi_geometry; 363 topology_check_type const& m_tc; 364 Result & m_result; 365 PtSegStrategy const& m_strategy; 366 }; 367 368 public: 369 typedef typename point_type<MultiPoint>::type point1_type; 370 typedef typename point_type<MultiGeometry>::type point2_type; 371 typedef model::box<point1_type> box1_type; 372 typedef model::box<point2_type> box2_type; 373 typedef std::pair<box2_type, std::size_t> box_pair_type; 374 375 template <typename Result, typename Strategy> apply(MultiPoint const & multi_point,MultiGeometry const & multi_geometry,std::vector<box_pair_type> const & boxes,detail::relate::topology_check<MultiGeometry,typename Strategy::equals_point_point_strategy_type> const & tc,Result & result,Strategy const & strategy)376 static inline void apply(MultiPoint const& multi_point, 377 MultiGeometry const& multi_geometry, 378 std::vector<box_pair_type> const& boxes, 379 detail::relate::topology_check 380 < 381 MultiGeometry, 382 typename Strategy::equals_point_point_strategy_type 383 > const& tc, 384 Result & result, 385 Strategy const& strategy) 386 { 387 item_visitor_type<Result, Strategy> visitor(multi_geometry, tc, result, strategy); 388 389 typedef expand_box_point 390 < 391 typename Strategy::expand_point_strategy_type 392 > expand_box_point_type; 393 typedef overlaps_box_point 394 < 395 typename Strategy::disjoint_point_box_strategy_type 396 > overlaps_box_point_type; 397 typedef expand_box_box_pair 398 < 399 typename Strategy::envelope_strategy_type::box_expand_strategy_type 400 > expand_box_box_pair_type; 401 typedef overlaps_box_box_pair 402 < 403 typename Strategy::disjoint_box_box_strategy_type 404 > overlaps_box_box_pair_type; 405 406 geometry::partition 407 < 408 box1_type 409 >::apply(multi_point, boxes, visitor, 410 expand_box_point_type(), 411 overlaps_box_point_type(), 412 expand_box_box_pair_type(), 413 overlaps_box_box_pair_type()); 414 } 415 416 }; 417 418 // MultiGeometry - Linear or Areal 419 // part of the algorithm calculating II, IB and IE 420 // using rtree 421 template <typename MultiPoint, typename MultiGeometry, bool Transpose> 422 struct multi_point_multi_geometry_ii_ib_ie 423 { 424 typedef typename point_type<MultiPoint>::type point1_type; 425 typedef typename point_type<MultiGeometry>::type point2_type; 426 typedef model::box<point1_type> box1_type; 427 typedef model::box<point2_type> box2_type; 428 typedef std::pair<box2_type, std::size_t> box_pair_type; 429 typedef std::vector<box_pair_type> boxes_type; 430 typedef typename boxes_type::const_iterator boxes_iterator; 431 432 template <typename Result, typename Strategy> applyboost::geometry::detail::relate::multi_point_multi_geometry_ii_ib_ie433 static inline void apply(MultiPoint const& multi_point, 434 MultiGeometry const& multi_geometry, 435 std::vector<box_pair_type> const& boxes, 436 detail::relate::topology_check 437 < 438 MultiGeometry, 439 typename Strategy::equals_point_point_strategy_type 440 > const& tc, 441 Result & result, 442 Strategy const& strategy) 443 { 444 typedef strategy::index::services::from_strategy 445 < 446 Strategy 447 > index_strategy_from; 448 typedef index::parameters 449 < 450 index::rstar<4>, typename index_strategy_from::type 451 > index_parameters_type; 452 index::rtree<box_pair_type, index_parameters_type> 453 rtree(boxes.begin(), boxes.end(), 454 index_parameters_type(index::rstar<4>(), index_strategy_from::get(strategy))); 455 456 typedef typename boost::range_const_iterator<MultiPoint>::type iterator; 457 for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it ) 458 { 459 if (! (relate::may_update<interior, interior, '0', Transpose>(result) 460 || relate::may_update<interior, boundary, '0', Transpose>(result) 461 || relate::may_update<interior, exterior, '0', Transpose>(result) ) ) 462 { 463 return; 464 } 465 466 typename boost::range_value<MultiPoint>::type const& point = *it; 467 468 boxes_type boxes_found; 469 rtree.query(index::intersects(point), std::back_inserter(boxes_found)); 470 471 bool found_ii_or_ib = false; 472 for (boxes_iterator bi = boxes_found.begin() ; bi != boxes_found.end() ; ++bi) 473 { 474 typename boost::range_value<MultiGeometry>::type const& 475 single = range::at(multi_geometry, bi->second); 476 477 int in_val = detail::within::point_in_geometry(point, single, strategy); 478 479 if (in_val > 0) // within 480 { 481 relate::set<interior, interior, '0', Transpose>(result); 482 found_ii_or_ib = true; 483 } 484 else if (in_val == 0) // on boundary of single 485 { 486 if (tc.check_boundary_point(point)) 487 relate::set<interior, boundary, '0', Transpose>(result); 488 else 489 relate::set<interior, interior, '0', Transpose>(result); 490 found_ii_or_ib = true; 491 } 492 } 493 494 // neither interior nor boundary found -> exterior 495 if (found_ii_or_ib == false) 496 { 497 relate::set<interior, exterior, '0', Transpose>(result); 498 } 499 500 if ( BOOST_GEOMETRY_CONDITION(result.interrupt) ) 501 { 502 return; 503 } 504 } 505 } 506 }; 507 508 // MultiGeometry - Linear or Areal 509 template <typename MultiPoint, typename MultiGeometry, bool Transpose = false> 510 struct multi_point_multi_geometry 511 { 512 static const bool interruption_enabled = true; 513 514 template <typename Result, typename Strategy> applyboost::geometry::detail::relate::multi_point_multi_geometry515 static inline void apply(MultiPoint const& multi_point, 516 MultiGeometry const& multi_geometry, 517 Result & result, 518 Strategy const& strategy) 519 { 520 typedef typename point_type<MultiGeometry>::type point2_type; 521 typedef model::box<point2_type> box2_type; 522 typedef std::pair<box2_type, std::size_t> box_pair_type; 523 524 typedef typename Strategy::equals_point_point_strategy_type eq_pp_strategy_type; 525 526 typename Strategy::envelope_strategy_type const 527 envelope_strategy = strategy.get_envelope_strategy(); 528 529 std::size_t count2 = boost::size(multi_geometry); 530 std::vector<box_pair_type> boxes(count2); 531 for (std::size_t i = 0 ; i < count2 ; ++i) 532 { 533 geometry::envelope(range::at(multi_geometry, i), boxes[i].first, envelope_strategy); 534 geometry::detail::expand_by_epsilon(boxes[i].first); 535 boxes[i].second = i; 536 } 537 538 typedef detail::relate::topology_check<MultiGeometry, eq_pp_strategy_type> tc_t; 539 tc_t tc(multi_geometry); 540 541 if ( relate::may_update<interior, interior, '0', Transpose>(result) 542 || relate::may_update<interior, boundary, '0', Transpose>(result) 543 || relate::may_update<interior, exterior, '0', Transpose>(result) ) 544 { 545 // If there is no need to calculate IE, use partition 546 if (! relate::may_update<interior, exterior, '0', Transpose>(result) ) 547 { 548 multi_point_multi_geometry_ii_ib<MultiPoint, MultiGeometry, Transpose> 549 ::apply(multi_point, multi_geometry, boxes, tc, result, strategy); 550 } 551 else // otherwise use rtree 552 { 553 multi_point_multi_geometry_ii_ib_ie<MultiPoint, MultiGeometry, Transpose> 554 ::apply(multi_point, multi_geometry, boxes, tc, result, strategy); 555 } 556 } 557 558 if ( BOOST_GEOMETRY_CONDITION(result.interrupt) ) 559 { 560 return; 561 } 562 563 if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result) 564 || relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) ) 565 { 566 if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result) 567 && tc.has_interior() ) 568 { 569 // TODO: this is not true if a linestring is degenerated to a point 570 // then the interior has topological dimension = 0, not 1 571 relate::set<exterior, interior, tc_t::interior, Transpose>(result); 572 } 573 574 if ( relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) 575 && tc.has_boundary() ) 576 { 577 if (multi_point_geometry_eb 578 < 579 MultiGeometry, eq_pp_strategy_type 580 >::apply(multi_point, tc)) 581 { 582 relate::set<exterior, boundary, tc_t::boundary, Transpose>(result); 583 } 584 } 585 } 586 587 relate::set<exterior, exterior, result_dimension<MultiPoint>::value, Transpose>(result); 588 } 589 590 }; 591 592 593 template 594 < 595 typename MultiPoint, typename Geometry, 596 bool Transpose = false, 597 bool isMulti = boost::is_same 598 < 599 typename tag_cast 600 < 601 typename tag<Geometry>::type, multi_tag 602 >::type, 603 multi_tag 604 >::value 605 > 606 struct multi_point_geometry 607 : multi_point_single_geometry<MultiPoint, Geometry, Transpose> 608 {}; 609 610 template <typename MultiPoint, typename Geometry, bool Transpose> 611 struct multi_point_geometry<MultiPoint, Geometry, Transpose, true> 612 : multi_point_multi_geometry<MultiPoint, Geometry, Transpose> 613 {}; 614 615 616 // transposed result of multi_point_geometry 617 template <typename Geometry, typename MultiPoint> 618 struct geometry_multi_point 619 { 620 static const bool interruption_enabled = true; 621 622 template <typename Result, typename Strategy> applyboost::geometry::detail::relate::geometry_multi_point623 static inline void apply(Geometry const& geometry, MultiPoint const& multi_point, 624 Result & result, Strategy const& strategy) 625 { 626 multi_point_geometry<MultiPoint, Geometry, true>::apply(multi_point, geometry, result, strategy); 627 } 628 }; 629 630 }} // namespace detail::relate 631 #endif // DOXYGEN_NO_DETAIL 632 633 }} // namespace boost::geometry 634 635 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_MULTI_POINT_GEOMETRY_HPP 636