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