nearest_neighbour_3D

This function compute the nearest neighbours by Euclidean distance.

Description

This function compute the nearest neighbours (by Euclidean distance) to a set of given points from a set of candidate points.
In this tool, exclusively the really nearest point will be calculated
without using special algorithms (delaunay, brute search etc. ) and also without a loop. Therefore, the function is very fast but
supports only a limited set of canditate and given points in 3D. For very large input data it can be lead to out of memory errors because the maximum adressable memory area of 32-Bit operation systems is located about 2 GByte (or 3 GByte with a change in the boot of the windows operation system).

INPUT:

an N1 x 3 matrix of cantitate_points
an N2 x 3 matrix of given_points (N1 and N2 can be different)

OUTPUT:

an N2 x 1 matrix (column) with the numbers of the nearest neighbour points to each canditate point. (The number of a row in the nearest neighbour matrix is equivalent to the number of the given point in the canditate points matrix)

• MATLAB release: MATLAB 7.6 (R2008a)
• Other requirements: should work on all platforms

[Bruno Luong]

- Computing the minimum distances for all pair of points is not a good way to compute nearest neighbor, and it's certainly not a fast one when the set of given points is large.

- As the author has warned, this method cannot handle large size data.

- The mfile miss the H1 line. When user type "help compute_nearest_neighbour' he/she would not know how to call the function, unless he is the author.

This function can accomplish with an equivalent stock function, which performs much faster. Here is the demo using new stock class in 2009A which is 10 time faster. For older Matlab version similar Delanay technique can be used to accomplish the same task as well.

% Data
n = 5000;
canditate_points=randn(n,3);
given_points=randn(n,3);

tic
nearest_neighbour=nearestNeighbor(DelaunayTri(canditate_points),given_points);
toc % Elapsed time is 0.322600 seconds.
clear idx

tic
[nearest_neighbour]=compute_nearest_neighbour(canditate_points,given_points);
toc % Elapsed time is 3.445318 seconds.
clear

[Andreas Richter]

Hello Bruno,

sorry for the missing of the H1 line. It will be corrected in the next update.

Maybe you're also rigth with the elapsed time of the function. But this tool is prior created for older Matlab versions as 2009A and for little or medium size of data. Under these conditions, the function works sufficient fast and authentic and is much easier than others. Of course, for large data size you need tools which use Delaunay techniques to works fast and to avoid out of memory errors.

Thanks for your comment

Andreas