1 // Boost.Geometry
2 
3 // Copyright (c) 2018 Yaghyavardhan Singh Khangarot, Hyderabad, India.
4 // Contributed and/or modified by Yaghyavardhan Singh Khangarot,
5 //   as part of Google Summer of Code 2018 program.
6 
7 // This file was modified by Oracle on 2018.
8 // Modifications copyright (c) 2018, Oracle and/or its affiliates.
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
10 
11 // Use, modification and distribution is subject to the Boost Software License,
12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
13 // http://www.boost.org/LICENSE_1_0.txt)
14 
15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DISCRETE_HAUSDORFF_DISTANCE_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_DISCRETE_HAUSDORFF_DISTANCE_HPP
17 
18 #include <algorithm>
19 
20 #ifdef BOOST_GEOMETRY_DEBUG_HAUSDORFF_DISTANCE
21 #include <iostream>
22 #endif
23 
24 #include <iterator>
25 #include <utility>
26 #include <vector>
27 #include <limits>
28 
29 #include <boost/geometry/algorithms/detail/throw_on_empty_input.hpp>
30 #include <boost/geometry/algorithms/not_implemented.hpp>
31 #include <boost/geometry/core/point_type.hpp>
32 #include <boost/geometry/core/tag.hpp>
33 #include <boost/geometry/core/tags.hpp>
34 #include <boost/geometry/strategies/distance.hpp>
35 #include <boost/geometry/strategies/distance_result.hpp>
36 #include <boost/geometry/util/range.hpp>
37 
38 #ifdef BOOST_GEOMETRY_ENABLE_SIMILARITY_RTREE
39 #include <boost/geometry/index/rtree.hpp>
40 #endif // BOOST_GEOMETRY_ENABLE_SIMILARITY_RTREE
41 
42 namespace boost { namespace geometry
43 {
44 
45 #ifndef DOXYGEN_NO_DETAIL
46 namespace detail { namespace discrete_hausdorff_distance
47 {
48 
49 struct point_range
50 {
51     template <typename Point, typename Range, typename Strategy>
52     static inline
53     typename distance_result
54         <
55             typename point_type<Point>::type,
56             typename point_type<Range>::type,
57             Strategy
58         >::type
applyboost::geometry::detail::discrete_hausdorff_distance::point_range59     apply(Point const& pnt, Range const& rng, Strategy const& strategy)
60     {
61         typedef typename distance_result
62             <
63                 typename point_type<Point>::type,
64                 typename point_type<Range>::type,
65                 Strategy
66             >::type result_type;
67         typedef typename boost::range_size<Range>::type size_type;
68 
69         size_type const n = boost::size(rng);
70         result_type dis_min = 0;
71         bool is_dis_min_set = false;
72 
73         for (size_type i = 0 ; i < n ; i++)
74         {
75             result_type dis_temp = strategy.apply(pnt, range::at(rng, i));
76             if (! is_dis_min_set || dis_temp < dis_min)
77             {
78                 dis_min = dis_temp;
79                 is_dis_min_set = true;
80             }
81         }
82         return dis_min;
83     }
84 };
85 
86 struct range_range
87 {
88     template <typename Range1, typename Range2, typename Strategy>
89     static inline
90     typename distance_result
91         <
92             typename point_type<Range1>::type,
93             typename point_type<Range2>::type,
94             Strategy
95         >::type
applyboost::geometry::detail::discrete_hausdorff_distance::range_range96     apply(Range1 const& r1, Range2 const& r2, Strategy const& strategy)
97     {
98 
99         typedef typename distance_result
100             <
101                 typename point_type<Range1>::type,
102                 typename point_type<Range2>::type,
103                 Strategy
104             >::type result_type;
105 
106         typedef typename boost::range_size<Range1>::type size_type;
107 
108         boost::geometry::detail::throw_on_empty_input(r1);
109         boost::geometry::detail::throw_on_empty_input(r2);
110 
111         size_type const n = boost::size(r1);
112         result_type dis_max = 0;
113 
114 #ifdef BOOST_GEOMETRY_ENABLE_SIMILARITY_RTREE
115         namespace bgi = boost::geometry::index;
116         typedef typename point_type<Range1>::type point_t;
117         typedef bgi::rtree<point_t, bgi::linear<4> > rtree_type;
118         rtree_type rtree(boost::begin(r2), boost::end(r2));
119         point_t res;
120 #endif
121 
122         for (size_type i = 0 ; i < n ; i++)
123         {
124 #ifdef BOOST_GEOMETRY_ENABLE_SIMILARITY_RTREE
125             size_type found = rtree.query(bgi::nearest(range::at(r1, i), 1), &res);
126             result_type dis_min = strategy.apply(range::at(r1,i), res);
127 #else
128             result_type dis_min = point_range::apply(range::at(r1, i), r2, strategy);
129 #endif
130             if (dis_min > dis_max )
131             {
132                 dis_max = dis_min;
133             }
134         }
135         return dis_max;
136     }
137 };
138 
139 
140 struct range_multi_range
141 {
142     template <typename Range, typename Multi_range, typename Strategy>
143     static inline
144     typename distance_result
145         <
146             typename point_type<Range>::type,
147             typename point_type<Multi_range>::type,
148             Strategy
149         >::type
applyboost::geometry::detail::discrete_hausdorff_distance::range_multi_range150     apply(Range const& rng, Multi_range const& mrng, Strategy const& strategy)
151     {
152         typedef typename distance_result
153             <
154                 typename point_type<Range>::type,
155                 typename point_type<Multi_range>::type,
156                 Strategy
157             >::type result_type;
158         typedef typename boost::range_size<Multi_range>::type size_type;
159 
160         boost::geometry::detail::throw_on_empty_input(rng);
161         boost::geometry::detail::throw_on_empty_input(mrng);
162 
163         size_type b = boost::size(mrng);
164         result_type haus_dis = 0;
165 
166         for (size_type j = 0 ; j < b ; j++)
167         {
168             result_type dis_max = range_range::apply(rng, range::at(mrng, j), strategy);
169             if (dis_max > haus_dis)
170             {
171                 haus_dis = dis_max;
172             }
173         }
174 
175         return haus_dis;
176     }
177 };
178 
179 
180 struct multi_range_multi_range
181 {
182     template <typename Multi_Range1, typename Multi_range2, typename Strategy>
183     static inline
184     typename distance_result
185         <
186             typename point_type<Multi_Range1>::type,
187             typename point_type<Multi_range2>::type,
188             Strategy
189         >::type
applyboost::geometry::detail::discrete_hausdorff_distance::multi_range_multi_range190     apply(Multi_Range1 const& mrng1, Multi_range2 const& mrng2, Strategy const& strategy)
191     {
192         typedef typename distance_result
193             <
194                 typename point_type<Multi_Range1>::type,
195                 typename point_type<Multi_range2>::type,
196                 Strategy
197             >::type result_type;
198         typedef typename boost::range_size<Multi_Range1>::type size_type;
199 
200         boost::geometry::detail::throw_on_empty_input(mrng1);
201         boost::geometry::detail::throw_on_empty_input(mrng2);
202 
203         size_type n = boost::size(mrng1);
204         result_type haus_dis = 0;
205 
206         for (size_type i = 0 ; i < n ; i++)
207         {
208             result_type dis_max = range_multi_range::apply(range::at(mrng1, i), mrng2, strategy);
209             if (dis_max > haus_dis)
210             {
211                 haus_dis = dis_max;
212             }
213         }
214         return haus_dis;
215     }
216 };
217 
218 }} // namespace detail::hausdorff_distance
219 #endif // DOXYGEN_NO_DETAIL
220 
221 #ifndef DOXYGEN_NO_DISPATCH
222 namespace dispatch
223 {
224 template
225 <
226     typename Geometry1,
227     typename Geometry2,
228     typename Tag1 = typename tag<Geometry1>::type,
229     typename Tag2 = typename tag<Geometry2>::type
230 >
231 struct discrete_hausdorff_distance : not_implemented<Tag1, Tag2>
232 {};
233 
234 // Specialization for point and multi_point
235 template <typename Point, typename MultiPoint>
236 struct discrete_hausdorff_distance<Point, MultiPoint, point_tag, multi_point_tag>
237     : detail::discrete_hausdorff_distance::point_range
238 {};
239 
240 // Specialization for linestrings
241 template <typename Linestring1, typename Linestring2>
242 struct discrete_hausdorff_distance<Linestring1, Linestring2, linestring_tag, linestring_tag>
243     : detail::discrete_hausdorff_distance::range_range
244 {};
245 
246 // Specialization for multi_point-multi_point
247 template <typename MultiPoint1, typename MultiPoint2>
248 struct discrete_hausdorff_distance<MultiPoint1, MultiPoint2, multi_point_tag, multi_point_tag>
249     : detail::discrete_hausdorff_distance::range_range
250 {};
251 
252 // Specialization for Linestring and MultiLinestring
253 template <typename Linestring, typename MultiLinestring>
254 struct discrete_hausdorff_distance<Linestring, MultiLinestring, linestring_tag, multi_linestring_tag>
255     : detail::discrete_hausdorff_distance::range_multi_range
256 {};
257 
258 // Specialization for MultiLinestring and MultiLinestring
259 template <typename MultiLinestring1, typename MultiLinestring2>
260 struct discrete_hausdorff_distance<MultiLinestring1, MultiLinestring2, multi_linestring_tag, multi_linestring_tag>
261     : detail::discrete_hausdorff_distance::multi_range_multi_range
262 {};
263 
264 } // namespace dispatch
265 #endif // DOXYGEN_NO_DISPATCH
266 
267 // Algorithm overload using explicitly passed Pt-Pt distance strategy
268 
269 /*!
270 \brief Calculate discrete Hausdorff distance between two geometries (currently
271     works for LineString-LineString, MultiPoint-MultiPoint, Point-MultiPoint,
272     MultiLineString-MultiLineString) using specified strategy.
273 \ingroup discrete_hausdorff_distance
274 \tparam Geometry1 \tparam_geometry
275 \tparam Geometry2 \tparam_geometry
276 \tparam Strategy A type fulfilling a DistanceStrategy concept
277 \param geometry1 Input geometry
278 \param geometry2 Input geometry
279 \param strategy Distance strategy to be used to calculate Pt-Pt distance
280 
281 \qbk{distinguish,with strategy}
282 \qbk{[include reference/algorithms/discrete_hausdorff_distance.qbk]}
283 
284 \qbk{
285 [heading Available Strategies]
286 \* [link geometry.reference.strategies.strategy_distance_pythagoras Pythagoras (cartesian)]
287 \* [link geometry.reference.strategies.strategy_distance_haversine Haversine (spherical)]
288 [/ \* more (currently extensions): Vincenty\, Andoyer (geographic) ]
289 
290 [heading Example]
291 [discrete_hausdorff_distance_strategy]
292 [discrete_hausdorff_distance_strategy_output]
293 }
294 */
295 template <typename Geometry1, typename Geometry2, typename Strategy>
296 inline
297 typename distance_result
298     <
299         typename point_type<Geometry1>::type,
300         typename point_type<Geometry2>::type,
301         Strategy
302     >::type
discrete_hausdorff_distance(Geometry1 const & geometry1,Geometry2 const & geometry2,Strategy const & strategy)303 discrete_hausdorff_distance(Geometry1 const& geometry1,
304                             Geometry2 const& geometry2,
305                             Strategy const& strategy)
306 {
307     return dispatch::discrete_hausdorff_distance
308         <
309             Geometry1, Geometry2
310         >::apply(geometry1, geometry2, strategy);
311 }
312 
313 /*!
314 \brief Calculate discrete Hausdorff distance between two geometries (currently
315     works for LineString-LineString, MultiPoint-MultiPoint, Point-MultiPoint,
316     MultiLineString-MultiLineString).
317 \ingroup discrete_hausdorff_distance
318 \tparam Geometry1 \tparam_geometry
319 \tparam Geometry2 \tparam_geometry
320 \param geometry1 Input geometry
321 \param geometry2 Input geometry
322 
323 \qbk{[include reference/algorithms/discrete_hausdorff_distance.qbk]}
324 
325 \qbk{
326 [heading Example]
327 [discrete_hausdorff_distance]
328 [discrete_hausdorff_distance_output]
329 }
330 */
331 template <typename Geometry1, typename Geometry2>
332 inline
333 typename distance_result
334     <
335         typename point_type<Geometry1>::type,
336         typename point_type<Geometry2>::type
337     >::type
discrete_hausdorff_distance(Geometry1 const & geometry1,Geometry2 const & geometry2)338 discrete_hausdorff_distance(Geometry1 const& geometry1,
339                             Geometry2 const& geometry2)
340 {
341     typedef typename strategy::distance::services::default_strategy
342         <
343             point_tag, point_tag,
344             typename point_type<Geometry1>::type,
345             typename point_type<Geometry2>::type
346         >::type strategy_type;
347 
348     return discrete_hausdorff_distance(geometry1, geometry2, strategy_type());
349 }
350 
351 }} // namespace boost::geometry
352 
353 #endif // BOOST_GEOMETRY_ALGORITHMS_DISCRETE_HAUSDORFF_DISTANCE_HPP
354