boost/geometry/algorithms/touches.hpp

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