Incrementally add points to point cloud and perform nearest neighbour search
15 views (last 30 days)
Show older comments
Sebastian
on 21 Aug 2018
Edited: Preetham Manjunatha
on 23 Jul 2021
Hello,
I use an algorithm for 3D path planning that alternately creates a new point, finds the nearest neighbor in an existing point cloud and then adds the new point to the point cloud. This step is being repeated hundreds of thousands of times which means that I need a data structure (k-d tree, octree, space partitioning in general) with which I can quickly find the nearest neighbor of a point and then append the point to it.
I tried to use the pointCloud object but the only way to make it grow is by merging it with another pointCloud which is a very computationally expensive task and thus is not an option for me.
Does anybody know of a Matlab built-in way or FEX contribution to perform nearest neighbor searches on a data structure that can grow incrementally?
Thank you in advance
2 Comments
Mohsin Shah
on 4 Mar 2019
Edited: Mohsin Shah
on 4 Mar 2019
Matlab findNearestNeighbors command for point clouds may be of use to you. There is also another toolbox https://www.geo.tuwien.ac.at/downloads/pg/pctools/pctools.html
Preetham Manjunatha
on 23 Jul 2021
Edited: Preetham Manjunatha
on 23 Jul 2021
Matlab's knnsearch works well to perform nearest neighbour search. Also this can be used to calculate the cloud-to-cloud distance (c2c distance as in CloudCompare) between two point clouds.
Accepted Answer
Sachin Meena
on 31 Aug 2018
I believe an approach similar to k-means clustering might work for you - as long as you do not have thousands of clusters. Try the following:
- Start with some initial points as cluster centers
- Check distances of new point from the cluster centers, and associate the new point to nearest cluster center
- Update the cluster center (not computationally extensive)
- If you wish to retrieve the cluster to which a point belongs, you can setup a lookup table with point as key - you will need to look for a hash function that suits you.
In case you want to increment the number of clusters dynamically, you can set a threshold distance for that. Whenever the nearest neighbor is farther than the threshold value, the new point will start its own cluster.
3 Comments
Mohammadreza Yavari
on 16 Jan 2019
Hi Sebastian,
I have the exact same problem you solved (find nearest neighbour in RRT). Is it possible for you to share your solution?
Dave Ober
on 20 Dec 2019
Hello Sebastian,
I am not sure if you answered Mohammadreza privately but your Octree with Knn search sounds like a great marriage. Is your solution available to the public? Other researchers?
Thank you
More Answers (0)
See Also
Categories
Find more on Point Cloud Processing in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!