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 #include <boost/geometry/strategies/relate/cartesian.hpp>
  40 #include <boost/geometry/strategies/relate/geographic.hpp>
  41 #include <boost/geometry/strategies/relate/spherical.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, typename Strategy>
 108     static inline bool apply(Box1 const& b1, Box2 const& b2, Strategy const& /*strategy*/)
 109     {
 110         BOOST_STATIC_ASSERT((std::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_start :
 189                 case overlay::method_none :
 190                 case overlay::method_disjoint :
 191                 case overlay::method_error :
 192                     break;
 193             }
 194         }
 195
 196         return false;
 197     }
 198
 199     template <typename Turn>
 200     inline bool ok_for_touch(Turn const& turn)
 201     {
 202         return turn.both(overlay::operation_union)
 203             || turn.both(overlay::operation_blocked)
 204             || turn.combination(overlay::operation_union, overlay::operation_blocked)
 205             ;
 206     }
 207 };
 208
 209 template <typename Geometry1, typename Geometry2, typename Strategy>
 210 inline bool point_on_border_within(Geometry1 const& geometry1,
 211                                    Geometry2 const& geometry2,
 212                                    Strategy const& strategy)
 213 {
 214     typename geometry::point_type<Geometry1>::type pt;
 215     return geometry::point_on_border(pt, geometry1)
 216         && geometry::within(pt, geometry2, strategy);
 217 }
 218
 219 template <typename FirstGeometry, typename SecondGeometry, typename Strategy>
 220 inline bool rings_containing(FirstGeometry const& geometry1,
 221                              SecondGeometry const& geometry2,
 222                              Strategy const& strategy)
 223 {
 224     return geometry::detail::any_range_of(geometry2, [&](auto const& range)
 225     {
 226         return point_on_border_within(range, geometry1, strategy);
 227     });
 228 }
 229
 230 template <typename Geometry1, typename Geometry2>
 231 struct areal_areal
 232 {
 233     template <typename Strategy>
 234     static inline bool apply(Geometry1 const& geometry1,
 235                              Geometry2 const& geometry2,
 236                              Strategy const& strategy)
 237     {
 238         typedef typename geometry::point_type<Geometry1>::type point_type;
 239         typedef detail::overlay::turn_info<point_type> turn_info;
 240
 241         std::deque<turn_info> turns;
 242         detail::touches::areal_interrupt_policy policy;
 243         geometry::get_turns
 244             <
 245                 detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
 246                 detail::overlay::do_reverse<geometry::point_order<Geometry2>::value>::value,
 247                 detail::overlay::assign_null_policy
 248             >(geometry1, geometry2, strategy, detail::no_rescale_policy(), turns, policy);
 249
 250         return policy.result()
 251             && ! geometry::detail::touches::rings_containing(geometry1, geometry2, strategy)
 252             && ! geometry::detail::touches::rings_containing(geometry2, geometry1, strategy);
 253     }
 254 };
 255
 256 // P/*
 257
 258 struct use_point_in_geometry
 259 {
 260     template <typename Point, typename Geometry, typename Strategy>
 261     static inline bool apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
 262     {
 263         return detail::within::point_in_geometry(point, geometry, strategy) == 0;
 264     }
 265 };
 266
 267
 268 }}
 269 #endif // DOXYGEN_NO_DETAIL
 270
 271 #ifndef DOXYGEN_NO_DISPATCH
 272 namespace dispatch {
 273
 274 // P/P
 275
 276 template <typename Geometry1, typename Geometry2>
 277 struct touches<Geometry1, Geometry2, point_tag, point_tag, pointlike_tag, pointlike_tag, false>
 278 {
 279     template <typename Strategy>
 280     static inline bool apply(Geometry1 const& , Geometry2 const& , Strategy const&)
 281     {
 282         return false;
 283     }
 284 };
 285
 286 template <typename Geometry1, typename Geometry2>
 287 struct touches<Geometry1, Geometry2, point_tag, multi_point_tag, pointlike_tag, pointlike_tag, false>
 288 {
 289     template <typename Strategy>
 290     static inline bool apply(Geometry1 const& , Geometry2 const& , Strategy const&)
 291     {
 292         return false;
 293     }
 294 };
 295
 296 template <typename Geometry1, typename Geometry2>
 297 struct touches<Geometry1, Geometry2, multi_point_tag, multi_point_tag, pointlike_tag, pointlike_tag, false>
 298 {
 299     template <typename Strategy>
 300     static inline bool apply(Geometry1 const&, Geometry2 const&, Strategy const&)
 301     {
 302         return false;
 303     }
 304 };
 305
 306 // P/L P/A
 307
 308 template <typename Point, typename Geometry, typename Tag2, typename CastedTag2>
 309 struct touches<Point, Geometry, point_tag, Tag2, pointlike_tag, CastedTag2, false>
 310     : detail::touches::use_point_in_geometry
 311 {};
 312
 313 template <typename MultiPoint, typename MultiGeometry, typename Tag2, typename CastedTag2>
 314 struct touches<MultiPoint, MultiGeometry, multi_point_tag, Tag2, pointlike_tag, CastedTag2, false>
 315     : detail::relate::relate_impl
 316         <
 317             detail::de9im::static_mask_touches_type,
 318             MultiPoint,
 319             MultiGeometry
 320         >
 321 {};
 322
 323 // L/P A/P
 324
 325 template <typename Geometry, typename MultiPoint, typename Tag1, typename CastedTag1>
 326 struct touches<Geometry, MultiPoint, Tag1, multi_point_tag, CastedTag1, pointlike_tag, false>
 327     : detail::relate::relate_impl
 328         <
 329             detail::de9im::static_mask_touches_type,
 330             Geometry,
 331             MultiPoint
 332         >
 333 {};
 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_impl
 352     <
 353         detail::de9im::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_impl
 364     <
 365         detail::de9im::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<Areal, Linear, Tag1, Tag2, areal_tag, linear_tag, false>
 374     : detail::relate::relate_impl
 375     <
 376         detail::de9im::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::relate::relate_impl
 387         <
 388             detail::de9im::static_mask_touches_type,
 389             Areal1,
 390             Areal2
 391         >
 392 {};
 393
 394 template <typename Areal1, typename Areal2>
 395 struct touches<Areal1, Areal2, ring_tag, ring_tag, areal_tag, areal_tag, false>
 396     : detail::touches::areal_areal<Areal1, Areal2>
 397 {};
 398
 399 } // namespace dispatch
 400 #endif // DOXYGEN_NO_DISPATCH
 401
 402
 403 namespace resolve_variant
 404 {
 405
 406 template <typename Geometry>
 407 struct self_touches
 408 {
 409     static bool apply(Geometry const& geometry)
 410     {
 411         concepts::check<Geometry const>();
 412
 413         typedef typename strategies::relate::services::default_strategy
 414             <
 415                 Geometry, Geometry
 416             >::type strategy_type;
 417         typedef typename geometry::point_type<Geometry>::type point_type;
 418         typedef detail::overlay::turn_info<point_type> turn_info;
 419
 420         typedef detail::overlay::get_turn_info
 421             <
 422                 detail::overlay::assign_null_policy
 423             > policy_type;
 424
 425         std::deque<turn_info> turns;
 426         detail::touches::areal_interrupt_policy policy;
 427         strategy_type strategy;
 428         // TODO: skip_adjacent should be set to false
 429         detail::self_get_turn_points::get_turns
 430             <
 431                 false, policy_type
 432             >::apply(geometry, strategy, detail::no_rescale_policy(),
 433                      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