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 2014-2020. 9 // Modifications copyright (c) 2014-2020, Oracle and/or its affiliates. 10 11 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle 12 // Contributed and/or modified by Adam Wulkiewicz, 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_DISTANCE_POINT_TO_GEOMETRY_HPP 22 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_POINT_TO_GEOMETRY_HPP 23 24 #include <iterator> 25 #include <type_traits> 26 27 #include <boost/core/ignore_unused.hpp> 28 #include <boost/range/begin.hpp> 29 #include <boost/range/end.hpp> 30 #include <boost/range/size.hpp> 31 #include <boost/range/value_type.hpp> 32 33 #include <boost/geometry/core/closure.hpp> 34 #include <boost/geometry/core/point_type.hpp> 35 #include <boost/geometry/core/exterior_ring.hpp> 36 #include <boost/geometry/core/interior_rings.hpp> 37 #include <boost/geometry/core/tag.hpp> 38 #include <boost/geometry/core/tags.hpp> 39 40 #include <boost/geometry/util/math.hpp> 41 42 #include <boost/geometry/strategies/distance.hpp> 43 #include <boost/geometry/strategies/tags.hpp> 44 45 #include <boost/geometry/algorithms/assign.hpp> 46 47 #include <boost/geometry/algorithms/detail/closest_feature/geometry_to_range.hpp> 48 #include <boost/geometry/algorithms/detail/closest_feature/point_to_range.hpp> 49 #include <boost/geometry/algorithms/detail/distance/is_comparable.hpp> 50 #include <boost/geometry/algorithms/detail/distance/iterator_selector.hpp> 51 #include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp> 52 53 #include <boost/geometry/algorithms/dispatch/distance.hpp> 54 55 56 namespace boost { namespace geometry 57 { 58 59 #ifndef DOXYGEN_NO_DETAIL 60 namespace detail { namespace distance 61 { 62 63 64 template <typename P1, typename P2, typename Strategy> 65 struct point_to_point 66 { 67 static inline 68 typename strategy::distance::services::return_type<Strategy, P1, P2>::type applyboost::geometry::detail::distance::point_to_point69 apply(P1 const& p1, P2 const& p2, Strategy const& strategy) 70 { 71 boost::ignore_unused(strategy); 72 return strategy.apply(p1, p2); 73 } 74 }; 75 76 77 template 78 < 79 typename Point, 80 typename Range, 81 closure_selector Closure, 82 typename Strategy 83 > 84 class point_to_range 85 { 86 private: 87 typedef typename strategy::distance::services::comparable_type 88 < 89 Strategy 90 >::type comparable_strategy; 91 92 typedef detail::closest_feature::point_to_point_range 93 < 94 Point, Range, Closure, comparable_strategy 95 > point_to_point_range; 96 97 public: 98 typedef typename strategy::distance::services::return_type 99 < 100 Strategy, 101 Point, 102 typename boost::range_value<Range>::type 103 >::type return_type; 104 apply(Point const & point,Range const & range,Strategy const & strategy)105 static inline return_type apply(Point const& point, Range const& range, 106 Strategy const& strategy) 107 { 108 return_type const zero = return_type(0); 109 110 if (boost::size(range) == 0) 111 { 112 return zero; 113 } 114 115 namespace sds = strategy::distance::services; 116 117 typename sds::return_type 118 < 119 comparable_strategy, 120 Point, 121 typename point_type<Range>::type 122 >::type cd_min; 123 124 std::pair 125 < 126 typename boost::range_iterator<Range const>::type, 127 typename boost::range_iterator<Range const>::type 128 > it_pair 129 = point_to_point_range::apply(point, 130 boost::begin(range), 131 boost::end(range), 132 sds::get_comparable 133 < 134 Strategy 135 >::apply(strategy), 136 cd_min); 137 138 return 139 is_comparable<Strategy>::value 140 ? 141 cd_min 142 : 143 strategy.apply(point, *it_pair.first, *it_pair.second); 144 } 145 }; 146 147 148 template 149 < 150 typename Point, 151 typename Ring, 152 closure_selector Closure, 153 typename Strategy 154 > 155 struct point_to_ring 156 { 157 typedef typename strategy::distance::services::return_type 158 < 159 Strategy, Point, typename point_type<Ring>::type 160 >::type return_type; 161 applyboost::geometry::detail::distance::point_to_ring162 static inline return_type apply(Point const& point, 163 Ring const& ring, 164 Strategy const& strategy) 165 { 166 // TODO: pass strategy 167 if (within::within_point_geometry(point, ring, 168 strategy.get_point_in_geometry_strategy())) 169 { 170 return return_type(0); 171 } 172 173 return point_to_range 174 < 175 Point, Ring, closure<Ring>::value, Strategy 176 >::apply(point, ring, strategy); 177 } 178 }; 179 180 181 template 182 < 183 typename Point, 184 typename Polygon, 185 closure_selector Closure, 186 typename Strategy 187 > 188 class point_to_polygon 189 { 190 public: 191 typedef typename strategy::distance::services::return_type 192 < 193 Strategy, Point, typename point_type<Polygon>::type 194 >::type return_type; 195 196 private: 197 typedef point_to_range 198 < 199 Point, typename ring_type<Polygon>::type, Closure, Strategy 200 > per_ring; 201 202 struct distance_to_interior_rings 203 { 204 template <typename InteriorRingIterator> applyboost::geometry::detail::distance::point_to_polygon::distance_to_interior_rings205 static inline return_type apply(Point const& point, 206 InteriorRingIterator first, 207 InteriorRingIterator last, 208 Strategy const& strategy) 209 { 210 for (InteriorRingIterator it = first; it != last; ++it) 211 { 212 // TODO: pass strategy 213 if (within::within_point_geometry(point, *it, 214 strategy.get_point_in_geometry_strategy())) 215 { 216 // the point is inside a polygon hole, so its distance 217 // to the polygon its distance to the polygon's 218 // hole boundary 219 return per_ring::apply(point, *it, strategy); 220 } 221 } 222 return 0; 223 } 224 225 template <typename InteriorRings> applyboost::geometry::detail::distance::point_to_polygon::distance_to_interior_rings226 static inline return_type apply(Point const& point, 227 InteriorRings const& interior_rings, 228 Strategy const& strategy) 229 { 230 return apply(point, 231 boost::begin(interior_rings), 232 boost::end(interior_rings), 233 strategy); 234 } 235 }; 236 237 238 public: apply(Point const & point,Polygon const & polygon,Strategy const & strategy)239 static inline return_type apply(Point const& point, 240 Polygon const& polygon, 241 Strategy const& strategy) 242 { 243 // TODO: pass strategy 244 if (! within::covered_by_point_geometry(point, exterior_ring(polygon), 245 strategy.get_point_in_geometry_strategy())) 246 { 247 // the point is outside the exterior ring, so its distance 248 // to the polygon is its distance to the polygon's exterior ring 249 return per_ring::apply(point, exterior_ring(polygon), strategy); 250 } 251 252 // Check interior rings 253 return distance_to_interior_rings::apply(point, 254 interior_rings(polygon), 255 strategy); 256 } 257 }; 258 259 260 template 261 < 262 typename Point, 263 typename MultiGeometry, 264 typename Strategy, 265 bool CheckCoveredBy = std::is_same 266 < 267 typename tag<MultiGeometry>::type, multi_polygon_tag 268 >::value 269 > 270 class point_to_multigeometry 271 { 272 private: 273 typedef detail::closest_feature::geometry_to_range geometry_to_range; 274 275 public: 276 typedef typename strategy::distance::services::return_type 277 < 278 Strategy, 279 Point, 280 typename point_type<MultiGeometry>::type 281 >::type return_type; 282 apply(Point const & point,MultiGeometry const & multigeometry,Strategy const & strategy)283 static inline return_type apply(Point const& point, 284 MultiGeometry const& multigeometry, 285 Strategy const& strategy) 286 { 287 typedef iterator_selector<MultiGeometry const> selector_type; 288 289 namespace sds = strategy::distance::services; 290 291 typename sds::return_type 292 < 293 typename sds::comparable_type<Strategy>::type, 294 Point, 295 typename point_type<MultiGeometry>::type 296 >::type cd; 297 298 typename selector_type::iterator_type it_min 299 = geometry_to_range::apply(point, 300 selector_type::begin(multigeometry), 301 selector_type::end(multigeometry), 302 sds::get_comparable 303 < 304 Strategy 305 >::apply(strategy), 306 cd); 307 308 return 309 is_comparable<Strategy>::value 310 ? 311 cd 312 : 313 dispatch::distance 314 < 315 Point, 316 typename std::iterator_traits 317 < 318 typename selector_type::iterator_type 319 >::value_type, 320 Strategy 321 >::apply(point, *it_min, strategy); 322 } 323 }; 324 325 326 // this is called only for multipolygons, hence the change in the 327 // template parameter name MultiGeometry to MultiPolygon 328 template <typename Point, typename MultiPolygon, typename Strategy> 329 struct point_to_multigeometry<Point, MultiPolygon, Strategy, true> 330 { 331 typedef typename strategy::distance::services::return_type 332 < 333 Strategy, 334 Point, 335 typename point_type<MultiPolygon>::type 336 >::type return_type; 337 applyboost::geometry::detail::distance::point_to_multigeometry338 static inline return_type apply(Point const& point, 339 MultiPolygon const& multipolygon, 340 Strategy const& strategy) 341 { 342 // TODO: pass strategy 343 if (within::covered_by_point_geometry(point, multipolygon, 344 strategy.get_point_in_geometry_strategy())) 345 { 346 return 0; 347 } 348 349 return point_to_multigeometry 350 < 351 Point, MultiPolygon, Strategy, false 352 >::apply(point, multipolygon, strategy); 353 } 354 }; 355 356 357 }} // namespace detail::distance 358 #endif // DOXYGEN_NO_DETAIL 359 360 361 362 363 #ifndef DOXYGEN_NO_DISPATCH 364 namespace dispatch 365 { 366 367 368 // Point-point 369 template <typename P1, typename P2, typename Strategy> 370 struct distance 371 < 372 P1, P2, Strategy, point_tag, point_tag, 373 strategy_tag_distance_point_point, false 374 > : detail::distance::point_to_point<P1, P2, Strategy> 375 {}; 376 377 378 // Point-line version 2, where point-segment strategy is specified 379 template <typename Point, typename Linestring, typename Strategy> 380 struct distance 381 < 382 Point, Linestring, Strategy, point_tag, linestring_tag, 383 strategy_tag_distance_point_segment, false 384 > : detail::distance::point_to_range<Point, Linestring, closed, Strategy> 385 {}; 386 387 388 // Point-ring , where point-segment strategy is specified 389 template <typename Point, typename Ring, typename Strategy> 390 struct distance 391 < 392 Point, Ring, Strategy, point_tag, ring_tag, 393 strategy_tag_distance_point_segment, false 394 > : detail::distance::point_to_ring 395 < 396 Point, Ring, closure<Ring>::value, Strategy 397 > 398 {}; 399 400 401 // Point-polygon , where point-segment strategy is specified 402 template <typename Point, typename Polygon, typename Strategy> 403 struct distance 404 < 405 Point, Polygon, Strategy, point_tag, polygon_tag, 406 strategy_tag_distance_point_segment, false 407 > : detail::distance::point_to_polygon 408 < 409 Point, Polygon, closure<Polygon>::value, Strategy 410 > 411 {}; 412 413 414 // Point-segment version 2, with point-segment strategy 415 template <typename Point, typename Segment, typename Strategy> 416 struct distance 417 < 418 Point, Segment, Strategy, point_tag, segment_tag, 419 strategy_tag_distance_point_segment, false 420 > 421 { 422 static inline typename strategy::distance::services::return_type 423 < 424 Strategy, Point, typename point_type<Segment>::type applyboost::geometry::dispatch::distance425 >::type apply(Point const& point, 426 Segment const& segment, 427 Strategy const& strategy) 428 { 429 typename point_type<Segment>::type p[2]; 430 geometry::detail::assign_point_from_index<0>(segment, p[0]); 431 geometry::detail::assign_point_from_index<1>(segment, p[1]); 432 433 boost::ignore_unused(strategy); 434 return strategy.apply(point, p[0], p[1]); 435 } 436 }; 437 438 439 template <typename Point, typename Box, typename Strategy> 440 struct distance 441 < 442 Point, Box, Strategy, point_tag, box_tag, 443 strategy_tag_distance_point_box, false 444 > 445 { 446 static inline typename strategy::distance::services::return_type 447 < 448 Strategy, Point, typename point_type<Box>::type 449 >::type applyboost::geometry::dispatch::distance450 apply(Point const& point, Box const& box, Strategy const& strategy) 451 { 452 boost::ignore_unused(strategy); 453 return strategy.apply(point, box); 454 } 455 }; 456 457 458 template<typename Point, typename MultiPoint, typename Strategy> 459 struct distance 460 < 461 Point, MultiPoint, Strategy, point_tag, multi_point_tag, 462 strategy_tag_distance_point_point, false 463 > : detail::distance::point_to_multigeometry 464 < 465 Point, MultiPoint, Strategy 466 > 467 {}; 468 469 470 template<typename Point, typename MultiLinestring, typename Strategy> 471 struct distance 472 < 473 Point, MultiLinestring, Strategy, point_tag, multi_linestring_tag, 474 strategy_tag_distance_point_segment, false 475 > : detail::distance::point_to_multigeometry 476 < 477 Point, MultiLinestring, Strategy 478 > 479 {}; 480 481 482 template<typename Point, typename MultiPolygon, typename Strategy> 483 struct distance 484 < 485 Point, MultiPolygon, Strategy, point_tag, multi_polygon_tag, 486 strategy_tag_distance_point_segment, false 487 > : detail::distance::point_to_multigeometry 488 < 489 Point, MultiPolygon, Strategy 490 > 491 {}; 492 493 494 template <typename Point, typename Linear, typename Strategy> 495 struct distance 496 < 497 Point, Linear, Strategy, point_tag, linear_tag, 498 strategy_tag_distance_point_segment, false 499 > : distance 500 < 501 Point, Linear, Strategy, 502 point_tag, typename tag<Linear>::type, 503 strategy_tag_distance_point_segment, false 504 > 505 {}; 506 507 508 template <typename Point, typename Areal, typename Strategy> 509 struct distance 510 < 511 Point, Areal, Strategy, point_tag, areal_tag, 512 strategy_tag_distance_point_segment, false 513 > : distance 514 < 515 Point, Areal, Strategy, 516 point_tag, typename tag<Areal>::type, 517 strategy_tag_distance_point_segment, false 518 > 519 {}; 520 521 522 } // namespace dispatch 523 #endif // DOXYGEN_NO_DISPATCH 524 525 526 }} // namespace boost::geometry 527 528 529 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_POINT_TO_GEOMETRY_HPP 530