Incrementally add points to point cloud and perform nearest neighbour search
14 次查看(过去 30 天)
显示 更早的评论
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 个评论
Mohsin Shah
2019-3-4
编辑:Mohsin Shah
2019-3-4
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
2021-7-23
编辑:Preetham Manjunatha
2021-7-23
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.
采纳的回答
Sachin Meena
2018-8-31
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 个评论
Mohammadreza Yavari
2019-1-16
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
2019-12-20
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
更多回答(0 个)
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Point Cloud Processing 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!