1 template <typename PointT> int
2 pcl::search::BruteForce<PointT>::denseKSearch (
3 const PointT &point, int k, std::vector<int> &k_indices, std::vector<float> &k_distances) const
4 {
5 // container for first k elements -> O(1) for insertion, since order not required here
6 std::vector<Entry> result;
7 result.reserve (k);
8 std::priority_queue<Entry> queue;
9
10 Entry entry;
11 for (entry.index = 0; entry.index < std::min (static_cast<unsigned> (k), static_cast<unsigned> (input_->size ())); ++entry.index)
12 {
13 entry.distance = getDistSqr (input_->points[entry.index], point);
14 result.push_back (entry);
15 }
16
17 queue = std::priority_queue<Entry> (result.begin (), result.end ());
18
19 // add the rest
20 for (; entry.index < input_->size (); ++entry.index)
21 {
22 entry.distance = getDistSqr (input_->points[entry.index], point);
23 if (queue.top ().distance > entry.distance)
24 {
25 queue.pop ();
26 queue.push (entry);
27 }
28 }
29
30 k_indices.resize (queue.size ());
31 k_distances.resize (queue.size ());
32 size_t idx = queue.size () - 1;
33 while (!queue.empty ())
34 {
35 k_indices [idx] = queue.top ().index;
36 k_distances [idx] = queue.top ().distance;
37 queue.pop ();
38 --idx;
39 }
40
41 return (static_cast<int> (k_indices.size ()));
42 }