detail/touches/implementation.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
0005 // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
0006 // Copyright (c) 2013-2022 Adam Wulkiewicz, Lodz, Poland.
0007
0008 // This file was modified by Oracle on 2013-2022.
0009 // Modifications copyright (c) 2013-2022, Oracle and/or its affiliates.
0010
0011 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0012
0013 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
0014 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
0015
0016 // Use, modification and distribution is subject to the Boost Software License,
0017 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0018 // http://www.boost.org/LICENSE_1_0.txt)
0019
0020 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_TOUCHES_IMPLEMENTATION_HPP
0021 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_TOUCHES_IMPLEMENTATION_HPP
0022
0023
0024 #include <type_traits>
0025
0026 #include <boost/geometry/algorithms/detail/for_each_range.hpp>
0027 #include <boost/geometry/algorithms/detail/gc_topological_dimension.hpp>
0028 #include <boost/geometry/algorithms/detail/overlay/overlay.hpp>
0029 #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
0030 #include <boost/geometry/algorithms/detail/sub_range.hpp>
0031 #include <boost/geometry/algorithms/detail/relate/implementation.hpp>
0032 #include <boost/geometry/algorithms/detail/relate/implementation_gc.hpp>
0033 #include <boost/geometry/algorithms/detail/relate/relate_impl.hpp>
0034 #include <boost/geometry/algorithms/detail/touches/interface.hpp>
0035 #include <boost/geometry/algorithms/detail/visit.hpp>
0036 #include <boost/geometry/algorithms/disjoint.hpp>
0037 #include <boost/geometry/algorithms/intersects.hpp>
0038 #include <boost/geometry/algorithms/num_geometries.hpp>
0039
0040 #include <boost/geometry/geometries/helper_geometry.hpp>
0041
0042 #include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
0043
0044 #include <boost/geometry/strategies/relate/cartesian.hpp>
0045 #include <boost/geometry/strategies/relate/geographic.hpp>
0046 #include <boost/geometry/strategies/relate/spherical.hpp>
0047
0048 #include <boost/geometry/views/detail/geometry_collection_view.hpp>
0049
0050
0051 namespace boost { namespace geometry
0052 {
0053
0054 #ifndef DOXYGEN_NO_DETAIL
0055 namespace detail { namespace touches
0056 {
0057
0058 // Box/Box
0059
0060 template
0061 <
0062     std::size_t Dimension,
0063     std::size_t DimensionCount
0064 >
0065 struct box_box_loop
0066 {
0067     template <typename Box1, typename Box2>
0068     static inline bool apply(Box1 const& b1, Box2 const& b2, bool & touch)
0069     {
0070         typedef typename coordinate_type<Box1>::type coordinate_type1;
0071         typedef typename coordinate_type<Box2>::type coordinate_type2;
0072
0073         coordinate_type1 const& min1 = get<min_corner, Dimension>(b1);
0074         coordinate_type1 const& max1 = get<max_corner, Dimension>(b1);
0075         coordinate_type2 const& min2 = get<min_corner, Dimension>(b2);
0076         coordinate_type2 const& max2 = get<max_corner, Dimension>(b2);
0077
0078         // TODO assert or exception?
0079         //BOOST_GEOMETRY_ASSERT(min1 <= max1 && min2 <= max2);
0080
0081         if (max1 < min2 || max2 < min1)
0082         {
0083             return false;
0084         }
0085
0086         if (max1 == min2 || max2 == min1)
0087         {
0088             touch = true;
0089         }
0090
0091         return box_box_loop
0092                 <
0093                     Dimension + 1,
0094                     DimensionCount
0095                 >::apply(b1, b2, touch);
0096     }
0097 };
0098
0099 template
0100 <
0101     std::size_t DimensionCount
0102 >
0103 struct box_box_loop<DimensionCount, DimensionCount>
0104 {
0105     template <typename Box1, typename Box2>
0106     static inline bool apply(Box1 const& , Box2 const&, bool &)
0107     {
0108         return true;
0109     }
0110 };
0111
0112 struct box_box
0113 {
0114     template <typename Box1, typename Box2, typename Strategy>
0115     static inline bool apply(Box1 const& b1, Box2 const& b2, Strategy const& /*strategy*/)
0116     {
0117         BOOST_STATIC_ASSERT((std::is_same
0118                                 <
0119                                     typename geometry::coordinate_system<Box1>::type,
0120                                     typename geometry::coordinate_system<Box2>::type
0121                                 >::value
0122                            ));
0123         assert_dimension_equal<Box1, Box2>();
0124
0125         bool touches = false;
0126         bool ok = box_box_loop
0127                     <
0128                         0,
0129                         dimension<Box1>::type::value
0130                     >::apply(b1, b2, touches);
0131
0132         return ok && touches;
0133     }
0134 };
0135
0136 // Areal/Areal
0137
0138 struct areal_interrupt_policy
0139 {
0140     static bool const enabled = true;
0141     bool found_touch;
0142     bool found_not_touch;
0143
0144     // dummy variable required by self_get_turn_points::get_turns
0145     static bool const has_intersections = false;
0146
0147     inline bool result()
0148     {
0149         return found_touch && !found_not_touch;
0150     }
0151
0152     inline areal_interrupt_policy()
0153         : found_touch(false), found_not_touch(false)
0154     {}
0155
0156     template <typename Range>
0157     inline bool apply(Range const& range)
0158     {
0159         // if already rejected (temp workaround?)
0160         if (found_not_touch)
0161         {
0162             return true;
0163         }
0164
0165         for (auto it = boost::begin(range); it != boost::end(range); ++it)
0166         {
0167             if (it->has(overlay::operation_intersection))
0168             {
0169                 found_not_touch = true;
0170                 return true;
0171             }
0172
0173             switch (it->method)
0174             {
0175                 case overlay::method_crosses:
0176                     found_not_touch = true;
0177                     return true;
0178                 case overlay::method_equal:
0179                     // Segment spatially equal means: at the right side
0180                     // the polygon internally overlaps. So return false.
0181                     found_not_touch = true;
0182                     return true;
0183                 case overlay::method_touch:
0184                 case overlay::method_touch_interior:
0185                 case overlay::method_collinear:
0186                     if ( ok_for_touch(*it) )
0187                     {
0188                         found_touch = true;
0189                     }
0190                     else
0191                     {
0192                         found_not_touch = true;
0193                         return true;
0194                     }
0195                     break;
0196                 case overlay::method_start :
0197                 case overlay::method_none :
0198                 case overlay::method_disjoint :
0199                 case overlay::method_error :
0200                     break;
0201             }
0202         }
0203
0204         return false;
0205     }
0206
0207     template <typename Turn>
0208     inline bool ok_for_touch(Turn const& turn)
0209     {
0210         return turn.both(overlay::operation_union)
0211             || turn.both(overlay::operation_blocked)
0212             || turn.combination(overlay::operation_union, overlay::operation_blocked)
0213             ;
0214     }
0215 };
0216
0217 template <typename Geometry1, typename Geometry2, typename Strategy>
0218 inline bool point_on_border_within(Geometry1 const& geometry1,
0219                                    Geometry2 const& geometry2,
0220                                    Strategy const& strategy)
0221 {
0222     using point_type = typename geometry::point_type<Geometry1>::type;
0223     typename helper_geometry<point_type>::type pt;
0224     return geometry::point_on_border(pt, geometry1)
0225         && geometry::within(pt, geometry2, strategy);
0226 }
0227
0228 template <typename FirstGeometry, typename SecondGeometry, typename Strategy>
0229 inline bool rings_containing(FirstGeometry const& geometry1,
0230                              SecondGeometry const& geometry2,
0231                              Strategy const& strategy)
0232 {
0233     return geometry::detail::any_range_of(geometry2, [&](auto const& range)
0234     {
0235         return point_on_border_within(range, geometry1, strategy);
0236     });
0237 }
0238
0239 template <typename Geometry1, typename Geometry2>
0240 struct areal_areal
0241 {
0242     template <typename Strategy>
0243     static inline bool apply(Geometry1 const& geometry1,
0244                              Geometry2 const& geometry2,
0245                              Strategy const& strategy)
0246     {
0247         using point_type = typename geometry::point_type<Geometry1>::type;
0248         using mutable_point_type = typename helper_geometry<point_type>::type;
0249         using turn_info = detail::overlay::turn_info<mutable_point_type>;
0250
0251         std::deque<turn_info> turns;
0252         detail::touches::areal_interrupt_policy policy;
0253         geometry::get_turns
0254             <
0255                 detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
0256                 detail::overlay::do_reverse<geometry::point_order<Geometry2>::value>::value,
0257                 detail::overlay::assign_null_policy
0258             >(geometry1, geometry2, strategy, detail::no_rescale_policy(), turns, policy);
0259
0260         return policy.result()
0261             && ! geometry::detail::touches::rings_containing(geometry1, geometry2, strategy)
0262             && ! geometry::detail::touches::rings_containing(geometry2, geometry1, strategy);
0263     }
0264 };
0265
0266 // P/*
0267
0268 struct use_point_in_geometry
0269 {
0270     template <typename Point, typename Geometry, typename Strategy>
0271     static inline bool apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
0272     {
0273         return detail::within::point_in_geometry(point, geometry, strategy) == 0;
0274     }
0275 };
0276
0277 // GC
0278
0279 struct gc_gc
0280 {
0281     template <typename Geometry1, typename Geometry2, typename Strategy>
0282     static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2,
0283                              Strategy const& strategy)
0284     {
0285         int const dimension1 = detail::gc_topological_dimension(geometry1);
0286         int const dimension2 = detail::gc_topological_dimension(geometry2);
0287
0288         if (dimension1 == 0 && dimension2 == 0)
0289         {
0290             return false;
0291         }
0292         else
0293         {
0294             return detail::relate::relate_impl
0295                 <
0296                     detail::de9im::static_mask_touches_not_pp_type,
0297                     Geometry1,
0298                     Geometry2
0299                 >::apply(geometry1, geometry2, strategy);
0300         }
0301     }
0302 };
0303
0304 struct notgc_gc
0305 {
0306     template <typename Geometry1, typename Geometry2, typename Strategy>
0307     static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2,
0308                              Strategy const& strategy)
0309     {
0310         using gc1_view_t = detail::geometry_collection_view<Geometry1>;
0311         return gc_gc::apply(gc1_view_t(geometry1), geometry2, strategy);
0312     }
0313 };
0314
0315 struct gc_notgc
0316 {
0317     template <typename Geometry1, typename Geometry2, typename Strategy>
0318     static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2,
0319                              Strategy const& strategy)
0320     {
0321         using gc2_view_t = detail::geometry_collection_view<Geometry2>;
0322         return gc_gc::apply(geometry1, gc2_view_t(geometry2), strategy);
0323     }
0324 };
0325
0326
0327 }}
0328 #endif // DOXYGEN_NO_DETAIL
0329
0330 #ifndef DOXYGEN_NO_DISPATCH
0331 namespace dispatch {
0332
0333 // P/P
0334
0335 template <typename Geometry1, typename Geometry2>
0336 struct touches<Geometry1, Geometry2, point_tag, point_tag, pointlike_tag, pointlike_tag, false>
0337 {
0338     template <typename Strategy>
0339     static inline bool apply(Geometry1 const& , Geometry2 const& , Strategy const&)
0340     {
0341         return false;
0342     }
0343 };
0344
0345 template <typename Geometry1, typename Geometry2>
0346 struct touches<Geometry1, Geometry2, point_tag, multi_point_tag, pointlike_tag, pointlike_tag, false>
0347 {
0348     template <typename Strategy>
0349     static inline bool apply(Geometry1 const& , Geometry2 const& , Strategy const&)
0350     {
0351         return false;
0352     }
0353 };
0354
0355 template <typename Geometry1, typename Geometry2>
0356 struct touches<Geometry1, Geometry2, multi_point_tag, multi_point_tag, pointlike_tag, pointlike_tag, false>
0357 {
0358     template <typename Strategy>
0359     static inline bool apply(Geometry1 const&, Geometry2 const&, Strategy const&)
0360     {
0361         return false;
0362     }
0363 };
0364
0365 // P/L P/A
0366
0367 template <typename Point, typename Geometry, typename Tag2, typename CastedTag2>
0368 struct touches<Point, Geometry, point_tag, Tag2, pointlike_tag, CastedTag2, false>
0369     : detail::touches::use_point_in_geometry
0370 {};
0371
0372 template <typename MultiPoint, typename MultiGeometry, typename Tag2, typename CastedTag2>
0373 struct touches<MultiPoint, MultiGeometry, multi_point_tag, Tag2, pointlike_tag, CastedTag2, false>
0374     : detail::relate::relate_impl
0375         <
0376             detail::de9im::static_mask_touches_type,
0377             MultiPoint,
0378             MultiGeometry
0379         >
0380 {};
0381
0382 // L/P A/P
0383
0384 template <typename Geometry, typename MultiPoint, typename Tag1, typename CastedTag1>
0385 struct touches<Geometry, MultiPoint, Tag1, multi_point_tag, CastedTag1, pointlike_tag, false>
0386     : detail::relate::relate_impl
0387         <
0388             detail::de9im::static_mask_touches_type,
0389             Geometry,
0390             MultiPoint
0391         >
0392 {};
0393
0394 // Box/Box
0395
0396 template <typename Box1, typename Box2, typename CastedTag1, typename CastedTag2>
0397 struct touches<Box1, Box2, box_tag, box_tag, CastedTag1, CastedTag2, false>
0398     : detail::touches::box_box
0399 {};
0400
0401 template <typename Box1, typename Box2>
0402 struct touches<Box1, Box2, box_tag, box_tag, areal_tag, areal_tag, false>
0403     : detail::touches::box_box
0404 {};
0405
0406 // L/L
0407
0408 template <typename Linear1, typename Linear2, typename Tag1, typename Tag2>
0409 struct touches<Linear1, Linear2, Tag1, Tag2, linear_tag, linear_tag, false>
0410     : detail::relate::relate_impl
0411     <
0412         detail::de9im::static_mask_touches_type,
0413         Linear1,
0414         Linear2
0415     >
0416 {};
0417
0418 // L/A
0419
0420 template <typename Linear, typename Areal, typename Tag1, typename Tag2>
0421 struct touches<Linear, Areal, Tag1, Tag2, linear_tag, areal_tag, false>
0422     : detail::relate::relate_impl
0423     <
0424         detail::de9im::static_mask_touches_type,
0425         Linear,
0426         Areal
0427     >
0428 {};
0429
0430 // A/L
0431 template <typename Linear, typename Areal, typename Tag1, typename Tag2>
0432 struct touches<Areal, Linear, Tag1, Tag2, areal_tag, linear_tag, false>
0433     : detail::relate::relate_impl
0434     <
0435         detail::de9im::static_mask_touches_type,
0436         Areal,
0437         Linear
0438     >
0439 {};
0440
0441 // A/A
0442
0443 template <typename Areal1, typename Areal2, typename Tag1, typename Tag2>
0444 struct touches<Areal1, Areal2, Tag1, Tag2, areal_tag, areal_tag, false>
0445     : detail::relate::relate_impl
0446         <
0447             detail::de9im::static_mask_touches_type,
0448             Areal1,
0449             Areal2
0450         >
0451 {};
0452
0453 template <typename Areal1, typename Areal2>
0454 struct touches<Areal1, Areal2, ring_tag, ring_tag, areal_tag, areal_tag, false>
0455     : detail::touches::areal_areal<Areal1, Areal2>
0456 {};
0457
0458 // GC
0459
0460 template <typename Geometry1, typename Geometry2>
0461 struct touches
0462     <
0463         Geometry1, Geometry2,
0464         geometry_collection_tag, geometry_collection_tag,
0465         geometry_collection_tag, geometry_collection_tag,
0466         false
0467     >
0468     : detail::touches::gc_gc
0469 {};
0470
0471
0472 template <typename Geometry1, typename Geometry2, typename Tag1, typename CastedTag1>
0473 struct touches
0474     <
0475         Geometry1, Geometry2,
0476         Tag1, geometry_collection_tag,
0477         CastedTag1, geometry_collection_tag,
0478         false
0479     >
0480     : detail::touches::notgc_gc
0481 {};
0482
0483
0484 template <typename Geometry1, typename Geometry2, typename Tag2, typename CastedTag2>
0485 struct touches
0486     <
0487         Geometry1, Geometry2,
0488         geometry_collection_tag, Tag2,
0489         geometry_collection_tag, CastedTag2,
0490         false
0491     >
0492     : detail::touches::gc_notgc
0493 {};
0494
0495
0496 } // namespace dispatch
0497 #endif // DOXYGEN_NO_DISPATCH
0498
0499
0500 namespace resolve_dynamic
0501 {
0502
0503 template <typename Geometry, typename Tag>
0504 struct self_touches
0505 {
0506     static bool apply(Geometry const& geometry)
0507     {
0508         concepts::check<Geometry const>();
0509
0510         typedef typename strategies::relate::services::default_strategy
0511             <
0512                 Geometry, Geometry
0513             >::type strategy_type;
0514         typedef typename geometry::point_type<Geometry>::type point_type;
0515         typedef detail::overlay::turn_info<point_type> turn_info;
0516
0517         typedef detail::overlay::get_turn_info
0518             <
0519                 detail::overlay::assign_null_policy
0520             > policy_type;
0521
0522         std::deque<turn_info> turns;
0523         detail::touches::areal_interrupt_policy policy;
0524         strategy_type strategy;
0525         // TODO: skip_adjacent should be set to false
0526         detail::self_get_turn_points::get_turns
0527             <
0528                 false, policy_type
0529             >::apply(geometry, strategy, detail::no_rescale_policy(),
0530                      turns, policy, 0, true);
0531
0532         return policy.result();
0533     }
0534 };
0535
0536 } // namespace resolve_dynamic
0537
0538 }} // namespace boost::geometry
0539
0540 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_TOUCHES_IMPLEMENTATION_HPP