ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/touches.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
   5 // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
   6 // Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland.
   7
   8 // This file was modified by Oracle on 2013, 2014, 2015.
   9 // Modifications copyright (c) 2013-2015, Oracle and/or its affiliates.
  10
  11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  12
  13 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  14 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  15
  16 // Use, modification and distribution is subject to the Boost Software License,
  17 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  18 // http://www.boost.org/LICENSE_1_0.txt)
  19
  20 #ifndef BOOST_GEOMETRY_ALGORITHMS_TOUCHES_HPP
  21 #define BOOST_GEOMETRY_ALGORITHMS_TOUCHES_HPP
  22
  23
  24 #include <deque>
  25
  26 #include <boost/variant/apply_visitor.hpp>
  27 #include <boost/variant/static_visitor.hpp>
  28 #include <boost/variant/variant_fwd.hpp>
  29
  30 #include <boost/geometry/geometries/concepts/check.hpp>
  31 #include <boost/geometry/algorithms/detail/for_each_range.hpp>
  32 #include <boost/geometry/algorithms/detail/overlay/overlay.hpp>
  33 #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
  34 #include <boost/geometry/algorithms/disjoint.hpp>
  35 #include <boost/geometry/algorithms/intersects.hpp>
  36 #include <boost/geometry/algorithms/num_geometries.hpp>
  37 #include <boost/geometry/algorithms/detail/sub_range.hpp>
  38 #include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
  39
  40 #include <boost/geometry/algorithms/relate.hpp>
  41 #include <boost/geometry/algorithms/detail/relate/relate_impl.hpp>
  42
  43
  44 namespace boost { namespace geometry
  45 {
  46
  47 #ifndef DOXYGEN_NO_DETAIL
  48 namespace detail { namespace touches
  49 {
  50
  51 // Box/Box
  52
  53 template
  54 <
  55     std::size_t Dimension,
  56     std::size_t DimensionCount
  57 >
  58 struct box_box_loop
  59 {
  60     template <typename Box1, typename Box2>
  61     static inline bool apply(Box1 const& b1, Box2 const& b2, bool & touch)
  62     {
  63         typedef typename coordinate_type<Box1>::type coordinate_type1;
  64         typedef typename coordinate_type<Box2>::type coordinate_type2;
  65
  66         coordinate_type1 const& min1 = get<min_corner, Dimension>(b1);
  67         coordinate_type1 const& max1 = get<max_corner, Dimension>(b1);
  68         coordinate_type2 const& min2 = get<min_corner, Dimension>(b2);
  69         coordinate_type2 const& max2 = get<max_corner, Dimension>(b2);
  70
  71         // TODO assert or exception?
  72         //BOOST_GEOMETRY_ASSERT(min1 <= max1 && min2 <= max2);
  73
  74         if (max1 < min2 || max2 < min1)
  75         {
  76             return false;
  77         }
  78
  79         if (max1 == min2 || max2 == min1)
  80         {
  81             touch = true;
  82         }
  83
  84         return box_box_loop
  85                 <
  86                     Dimension + 1,
  87                     DimensionCount
  88                 >::apply(b1, b2, touch);
  89     }
  90 };
  91
  92 template
  93 <
  94     std::size_t DimensionCount
  95 >
  96 struct box_box_loop<DimensionCount, DimensionCount>
  97 {
  98     template <typename Box1, typename Box2>
  99     static inline bool apply(Box1 const& , Box2 const&, bool &)
 100     {
 101         return true;
 102     }
 103 };
 104
 105 struct box_box
 106 {
 107     template <typename Box1, typename Box2>
 108     static inline bool apply(Box1 const& b1, Box2 const& b2)
 109     {
 110         BOOST_STATIC_ASSERT((boost::is_same
 111                                 <
 112                                     typename geometry::coordinate_system<Box1>::type,
 113                                     typename geometry::coordinate_system<Box2>::type
 114                                 >::value
 115                            ));
 116         assert_dimension_equal<Box1, Box2>();
 117
 118         bool touches = false;
 119         bool ok = box_box_loop
 120                     <
 121                         0,
 122                         dimension<Box1>::type::value
 123                     >::apply(b1, b2, touches);
 124
 125         return ok && touches;
 126     }
 127 };
 128
 129 // Areal/Areal
 130
 131 struct areal_interrupt_policy
 132 {
 133     static bool const enabled = true;
 134     bool found_touch;
 135     bool found_not_touch;
 136
 137     // dummy variable required by self_get_turn_points::get_turns
 138     static bool const has_intersections = false;
 139
 140     inline bool result()
 141     {
 142         return found_touch && !found_not_touch;
 143     }
 144
 145     inline areal_interrupt_policy()
 146         : found_touch(false), found_not_touch(false)
 147     {}
 148
 149     template <typename Range>
 150     inline bool apply(Range const& range)
 151     {
 152         // if already rejected (temp workaround?)
 153         if ( found_not_touch )
 154             return true;
 155
 156         typedef typename boost::range_iterator<Range const>::type iterator;
 157         for ( iterator it = boost::begin(range) ; it != boost::end(range) ; ++it )
 158         {
 159             if ( it->has(overlay::operation_intersection) )
 160             {
 161                 found_not_touch = true;
 162                 return true;
 163             }
 164
 165             switch(it->method)
 166             {
 167                 case overlay::method_crosses:
 168                     found_not_touch = true;
 169                     return true;
 170                 case overlay::method_equal:
 171                     // Segment spatially equal means: at the right side
 172                     // the polygon internally overlaps. So return false.
 173                     found_not_touch = true;
 174                     return true;
 175                 case overlay::method_touch:
 176                 case overlay::method_touch_interior:
 177                 case overlay::method_collinear:
 178                     if ( ok_for_touch(*it) )
 179                     {
 180                         found_touch = true;
 181                     }
 182                     else
 183                     {
 184                         found_not_touch = true;
 185                         return true;
 186                     }
 187                     break;
 188                 case overlay::method_none :
 189                 case overlay::method_disjoint :
 190                 case overlay::method_error :
 191                     break;
 192             }
 193         }
 194
 195         return false;
 196     }
 197
 198     template <typename Turn>
 199     inline bool ok_for_touch(Turn const& turn)
 200     {
 201         return turn.both(overlay::operation_union)
 202             || turn.both(overlay::operation_blocked)
 203             || turn.combination(overlay::operation_union, overlay::operation_blocked)
 204             ;
 205     }
 206 };
 207
 208 template<typename Geometry>
 209 struct check_each_ring_for_within
 210 {
 211     bool has_within;
 212     Geometry const& m_geometry;
 213
 214     inline check_each_ring_for_within(Geometry const& g)
 215         : has_within(false)
 216         , m_geometry(g)
 217     {}
 218
 219     template <typename Range>
 220     inline void apply(Range const& range)
 221     {
 222         typename geometry::point_type<Range>::type p;
 223         geometry::point_on_border(p, range);
 224         if ( !has_within && geometry::within(p, m_geometry) )
 225         {
 226             has_within = true;
 227         }
 228     }
 229 };
 230
 231 template <typename FirstGeometry, typename SecondGeometry>
 232 inline bool rings_containing(FirstGeometry const& geometry1,
 233                 SecondGeometry const& geometry2)
 234 {
 235     check_each_ring_for_within<FirstGeometry> checker(geometry1);
 236     geometry::detail::for_each_range(geometry2, checker);
 237     return checker.has_within;
 238 }
 239
 240 template <typename Geometry1, typename Geometry2>
 241 struct areal_areal
 242 {
 243     static inline
 244     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2)
 245     {
 246         typedef detail::no_rescale_policy rescale_policy_type;
 247         typedef typename geometry::point_type<Geometry1>::type point_type;
 248         typedef detail::overlay::turn_info
 249             <
 250                 point_type,
 251                 typename segment_ratio_type<point_type, rescale_policy_type>::type
 252             > turn_info;
 253
 254         std::deque<turn_info> turns;
 255         detail::touches::areal_interrupt_policy policy;
 256         rescale_policy_type robust_policy;
 257         boost::geometry::get_turns
 258                 <
 259                     detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
 260                     detail::overlay::do_reverse<geometry::point_order<Geometry2>::value>::value,
 261                     detail::overlay::assign_null_policy
 262                 >(geometry1, geometry2, robust_policy, turns, policy);
 263
 264         return policy.result()
 265             && ! geometry::detail::touches::rings_containing(geometry1, geometry2)
 266             && ! geometry::detail::touches::rings_containing(geometry2, geometry1);
 267     }
 268 };
 269
 270 // P/*
 271
 272 struct use_point_in_geometry
 273 {
 274     template <typename Point, typename Geometry>
 275     static inline bool apply(Point const& point, Geometry const& geometry)
 276     {
 277         return detail::within::point_in_geometry(point, geometry) == 0;
 278     }
 279 };
 280
 281 }}
 282 #endif // DOXYGEN_NO_DETAIL
 283
 284 #ifndef DOXYGEN_NO_DISPATCH
 285 namespace dispatch {
 286
 287 // TODO: Since CastedTags are used is Reverse needed?
 288
 289 template
 290 <
 291     typename Geometry1, typename Geometry2,
 292     typename Tag1 = typename tag<Geometry1>::type,
 293     typename Tag2 = typename tag<Geometry2>::type,
 294     typename CastedTag1 = typename tag_cast<Tag1, pointlike_tag, linear_tag, areal_tag>::type,
 295     typename CastedTag2 = typename tag_cast<Tag2, pointlike_tag, linear_tag, areal_tag>::type,
 296     bool Reverse = reverse_dispatch<Geometry1, Geometry2>::type::value
 297 >
 298 struct touches
 299     : not_implemented<Tag1, Tag2>
 300 {};
 301
 302 // If reversal is needed, perform it
 303 template
 304 <
 305     typename Geometry1, typename Geometry2,
 306     typename Tag1, typename Tag2,
 307     typename CastedTag1, typename CastedTag2
 308 >
 309 struct touches<Geometry1, Geometry2, Tag1, Tag2, CastedTag1, CastedTag2, true>
 310     : touches<Geometry2, Geometry1, Tag2, Tag1, CastedTag2, CastedTag1, false>
 311 {
 312     static inline bool apply(Geometry1 const& g1, Geometry2 const& g2)
 313     {
 314         return touches<Geometry2, Geometry1>::apply(g2, g1);
 315     }
 316 };
 317
 318 // P/P
 319
 320 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2>
 321 struct touches<Geometry1, Geometry2, Tag1, Tag2, pointlike_tag, pointlike_tag, false>
 322 {
 323     static inline bool apply(Geometry1 const& , Geometry2 const& )
 324     {
 325         return false;
 326     }
 327 };
 328
 329 // P/*
 330
 331 template <typename Point, typename Geometry, typename Tag2, typename CastedTag2>
 332 struct touches<Point, Geometry, point_tag, Tag2, pointlike_tag, CastedTag2, false>
 333     : detail::touches::use_point_in_geometry
 334 {};
 335
 336 // TODO: support touches(MPt, Linear/Areal)
 337
 338 // Box/Box
 339
 340 template <typename Box1, typename Box2, typename CastedTag1, typename CastedTag2>
 341 struct touches<Box1, Box2, box_tag, box_tag, CastedTag1, CastedTag2, false>
 342     : detail::touches::box_box
 343 {};
 344
 345 template <typename Box1, typename Box2>
 346 struct touches<Box1, Box2, box_tag, box_tag, areal_tag, areal_tag, false>
 347     : detail::touches::box_box
 348 {};
 349
 350 // L/L
 351
 352 template <typename Linear1, typename Linear2, typename Tag1, typename Tag2>
 353 struct touches<Linear1, Linear2, Tag1, Tag2, linear_tag, linear_tag, false>
 354     : detail::relate::relate_impl
 355     <
 356         detail::de9im::static_mask_touches_type,
 357         Linear1,
 358         Linear2
 359     >
 360 {};
 361
 362 // L/A
 363
 364 template <typename Linear, typename Areal, typename Tag1, typename Tag2>
 365 struct touches<Linear, Areal, Tag1, Tag2, linear_tag, areal_tag, false>
 366     : detail::relate::relate_impl
 367     <
 368         detail::de9im::static_mask_touches_type,
 369         Linear,
 370         Areal
 371     >
 372 {};
 373
 374 // A/L
 375 template <typename Linear, typename Areal, typename Tag1, typename Tag2>
 376 struct touches<Areal, Linear, Tag1, Tag2, areal_tag, linear_tag, false>
 377     : detail::relate::relate_impl
 378     <
 379         detail::de9im::static_mask_touches_type,
 380         Areal,
 381         Linear
 382     >
 383 {};
 384
 385 // A/A
 386
 387 template <typename Areal1, typename Areal2, typename Tag1, typename Tag2>
 388 struct touches<Areal1, Areal2, Tag1, Tag2, areal_tag, areal_tag, false>
 389     : detail::relate::relate_impl
 390         <
 391             detail::de9im::static_mask_touches_type,
 392             Areal1,
 393             Areal2
 394         >
 395 {};
 396
 397 template <typename Areal1, typename Areal2>
 398 struct touches<Areal1, Areal2, ring_tag, ring_tag, areal_tag, areal_tag, false>
 399     : detail::touches::areal_areal<Areal1, Areal2>
 400 {};
 401
 402 } // namespace dispatch
 403 #endif // DOXYGEN_NO_DISPATCH
 404
 405
 406 namespace resolve_variant {
 407
 408 template <typename Geometry1, typename Geometry2>
 409 struct touches
 410 {
 411     static bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2)
 412     {
 413         concepts::check<Geometry1 const>();
 414         concepts::check<Geometry2 const>();
 415
 416         return dispatch::touches<Geometry1, Geometry2>
 417                        ::apply(geometry1, geometry2);
 418     }
 419 };
 420
 421 template <BOOST_VARIANT_ENUM_PARAMS(typename T), typename Geometry2>
 422 struct touches<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>, Geometry2>
 423 {
 424     struct visitor: boost::static_visitor<bool>
 425     {
 426         Geometry2 const& m_geometry2;
 427
 428         visitor(Geometry2 const& geometry2): m_geometry2(geometry2) {}
 429
 430         template <typename Geometry1>
 431         bool operator()(Geometry1 const& geometry1) const
 432         {
 433             return touches<Geometry1, Geometry2>::apply(geometry1, m_geometry2);
 434         }
 435     };
 436
 437     static inline bool
 438     apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry1,
 439           Geometry2 const& geometry2)
 440     {
 441         return boost::apply_visitor(visitor(geometry2), geometry1);
 442     }
 443 };
 444
 445 template <typename Geometry1, BOOST_VARIANT_ENUM_PARAMS(typename T)>
 446 struct touches<Geometry1, boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
 447 {
 448     struct visitor: boost::static_visitor<bool>
 449     {
 450         Geometry1 const& m_geometry1;
 451
 452         visitor(Geometry1 const& geometry1): m_geometry1(geometry1) {}
 453
 454         template <typename Geometry2>
 455         bool operator()(Geometry2 const& geometry2) const
 456         {
 457             return touches<Geometry1, Geometry2>::apply(m_geometry1, geometry2);
 458         }
 459     };
 460
 461     static inline bool
 462     apply(Geometry1 const& geometry1,
 463           boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry2)
 464     {
 465         return boost::apply_visitor(visitor(geometry1), geometry2);
 466     }
 467 };
 468
 469 template <BOOST_VARIANT_ENUM_PARAMS(typename T1),
 470           BOOST_VARIANT_ENUM_PARAMS(typename T2)>
 471 struct touches<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T1)>,
 472                boost::variant<BOOST_VARIANT_ENUM_PARAMS(T2)> >
 473 {
 474     struct visitor: boost::static_visitor<bool>
 475     {
 476         template <typename Geometry1, typename Geometry2>
 477         bool operator()(Geometry1 const& geometry1,
 478                         Geometry2 const& geometry2) const
 479         {
 480             return touches<Geometry1, Geometry2>::apply(geometry1, geometry2);
 481         }
 482     };
 483
 484     static inline bool
 485     apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T1)> const& geometry1,
 486           boost::variant<BOOST_VARIANT_ENUM_PARAMS(T2)> const& geometry2)
 487     {
 488         return boost::apply_visitor(visitor(), geometry1, geometry2);
 489     }
 490 };
 491
 492 template <typename Geometry>
 493 struct self_touches
 494 {
 495     static bool apply(Geometry const& geometry)
 496     {
 497         concepts::check<Geometry const>();
 498
 499         typedef detail::no_rescale_policy rescale_policy_type;
 500         typedef typename geometry::point_type<Geometry>::type point_type;
 501         typedef detail::overlay::turn_info
 502             <
 503                 point_type,
 504                 typename segment_ratio_type<point_type, rescale_policy_type>::type
 505             > turn_info;
 506
 507         typedef detail::overlay::get_turn_info
 508         <
 509             detail::overlay::assign_null_policy
 510         > policy_type;
 511
 512         std::deque<turn_info> turns;
 513         detail::touches::areal_interrupt_policy policy;
 514         rescale_policy_type robust_policy;
 515         detail::self_get_turn_points::get_turns
 516         <
 517             policy_type
 518         >::apply(geometry, robust_policy, turns, policy);
 519
 520         return policy.result();
 521     }
 522 };
 523
 524 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
 525 struct self_touches<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
 526 {
 527     struct visitor: boost::static_visitor<bool>
 528     {
 529         template <typename Geometry>
 530         bool operator()(Geometry const& geometry) const
 531         {
 532             return self_touches<Geometry>::apply(geometry);
 533         }
 534     };
 535
 536     static inline bool
 537     apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry)
 538     {
 539         return boost::apply_visitor(visitor(), geometry);
 540     }
 541 };
 542
 543 } // namespace resolve_variant
 544
 545
 546 /*!
 547 \brief \brief_check{has at least one touching point (self-tangency)}
 548 \note This function can be called for one geometry (self-tangency) and
 549     also for two geometries (touch)
 550 \ingroup touches
 551 \tparam Geometry \tparam_geometry
 552 \param geometry \param_geometry
 553 \return \return_check{is self-touching}
 554
 555 \qbk{distinguish,one geometry}
 556 \qbk{[def __one_parameter__]}
 557 \qbk{[include reference/algorithms/touches.qbk]}
 558 */
 559 template <typename Geometry>
 560 inline bool touches(Geometry const& geometry)
 561 {
 562     return resolve_variant::self_touches<Geometry>::apply(geometry);
 563 }
 564
 565
 566 /*!
 567 \brief \brief_check2{have at least one touching point (tangent - non overlapping)}
 568 \ingroup touches
 569 \tparam Geometry1 \tparam_geometry
 570 \tparam Geometry2 \tparam_geometry
 571 \param geometry1 \param_geometry
 572 \param geometry2 \param_geometry
 573 \return \return_check2{touch each other}
 574
 575 \qbk{distinguish,two geometries}
 576 \qbk{[include reference/algorithms/touches.qbk]}
 577  */
 578 template <typename Geometry1, typename Geometry2>
 579 inline bool touches(Geometry1 const& geometry1, Geometry2 const& geometry2)
 580 {
 581     return resolve_variant::touches<Geometry1, Geometry2>::apply(geometry1, geometry2);
 582 }
 583
 584
 585 }} // namespace boost::geometry
 586
 587 #endif // BOOST_GEOMETRY_ALGORITHMS_TOUCHES_HPP