detail/algorithms/minmaxdist.hpp

0001 // Boost.Geometry Index
0002 //
0003 // minmaxdist used in R-tree k nearest neighbors query
0004 //
0005 // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2020.
0008 // Modifications copyright (c) 2020 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_INDEX_DETAIL_ALGORITHMS_MINMAXDIST_HPP
0016 #define BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_MINMAXDIST_HPP
0017
0018 #include <boost/geometry/algorithms/distance.hpp>
0019 #include <boost/geometry/algorithms/comparable_distance.hpp>
0020
0021 #include <boost/geometry/core/static_assert.hpp>
0022
0023 #include <boost/geometry/index/detail/algorithms/diff_abs.hpp>
0024 #include <boost/geometry/index/detail/algorithms/sum_for_indexable.hpp>
0025 #include <boost/geometry/index/detail/algorithms/smallest_for_indexable.hpp>
0026
0027 namespace boost { namespace geometry { namespace index { namespace detail {
0028
0029 struct minmaxdist_tag {};
0030
0031 template <
0032     typename Point,
0033     typename BoxIndexable,
0034     size_t DimensionIndex>
0035 struct smallest_for_indexable_dimension<Point, BoxIndexable, box_tag, minmaxdist_tag, DimensionIndex>
0036 {
0037     typedef typename geometry::default_comparable_distance_result<Point, BoxIndexable>::type result_type;
0038
0039     inline static result_type apply(Point const& pt, BoxIndexable const& i, result_type const& maxd)
0040     {
0041         typedef typename coordinate_type<Point>::type point_coord_t;
0042         typedef typename coordinate_type<BoxIndexable>::type indexable_coord_t;
0043
0044         point_coord_t pt_c = geometry::get<DimensionIndex>(pt);
0045         indexable_coord_t ind_c_min = geometry::get<geometry::min_corner, DimensionIndex>(i);
0046         indexable_coord_t ind_c_max = geometry::get<geometry::max_corner, DimensionIndex>(i);
0047
0048         indexable_coord_t ind_c_avg = ind_c_min + (ind_c_max - ind_c_min) / 2;
0049         // TODO: awulkiew - is (ind_c_min + ind_c_max) / 2 safe?
0050
0051         // TODO: awulkiew - optimize! don't calculate 2x pt_c <= ind_c_avg
0052         // take particular case pt_c == ind_c_avg into account
0053
0054         result_type closer_comp = 0;
0055         if ( pt_c <= ind_c_avg )
0056             closer_comp = detail::diff_abs(pt_c, ind_c_min); // unsigned values protection
0057         else
0058             closer_comp = ind_c_max - pt_c;
0059
0060         result_type further_comp = 0;
0061         if ( ind_c_avg <= pt_c )
0062             further_comp = pt_c - ind_c_min;
0063         else
0064             further_comp = detail::diff_abs(pt_c, ind_c_max); // unsigned values protection
0065
0066         return (maxd + closer_comp * closer_comp) - further_comp * further_comp;
0067     }
0068 };
0069
0070 template <typename Point, typename Indexable, typename IndexableTag>
0071 struct minmaxdist_impl
0072 {
0073     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
0074         "Not implemented for this Indexable type.",
0075         Point, Indexable, IndexableTag);
0076 };
0077
0078 template <typename Point, typename Indexable>
0079 struct minmaxdist_impl<Point, Indexable, point_tag>
0080 {
0081     typedef typename geometry::default_comparable_distance_result<Point, Indexable>::type result_type;
0082
0083     inline static result_type apply(Point const& pt, Indexable const& i)
0084     {
0085         return geometry::comparable_distance(pt, i);
0086     }
0087 };
0088
0089 template <typename Point, typename Indexable>
0090 struct minmaxdist_impl<Point, Indexable, box_tag>
0091 {
0092     typedef typename geometry::default_comparable_distance_result<Point, Indexable>::type result_type;
0093
0094     inline static result_type apply(Point const& pt, Indexable const& i)
0095     {
0096         result_type maxd = geometry::comparable_distance(pt, i);
0097
0098         return smallest_for_indexable<
0099             Point,
0100             Indexable,
0101             box_tag,
0102             minmaxdist_tag,
0103             dimension<Indexable>::value
0104         >::apply(pt, i, maxd);
0105     }
0106 };
0107
0108 /**
0109  * This is comparable distace.
0110  */
0111 template <typename Point, typename Indexable>
0112 typename geometry::default_comparable_distance_result<Point, Indexable>::type
0113 minmaxdist(Point const& pt, Indexable const& i)
0114 {
0115     return detail::minmaxdist_impl<
0116         Point,
0117         Indexable,
0118         typename tag<Indexable>::type
0119     >::apply(pt, i);
0120 }
0121
0122 }}}} // namespace boost::geometry::index::detail
0123
0124 #endif // BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_MINMAXDIST_HPP