]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |