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
applyboost::geometry::index::detail::smallest_for_indexable_dimension33 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
applyboost::geometry::index::detail::minmaxdist_impl78 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
applyboost::geometry::index::detail::minmaxdist_impl89 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
minmaxdist(Point const & pt,Indexable const & i)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
120