1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. 4 // Copyright (c) 2008-2012 Bruno Lalande, Paris, France. 5 // Copyright (c) 2009-2012 Mateusz Loskot, London, UK. 6 // Copyright (c) 2014 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_WITHIN_POINT_IN_GEOMETRY_HPP 21 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP 22 23 24 #include <boost/core/ignore_unused.hpp> 25 #include <boost/mpl/assert.hpp> 26 #include <boost/range.hpp> 27 #include <boost/type_traits/is_same.hpp> 28 #include <boost/type_traits/remove_reference.hpp> 29 30 #include <boost/geometry/core/assert.hpp> 31 32 #include <boost/geometry/algorithms/detail/equals/point_point.hpp> 33 #include <boost/geometry/algorithms/detail/interior_iterator.hpp> 34 35 #include <boost/geometry/geometries/concepts/check.hpp> 36 #include <boost/geometry/strategies/concepts/within_concept.hpp> 37 #include <boost/geometry/strategies/default_strategy.hpp> 38 #include <boost/geometry/strategies/relate.hpp> 39 40 #include <boost/geometry/util/range.hpp> 41 #include <boost/geometry/views/detail/normalized_view.hpp> 42 43 namespace boost { namespace geometry { 44 45 #ifndef DOXYGEN_NO_DETAIL 46 namespace detail { namespace within { 47 48 49 // TODO: is this needed? 50 inline int check_result_type(int result) 51 { 52 return result; 53 } 54 55 template <typename T> 56 inline T check_result_type(T result) 57 { 58 BOOST_GEOMETRY_ASSERT(false); 59 return result; 60 } 61 62 template <typename Point, typename Range, typename Strategy> inline 63 int point_in_range(Point const& point, Range const& range, Strategy const& strategy) 64 { 65 boost::ignore_unused(strategy); 66 67 typedef typename boost::range_iterator<Range const>::type iterator_type; 68 typename Strategy::state_type state; 69 iterator_type it = boost::begin(range); 70 iterator_type end = boost::end(range); 71 72 for ( iterator_type previous = it++ ; it != end ; ++previous, ++it ) 73 { 74 if ( ! strategy.apply(point, *previous, *it, state) ) 75 { 76 break; 77 } 78 } 79 80 return check_result_type(strategy.result(state)); 81 } 82 83 template <typename Geometry, typename Point, typename Range> 84 inline int point_in_range(Point const& point, Range const& range) 85 { 86 typedef typename strategy::point_in_geometry::services::default_strategy 87 < 88 Point, Geometry 89 >::type strategy_type; 90 91 return point_in_range(point, range, strategy_type()); 92 } 93 94 }} // namespace detail::within 95 96 namespace detail_dispatch { namespace within { 97 98 // checks the relation between a point P and geometry G 99 // returns 1 if P is in the interior of G 100 // returns 0 if P is on the boundry of G 101 // returns -1 if P is in the exterior of G 102 103 template <typename Geometry, 104 typename Tag = typename geometry::tag<Geometry>::type> 105 struct point_in_geometry 106 : not_implemented<Tag> 107 {}; 108 109 template <typename Point2> 110 struct point_in_geometry<Point2, point_tag> 111 { 112 template <typename Point1, typename Strategy> static inline 113 int apply(Point1 const& point1, Point2 const& point2, Strategy const& strategy) 114 { 115 boost::ignore_unused(strategy); 116 return strategy.apply(point1, point2) ? 1 : -1; 117 } 118 }; 119 120 template <typename Segment> 121 struct point_in_geometry<Segment, segment_tag> 122 { 123 template <typename Point, typename Strategy> static inline 124 int apply(Point const& point, Segment const& segment, Strategy const& strategy) 125 { 126 boost::ignore_unused(strategy); 127 128 typedef typename geometry::point_type<Segment>::type point_type; 129 point_type p0, p1; 130 // TODO: don't copy points 131 detail::assign_point_from_index<0>(segment, p0); 132 detail::assign_point_from_index<1>(segment, p1); 133 134 typename Strategy::state_type state; 135 strategy.apply(point, p0, p1, state); 136 int r = detail::within::check_result_type(strategy.result(state)); 137 138 if ( r != 0 ) 139 return -1; // exterior 140 141 // if the point is equal to the one of the terminal points 142 if ( detail::equals::equals_point_point(point, p0) 143 || detail::equals::equals_point_point(point, p1) ) 144 return 0; // boundary 145 else 146 return 1; // interior 147 } 148 }; 149 150 151 template <typename Linestring> 152 struct point_in_geometry<Linestring, linestring_tag> 153 { 154 template <typename Point, typename Strategy> static inline 155 int apply(Point const& point, Linestring const& linestring, Strategy const& strategy) 156 { 157 std::size_t count = boost::size(linestring); 158 if ( count > 1 ) 159 { 160 if ( detail::within::point_in_range(point, linestring, strategy) != 0 ) 161 return -1; // exterior 162 163 // if the linestring doesn't have a boundary 164 if (detail::equals::equals_point_point(range::front(linestring), range::back(linestring))) 165 return 1; // interior 166 // else if the point is equal to the one of the terminal points 167 else if (detail::equals::equals_point_point(point, range::front(linestring)) 168 || detail::equals::equals_point_point(point, range::back(linestring))) 169 return 0; // boundary 170 else 171 return 1; // interior 172 } 173 // TODO: for now degenerated linestrings are ignored 174 // throw an exception here? 175 /*else if ( count == 1 ) 176 { 177 if ( detail::equals::equals_point_point(point, range::front(linestring)) ) 178 return 1; 179 }*/ 180 181 return -1; // exterior 182 } 183 }; 184 185 template <typename Ring> 186 struct point_in_geometry<Ring, ring_tag> 187 { 188 template <typename Point, typename Strategy> static inline 189 int apply(Point const& point, Ring const& ring, Strategy const& strategy) 190 { 191 if ( boost::size(ring) < core_detail::closure::minimum_ring_size 192 < 193 geometry::closure<Ring>::value 194 >::value ) 195 { 196 return -1; 197 } 198 199 detail::normalized_view<Ring const> view(ring); 200 return detail::within::point_in_range(point, view, strategy); 201 } 202 }; 203 204 // Polygon: in exterior ring, and if so, not within interior ring(s) 205 template <typename Polygon> 206 struct point_in_geometry<Polygon, polygon_tag> 207 { 208 template <typename Point, typename Strategy> 209 static inline int apply(Point const& point, Polygon const& polygon, 210 Strategy const& strategy) 211 { 212 int const code = point_in_geometry 213 < 214 typename ring_type<Polygon>::type 215 >::apply(point, exterior_ring(polygon), strategy); 216 217 if (code == 1) 218 { 219 typename interior_return_type<Polygon const>::type 220 rings = interior_rings(polygon); 221 222 for (typename detail::interior_iterator<Polygon const>::type 223 it = boost::begin(rings); 224 it != boost::end(rings); 225 ++it) 226 { 227 int const interior_code = point_in_geometry 228 < 229 typename ring_type<Polygon>::type 230 >::apply(point, *it, strategy); 231 232 if (interior_code != -1) 233 { 234 // If 0, return 0 (touch) 235 // If 1 (inside hole) return -1 (outside polygon) 236 // If -1 (outside hole) check other holes if any 237 return -interior_code; 238 } 239 } 240 } 241 return code; 242 } 243 }; 244 245 template <typename Geometry> 246 struct point_in_geometry<Geometry, multi_point_tag> 247 { 248 template <typename Point, typename Strategy> static inline 249 int apply(Point const& point, Geometry const& geometry, Strategy const& strategy) 250 { 251 typedef typename boost::range_value<Geometry>::type point_type; 252 typedef typename boost::range_const_iterator<Geometry>::type iterator; 253 for ( iterator it = boost::begin(geometry) ; it != boost::end(geometry) ; ++it ) 254 { 255 int pip = point_in_geometry<point_type>::apply(point, *it, strategy); 256 257 //BOOST_GEOMETRY_ASSERT(pip != 0); 258 if ( pip > 0 ) // inside 259 return 1; 260 } 261 262 return -1; // outside 263 } 264 }; 265 266 template <typename Geometry> 267 struct point_in_geometry<Geometry, multi_linestring_tag> 268 { 269 template <typename Point, typename Strategy> static inline 270 int apply(Point const& point, Geometry const& geometry, Strategy const& strategy) 271 { 272 int pip = -1; // outside 273 274 typedef typename boost::range_value<Geometry>::type linestring_type; 275 typedef typename boost::range_value<linestring_type>::type point_type; 276 typedef typename boost::range_iterator<Geometry const>::type iterator; 277 iterator it = boost::begin(geometry); 278 for ( ; it != boost::end(geometry) ; ++it ) 279 { 280 pip = point_in_geometry<linestring_type>::apply(point, *it, strategy); 281 282 // inside or on the boundary 283 if ( pip >= 0 ) 284 { 285 ++it; 286 break; 287 } 288 } 289 290 // outside 291 if ( pip < 0 ) 292 return -1; 293 294 // TODO: the following isn't needed for covered_by() 295 296 unsigned boundaries = pip == 0 ? 1 : 0; 297 298 for ( ; it != boost::end(geometry) ; ++it ) 299 { 300 if ( boost::size(*it) < 2 ) 301 continue; 302 303 point_type const& front = range::front(*it); 304 point_type const& back = range::back(*it); 305 306 // is closed_ring - no boundary 307 if ( detail::equals::equals_point_point(front, back) ) 308 continue; 309 310 // is point on boundary 311 if ( detail::equals::equals_point_point(point, front) 312 || detail::equals::equals_point_point(point, back) ) 313 { 314 ++boundaries; 315 } 316 } 317 318 // if the number of boundaries is odd, the point is on the boundary 319 return boundaries % 2 ? 0 : 1; 320 } 321 }; 322 323 template <typename Geometry> 324 struct point_in_geometry<Geometry, multi_polygon_tag> 325 { 326 template <typename Point, typename Strategy> static inline 327 int apply(Point const& point, Geometry const& geometry, Strategy const& strategy) 328 { 329 // For invalid multipolygons 330 //int res = -1; // outside 331 332 typedef typename boost::range_value<Geometry>::type polygon_type; 333 typedef typename boost::range_const_iterator<Geometry>::type iterator; 334 for ( iterator it = boost::begin(geometry) ; it != boost::end(geometry) ; ++it ) 335 { 336 int pip = point_in_geometry<polygon_type>::apply(point, *it, strategy); 337 338 // inside or on the boundary 339 if ( pip >= 0 ) 340 return pip; 341 342 // For invalid multi-polygons 343 //if ( 1 == pip ) // inside polygon 344 // return 1; 345 //else if ( res < pip ) // point must be inside at least one polygon 346 // res = pip; 347 } 348 349 return -1; // for valid multipolygons 350 //return res; // for invalid multipolygons 351 } 352 }; 353 354 }} // namespace detail_dispatch::within 355 356 namespace detail { namespace within { 357 358 // 1 - in the interior 359 // 0 - in the boundry 360 // -1 - in the exterior 361 template <typename Point, typename Geometry, typename Strategy> 362 inline int point_in_geometry(Point const& point, Geometry const& geometry, Strategy const& strategy) 363 { 364 concepts::within::check 365 < 366 typename tag<Point>::type, 367 typename tag<Geometry>::type, 368 typename tag_cast<typename tag<Geometry>::type, areal_tag>::type, 369 Strategy 370 >(); 371 372 return detail_dispatch::within::point_in_geometry<Geometry>::apply(point, geometry, strategy); 373 } 374 375 template <typename Point, typename Geometry> 376 inline int point_in_geometry(Point const& point, Geometry const& geometry) 377 { 378 typedef typename strategy::point_in_geometry::services::default_strategy 379 < 380 Point, Geometry 381 >::type strategy_type; 382 383 return point_in_geometry(point, geometry, strategy_type()); 384 } 385 386 }} // namespace detail::within 387 #endif // DOXYGEN_NO_DETAIL 388 389 }} // namespace boost::geometry 390 391 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP 392