1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. 4 // Copyright (c) 2008-2014 Bruno Lalande, Paris, France. 5 // Copyright (c) 2009-2014 Mateusz Loskot, London, UK. 6 // Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland. 7 8 // This file was modified by Oracle on 2013-2018. 9 // Modifications copyright (c) 2013-2018, Oracle and/or its affiliates. 10 11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 12 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle 13 14 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library 15 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. 16 17 // Use, modification and distribution is subject to the Boost Software License, 18 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 19 // http://www.boost.org/LICENSE_1_0.txt) 20 21 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_LINEAR_AREAL_HPP 22 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_LINEAR_AREAL_HPP 23 24 #include <iterator> 25 26 #include <boost/range.hpp> 27 28 #include <boost/geometry/core/closure.hpp> 29 #include <boost/geometry/core/point_type.hpp> 30 #include <boost/geometry/core/ring_type.hpp> 31 #include <boost/geometry/core/exterior_ring.hpp> 32 #include <boost/geometry/core/interior_rings.hpp> 33 #include <boost/geometry/core/tag.hpp> 34 #include <boost/geometry/core/tag_cast.hpp> 35 #include <boost/geometry/core/tags.hpp> 36 37 #include <boost/geometry/algorithms/covered_by.hpp> 38 #include <boost/geometry/algorithms/not_implemented.hpp> 39 40 #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp> 41 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp> 42 #include <boost/geometry/algorithms/detail/point_on_border.hpp> 43 44 #include <boost/geometry/algorithms/detail/disjoint/linear_linear.hpp> 45 #include <boost/geometry/algorithms/detail/disjoint/linear_segment_or_box.hpp> 46 #include <boost/geometry/algorithms/detail/disjoint/multirange_geometry.hpp> 47 #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> 48 #include <boost/geometry/algorithms/detail/disjoint/segment_box.hpp> 49 50 #include <boost/geometry/algorithms/dispatch/disjoint.hpp> 51 52 53 namespace boost { namespace geometry 54 { 55 56 #ifndef DOXYGEN_NO_DETAIL 57 namespace detail { namespace disjoint 58 { 59 60 template <typename Geometry1, typename Geometry2, 61 typename Tag1 = typename tag<Geometry1>::type, 62 typename Tag1OrMulti = typename tag_cast<Tag1, multi_tag>::type> 63 struct disjoint_no_intersections_policy 64 { 65 /*! 66 \tparam Strategy point_in_geometry strategy 67 */ 68 template <typename Strategy> applyboost::geometry::detail::disjoint::disjoint_no_intersections_policy69 static inline bool apply(Geometry1 const& g1, Geometry2 const& g2, Strategy const& strategy) 70 { 71 typedef typename point_type<Geometry1>::type point1_type; 72 point1_type p; 73 geometry::point_on_border(p, g1); 74 75 return !geometry::covered_by(p, g2, strategy); 76 } 77 }; 78 79 template <typename Geometry1, typename Geometry2, typename Tag1> 80 struct disjoint_no_intersections_policy<Geometry1, Geometry2, Tag1, multi_tag> 81 { 82 /*! 83 \tparam Strategy point_in_geometry strategy 84 */ 85 template <typename Strategy> applyboost::geometry::detail::disjoint::disjoint_no_intersections_policy86 static inline bool apply(Geometry1 const& g1, Geometry2 const& g2, Strategy const& strategy) 87 { 88 // TODO: use partition or rtree on g2 89 typedef typename boost::range_iterator<Geometry1 const>::type iterator; 90 for ( iterator it = boost::begin(g1) ; it != boost::end(g1) ; ++it ) 91 { 92 typedef typename boost::range_value<Geometry1 const>::type value_type; 93 if ( ! disjoint_no_intersections_policy<value_type const, Geometry2> 94 ::apply(*it, g2, strategy) ) 95 { 96 return false; 97 } 98 } 99 return true; 100 } 101 }; 102 103 104 template<typename Geometry1, typename Geometry2, 105 typename NoIntersectionsPolicy 106 = disjoint_no_intersections_policy<Geometry1, Geometry2> > 107 struct disjoint_linear_areal 108 { 109 /*! 110 \tparam Strategy relate (segments intersection) strategy 111 */ 112 template <typename Strategy> applyboost::geometry::detail::disjoint::disjoint_linear_areal113 static inline bool apply(Geometry1 const& g1, Geometry2 const& g2, Strategy const& strategy) 114 { 115 // if there are intersections - return false 116 if ( !disjoint_linear<Geometry1, Geometry2>::apply(g1, g2, strategy) ) 117 { 118 return false; 119 } 120 121 return NoIntersectionsPolicy 122 ::apply(g1, g2, 123 strategy.template get_point_in_geometry_strategy<Geometry1, Geometry2>()); 124 } 125 }; 126 127 128 129 130 template 131 < 132 typename Segment, 133 typename Areal, 134 typename Tag = typename tag<Areal>::type 135 > 136 struct disjoint_segment_areal 137 : not_implemented<Segment, Areal> 138 {}; 139 140 141 template <typename Segment, typename Polygon> 142 class disjoint_segment_areal<Segment, Polygon, polygon_tag> 143 { 144 private: 145 template <typename InteriorRings, typename Strategy> 146 static inline check_interior_rings(InteriorRings const & interior_rings,Segment const & segment,Strategy const & strategy)147 bool check_interior_rings(InteriorRings const& interior_rings, 148 Segment const& segment, 149 Strategy const& strategy) 150 { 151 typedef typename boost::range_value<InteriorRings>::type ring_type; 152 153 typedef unary_disjoint_geometry_to_query_geometry 154 < 155 Segment, 156 Strategy, 157 disjoint_range_segment_or_box 158 < 159 ring_type, closure<ring_type>::value, Segment 160 > 161 > unary_predicate_type; 162 163 return check_iterator_range 164 < 165 unary_predicate_type 166 >::apply(boost::begin(interior_rings), 167 boost::end(interior_rings), 168 unary_predicate_type(segment, strategy)); 169 } 170 171 172 public: 173 template <typename IntersectionStrategy> apply(Segment const & segment,Polygon const & polygon,IntersectionStrategy const & strategy)174 static inline bool apply(Segment const& segment, 175 Polygon const& polygon, 176 IntersectionStrategy const& strategy) 177 { 178 typedef typename geometry::ring_type<Polygon>::type ring; 179 180 if ( !disjoint_range_segment_or_box 181 < 182 ring, closure<Polygon>::value, Segment 183 >::apply(geometry::exterior_ring(polygon), segment, strategy) ) 184 { 185 return false; 186 } 187 188 if ( !check_interior_rings(geometry::interior_rings(polygon), segment, strategy) ) 189 { 190 return false; 191 } 192 193 typename point_type<Segment>::type p; 194 detail::assign_point_from_index<0>(segment, p); 195 196 return !geometry::covered_by(p, polygon, 197 strategy.template get_point_in_geometry_strategy<Segment, Polygon>()); 198 } 199 }; 200 201 202 template <typename Segment, typename MultiPolygon> 203 struct disjoint_segment_areal<Segment, MultiPolygon, multi_polygon_tag> 204 { 205 template <typename IntersectionStrategy> applyboost::geometry::detail::disjoint::disjoint_segment_areal206 static inline bool apply(Segment const& segment, MultiPolygon const& multipolygon, 207 IntersectionStrategy const& strategy) 208 { 209 return multirange_constant_size_geometry 210 < 211 MultiPolygon, Segment 212 >::apply(multipolygon, segment, strategy); 213 } 214 }; 215 216 217 template <typename Segment, typename Ring> 218 struct disjoint_segment_areal<Segment, Ring, ring_tag> 219 { 220 template <typename IntersectionStrategy> applyboost::geometry::detail::disjoint::disjoint_segment_areal221 static inline bool apply(Segment const& segment, 222 Ring const& ring, 223 IntersectionStrategy const& strategy) 224 { 225 if ( !disjoint_range_segment_or_box 226 < 227 Ring, closure<Ring>::value, Segment 228 >::apply(ring, segment, strategy) ) 229 { 230 return false; 231 } 232 233 typename point_type<Segment>::type p; 234 detail::assign_point_from_index<0>(segment, p); 235 236 return !geometry::covered_by(p, ring, 237 strategy.template get_point_in_geometry_strategy<Segment, Ring>()); 238 } 239 }; 240 241 242 }} // namespace detail::disjoint 243 #endif // DOXYGEN_NO_DETAIL 244 245 246 247 248 #ifndef DOXYGEN_NO_DISPATCH 249 namespace dispatch 250 { 251 252 253 template <typename Linear, typename Areal> 254 struct disjoint<Linear, Areal, 2, linear_tag, areal_tag, false> 255 : public detail::disjoint::disjoint_linear_areal<Linear, Areal> 256 {}; 257 258 259 template <typename Areal, typename Linear> 260 struct disjoint<Areal, Linear, 2, areal_tag, linear_tag, false> 261 { 262 template <typename Strategy> applyboost::geometry::dispatch::disjoint263 static inline bool apply(Areal const& areal, Linear const& linear, 264 Strategy const& strategy) 265 { 266 return detail::disjoint::disjoint_linear_areal 267 < 268 Linear, Areal 269 >::apply(linear, areal, strategy); 270 } 271 }; 272 273 274 template <typename Areal, typename Segment> 275 struct disjoint<Areal, Segment, 2, areal_tag, segment_tag, false> 276 { 277 template <typename Strategy> applyboost::geometry::dispatch::disjoint278 static inline bool apply(Areal const& g1, Segment const& g2, 279 Strategy const& strategy) 280 { 281 return detail::disjoint::disjoint_segment_areal 282 < 283 Segment, Areal 284 >::apply(g2, g1, strategy); 285 } 286 }; 287 288 289 template <typename Segment, typename Areal> 290 struct disjoint<Segment, Areal, 2, segment_tag, areal_tag, false> 291 : detail::disjoint::disjoint_segment_areal<Segment, Areal> 292 {}; 293 294 295 } // namespace dispatch 296 #endif // DOXYGEN_NO_DISPATCH 297 298 299 }} // namespace boost::geometry 300 301 302 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_LINEAR_AREAL_HPP 303