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