ceph/src/boost/boost/geometry/algorithms/detail/touches/implementation.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-2020.
   9 // Modifications copyright (c) 2013-2020, 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_DETAIL_TOUCHES_IMPLEMENTATION_HPP
  21 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_TOUCHES_IMPLEMENTATION_HPP
  22
  23
  24 #include <type_traits>
  25
  26 #include <boost/geometry/algorithms/detail/for_each_range.hpp>
  27 #include <boost/geometry/algorithms/detail/overlay/overlay.hpp>
  28 #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
  29 #include <boost/geometry/algorithms/detail/sub_range.hpp>
  30 #include <boost/geometry/algorithms/detail/relate/relate_impl.hpp>
  31 #include <boost/geometry/algorithms/detail/touches/interface.hpp>
  32 #include <boost/geometry/algorithms/disjoint.hpp>
  33 #include <boost/geometry/algorithms/intersects.hpp>
  34 #include <boost/geometry/algorithms/num_geometries.hpp>
  35 #include <boost/geometry/algorithms/relate.hpp>
  36
  37 #include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
  38
  39
  40 namespace boost { namespace geometry
  41 {
  42
  43 #ifndef DOXYGEN_NO_DETAIL
  44 namespace detail { namespace touches
  45 {
  46
  47 // Box/Box
  48
  49 template
  50 <
  51     std::size_t Dimension,
  52     std::size_t DimensionCount
  53 >
  54 struct box_box_loop
  55 {
  56     template <typename Box1, typename Box2>
  57     static inline bool apply(Box1 const& b1, Box2 const& b2, bool & touch)
  58     {
  59         typedef typename coordinate_type<Box1>::type coordinate_type1;
  60         typedef typename coordinate_type<Box2>::type coordinate_type2;
  61
  62         coordinate_type1 const& min1 = get<min_corner, Dimension>(b1);
  63         coordinate_type1 const& max1 = get<max_corner, Dimension>(b1);
  64         coordinate_type2 const& min2 = get<min_corner, Dimension>(b2);
  65         coordinate_type2 const& max2 = get<max_corner, Dimension>(b2);
  66
  67         // TODO assert or exception?
  68         //BOOST_GEOMETRY_ASSERT(min1 <= max1 && min2 <= max2);
  69
  70         if (max1 < min2 || max2 < min1)
  71         {
  72             return false;
  73         }
  74
  75         if (max1 == min2 || max2 == min1)
  76         {
  77             touch = true;
  78         }
  79
  80         return box_box_loop
  81                 <
  82                     Dimension + 1,
  83                     DimensionCount
  84                 >::apply(b1, b2, touch);
  85     }
  86 };
  87
  88 template
  89 <
  90     std::size_t DimensionCount
  91 >
  92 struct box_box_loop<DimensionCount, DimensionCount>
  93 {
  94     template <typename Box1, typename Box2>
  95     static inline bool apply(Box1 const& , Box2 const&, bool &)
  96     {
  97         return true;
  98     }
  99 };
 100
 101 struct box_box
 102 {
 103     template <typename Box1, typename Box2, typename Strategy>
 104     static inline bool apply(Box1 const& b1, Box2 const& b2, Strategy const& /*strategy*/)
 105     {
 106         BOOST_STATIC_ASSERT((std::is_same
 107                                 <
 108                                     typename geometry::coordinate_system<Box1>::type,
 109                                     typename geometry::coordinate_system<Box2>::type
 110                                 >::value
 111                            ));
 112         assert_dimension_equal<Box1, Box2>();
 113
 114         bool touches = false;
 115         bool ok = box_box_loop
 116                     <
 117                         0,
 118                         dimension<Box1>::type::value
 119                     >::apply(b1, b2, touches);
 120
 121         return ok && touches;
 122     }
 123 };
 124
 125 // Areal/Areal
 126
 127 struct areal_interrupt_policy
 128 {
 129     static bool const enabled = true;
 130     bool found_touch;
 131     bool found_not_touch;
 132
 133     // dummy variable required by self_get_turn_points::get_turns
 134     static bool const has_intersections = false;
 135
 136     inline bool result()
 137     {
 138         return found_touch && !found_not_touch;
 139     }
 140
 141     inline areal_interrupt_policy()
 142         : found_touch(false), found_not_touch(false)
 143     {}
 144
 145     template <typename Range>
 146     inline bool apply(Range const& range)
 147     {
 148         // if already rejected (temp workaround?)
 149         if ( found_not_touch )
 150             return true;
 151
 152         typedef typename boost::range_iterator<Range const>::type iterator;
 153         for ( iterator it = boost::begin(range) ; it != boost::end(range) ; ++it )
 154         {
 155             if ( it->has(overlay::operation_intersection) )
 156             {
 157                 found_not_touch = true;
 158                 return true;
 159             }
 160
 161             switch(it->method)
 162             {
 163                 case overlay::method_crosses:
 164                     found_not_touch = true;
 165                     return true;
 166                 case overlay::method_equal:
 167                     // Segment spatially equal means: at the right side
 168                     // the polygon internally overlaps. So return false.
 169                     found_not_touch = true;
 170                     return true;
 171                 case overlay::method_touch:
 172                 case overlay::method_touch_interior:
 173                 case overlay::method_collinear:
 174                     if ( ok_for_touch(*it) )
 175                     {
 176                         found_touch = true;
 177                     }
 178                     else
 179                     {
 180                         found_not_touch = true;
 181                         return true;
 182                     }
 183                     break;
 184                 case overlay::method_start :
 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 Geometry1, typename Geometry2, typename Strategy>
 206 inline bool point_on_border_within(Geometry1 const& geometry1,
 207                                    Geometry2 const& geometry2,
 208                                    Strategy const& strategy)
 209 {
 210     typename geometry::point_type<Geometry1>::type pt;
 211     return geometry::point_on_border(pt, geometry1)
 212         && geometry::within(pt, geometry2, strategy);
 213 }
 214
 215 template <typename FirstGeometry, typename SecondGeometry, typename IntersectionStrategy>
 216 inline bool rings_containing(FirstGeometry const& geometry1,
 217                              SecondGeometry const& geometry2,
 218                              IntersectionStrategy const& strategy)
 219 {
 220     // TODO: This will be removed when IntersectionStrategy is replaced with
 221     //       UmbrellaStrategy
 222     auto const point_in_ring_strategy
 223         = strategy.template get_point_in_geometry_strategy<FirstGeometry, SecondGeometry>();
 224
 225     return geometry::detail::any_range_of(geometry2, [&](auto const& range)
 226     {
 227         return point_on_border_within(range, geometry1, point_in_ring_strategy);
 228     });
 229 }
 230
 231 template <typename Geometry1, typename Geometry2>
 232 struct areal_areal
 233 {
 234     template <typename IntersectionStrategy>
 235     static inline bool apply(Geometry1 const& geometry1,
 236                              Geometry2 const& geometry2,
 237                              IntersectionStrategy const& strategy)
 238     {
 239         typedef typename geometry::point_type<Geometry1>::type point_type;
 240         typedef detail::overlay::turn_info<point_type> turn_info;
 241
 242         std::deque<turn_info> turns;
 243         detail::touches::areal_interrupt_policy policy;
 244         boost::geometry::get_turns
 245                 <
 246                     detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
 247                     detail::overlay::do_reverse<geometry::point_order<Geometry2>::value>::value,
 248                     detail::overlay::assign_null_policy
 249                 >(geometry1, geometry2, strategy, detail::no_rescale_policy(), turns, policy);
 250
 251         return policy.result()
 252             && ! geometry::detail::touches::rings_containing(geometry1, geometry2, strategy)
 253             && ! geometry::detail::touches::rings_containing(geometry2, geometry1, strategy);
 254     }
 255 };
 256
 257 // P/*
 258
 259 struct use_point_in_geometry
 260 {
 261     template <typename Point, typename Geometry, typename Strategy>
 262     static inline bool apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
 263     {
 264         return detail::within::point_in_geometry(point, geometry, strategy) == 0;
 265     }
 266 };
 267
 268
 269 }}
 270 #endif // DOXYGEN_NO_DETAIL
 271
 272 #ifndef DOXYGEN_NO_DISPATCH
 273 namespace dispatch {
 274
 275 // P/P
 276
 277 template <typename Geometry1, typename Geometry2>
 278 struct touches<Geometry1, Geometry2, point_tag, point_tag, pointlike_tag, pointlike_tag, false>
 279 {
 280     template <typename Strategy>
 281     static inline bool apply(Geometry1 const& , Geometry2 const& , Strategy const&)
 282     {
 283         return false;
 284     }
 285 };
 286
 287 template <typename Geometry1, typename Geometry2>
 288 struct touches<Geometry1, Geometry2, point_tag, multi_point_tag, pointlike_tag, pointlike_tag, false>
 289 {
 290     template <typename Strategy>
 291     static inline bool apply(Geometry1 const& , Geometry2 const& , Strategy const&)
 292     {
 293         return false;
 294     }
 295 };
 296
 297 template <typename Geometry1, typename Geometry2>
 298 struct touches<Geometry1, Geometry2, multi_point_tag, multi_point_tag, pointlike_tag, pointlike_tag, false>
 299 {
 300     template <typename Strategy>
 301     static inline bool apply(Geometry1 const&, Geometry2 const&, Strategy const&)
 302     {
 303         return false;
 304     }
 305 };
 306
 307 // P/L P/A
 308
 309 template <typename Point, typename Geometry, typename Tag2, typename CastedTag2>
 310 struct touches<Point, Geometry, point_tag, Tag2, pointlike_tag, CastedTag2, false>
 311     : detail::touches::use_point_in_geometry
 312 {};
 313
 314 template <typename MultiPoint, typename MultiGeometry, typename Tag2, typename CastedTag2>
 315 struct touches<MultiPoint, MultiGeometry, multi_point_tag, Tag2, pointlike_tag, CastedTag2, false>
 316     : detail::relate::relate_impl
 317         <
 318             detail::de9im::static_mask_touches_type,
 319             MultiPoint,
 320             MultiGeometry
 321         >
 322 {};
 323
 324 // L/P A/P
 325
 326 template <typename Geometry, typename MultiPoint, typename Tag1, typename CastedTag1>
 327 struct touches<Geometry, MultiPoint, Tag1, multi_point_tag, CastedTag1, pointlike_tag, false>
 328     : detail::relate::relate_impl
 329         <
 330             detail::de9im::static_mask_touches_type,
 331             Geometry,
 332             MultiPoint
 333         >
 334 {};
 335
 336 // Box/Box
 337
 338 template <typename Box1, typename Box2, typename CastedTag1, typename CastedTag2>
 339 struct touches<Box1, Box2, box_tag, box_tag, CastedTag1, CastedTag2, false>
 340     : detail::touches::box_box
 341 {};
 342
 343 template <typename Box1, typename Box2>
 344 struct touches<Box1, Box2, box_tag, box_tag, areal_tag, areal_tag, false>
 345     : detail::touches::box_box
 346 {};
 347
 348 // L/L
 349
 350 template <typename Linear1, typename Linear2, typename Tag1, typename Tag2>
 351 struct touches<Linear1, Linear2, Tag1, Tag2, linear_tag, linear_tag, false>
 352     : detail::relate::relate_impl
 353     <
 354         detail::de9im::static_mask_touches_type,
 355         Linear1,
 356         Linear2
 357     >
 358 {};
 359
 360 // L/A
 361
 362 template <typename Linear, typename Areal, typename Tag1, typename Tag2>
 363 struct touches<Linear, Areal, Tag1, Tag2, linear_tag, areal_tag, false>
 364     : detail::relate::relate_impl
 365     <
 366         detail::de9im::static_mask_touches_type,
 367         Linear,
 368         Areal
 369     >
 370 {};
 371
 372 // A/L
 373 template <typename Linear, typename Areal, typename Tag1, typename Tag2>
 374 struct touches<Areal, Linear, Tag1, Tag2, areal_tag, linear_tag, false>
 375     : detail::relate::relate_impl
 376     <
 377         detail::de9im::static_mask_touches_type,
 378         Areal,
 379         Linear
 380     >
 381 {};
 382
 383 // A/A
 384
 385 template <typename Areal1, typename Areal2, typename Tag1, typename Tag2>
 386 struct touches<Areal1, Areal2, Tag1, Tag2, areal_tag, areal_tag, false>
 387     : detail::relate::relate_impl
 388         <
 389             detail::de9im::static_mask_touches_type,
 390             Areal1,
 391             Areal2
 392         >
 393 {};
 394
 395 template <typename Areal1, typename Areal2>
 396 struct touches<Areal1, Areal2, ring_tag, ring_tag, areal_tag, areal_tag, false>
 397     : detail::touches::areal_areal<Areal1, Areal2>
 398 {};
 399
 400 } // namespace dispatch
 401 #endif // DOXYGEN_NO_DISPATCH
 402
 403
 404 namespace resolve_variant
 405 {
 406
 407 template <typename Geometry>
 408 struct self_touches
 409 {
 410     static bool apply(Geometry const& geometry)
 411     {
 412         concepts::check<Geometry const>();
 413
 414         typedef typename strategy::relate::services::default_strategy
 415             <
 416                 Geometry, Geometry
 417             >::type strategy_type;
 418         typedef typename geometry::point_type<Geometry>::type point_type;
 419         typedef detail::overlay::turn_info<point_type> turn_info;
 420
 421         typedef detail::overlay::get_turn_info
 422         <
 423             detail::overlay::assign_null_policy
 424         > policy_type;
 425
 426         std::deque<turn_info> turns;
 427         detail::touches::areal_interrupt_policy policy;
 428         strategy_type strategy;
 429         // TODO: skip_adjacent should be set to false
 430         detail::self_get_turn_points::get_turns
 431         <
 432             false, policy_type
 433         >::apply(geometry, strategy, detail::no_rescale_policy(), turns, policy, 0, true);
 434
 435         return policy.result();
 436     }
 437 };
 438
 439 }
 440
 441 }} // namespace boost::geometry
 442
 443 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_TOUCHES_IMPLEMENTATION_HPP