Ridiculously Simple Nearest Neighbor Search 3D

Hello,

What is the best way to implement a nearest neighbor search between 3d points, here I have 2 sets of 3d points where the matrices are not the same size. The goal is compute the nearest neighbor to the 1st point in the first set with all the points in the second set and then index it. On top of that then I have to do a NNS search between one point and points in other set as well as the other points in the same set.

Answer 1

[Cedric]

Look at PDIST, PDIST2, KNNSEARCH here: http://www.mathworks.com/help/stats/nearest-neighbors.html

If you don't have the Stat. toolbox, it is easy to implement a loop over one set computing the distance from each point to all points of the other set, and taking the minimal distance.

Answer 2

[Kelly Kearney]

It's sort of overkill, but I usually use interpolation to do this ( scatteredInterpolant in the latest version of Matlab, previously used TriScatteredInterp or griddata).

Here's an example in 2D, but it works exactly the same in 3D:

 % Sample data

 x1 = rand(10,1);
 y1 = rand(10,1);
 x2 = rand(5,1);
 y2 = rand(5,1);

 % Calculate index of set 1 closest to each point in set 2

 F = scatteredInterpolant(x1, y1, (1:10)', 'nearest', 'nearest')
 idx = F(x2,y2)

 % A plot to check

 scatter(x1,y1,[], (1:10)', 'filled');
 hold on;
 scatter(x2,y2,[], idx);
 axis equal