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