/usr/include/boost/geometry/algorithms
Edit: /usr/include/boost/geometry/algorithms/discrete_frechet_distance.hpp (7844B)
// Boost.Geometry
// Copyright (c) 2018 Yaghyavardhan Singh Khangarot, Hyderabad, India.
// Contributed and/or modified by Yaghyavardhan Singh Khangarot,
// as part of Google Summer of Code 2018 program.
// This file was modified by Oracle on 2018.
// Modifications copyright (c) 2018 Oracle and/or its affiliates.
// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
// Use, modification and distribution is subject to the Boost Software License,
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
#ifndef BOOST_GEOMETRY_ALGORITHMS_DISCRETE_FRECHET_DISTANCE_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DISCRETE_FRECHET_DISTANCE_HPP
#include
#ifdef BOOST_GEOMETRY_DEBUG_FRECHET_DISTANCE
#include
#endif
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
namespace boost { namespace geometry
{
#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace discrete_frechet_distance
{
template
class coup_mat
{
public:
coup_mat(size_type1 w, size_type2 h)
: m_data(w * h,-1), m_width(w), m_height(h)
{}
result_type & operator()(size_type1 i, size_type2 j)
{
BOOST_GEOMETRY_ASSERT(i < m_width && j < m_height);
return m_data[j * m_width + i];
}
private:
std::vector m_data;
size_type1 m_width;
size_type2 m_height;
};
struct linestring_linestring
{
template
static inline typename distance_result
<
typename point_type::type,
typename point_type::type,
Strategy
>::type apply(Linestring1 const& ls1, Linestring2 const& ls2, Strategy const& strategy)
{
typedef typename distance_result
<
typename point_type::type,
typename point_type::type,
Strategy
>::type result_type;
typedef typename boost::range_size::type size_type1;
typedef typename boost::range_size::type size_type2;
boost::geometry::detail::throw_on_empty_input(ls1);
boost::geometry::detail::throw_on_empty_input(ls2);
size_type1 const a = boost::size(ls1);
size_type2 const b = boost::size(ls2);
//Coupling Matrix CoupMat(a,b,-1);
coup_mat coup_matrix(a,b);
result_type const not_feasible = -100;
//findin the Coupling Measure
for (size_type1 i = 0 ; i < a ; i++ )
{
for(size_type2 j=0;j0)
coup_matrix(i,j) =
(std::max)(coup_matrix(i,j-1), dis);
else if(i>0 && j==0)
coup_matrix(i,j) =
(std::max)(coup_matrix(i-1,j), dis);
else if(i>0 && j>0)
coup_matrix(i,j) =
(std::max)((std::min)(coup_matrix(i,j-1),
(std::min)(coup_matrix(i-1,j),
coup_matrix(i-1,j-1))),
dis);
else
coup_matrix(i,j) = not_feasible;
}
}
#ifdef BOOST_GEOMETRY_DEBUG_FRECHET_DISTANCE
//Print CoupLing Matrix
for(size_type i = 0; i ::type,
typename Tag2 = typename tag::type
>
struct discrete_frechet_distance : not_implemented
{};
template
struct discrete_frechet_distance
<
Linestring1,
Linestring2,
linestring_tag,
linestring_tag
>
: detail::discrete_frechet_distance::linestring_linestring
{};
} // namespace dispatch
#endif // DOXYGEN_NO_DISPATCH
/*!
\brief Calculate discrete Frechet distance between two geometries (currently
works for LineString-LineString) using specified strategy.
\ingroup discrete_frechet_distance
\tparam Geometry1 \tparam_geometry
\tparam Geometry2 \tparam_geometry
\tparam Strategy A type fulfilling a DistanceStrategy concept
\param geometry1 Input geometry
\param geometry2 Input geometry
\param strategy Distance strategy to be used to calculate Pt-Pt distance
\qbk{distinguish,with strategy}
\qbk{[include reference/algorithms/discrete_frechet_distance.qbk]}
\qbk{
[heading Available Strategies]
\* [link geometry.reference.strategies.strategy_distance_pythagoras Pythagoras (cartesian)]
\* [link geometry.reference.strategies.strategy_distance_haversine Haversine (spherical)]
[/ \* more (currently extensions): Vincenty\, Andoyer (geographic) ]
[heading Example]
[discrete_frechet_distance_strategy]
[discrete_frechet_distance_strategy_output]
}
*/
template
inline typename distance_result
<
typename point_type::type,
typename point_type::type,
Strategy
>::type
discrete_frechet_distance(Geometry1 const& geometry1,
Geometry2 const& geometry2,
Strategy const& strategy)
{
return dispatch::discrete_frechet_distance
<
Geometry1, Geometry2
>::apply(geometry1, geometry2, strategy);
}
// Algorithm overload using default Pt-Pt distance strategy
/*!
\brief Calculate discrete Frechet distance between two geometries (currently
work for LineString-LineString).
\ingroup discrete_frechet_distance
\tparam Geometry1 \tparam_geometry
\tparam Geometry2 \tparam_geometry
\param geometry1 Input geometry
\param geometry2 Input geometry
\qbk{[include reference/algorithms/discrete_frechet_distance.qbk]}
\qbk{
[heading Example]
[discrete_frechet_distance]
[discrete_frechet_distance_output]
}
*/
template
inline typename distance_result
<
typename point_type::type,
typename point_type::type
>::type
discrete_frechet_distance(Geometry1 const& geometry1, Geometry2 const& geometry2)
{
typedef typename strategy::distance::services::default_strategy
<
point_tag, point_tag,
typename point_type::type,
typename point_type::type
>::type strategy_type;
return discrete_frechet_distance(geometry1, geometry2, strategy_type());
}
}} // namespace boost::geometry
#endif // BOOST_GEOMETRY_ALGORITHMS_DISCRETE_FRECHET_DISTANCE_HPP