I know I can use a data structure such as the kd-tree to look for the k nearest points to each point in the plane (using the Euclidean distance). But I've already constructed a Delaunay triagulation in my program, so I'd like to find the k nearest neighbors more efficiently by taking adavntage of the Delaunay triangulation. I'm using Matlab, and the delaunayTriangulation class allows to query only the first nearest neighbor to a given point. How can I find the k nearest neighbors in MATLAB using the Delaunay triangulation? Or otherwise, if I have to implement myself the k nearest neighbors search algorithm from the Delaunay triangulation, can you point me out to such an algorithm?
1 Answers
If you are only interested in finding k points nearest to a centroid, then forget you have triangles. You have a cloud of points (that cloud be related to triangles, but its irrelevant) that you need to find kn nearest neighbors to it.
knnsearch() is sufficient.
Original answer:
When I had this problem, I found 2 efficient solutions.
if you want K nearest neighbours to an arbitrary point, you need to build a tree. I used R*-trees because they allow volumetric objects, but if you only consider the centroid of the elements then you can survive with an easier to code tree.
If you want K nearest neighbors to an element itself, the best way I found is by building a network graph. A Delaunay triangulation is not structure and finding in this list gets intractable soon as you increase it, so you need to enforce some order. You need to build a graph that will order these elements and store their neighbours, so you can simply query neigbours in distance from the element if your interest.
I found no MATLAB function to solve this for me and I ended up writing my own stuff. This was in a larger framework of using tetrahedra as image basis for computed tomography, so there is a lot of extra stuff in that repo and things may need touching here and there. Use at your own risk.
Related