geometry/algorithms/discrete_frechet_distance.hpp

0001 // Boost.Geometry
0002
0003 // Copyright (c) 2018 Yaghyavardhan Singh Khangarot, Hyderabad, India.
0004 // Contributed and/or modified by Yaghyavardhan Singh Khangarot,
0005 //   as part of Google Summer of Code 2018 program.
0006
0007 // This file was modified by Oracle on 2018-2023.
0008 // Modifications copyright (c) 2018-2023 Oracle and/or its affiliates.
0009 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011
0012 // Use, modification and distribution is subject to the Boost Software License,
0013 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0014 // http://www.boost.org/LICENSE_1_0.txt)
0015
0016 #ifndef BOOST_GEOMETRY_ALGORITHMS_DISCRETE_FRECHET_DISTANCE_HPP
0017 #define BOOST_GEOMETRY_ALGORITHMS_DISCRETE_FRECHET_DISTANCE_HPP
0018
0019 #ifdef BOOST_GEOMETRY_DEBUG_FRECHET_DISTANCE
0020 #include <iostream>
0021 #endif
0022
0023 #include <vector>
0024
0025 #include <boost/range/size.hpp>
0026
0027 #include <boost/geometry/algorithms/detail/dummy_geometries.hpp>
0028 #include <boost/geometry/algorithms/detail/throw_on_empty_input.hpp>
0029 #include <boost/geometry/algorithms/not_implemented.hpp>
0030 #include <boost/geometry/core/assert.hpp>
0031 #include <boost/geometry/core/tag.hpp>
0032 #include <boost/geometry/core/tags.hpp>
0033 #include <boost/geometry/core/point_type.hpp>
0034 #include <boost/geometry/strategies/detail.hpp>
0035 #include <boost/geometry/strategies/discrete_distance/cartesian.hpp>
0036 #include <boost/geometry/strategies/discrete_distance/geographic.hpp>
0037 #include <boost/geometry/strategies/discrete_distance/spherical.hpp>
0038 #include <boost/geometry/strategies/distance_result.hpp>
0039 #include <boost/geometry/util/range.hpp>
0040
0041
0042 namespace boost { namespace geometry
0043 {
0044
0045 #ifndef DOXYGEN_NO_DETAIL
0046 namespace detail { namespace discrete_frechet_distance
0047 {
0048
0049 // TODO: The implementation should calculate comparable distances
0050
0051 template <typename SizeType1, typename SizeType2, typename ResultType>
0052 class coup_mat
0053 {
0054 public:
0055     coup_mat(SizeType1 w, SizeType2 h)
0056         : m_data(w * h,-1), m_width(w), m_height(h)
0057     {}
0058
0059     ResultType & operator()(SizeType1 i, SizeType2 j)
0060     {
0061         BOOST_GEOMETRY_ASSERT(i < m_width && j < m_height);
0062         return m_data[j * m_width + i];
0063     }
0064
0065 private:
0066     std::vector<ResultType> m_data;
0067     SizeType1 m_width;
0068     SizeType2 m_height;
0069 };
0070
0071 struct linestring_linestring
0072 {
0073     template <typename Linestring1, typename Linestring2, typename Strategies>
0074     static inline auto apply(Linestring1 const& ls1, Linestring2 const& ls2,
0075                              Strategies const& strategies)
0076     {
0077         typedef typename distance_result
0078             <
0079                 typename point_type<Linestring1>::type,
0080                 typename point_type<Linestring2>::type,
0081                 Strategies
0082             >::type result_type;
0083         typedef typename boost::range_size<Linestring1>::type size_type1;
0084         typedef typename boost::range_size<Linestring2>::type size_type2;
0085
0086         boost::geometry::detail::throw_on_empty_input(ls1);
0087         boost::geometry::detail::throw_on_empty_input(ls2);
0088
0089         // We can assume the inputs are not empty
0090         auto const strategy = strategies.distance(dummy_point(), dummy_point());
0091
0092         size_type1 const a = boost::size(ls1);
0093         size_type2 const b = boost::size(ls2);
0094
0095         //Coupling Matrix CoupMat(a,b,-1);
0096         coup_mat<size_type1, size_type2, result_type> coup_matrix(a, b);
0097
0098         result_type const not_feasible = -100;
0099         //findin the Coupling Measure
0100         for (size_type1 i = 0 ; i < a ; i++ )
0101         {
0102             for (size_type2 j = 0 ; j < b ; j++ )
0103             {
0104                 result_type dis = strategy.apply(range::at(ls1,i), range::at(ls2,j));
0105                 if(i==0 && j==0)
0106                     coup_matrix(i,j) = dis;
0107                 else if(i==0 && j>0)
0108                     coup_matrix(i,j) =
0109                         (std::max)(coup_matrix(i,j-1), dis);
0110                 else if(i>0 && j==0)
0111                     coup_matrix(i,j) =
0112                         (std::max)(coup_matrix(i-1,j), dis);
0113                 else if(i>0 && j>0)
0114                     coup_matrix(i,j) =
0115                         (std::max)((std::min)(coup_matrix(i,j-1),
0116                                               (std::min)(coup_matrix(i-1,j),
0117                                                          coup_matrix(i-1,j-1))),
0118                                    dis);
0119                 else
0120                     coup_matrix(i,j) = not_feasible;
0121             }
0122         }
0123
0124         #ifdef BOOST_GEOMETRY_DEBUG_FRECHET_DISTANCE
0125         //Print CoupLing Matrix
0126         for(size_type i = 0; i <a; i++)
0127         {
0128             for(size_type j = 0; j <b; j++)
0129             std::cout << coup_matrix(i,j) << " ";
0130             std::cout << std::endl;
0131         }
0132         #endif
0133
0134         return coup_matrix(a-1,b-1);
0135     }
0136 };
0137
0138 }} // namespace detail::frechet_distance
0139 #endif // DOXYGEN_NO_DETAIL
0140
0141 #ifndef DOXYGEN_NO_DISPATCH
0142 namespace dispatch
0143 {
0144 template
0145 <
0146     typename Geometry1,
0147     typename Geometry2,
0148     typename Tag1 = typename tag<Geometry1>::type,
0149     typename Tag2 = typename tag<Geometry2>::type
0150 >
0151 struct discrete_frechet_distance : not_implemented<Tag1, Tag2>
0152 {};
0153
0154 template <typename Linestring1, typename Linestring2>
0155 struct discrete_frechet_distance
0156     <
0157         Linestring1,
0158         Linestring2,
0159         linestring_tag,
0160         linestring_tag
0161     >
0162     : detail::discrete_frechet_distance::linestring_linestring
0163 {};
0164
0165 } // namespace dispatch
0166 #endif // DOXYGEN_NO_DISPATCH
0167
0168
0169 namespace resolve_strategy {
0170
0171 template
0172 <
0173     typename Strategies,
0174     bool IsUmbrella = strategies::detail::is_umbrella_strategy<Strategies>::value
0175 >
0176 struct discrete_frechet_distance
0177 {
0178     template <typename Geometry1, typename Geometry2>
0179     static inline auto apply(Geometry1 const& geometry1, Geometry2 const& geometry2,
0180                              Strategies const& strategies)
0181     {
0182         return dispatch::discrete_frechet_distance
0183             <
0184                 Geometry1, Geometry2
0185             >::apply(geometry1, geometry2, strategies);
0186     }
0187 };
0188
0189 template <typename Strategy>
0190 struct discrete_frechet_distance<Strategy, false>
0191 {
0192     template <typename Geometry1, typename Geometry2>
0193     static inline auto apply(Geometry1 const& geometry1, Geometry2 const& geometry2,
0194                              Strategy const& strategy)
0195     {
0196         using strategies::discrete_distance::services::strategy_converter;
0197         return dispatch::discrete_frechet_distance
0198             <
0199                 Geometry1, Geometry2
0200             >::apply(geometry1, geometry2,
0201                      strategy_converter<Strategy>::get(strategy));
0202     }
0203 };
0204
0205 template <>
0206 struct discrete_frechet_distance<default_strategy, false>
0207 {
0208     template <typename Geometry1, typename Geometry2>
0209     static inline auto apply(Geometry1 const& geometry1, Geometry2 const& geometry2,
0210                              default_strategy const&)
0211     {
0212         typedef typename strategies::discrete_distance::services::default_strategy
0213             <
0214                 Geometry1, Geometry2
0215             >::type strategies_type;
0216
0217         return dispatch::discrete_frechet_distance
0218             <
0219                 Geometry1, Geometry2
0220             >::apply(geometry1, geometry2, strategies_type());
0221     }
0222 };
0223
0224 } // namespace resolve_strategy
0225
0226
0227 /*!
0228 \brief Calculate discrete Frechet distance between two geometries (currently
0229        works for LineString-LineString) using specified strategy.
0230 \ingroup discrete_frechet_distance
0231 \tparam Geometry1 \tparam_geometry
0232 \tparam Geometry2 \tparam_geometry
0233 \tparam Strategy A type fulfilling a DistanceStrategy concept
0234 \param geometry1 Input geometry
0235 \param geometry2 Input geometry
0236 \param strategy Distance strategy to be used to calculate Pt-Pt distance
0237
0238 \qbk{distinguish,with strategy}
0239 \qbk{[include reference/algorithms/discrete_frechet_distance.qbk]}
0240
0241 \qbk{
0242 [heading Available Strategies]
0243 \* [link geometry.reference.strategies.strategy_distance_pythagoras Pythagoras (cartesian)]
0244 \* [link geometry.reference.strategies.strategy_distance_haversine Haversine (spherical)]
0245 [/ \* more (currently extensions): Vincenty\, Andoyer (geographic) ]
0246
0247 [heading Example]
0248 [discrete_frechet_distance_strategy]
0249 [discrete_frechet_distance_strategy_output]
0250 }
0251 */
0252 template <typename Geometry1, typename Geometry2, typename Strategy>
0253 inline auto discrete_frechet_distance(Geometry1 const& geometry1,
0254                                       Geometry2 const& geometry2,
0255                                       Strategy const& strategy)
0256 {
0257     return resolve_strategy::discrete_frechet_distance
0258             <
0259                 Strategy
0260             >::apply(geometry1, geometry2, strategy);
0261 }
0262
0263 // Algorithm overload using default Pt-Pt distance strategy
0264
0265 /*!
0266 \brief Calculate discrete Frechet distance between two geometries (currently
0267        work for LineString-LineString).
0268 \ingroup discrete_frechet_distance
0269 \tparam Geometry1 \tparam_geometry
0270 \tparam Geometry2 \tparam_geometry
0271 \param geometry1 Input geometry
0272 \param geometry2 Input geometry
0273
0274 \qbk{[include reference/algorithms/discrete_frechet_distance.qbk]}
0275
0276 \qbk{
0277 [heading Example]
0278 [discrete_frechet_distance]
0279 [discrete_frechet_distance_output]
0280 }
0281 */
0282 template <typename Geometry1, typename Geometry2>
0283 inline auto discrete_frechet_distance(Geometry1 const& geometry1,
0284                                       Geometry2 const& geometry2)
0285 {
0286     return resolve_strategy::discrete_frechet_distance
0287             <
0288                 default_strategy
0289             >::apply(geometry1, geometry2, default_strategy());
0290 }
0291
0292 }} // namespace boost::geometry
0293
0294 #endif // BOOST_GEOMETRY_ALGORITHMS_DISCRETE_FRECHET_DISTANCE_HPP