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, 2014, 2015, 2017.
   9 // Modifications copyright (c) 2013-2017, 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 detail::no_rescale_policy rescale_policy_type;
 258         typedef typename geometry::point_type<Geometry1>::type point_type;
 259         typedef detail::overlay::turn_info
 260             <
 261                 point_type,
 262                 typename segment_ratio_type<point_type, rescale_policy_type>::type
 263             > turn_info;
 264
 265         std::deque<turn_info> turns;
 266         detail::touches::areal_interrupt_policy policy;
 267         rescale_policy_type robust_policy;
 268         boost::geometry::get_turns
 269                 <
 270                     detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
 271                     detail::overlay::do_reverse<geometry::point_order<Geometry2>::value>::value,
 272                     detail::overlay::assign_null_policy
 273                 >(geometry1, geometry2, strategy, robust_policy, turns, policy);
 274
 275         return policy.result()
 276             && ! geometry::detail::touches::rings_containing(geometry1, geometry2, strategy)
 277             && ! geometry::detail::touches::rings_containing(geometry2, geometry1, strategy);
 278     }
 279 };
 280
 281 // P/*
 282
 283 struct use_point_in_geometry
 284 {
 285     template <typename Point, typename Geometry, typename Strategy>
 286     static inline bool apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
 287     {
 288         return detail::within::point_in_geometry(point, geometry, strategy) == 0;
 289     }
 290 };
 291
 292
 293 }}
 294 #endif // DOXYGEN_NO_DETAIL
 295
 296 #ifndef DOXYGEN_NO_DISPATCH
 297 namespace dispatch {
 298
 299 // P/P
 300
 301 template <typename Geometry1, typename Geometry2, typename Tag2>
 302 struct touches<Geometry1, Geometry2, point_tag, Tag2, pointlike_tag, pointlike_tag, false>
 303 {
 304     template <typename Strategy>
 305     static inline bool apply(Geometry1 const& , Geometry2 const& , Strategy const&)
 306     {
 307         return false;
 308     }
 309 };
 310
 311 template <typename Geometry1, typename Geometry2, typename Tag2>
 312 struct touches<Geometry1, Geometry2, multi_point_tag, Tag2, pointlike_tag, pointlike_tag, false>
 313 {
 314     template <typename Strategy>
 315     static inline bool apply(Geometry1 const&, Geometry2 const&, Strategy const&)
 316     {
 317         return false;
 318     }
 319 };
 320
 321 // P/*
 322
 323 template <typename Point, typename Geometry, typename Tag2, typename CastedTag2>
 324 struct touches<Point, Geometry, point_tag, Tag2, pointlike_tag, CastedTag2, false>
 325     : detail::touches::use_point_in_geometry
 326 {};
 327
 328 template <typename MultiPoint, typename MultiGeometry, typename Tag2, typename CastedTag2>
 329 struct touches<MultiPoint, MultiGeometry, multi_point_tag, Tag2, pointlike_tag, CastedTag2, false>
 330     : detail::relate::relate_impl
 331         <
 332             detail::de9im::static_mask_touches_type,
 333             MultiPoint,
 334             MultiGeometry
 335         >
 336 {};
 337
 338 template <typename Geometry, typename MultiPoint, typename Tag1, typename CastedTag1>
 339 struct touches<Geometry, MultiPoint, Tag1, multi_point_tag, CastedTag1, pointlike_tag, false>
 340     : detail::relate::relate_impl
 341         <
 342             detail::de9im::static_mask_touches_type,
 343             Geometry,
 344             MultiPoint
 345         >
 346 {};
 347
 348 // Box/Box
 349
 350 template <typename Box1, typename Box2, typename CastedTag1, typename CastedTag2>
 351 struct touches<Box1, Box2, box_tag, box_tag, CastedTag1, CastedTag2, false>
 352     : detail::touches::box_box
 353 {};
 354
 355 template <typename Box1, typename Box2>
 356 struct touches<Box1, Box2, box_tag, box_tag, areal_tag, areal_tag, false>
 357     : detail::touches::box_box
 358 {};
 359
 360 // L/L
 361
 362 template <typename Linear1, typename Linear2, typename Tag1, typename Tag2>
 363 struct touches<Linear1, Linear2, Tag1, Tag2, linear_tag, linear_tag, false>
 364     : detail::relate::relate_impl
 365     <
 366         detail::de9im::static_mask_touches_type,
 367         Linear1,
 368         Linear2
 369     >
 370 {};
 371
 372 // L/A
 373
 374 template <typename Linear, typename Areal, typename Tag1, typename Tag2>
 375 struct touches<Linear, Areal, Tag1, Tag2, linear_tag, areal_tag, false>
 376     : detail::relate::relate_impl
 377     <
 378         detail::de9im::static_mask_touches_type,
 379         Linear,
 380         Areal
 381     >
 382 {};
 383
 384 // A/L
 385 template <typename Linear, typename Areal, typename Tag1, typename Tag2>
 386 struct touches<Areal, Linear, Tag1, Tag2, areal_tag, linear_tag, false>
 387     : detail::relate::relate_impl
 388     <
 389         detail::de9im::static_mask_touches_type,
 390         Areal,
 391         Linear
 392     >
 393 {};
 394
 395 // A/A
 396
 397 template <typename Areal1, typename Areal2, typename Tag1, typename Tag2>
 398 struct touches<Areal1, Areal2, Tag1, Tag2, areal_tag, areal_tag, false>
 399     : detail::relate::relate_impl
 400         <
 401             detail::de9im::static_mask_touches_type,
 402             Areal1,
 403             Areal2
 404         >
 405 {};
 406
 407 template <typename Areal1, typename Areal2>
 408 struct touches<Areal1, Areal2, ring_tag, ring_tag, areal_tag, areal_tag, false>
 409     : detail::touches::areal_areal<Areal1, Areal2>
 410 {};
 411
 412 } // namespace dispatch
 413 #endif // DOXYGEN_NO_DISPATCH
 414
 415
 416 namespace resolve_variant
 417 {
 418
 419 template <typename Geometry>
 420 struct self_touches
 421 {
 422     static bool apply(Geometry const& geometry)
 423     {
 424         concepts::check<Geometry const>();
 425
 426         typedef typename strategy::relate::services::default_strategy
 427             <
 428                 Geometry, Geometry
 429             >::type strategy_type;
 430         typedef detail::no_rescale_policy rescale_policy_type;
 431         typedef typename geometry::point_type<Geometry>::type point_type;
 432         typedef detail::overlay::turn_info
 433             <
 434                 point_type,
 435                 typename segment_ratio_type<point_type, rescale_policy_type>::type
 436             > turn_info;
 437
 438         typedef detail::overlay::get_turn_info
 439         <
 440             detail::overlay::assign_null_policy
 441         > policy_type;
 442
 443         std::deque<turn_info> turns;
 444         detail::touches::areal_interrupt_policy policy;
 445         strategy_type strategy;
 446         rescale_policy_type robust_policy;
 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, robust_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