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_FRECHET_DISTANCE_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_DISCRETE_FRECHET_DISTANCE_HPP
17
18 #include <algorithm>
19
20 #ifdef BOOST_GEOMETRY_DEBUG_FRECHET_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/assert.hpp>
32 #include <boost/geometry/core/tag.hpp>
33 #include <boost/geometry/core/tags.hpp>
34 #include <boost/geometry/core/point_type.hpp>
35 #include <boost/geometry/strategies/distance.hpp>
36 #include <boost/geometry/strategies/distance_result.hpp>
37 #include <boost/geometry/util/range.hpp>
38
39
40 namespace boost { namespace geometry
41 {
42
43 #ifndef DOXYGEN_NO_DETAIL
44 namespace detail { namespace discrete_frechet_distance
45 {
46
47 template <typename size_type1 , typename size_type2,typename result_type>
48 class coup_mat
49 {
50 public:
coup_mat(size_type1 w,size_type2 h)51 coup_mat(size_type1 w, size_type2 h)
52 : m_data(w * h,-1), m_width(w), m_height(h)
53 {}
54
operator ()(size_type1 i,size_type2 j)55 result_type & operator()(size_type1 i, size_type2 j)
56 {
57 BOOST_GEOMETRY_ASSERT(i < m_width && j < m_height);
58 return m_data[j * m_width + i];
59 }
60
61 private:
62 std::vector<result_type> m_data;
63 size_type1 m_width;
64 size_type2 m_height;
65 };
66
67 struct linestring_linestring
68 {
69 template <typename Linestring1, typename Linestring2, typename Strategy>
70 static inline typename distance_result
71 <
72 typename point_type<Linestring1>::type,
73 typename point_type<Linestring2>::type,
74 Strategy
applyboost::geometry::detail::discrete_frechet_distance::linestring_linestring75 >::type apply(Linestring1 const& ls1, Linestring2 const& ls2, Strategy const& strategy)
76 {
77 typedef typename distance_result
78 <
79 typename point_type<Linestring1>::type,
80 typename point_type<Linestring2>::type,
81 Strategy
82 >::type result_type;
83 typedef typename boost::range_size<Linestring1>::type size_type1;
84 typedef typename boost::range_size<Linestring2>::type size_type2;
85
86
87 boost::geometry::detail::throw_on_empty_input(ls1);
88 boost::geometry::detail::throw_on_empty_input(ls2);
89
90 size_type1 const a = boost::size(ls1);
91 size_type2 const b = boost::size(ls2);
92
93
94 //Coupling Matrix CoupMat(a,b,-1);
95 coup_mat<size_type1,size_type2,result_type> coup_matrix(a,b);
96
97 result_type const not_feasible = -100;
98 //findin the Coupling Measure
99 for (size_type1 i = 0 ; i < a ; i++ )
100 {
101 for(size_type2 j=0;j<b;j++)
102 {
103 result_type dis = strategy.apply(range::at(ls1,i), range::at(ls2,j));
104 if(i==0 && j==0)
105 coup_matrix(i,j) = dis;
106 else if(i==0 && j>0)
107 coup_matrix(i,j) =
108 (std::max)(coup_matrix(i,j-1), dis);
109 else if(i>0 && j==0)
110 coup_matrix(i,j) =
111 (std::max)(coup_matrix(i-1,j), dis);
112 else if(i>0 && j>0)
113 coup_matrix(i,j) =
114 (std::max)((std::min)(coup_matrix(i,j-1),
115 (std::min)(coup_matrix(i-1,j),
116 coup_matrix(i-1,j-1))),
117 dis);
118 else
119 coup_matrix(i,j) = not_feasible;
120 }
121 }
122
123 #ifdef BOOST_GEOMETRY_DEBUG_FRECHET_DISTANCE
124 //Print CoupLing Matrix
125 for(size_type i = 0; i <a; i++)
126 {
127 for(size_type j = 0; j <b; j++)
128 std::cout << coup_matrix(i,j) << " ";
129 std::cout << std::endl;
130 }
131 #endif
132
133 return coup_matrix(a-1,b-1);
134 }
135 };
136
137 }} // namespace detail::frechet_distance
138 #endif // DOXYGEN_NO_DETAIL
139
140 #ifndef DOXYGEN_NO_DISPATCH
141 namespace dispatch
142 {
143 template
144 <
145 typename Geometry1,
146 typename Geometry2,
147 typename Tag1 = typename tag<Geometry1>::type,
148 typename Tag2 = typename tag<Geometry2>::type
149 >
150 struct discrete_frechet_distance : not_implemented<Tag1, Tag2>
151 {};
152
153 template <typename Linestring1, typename Linestring2>
154 struct discrete_frechet_distance
155 <
156 Linestring1,
157 Linestring2,
158 linestring_tag,
159 linestring_tag
160 >
161 : detail::discrete_frechet_distance::linestring_linestring
162 {};
163
164 } // namespace dispatch
165 #endif // DOXYGEN_NO_DISPATCH
166
167
168 /*!
169 \brief Calculate discrete Frechet distance between two geometries (currently
170 works for LineString-LineString) using specified strategy.
171 \ingroup discrete_frechet_distance
172 \tparam Geometry1 \tparam_geometry
173 \tparam Geometry2 \tparam_geometry
174 \tparam Strategy A type fulfilling a DistanceStrategy concept
175 \param geometry1 Input geometry
176 \param geometry2 Input geometry
177 \param strategy Distance strategy to be used to calculate Pt-Pt distance
178
179 \qbk{distinguish,with strategy}
180 \qbk{[include reference/algorithms/discrete_frechet_distance.qbk]}
181
182 \qbk{
183 [heading Available Strategies]
184 \* [link geometry.reference.strategies.strategy_distance_pythagoras Pythagoras (cartesian)]
185 \* [link geometry.reference.strategies.strategy_distance_haversine Haversine (spherical)]
186 [/ \* more (currently extensions): Vincenty\, Andoyer (geographic) ]
187
188 [heading Example]
189 [discrete_frechet_distance_strategy]
190 [discrete_frechet_distance_strategy_output]
191 }
192 */
193 template <typename Geometry1, typename Geometry2, typename Strategy>
194 inline typename distance_result
195 <
196 typename point_type<Geometry1>::type,
197 typename point_type<Geometry2>::type,
198 Strategy
199 >::type
discrete_frechet_distance(Geometry1 const & geometry1,Geometry2 const & geometry2,Strategy const & strategy)200 discrete_frechet_distance(Geometry1 const& geometry1,
201 Geometry2 const& geometry2,
202 Strategy const& strategy)
203 {
204 return dispatch::discrete_frechet_distance
205 <
206 Geometry1, Geometry2
207 >::apply(geometry1, geometry2, strategy);
208 }
209
210 // Algorithm overload using default Pt-Pt distance strategy
211
212 /*!
213 \brief Calculate discrete Frechet distance between two geometries (currently
214 work for LineString-LineString).
215 \ingroup discrete_frechet_distance
216 \tparam Geometry1 \tparam_geometry
217 \tparam Geometry2 \tparam_geometry
218 \param geometry1 Input geometry
219 \param geometry2 Input geometry
220
221 \qbk{[include reference/algorithms/discrete_frechet_distance.qbk]}
222
223 \qbk{
224 [heading Example]
225 [discrete_frechet_distance]
226 [discrete_frechet_distance_output]
227 }
228 */
229 template <typename Geometry1, typename Geometry2>
230 inline typename distance_result
231 <
232 typename point_type<Geometry1>::type,
233 typename point_type<Geometry2>::type
234 >::type
discrete_frechet_distance(Geometry1 const & geometry1,Geometry2 const & geometry2)235 discrete_frechet_distance(Geometry1 const& geometry1, Geometry2 const& geometry2)
236 {
237 typedef typename strategy::distance::services::default_strategy
238 <
239 point_tag, point_tag,
240 typename point_type<Geometry1>::type,
241 typename point_type<Geometry2>::type
242 >::type strategy_type;
243
244 return discrete_frechet_distance(geometry1, geometry2, strategy_type());
245 }
246
247 }} // namespace boost::geometry
248
249 #endif // BOOST_GEOMETRY_ALGORITHMS_DISCRETE_FRECHET_DISTANCE_HPP
250