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