1 // Boost.Geometry (aka GGL, Generic Geometry Library)
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.
8 // This file was modified by Oracle on 2013, 2014, 2015.
9 // Modifications copyright (c) 2013-2015, Oracle and/or its affiliates.
11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
13 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
14 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
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)
20 #ifndef BOOST_GEOMETRY_ALGORITHMS_TOUCHES_HPP
21 #define BOOST_GEOMETRY_ALGORITHMS_TOUCHES_HPP
26 #include <boost/variant/apply_visitor.hpp>
27 #include <boost/variant/static_visitor.hpp>
28 #include <boost/variant/variant_fwd.hpp>
30 #include <boost/geometry/geometries/concepts/check.hpp>
31 #include <boost/geometry/algorithms/detail/for_each_range.hpp>
32 #include <boost/geometry/algorithms/detail/overlay/overlay.hpp>
33 #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
34 #include <boost/geometry/algorithms/disjoint.hpp>
35 #include <boost/geometry/algorithms/intersects.hpp>
36 #include <boost/geometry/algorithms/num_geometries.hpp>
37 #include <boost/geometry/algorithms/detail/sub_range.hpp>
38 #include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
40 #include <boost/geometry/algorithms/relate.hpp>
41 #include <boost/geometry/algorithms/detail/relate/relate_impl.hpp>
44 namespace boost { namespace geometry
47 #ifndef DOXYGEN_NO_DETAIL
48 namespace detail { namespace touches
55 std::size_t Dimension,
56 std::size_t DimensionCount
60 template <typename Box1, typename Box2>
61 static inline bool apply(Box1 const& b1, Box2 const& b2, bool & touch)
63 typedef typename coordinate_type<Box1>::type coordinate_type1;
64 typedef typename coordinate_type<Box2>::type coordinate_type2;
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);
71 // TODO assert or exception?
72 //BOOST_GEOMETRY_ASSERT(min1 <= max1 && min2 <= max2);
74 if (max1 < min2 || max2 < min1)
79 if (max1 == min2 || max2 == min1)
88 >::apply(b1, b2, touch);
94 std::size_t DimensionCount
96 struct box_box_loop<DimensionCount, DimensionCount>
98 template <typename Box1, typename Box2>
99 static inline bool apply(Box1 const& , Box2 const&, bool &)
107 template <typename Box1, typename Box2>
108 static inline bool apply(Box1 const& b1, Box2 const& b2)
110 BOOST_STATIC_ASSERT((boost::is_same
112 typename geometry::coordinate_system<Box1>::type,
113 typename geometry::coordinate_system<Box2>::type
116 assert_dimension_equal<Box1, Box2>();
118 bool touches = false;
119 bool ok = box_box_loop
122 dimension<Box1>::type::value
123 >::apply(b1, b2, touches);
125 return ok && touches;
131 struct areal_interrupt_policy
133 static bool const enabled = true;
135 bool found_not_touch;
137 // dummy variable required by self_get_turn_points::get_turns
138 static bool const has_intersections = false;
142 return found_touch && !found_not_touch;
145 inline areal_interrupt_policy()
146 : found_touch(false), found_not_touch(false)
149 template <typename Range>
150 inline bool apply(Range const& range)
152 // if already rejected (temp workaround?)
153 if ( found_not_touch )
156 typedef typename boost::range_iterator<Range const>::type iterator;
157 for ( iterator it = boost::begin(range) ; it != boost::end(range) ; ++it )
159 if ( it->has(overlay::operation_intersection) )
161 found_not_touch = true;
167 case overlay::method_crosses:
168 found_not_touch = 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;
175 case overlay::method_touch:
176 case overlay::method_touch_interior:
177 case overlay::method_collinear:
178 if ( ok_for_touch(*it) )
184 found_not_touch = true;
188 case overlay::method_none :
189 case overlay::method_disjoint :
190 case overlay::method_error :
198 template <typename Turn>
199 inline bool ok_for_touch(Turn const& turn)
201 return turn.both(overlay::operation_union)
202 || turn.both(overlay::operation_blocked)
203 || turn.combination(overlay::operation_union, overlay::operation_blocked)
208 template<typename Geometry>
209 struct check_each_ring_for_within
212 Geometry const& m_geometry;
214 inline check_each_ring_for_within(Geometry const& g)
219 template <typename Range>
220 inline void apply(Range const& range)
222 typename geometry::point_type<Range>::type p;
223 geometry::point_on_border(p, range);
224 if ( !has_within && geometry::within(p, m_geometry) )
231 template <typename FirstGeometry, typename SecondGeometry>
232 inline bool rings_containing(FirstGeometry const& geometry1,
233 SecondGeometry const& geometry2)
235 check_each_ring_for_within<FirstGeometry> checker(geometry1);
236 geometry::detail::for_each_range(geometry2, checker);
237 return checker.has_within;
240 template <typename Geometry1, typename Geometry2>
244 bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2)
246 typedef detail::no_rescale_policy rescale_policy_type;
247 typedef typename geometry::point_type<Geometry1>::type point_type;
248 typedef detail::overlay::turn_info
251 typename segment_ratio_type<point_type, rescale_policy_type>::type
254 std::deque<turn_info> turns;
255 detail::touches::areal_interrupt_policy policy;
256 rescale_policy_type robust_policy;
257 boost::geometry::get_turns
259 detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
260 detail::overlay::do_reverse<geometry::point_order<Geometry2>::value>::value,
261 detail::overlay::assign_null_policy
262 >(geometry1, geometry2, robust_policy, turns, policy);
264 return policy.result()
265 && ! geometry::detail::touches::rings_containing(geometry1, geometry2)
266 && ! geometry::detail::touches::rings_containing(geometry2, geometry1);
272 struct use_point_in_geometry
274 template <typename Point, typename Geometry>
275 static inline bool apply(Point const& point, Geometry const& geometry)
277 return detail::within::point_in_geometry(point, geometry) == 0;
282 #endif // DOXYGEN_NO_DETAIL
284 #ifndef DOXYGEN_NO_DISPATCH
287 // TODO: Since CastedTags are used is Reverse needed?
291 typename Geometry1, typename Geometry2,
292 typename Tag1 = typename tag<Geometry1>::type,
293 typename Tag2 = typename tag<Geometry2>::type,
294 typename CastedTag1 = typename tag_cast<Tag1, pointlike_tag, linear_tag, areal_tag>::type,
295 typename CastedTag2 = typename tag_cast<Tag2, pointlike_tag, linear_tag, areal_tag>::type,
296 bool Reverse = reverse_dispatch<Geometry1, Geometry2>::type::value
299 : not_implemented<Tag1, Tag2>
302 // If reversal is needed, perform it
305 typename Geometry1, typename Geometry2,
306 typename Tag1, typename Tag2,
307 typename CastedTag1, typename CastedTag2
309 struct touches<Geometry1, Geometry2, Tag1, Tag2, CastedTag1, CastedTag2, true>
310 : touches<Geometry2, Geometry1, Tag2, Tag1, CastedTag2, CastedTag1, false>
312 static inline bool apply(Geometry1 const& g1, Geometry2 const& g2)
314 return touches<Geometry2, Geometry1>::apply(g2, g1);
320 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2>
321 struct touches<Geometry1, Geometry2, Tag1, Tag2, pointlike_tag, pointlike_tag, false>
323 static inline bool apply(Geometry1 const& , Geometry2 const& )
331 template <typename Point, typename Geometry, typename Tag2, typename CastedTag2>
332 struct touches<Point, Geometry, point_tag, Tag2, pointlike_tag, CastedTag2, false>
333 : detail::touches::use_point_in_geometry
336 // TODO: support touches(MPt, Linear/Areal)
340 template <typename Box1, typename Box2, typename CastedTag1, typename CastedTag2>
341 struct touches<Box1, Box2, box_tag, box_tag, CastedTag1, CastedTag2, false>
342 : detail::touches::box_box
345 template <typename Box1, typename Box2>
346 struct touches<Box1, Box2, box_tag, box_tag, areal_tag, areal_tag, false>
347 : detail::touches::box_box
352 template <typename Linear1, typename Linear2, typename Tag1, typename Tag2>
353 struct touches<Linear1, Linear2, Tag1, Tag2, linear_tag, linear_tag, false>
354 : detail::relate::relate_impl
356 detail::de9im::static_mask_touches_type,
364 template <typename Linear, typename Areal, typename Tag1, typename Tag2>
365 struct touches<Linear, Areal, Tag1, Tag2, linear_tag, areal_tag, false>
366 : detail::relate::relate_impl
368 detail::de9im::static_mask_touches_type,
375 template <typename Linear, typename Areal, typename Tag1, typename Tag2>
376 struct touches<Areal, Linear, Tag1, Tag2, areal_tag, linear_tag, false>
377 : detail::relate::relate_impl
379 detail::de9im::static_mask_touches_type,
387 template <typename Areal1, typename Areal2, typename Tag1, typename Tag2>
388 struct touches<Areal1, Areal2, Tag1, Tag2, areal_tag, areal_tag, false>
389 : detail::relate::relate_impl
391 detail::de9im::static_mask_touches_type,
397 template <typename Areal1, typename Areal2>
398 struct touches<Areal1, Areal2, ring_tag, ring_tag, areal_tag, areal_tag, false>
399 : detail::touches::areal_areal<Areal1, Areal2>
402 } // namespace dispatch
403 #endif // DOXYGEN_NO_DISPATCH
406 namespace resolve_variant {
408 template <typename Geometry1, typename Geometry2>
411 static bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2)
413 concepts::check<Geometry1 const>();
414 concepts::check<Geometry2 const>();
416 return dispatch::touches<Geometry1, Geometry2>
417 ::apply(geometry1, geometry2);
421 template <BOOST_VARIANT_ENUM_PARAMS(typename T), typename Geometry2>
422 struct touches<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>, Geometry2>
424 struct visitor: boost::static_visitor<bool>
426 Geometry2 const& m_geometry2;
428 visitor(Geometry2 const& geometry2): m_geometry2(geometry2) {}
430 template <typename Geometry1>
431 bool operator()(Geometry1 const& geometry1) const
433 return touches<Geometry1, Geometry2>::apply(geometry1, m_geometry2);
438 apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry1,
439 Geometry2 const& geometry2)
441 return boost::apply_visitor(visitor(geometry2), geometry1);
445 template <typename Geometry1, BOOST_VARIANT_ENUM_PARAMS(typename T)>
446 struct touches<Geometry1, boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
448 struct visitor: boost::static_visitor<bool>
450 Geometry1 const& m_geometry1;
452 visitor(Geometry1 const& geometry1): m_geometry1(geometry1) {}
454 template <typename Geometry2>
455 bool operator()(Geometry2 const& geometry2) const
457 return touches<Geometry1, Geometry2>::apply(m_geometry1, geometry2);
462 apply(Geometry1 const& geometry1,
463 boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry2)
465 return boost::apply_visitor(visitor(geometry1), geometry2);
469 template <BOOST_VARIANT_ENUM_PARAMS(typename T1),
470 BOOST_VARIANT_ENUM_PARAMS(typename T2)>
471 struct touches<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T1)>,
472 boost::variant<BOOST_VARIANT_ENUM_PARAMS(T2)> >
474 struct visitor: boost::static_visitor<bool>
476 template <typename Geometry1, typename Geometry2>
477 bool operator()(Geometry1 const& geometry1,
478 Geometry2 const& geometry2) const
480 return touches<Geometry1, Geometry2>::apply(geometry1, geometry2);
485 apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T1)> const& geometry1,
486 boost::variant<BOOST_VARIANT_ENUM_PARAMS(T2)> const& geometry2)
488 return boost::apply_visitor(visitor(), geometry1, geometry2);
492 template <typename Geometry>
495 static bool apply(Geometry const& geometry)
497 concepts::check<Geometry const>();
499 typedef detail::no_rescale_policy rescale_policy_type;
500 typedef typename geometry::point_type<Geometry>::type point_type;
501 typedef detail::overlay::turn_info
504 typename segment_ratio_type<point_type, rescale_policy_type>::type
507 typedef detail::overlay::get_turn_info
509 detail::overlay::assign_null_policy
512 std::deque<turn_info> turns;
513 detail::touches::areal_interrupt_policy policy;
514 rescale_policy_type robust_policy;
515 detail::self_get_turn_points::get_turns
518 >::apply(geometry, robust_policy, turns, policy);
520 return policy.result();
524 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
525 struct self_touches<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
527 struct visitor: boost::static_visitor<bool>
529 template <typename Geometry>
530 bool operator()(Geometry const& geometry) const
532 return self_touches<Geometry>::apply(geometry);
537 apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry)
539 return boost::apply_visitor(visitor(), geometry);
543 } // namespace resolve_variant
547 \brief \brief_check{has at least one touching point (self-tangency)}
548 \note This function can be called for one geometry (self-tangency) and
549 also for two geometries (touch)
551 \tparam Geometry \tparam_geometry
552 \param geometry \param_geometry
553 \return \return_check{is self-touching}
555 \qbk{distinguish,one geometry}
556 \qbk{[def __one_parameter__]}
557 \qbk{[include reference/algorithms/touches.qbk]}
559 template <typename Geometry>
560 inline bool touches(Geometry const& geometry)
562 return resolve_variant::self_touches<Geometry>::apply(geometry);
567 \brief \brief_check2{have at least one touching point (tangent - non overlapping)}
569 \tparam Geometry1 \tparam_geometry
570 \tparam Geometry2 \tparam_geometry
571 \param geometry1 \param_geometry
572 \param geometry2 \param_geometry
573 \return \return_check2{touch each other}
575 \qbk{distinguish,two geometries}
576 \qbk{[include reference/algorithms/touches.qbk]}
578 template <typename Geometry1, typename Geometry2>
579 inline bool touches(Geometry1 const& geometry1, Geometry2 const& geometry2)
581 return resolve_variant::touches<Geometry1, Geometry2>::apply(geometry1, geometry2);
585 }} // namespace boost::geometry
587 #endif // BOOST_GEOMETRY_ALGORITHMS_TOUCHES_HPP