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