geometry/algorithms/discrete_hausdorff_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-2021.
0008 // Modifications copyright (c) 2018-2021, Oracle and/or its affiliates.
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010
0011 // Use, modification and distribution is subject to the Boost Software License,
0012 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0013 // http://www.boost.org/LICENSE_1_0.txt)
0014
0015 #ifndef BOOST_GEOMETRY_ALGORITHMS_DISCRETE_HAUSDORFF_DISTANCE_HPP
0016 #define BOOST_GEOMETRY_ALGORITHMS_DISCRETE_HAUSDORFF_DISTANCE_HPP
0017
0018 #include <algorithm>
0019
0020 #ifdef BOOST_GEOMETRY_DEBUG_HAUSDORFF_DISTANCE
0021 #include <iostream>
0022 #endif
0023
0024 #include <iterator>
0025 #include <utility>
0026 #include <vector>
0027 #include <limits>
0028
0029 #include <boost/range/size.hpp>
0030
0031 #include <boost/geometry/algorithms/detail/dummy_geometries.hpp>
0032 #include <boost/geometry/algorithms/detail/throw_on_empty_input.hpp>
0033 #include <boost/geometry/algorithms/not_implemented.hpp>
0034 #include <boost/geometry/core/point_type.hpp>
0035 #include <boost/geometry/core/tag.hpp>
0036 #include <boost/geometry/core/tags.hpp>
0037 #include <boost/geometry/strategies/detail.hpp>
0038 #include <boost/geometry/strategies/discrete_distance/cartesian.hpp>
0039 #include <boost/geometry/strategies/discrete_distance/geographic.hpp>
0040 #include <boost/geometry/strategies/discrete_distance/spherical.hpp>
0041 #include <boost/geometry/strategies/distance_result.hpp>
0042 #include <boost/geometry/util/range.hpp>
0043
0044 // Note that in order for this to work umbrella strategy has to contain
0045 // index strategies.
0046 #ifdef BOOST_GEOMETRY_ENABLE_SIMILARITY_RTREE
0047 #include <boost/geometry/index/rtree.hpp>
0048 #endif // BOOST_GEOMETRY_ENABLE_SIMILARITY_RTREE
0049
0050 namespace boost { namespace geometry
0051 {
0052
0053 #ifndef DOXYGEN_NO_DETAIL
0054 namespace detail { namespace discrete_hausdorff_distance
0055 {
0056
0057 // TODO: The implementation should calculate comparable distances
0058
0059 struct point_range
0060 {
0061     template <typename Point, typename Range, typename Strategies>
0062     static inline auto apply(Point const& pnt, Range const& rng,
0063                              Strategies const& strategies)
0064     {
0065         typedef typename distance_result
0066             <
0067                 Point,
0068                 typename point_type<Range>::type,
0069                 Strategies
0070             >::type result_type;
0071
0072         typedef typename boost::range_size<Range>::type size_type;
0073
0074         boost::geometry::detail::throw_on_empty_input(rng);
0075
0076         auto const strategy = strategies.distance(dummy_point(), dummy_point());
0077
0078         size_type const n = boost::size(rng);
0079         result_type dis_min = 0;
0080         bool is_dis_min_set = false;
0081
0082         for (size_type i = 0 ; i < n ; i++)
0083         {
0084             result_type dis_temp = strategy.apply(pnt, range::at(rng, i));
0085             if (! is_dis_min_set || dis_temp < dis_min)
0086             {
0087                 dis_min = dis_temp;
0088                 is_dis_min_set = true;
0089             }
0090         }
0091         return dis_min;
0092     }
0093 };
0094
0095 struct range_range
0096 {
0097     template <typename Range1, typename Range2, typename Strategies>
0098     static inline auto apply(Range1 const& r1, Range2 const& r2,
0099                              Strategies const& strategies)
0100     {
0101         typedef typename distance_result
0102             <
0103                 typename point_type<Range1>::type,
0104                 typename point_type<Range2>::type,
0105                 Strategies
0106             >::type result_type;
0107
0108         typedef typename boost::range_size<Range1>::type size_type;
0109
0110         boost::geometry::detail::throw_on_empty_input(r1);
0111         boost::geometry::detail::throw_on_empty_input(r2);
0112
0113         size_type const n = boost::size(r1);
0114         result_type dis_max = 0;
0115
0116 #ifdef BOOST_GEOMETRY_ENABLE_SIMILARITY_RTREE
0117         namespace bgi = boost::geometry::index;
0118         typedef typename point_type<Range1>::type point_t;
0119         typedef bgi::rtree<point_t, bgi::linear<4> > rtree_type;
0120         rtree_type rtree(boost::begin(r2), boost::end(r2));
0121         point_t res;
0122 #endif
0123
0124         for (size_type i = 0 ; i < n ; i++)
0125         {
0126 #ifdef BOOST_GEOMETRY_ENABLE_SIMILARITY_RTREE
0127             size_type found = rtree.query(bgi::nearest(range::at(r1, i), 1), &res);
0128             result_type dis_min = strategy.apply(range::at(r1,i), res);
0129 #else
0130             result_type dis_min = point_range::apply(range::at(r1, i), r2, strategies);
0131 #endif
0132             if (dis_min > dis_max )
0133             {
0134                 dis_max = dis_min;
0135             }
0136         }
0137         return dis_max;
0138     }
0139 };
0140
0141
0142 struct range_multi_range
0143 {
0144     template <typename Range, typename Multi_range, typename Strategies>
0145     static inline auto apply(Range const& rng, Multi_range const& mrng,
0146                              Strategies const& strategies)
0147     {
0148         typedef typename distance_result
0149             <
0150                 typename point_type<Range>::type,
0151                 typename point_type<Multi_range>::type,
0152                 Strategies
0153             >::type result_type;
0154         typedef typename boost::range_size<Multi_range>::type size_type;
0155
0156         boost::geometry::detail::throw_on_empty_input(rng);
0157         boost::geometry::detail::throw_on_empty_input(mrng);
0158
0159         size_type b = boost::size(mrng);
0160         result_type haus_dis = 0;
0161
0162         for (size_type j = 0 ; j < b ; j++)
0163         {
0164             result_type dis_max = range_range::apply(rng, range::at(mrng, j), strategies);
0165             if (dis_max > haus_dis)
0166             {
0167                 haus_dis = dis_max;
0168             }
0169         }
0170
0171         return haus_dis;
0172     }
0173 };
0174
0175
0176 struct multi_range_multi_range
0177 {
0178     template <typename Multi_Range1, typename Multi_range2, typename Strategies>
0179     static inline auto apply(Multi_Range1 const& mrng1, Multi_range2 const& mrng2,
0180                              Strategies const& strategies)
0181     {
0182         typedef typename distance_result
0183             <
0184                 typename point_type<Multi_Range1>::type,
0185                 typename point_type<Multi_range2>::type,
0186                 Strategies
0187             >::type result_type;
0188         typedef typename boost::range_size<Multi_Range1>::type size_type;
0189
0190         boost::geometry::detail::throw_on_empty_input(mrng1);
0191         boost::geometry::detail::throw_on_empty_input(mrng2);
0192
0193         size_type n = boost::size(mrng1);
0194         result_type haus_dis = 0;
0195
0196         for (size_type i = 0 ; i < n ; i++)
0197         {
0198             result_type dis_max = range_multi_range::apply(range::at(mrng1, i), mrng2, strategies);
0199             if (dis_max > haus_dis)
0200             {
0201                 haus_dis = dis_max;
0202             }
0203         }
0204         return haus_dis;
0205     }
0206 };
0207
0208 }} // namespace detail::hausdorff_distance
0209 #endif // DOXYGEN_NO_DETAIL
0210
0211 #ifndef DOXYGEN_NO_DISPATCH
0212 namespace dispatch
0213 {
0214 template
0215 <
0216     typename Geometry1,
0217     typename Geometry2,
0218     typename Tag1 = typename tag<Geometry1>::type,
0219     typename Tag2 = typename tag<Geometry2>::type
0220 >
0221 struct discrete_hausdorff_distance : not_implemented<Tag1, Tag2>
0222 {};
0223
0224 // Specialization for point and multi_point
0225 template <typename Point, typename MultiPoint>
0226 struct discrete_hausdorff_distance<Point, MultiPoint, point_tag, multi_point_tag>
0227     : detail::discrete_hausdorff_distance::point_range
0228 {};
0229
0230 // Specialization for linestrings
0231 template <typename Linestring1, typename Linestring2>
0232 struct discrete_hausdorff_distance<Linestring1, Linestring2, linestring_tag, linestring_tag>
0233     : detail::discrete_hausdorff_distance::range_range
0234 {};
0235
0236 // Specialization for multi_point-multi_point
0237 template <typename MultiPoint1, typename MultiPoint2>
0238 struct discrete_hausdorff_distance<MultiPoint1, MultiPoint2, multi_point_tag, multi_point_tag>
0239     : detail::discrete_hausdorff_distance::range_range
0240 {};
0241
0242 // Specialization for Linestring and MultiLinestring
0243 template <typename Linestring, typename MultiLinestring>
0244 struct discrete_hausdorff_distance<Linestring, MultiLinestring, linestring_tag, multi_linestring_tag>
0245     : detail::discrete_hausdorff_distance::range_multi_range
0246 {};
0247
0248 // Specialization for MultiLinestring and MultiLinestring
0249 template <typename MultiLinestring1, typename MultiLinestring2>
0250 struct discrete_hausdorff_distance<MultiLinestring1, MultiLinestring2, multi_linestring_tag, multi_linestring_tag>
0251     : detail::discrete_hausdorff_distance::multi_range_multi_range
0252 {};
0253
0254 } // namespace dispatch
0255 #endif // DOXYGEN_NO_DISPATCH
0256
0257
0258 namespace resolve_strategy {
0259
0260 template
0261 <
0262     typename Strategies,
0263     bool IsUmbrella = strategies::detail::is_umbrella_strategy<Strategies>::value
0264 >
0265 struct discrete_hausdorff_distance
0266 {
0267     template <typename Geometry1, typename Geometry2>
0268     static inline auto apply(Geometry1 const& geometry1, Geometry2 const& geometry2,
0269                              Strategies const& strategies)
0270     {
0271         return dispatch::discrete_hausdorff_distance
0272             <
0273                 Geometry1, Geometry2
0274             >::apply(geometry1, geometry2, strategies);
0275     }
0276 };
0277
0278 template <typename Strategy>
0279 struct discrete_hausdorff_distance<Strategy, false>
0280 {
0281     template <typename Geometry1, typename Geometry2>
0282     static inline auto apply(Geometry1 const& geometry1, Geometry2 const& geometry2,
0283                              Strategy const& strategy)
0284     {
0285         using strategies::discrete_distance::services::strategy_converter;
0286         return dispatch::discrete_hausdorff_distance
0287             <
0288                 Geometry1, Geometry2
0289             >::apply(geometry1, geometry2,
0290                      strategy_converter<Strategy>::get(strategy));
0291     }
0292 };
0293
0294 template <>
0295 struct discrete_hausdorff_distance<default_strategy, false>
0296 {
0297     template <typename Geometry1, typename Geometry2>
0298     static inline auto apply(Geometry1 const& geometry1, Geometry2 const& geometry2,
0299                              default_strategy const&)
0300     {
0301         typedef typename strategies::discrete_distance::services::default_strategy
0302             <
0303                 Geometry1, Geometry2
0304             >::type strategies_type;
0305
0306         return dispatch::discrete_hausdorff_distance
0307             <
0308                 Geometry1, Geometry2
0309             >::apply(geometry1, geometry2, strategies_type());
0310     }
0311 };
0312
0313 } // namespace resolve_strategy
0314
0315
0316 /*!
0317 \brief Calculate discrete Hausdorff distance between two geometries (currently
0318     works for LineString-LineString, MultiPoint-MultiPoint, Point-MultiPoint,
0319     MultiLineString-MultiLineString) using specified strategy.
0320 \ingroup discrete_hausdorff_distance
0321 \tparam Geometry1 \tparam_geometry
0322 \tparam Geometry2 \tparam_geometry
0323 \tparam Strategy A type fulfilling a DistanceStrategy concept
0324 \param geometry1 Input geometry
0325 \param geometry2 Input geometry
0326 \param strategy Distance strategy to be used to calculate Pt-Pt distance
0327
0328 \qbk{distinguish,with strategy}
0329 \qbk{[include reference/algorithms/discrete_hausdorff_distance.qbk]}
0330
0331 \qbk{
0332 [heading Available Strategies]
0333 \* [link geometry.reference.strategies.strategy_distance_pythagoras Pythagoras (cartesian)]
0334 \* [link geometry.reference.strategies.strategy_distance_haversine Haversine (spherical)]
0335 [/ \* more (currently extensions): Vincenty\, Andoyer (geographic) ]
0336
0337 [heading Example]
0338 [discrete_hausdorff_distance_strategy]
0339 [discrete_hausdorff_distance_strategy_output]
0340 }
0341 */
0342 template <typename Geometry1, typename Geometry2, typename Strategy>
0343 inline auto discrete_hausdorff_distance(Geometry1 const& geometry1,
0344                                         Geometry2 const& geometry2,
0345                                         Strategy const& strategy)
0346 {
0347     return resolve_strategy::discrete_hausdorff_distance
0348         <
0349             Strategy
0350         >::apply(geometry1, geometry2, strategy);
0351 }
0352
0353 /*!
0354 \brief Calculate discrete Hausdorff distance between two geometries (currently
0355     works for LineString-LineString, MultiPoint-MultiPoint, Point-MultiPoint,
0356     MultiLineString-MultiLineString).
0357 \ingroup discrete_hausdorff_distance
0358 \tparam Geometry1 \tparam_geometry
0359 \tparam Geometry2 \tparam_geometry
0360 \param geometry1 Input geometry
0361 \param geometry2 Input geometry
0362
0363 \qbk{[include reference/algorithms/discrete_hausdorff_distance.qbk]}
0364
0365 \qbk{
0366 [heading Example]
0367 [discrete_hausdorff_distance]
0368 [discrete_hausdorff_distance_output]
0369 }
0370 */
0371 template <typename Geometry1, typename Geometry2>
0372 inline auto discrete_hausdorff_distance(Geometry1 const& geometry1,
0373                                         Geometry2 const& geometry2)
0374 {
0375     return resolve_strategy::discrete_hausdorff_distance
0376         <
0377             default_strategy
0378         >::apply(geometry1, geometry2, default_strategy());
0379 }
0380
0381 }} // namespace boost::geometry
0382
0383 #endif // BOOST_GEOMETRY_ALGORITHMS_DISCRETE_HAUSDORFF_DISTANCE_HPP