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.
9 // Modifications copyright (c) 2014, Oracle and/or its affiliates.
10 
11 // Contributed and/or modified by Menelaos Karavelas, 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_DISTANCE_POINT_TO_GEOMETRY_HPP
21 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_POINT_TO_GEOMETRY_HPP
22 
23 #include <iterator>
24 
25 #include <boost/core/ignore_unused.hpp>
26 #include <boost/range.hpp>
27 #include <boost/type_traits/is_same.hpp>
28 
29 #include <boost/geometry/core/closure.hpp>
30 #include <boost/geometry/core/point_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/tags.hpp>
35 
36 #include <boost/geometry/util/math.hpp>
37 
38 #include <boost/geometry/strategies/distance.hpp>
39 #include <boost/geometry/strategies/tags.hpp>
40 
41 #include <boost/geometry/algorithms/assign.hpp>
42 #include <boost/geometry/algorithms/covered_by.hpp>
43 #include <boost/geometry/algorithms/within.hpp>
44 
45 #include <boost/geometry/algorithms/detail/closest_feature/geometry_to_range.hpp>
46 #include <boost/geometry/algorithms/detail/closest_feature/point_to_range.hpp>
47 #include <boost/geometry/algorithms/detail/distance/is_comparable.hpp>
48 #include <boost/geometry/algorithms/detail/distance/iterator_selector.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         if (geometry::within(point, ring))
164         {
165             return return_type(0);
166         }
167 
168         return point_to_range
169             <
170                 Point, Ring, closure<Ring>::value, Strategy
171             >::apply(point, ring, strategy);
172     }
173 };
174 
175 
176 template
177 <
178     typename Point,
179     typename Polygon,
180     closure_selector Closure,
181     typename Strategy
182 >
183 class point_to_polygon
184 {
185 public:
186     typedef typename strategy::distance::services::return_type
187         <
188             Strategy, Point, typename point_type<Polygon>::type
189         >::type return_type;
190 
191 private:
192     typedef point_to_range
193         <
194             Point, typename ring_type<Polygon>::type, Closure, Strategy
195         > per_ring;
196 
197     struct distance_to_interior_rings
198     {
199         template <typename InteriorRingIterator>
applyboost::geometry::detail::distance::point_to_polygon::distance_to_interior_rings200         static inline return_type apply(Point const& point,
201                                         InteriorRingIterator first,
202                                         InteriorRingIterator last,
203                                         Strategy const& strategy)
204         {
205             for (InteriorRingIterator it = first; it != last; ++it)
206             {
207                 if (geometry::within(point, *it))
208                 {
209                     // the point is inside a polygon hole, so its distance
210                     // to the polygon its distance to the polygon's
211                     // hole boundary
212                     return per_ring::apply(point, *it, strategy);
213                 }
214             }
215             return 0;
216         }
217 
218         template <typename InteriorRings>
applyboost::geometry::detail::distance::point_to_polygon::distance_to_interior_rings219         static inline return_type apply(Point const& point,
220                                         InteriorRings const& interior_rings,
221                                         Strategy const& strategy)
222         {
223             return apply(point,
224                          boost::begin(interior_rings),
225                          boost::end(interior_rings),
226                          strategy);
227         }
228     };
229 
230 
231 public:
apply(Point const & point,Polygon const & polygon,Strategy const & strategy)232     static inline return_type apply(Point const& point,
233                                     Polygon const& polygon,
234                                     Strategy const& strategy)
235     {
236         if (!geometry::covered_by(point, exterior_ring(polygon)))
237         {
238             // the point is outside the exterior ring, so its distance
239             // to the polygon is its distance to the polygon's exterior ring
240             return per_ring::apply(point, exterior_ring(polygon), strategy);
241         }
242 
243         // Check interior rings
244         return distance_to_interior_rings::apply(point,
245                                                  interior_rings(polygon),
246                                                  strategy);
247     }
248 };
249 
250 
251 template
252 <
253     typename Point,
254     typename MultiGeometry,
255     typename Strategy,
256     bool CheckCoveredBy = boost::is_same
257         <
258             typename tag<MultiGeometry>::type, multi_polygon_tag
259         >::value
260 >
261 class point_to_multigeometry
262 {
263 private:
264     typedef detail::closest_feature::geometry_to_range geometry_to_range;
265 
266 public:
267     typedef typename strategy::distance::services::return_type
268         <
269             Strategy,
270             Point,
271             typename point_type<MultiGeometry>::type
272         >::type return_type;
273 
apply(Point const & point,MultiGeometry const & multigeometry,Strategy const & strategy)274     static inline return_type apply(Point const& point,
275                                     MultiGeometry const& multigeometry,
276                                     Strategy const& strategy)
277     {
278         typedef iterator_selector<MultiGeometry const> selector_type;
279 
280         namespace sds = strategy::distance::services;
281 
282         typename sds::return_type
283             <
284                 typename sds::comparable_type<Strategy>::type,
285                 Point,
286                 typename point_type<MultiGeometry>::type
287             >::type cd;
288 
289         typename selector_type::iterator_type it_min
290             = geometry_to_range::apply(point,
291                                        selector_type::begin(multigeometry),
292                                        selector_type::end(multigeometry),
293                                        sds::get_comparable
294                                            <
295                                                Strategy
296                                            >::apply(strategy),
297                                        cd);
298 
299         return
300             is_comparable<Strategy>::value
301             ?
302             cd
303             :
304             dispatch::distance
305                 <
306                     Point,
307                     typename std::iterator_traits
308                         <
309                             typename selector_type::iterator_type
310                         >::value_type,
311                     Strategy
312                 >::apply(point, *it_min, strategy);
313     }
314 };
315 
316 
317 // this is called only for multipolygons, hence the change in the
318 // template parameter name MultiGeometry to MultiPolygon
319 template <typename Point, typename MultiPolygon, typename Strategy>
320 struct point_to_multigeometry<Point, MultiPolygon, Strategy, true>
321 {
322     typedef typename strategy::distance::services::return_type
323         <
324             Strategy,
325             Point,
326             typename point_type<MultiPolygon>::type
327         >::type return_type;
328 
applyboost::geometry::detail::distance::point_to_multigeometry329     static inline return_type apply(Point const& point,
330                                     MultiPolygon const& multipolygon,
331                                     Strategy const& strategy)
332     {
333         if (geometry::covered_by(point, multipolygon))
334         {
335             return 0;
336         }
337 
338         return point_to_multigeometry
339             <
340                 Point, MultiPolygon, Strategy, false
341             >::apply(point, multipolygon, strategy);
342     }
343 };
344 
345 
346 }} // namespace detail::distance
347 #endif // DOXYGEN_NO_DETAIL
348 
349 
350 
351 
352 #ifndef DOXYGEN_NO_DISPATCH
353 namespace dispatch
354 {
355 
356 
357 // Point-point
358 template <typename P1, typename P2, typename Strategy>
359 struct distance
360     <
361         P1, P2, Strategy, point_tag, point_tag,
362         strategy_tag_distance_point_point, false
363     > : detail::distance::point_to_point<P1, P2, Strategy>
364 {};
365 
366 
367 // Point-line version 2, where point-segment strategy is specified
368 template <typename Point, typename Linestring, typename Strategy>
369 struct distance
370     <
371         Point, Linestring, Strategy, point_tag, linestring_tag,
372         strategy_tag_distance_point_segment, false
373     > : detail::distance::point_to_range<Point, Linestring, closed, Strategy>
374 {};
375 
376 
377 // Point-ring , where point-segment strategy is specified
378 template <typename Point, typename Ring, typename Strategy>
379 struct distance
380     <
381         Point, Ring, Strategy, point_tag, ring_tag,
382         strategy_tag_distance_point_segment, false
383     > : detail::distance::point_to_ring
384         <
385             Point, Ring, closure<Ring>::value, Strategy
386         >
387 {};
388 
389 
390 // Point-polygon , where point-segment strategy is specified
391 template <typename Point, typename Polygon, typename Strategy>
392 struct distance
393     <
394         Point, Polygon, Strategy, point_tag, polygon_tag,
395         strategy_tag_distance_point_segment, false
396     > : detail::distance::point_to_polygon
397         <
398             Point, Polygon, closure<Polygon>::value, Strategy
399         >
400 {};
401 
402 
403 // Point-segment version 2, with point-segment strategy
404 template <typename Point, typename Segment, typename Strategy>
405 struct distance
406     <
407         Point, Segment, Strategy, point_tag, segment_tag,
408         strategy_tag_distance_point_segment, false
409     >
410 {
411     static inline typename strategy::distance::services::return_type
412         <
413             Strategy, Point, typename point_type<Segment>::type
applyboost::geometry::dispatch::distance414         >::type apply(Point const& point,
415                       Segment const& segment,
416                       Strategy const& strategy)
417     {
418         typename point_type<Segment>::type p[2];
419         geometry::detail::assign_point_from_index<0>(segment, p[0]);
420         geometry::detail::assign_point_from_index<1>(segment, p[1]);
421 
422         boost::ignore_unused(strategy);
423         return strategy.apply(point, p[0], p[1]);
424     }
425 };
426 
427 
428 template <typename Point, typename Box, typename Strategy>
429 struct distance
430     <
431          Point, Box, Strategy, point_tag, box_tag,
432          strategy_tag_distance_point_box, false
433     >
434 {
435     static inline typename strategy::distance::services::return_type
436         <
437             Strategy, Point, typename point_type<Box>::type
438         >::type
applyboost::geometry::dispatch::distance439     apply(Point const& point, Box const& box, Strategy const& strategy)
440     {
441         boost::ignore_unused(strategy);
442         return strategy.apply(point, box);
443     }
444 };
445 
446 
447 template<typename Point, typename MultiPoint, typename Strategy>
448 struct distance
449     <
450         Point, MultiPoint, Strategy, point_tag, multi_point_tag,
451         strategy_tag_distance_point_point, false
452     > : detail::distance::point_to_multigeometry
453         <
454             Point, MultiPoint, Strategy
455         >
456 {};
457 
458 
459 template<typename Point, typename MultiLinestring, typename Strategy>
460 struct distance
461     <
462         Point, MultiLinestring, Strategy, point_tag, multi_linestring_tag,
463         strategy_tag_distance_point_segment, false
464     > : detail::distance::point_to_multigeometry
465         <
466             Point, MultiLinestring, Strategy
467         >
468 {};
469 
470 
471 template<typename Point, typename MultiPolygon, typename Strategy>
472 struct distance
473     <
474         Point, MultiPolygon, Strategy, point_tag, multi_polygon_tag,
475         strategy_tag_distance_point_segment, false
476     > : detail::distance::point_to_multigeometry
477         <
478             Point, MultiPolygon, Strategy
479         >
480 {};
481 
482 
483 template <typename Point, typename Linear, typename Strategy>
484 struct distance
485     <
486          Point, Linear, Strategy, point_tag, linear_tag,
487          strategy_tag_distance_point_segment, false
488     > : distance
489         <
490             Point, Linear, Strategy,
491             point_tag, typename tag<Linear>::type,
492             strategy_tag_distance_point_segment, false
493         >
494 {};
495 
496 
497 template <typename Point, typename Areal, typename Strategy>
498 struct distance
499     <
500          Point, Areal, Strategy, point_tag, areal_tag,
501          strategy_tag_distance_point_segment, false
502     > : distance
503         <
504             Point, Areal, Strategy,
505             point_tag, typename tag<Areal>::type,
506             strategy_tag_distance_point_segment, false
507         >
508 {};
509 
510 
511 } // namespace dispatch
512 #endif // DOXYGEN_NO_DISPATCH
513 
514 
515 }} // namespace boost::geometry
516 
517 
518 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_POINT_TO_GEOMETRY_HPP
519