ceph/src/boost/boost/geometry/index/detail/algorithms/minmaxdist.hpp

   1 // Boost.Geometry Index
   2 //
   3 // minmaxdist used in R-tree k nearest neighbors query
   4 //
   5 // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland.
   6 //
   7 // Use, modification and distribution is subject to the Boost Software License,
   8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   9 // http://www.boost.org/LICENSE_1_0.txt)
  10
  11 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_MINMAXDIST_HPP
  12 #define BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_MINMAXDIST_HPP
  13
  14 #include <boost/geometry/algorithms/distance.hpp>
  15 #include <boost/geometry/algorithms/comparable_distance.hpp>
  16
  17 #include <boost/geometry/index/detail/algorithms/diff_abs.hpp>
  18 #include <boost/geometry/index/detail/algorithms/sum_for_indexable.hpp>
  19 #include <boost/geometry/index/detail/algorithms/smallest_for_indexable.hpp>
  20
  21 namespace boost { namespace geometry { namespace index { namespace detail {
  22
  23 struct minmaxdist_tag {};
  24
  25 template <
  26     typename Point,
  27     typename BoxIndexable,
  28     size_t DimensionIndex>
  29 struct smallest_for_indexable_dimension<Point, BoxIndexable, box_tag, minmaxdist_tag, DimensionIndex>
  30 {
  31     typedef typename geometry::default_comparable_distance_result<Point, BoxIndexable>::type result_type;
  32
  33     inline static result_type apply(Point const& pt, BoxIndexable const& i, result_type const& maxd)
  34     {
  35         typedef typename coordinate_type<Point>::type point_coord_t;
  36         typedef typename coordinate_type<BoxIndexable>::type indexable_coord_t;
  37
  38         point_coord_t pt_c = geometry::get<DimensionIndex>(pt);
  39         indexable_coord_t ind_c_min = geometry::get<geometry::min_corner, DimensionIndex>(i);
  40         indexable_coord_t ind_c_max = geometry::get<geometry::max_corner, DimensionIndex>(i);
  41
  42         indexable_coord_t ind_c_avg = ind_c_min + (ind_c_max - ind_c_min) / 2;
  43         // TODO: awulkiew - is (ind_c_min + ind_c_max) / 2 safe?
  44
  45         // TODO: awulkiew - optimize! don't calculate 2x pt_c <= ind_c_avg
  46         // take particular case pt_c == ind_c_avg into account
  47
  48         result_type closer_comp = 0;
  49         if ( pt_c <= ind_c_avg )
  50             closer_comp = detail::diff_abs(pt_c, ind_c_min); // unsigned values protection
  51         else
  52             closer_comp = ind_c_max - pt_c;
  53
  54         result_type further_comp = 0;
  55         if ( ind_c_avg <= pt_c )
  56             further_comp = pt_c - ind_c_min;
  57         else
  58             further_comp = detail::diff_abs(pt_c, ind_c_max); // unsigned values protection
  59
  60         return (maxd + closer_comp * closer_comp) - further_comp * further_comp;
  61     }
  62 };
  63
  64 template <typename Point, typename Indexable, typename IndexableTag>
  65 struct minmaxdist_impl
  66 {
  67     BOOST_MPL_ASSERT_MSG(
  68         (false),
  69         NOT_IMPLEMENTED_FOR_THIS_INDEXABLE_TAG_TYPE,
  70         (minmaxdist_impl));
  71 };
  72
  73 template <typename Point, typename Indexable>
  74 struct minmaxdist_impl<Point, Indexable, point_tag>
  75 {
  76     typedef typename geometry::default_comparable_distance_result<Point, Indexable>::type result_type;
  77
  78     inline static result_type apply(Point const& pt, Indexable const& i)
  79     {
  80         return geometry::comparable_distance(pt, i);
  81     }
  82 };
  83
  84 template <typename Point, typename Indexable>
  85 struct minmaxdist_impl<Point, Indexable, box_tag>
  86 {
  87     typedef typename geometry::default_comparable_distance_result<Point, Indexable>::type result_type;
  88
  89     inline static result_type apply(Point const& pt, Indexable const& i)
  90     {
  91         result_type maxd = geometry::comparable_distance(pt, i);
  92
  93         return smallest_for_indexable<
  94             Point,
  95             Indexable,
  96             box_tag,
  97             minmaxdist_tag,
  98             dimension<Indexable>::value
  99         >::apply(pt, i, maxd);
 100     }
 101 };
 102
 103 /**
 104  * This is comparable distace.
 105  */
 106 template <typename Point, typename Indexable>
 107 typename geometry::default_comparable_distance_result<Point, Indexable>::type
 108 minmaxdist(Point const& pt, Indexable const& i)
 109 {
 110     return detail::minmaxdist_impl<
 111         Point,
 112         Indexable,
 113         typename tag<Indexable>::type
 114     >::apply(pt, i);
 115 }
 116
 117 }}}} // namespace boost::geometry::index::detail
 118
 119 #endif // BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_MINMAXDIST_HPP