Pcl: The most efficient way to find K points in point cloud which their Z value is less than other points

[MBSadeghzadeh]

We have a point cloud like pcl::PointCloud<pcl::PointXYZ> cloud which has N points. We want to find K points in cloud which their z value is less than other N-K points. What is the most efficient way to do it in pcl?

[kunaltyagi]

Closing since issue is unrelated to the library (but is instead a question regarding using the library for which Discord is a better fit)

You aim can be achieved through so many ways:

• std::partitionstd::nth_element in C++ stdlib
• Octree or Kdtree iterators in PCL
• FLANN (as approx NN) (dependency used by PCL)
• PassThrough filter, experimental::FunctionFilter in PCL

The most efficient way depends on what else you're doing with the cloud, size of cloud, etc.

The question is also a bit ambiguous. Do you know z and are trying to find the points (and the value of k) or do you know k and are looking for the prefect value of z

[MBSadeghzadeh]

The cloud is updated each 100 milliseconds and obviously we don't know the z value. If it is not possible in pcl, it can be a good feature to be implemented. The proposed methods are not suitable in this case.

[kunaltyagi]

Please create a suitable proposal issue in that case. Please try to enter all possible requirements (eg: organized pre and post 'filter', example use cases, etc.)

[JStech]

This is solved by std::nth_element.

[kunaltyagi]

partition is faster (since it imposes weaker posterior conditions compared to nth_element) 😄

[mvieth]

partition is faster (since it imposes weaker posterior conditions compared to nth_element) smile

But partition needs a true/false predicate, which (as I understood the issue) is not given, because the z value that divides the two groups in unknown. I too think that nth_element should be the solution.

[MBSadeghzadeh]

The brute force approach to this problem is sorting whole points of vector and then get K first elements from vector which its complexity is O(NlogN)while std::nth_element solves this problem in O(N).