nearestneighbour.m

Computes nearest neighbour(s) by Euclidean distance

Description

Compute nearest neighbours (by Euclidean distance) to a set of points of interest from a set of candidate points.

The points of interest can be specified as either a matrix of points (as columns) or indices into the matrix of candidate points.

Points can be of any (within reason) dimension.

nearestneighbour can be used to search for k nearest neighbours, or neighbours within some distance (or both)

If only 1 neighbour is required for each point of interest, nearestneighbour tests to see whether it would be faster to construct the Delaunay Triangulation (delaunayn) and use dsearchn to lookup the neighbours, and if so, automatically computes the neighbours this way. This means the fastest neighbour lookup method is always used.

A couple of examples:

% Candidate points
X = rand(2, 100);

% Points of interest
P = rand(2, 3);

% Find the nearest neighbour to each column of P
% where X(:, I(i)) is the neighbour to P(:,i)
I = nearestneighbour(P, X)

% Find the nearest 10 neighbours to each column of P
I = nearestneighbour(P, X, 'NumberOfNeighbours', 10)

% Find the nearest neighbours to the 2nd and 20th points in X
I = nearestneighbour([2 20], X)

% Find the neighbours in X which are within a radius of 0.2 from P
I = nearestneighbour(P, X, 'Radius', 0.2)

% Find the nearest neighbours to all columns of X
I = nearestneighbour(X)

• Acknowledgements: This submission has inspired the following:; Kirchhoff Vortex Contour Dynamics Simulation, Efficient K-Nearest Neighbor Search using JIT, IPDM: Inter-Point Distance Matrix
• MATLAB release: MATLAB 7.3 (R2006b)
• Other requirements: Tested on Matlab 7.1 (R14SP3) It *should* work on R13 (untested) with minimal modification. The demo can only be published on Matlab 7.0 onwards. If it doesn't work in R13 try replacing all instances of True with 1, and all instances of False with 0.
• Published M Files: NEARESTNEIGHBOUR Demonstration
• Other Files: nearestneighbour.m, ; demo/timingtest.m, ; demo/html/nndemo.png, ; demo/html/nndemo_01.png, ; demo/nndemo.m, ; demo/html/nndemo_03.png, ; demo/html/nndemo_04.png, ; demo/html/nndemo_02.png

[John D'Errico]

Excellent on all counts. Good help, error checks, etc. Carefuly coded.

If the spelling bothers anyone, they can always write a synonym function. But with tab completion, why bother?

function [idx,tri] = nearestneighbor(varargin)
% Synonym for nearestneighbour
[idx,tri] = nearestneighbour(varargin{:});

A minor point - with only one argument, should nearestneighbour find nearest neighbors within columns of that array itelf? This is sometimes of interest. It currently produces an error. At the least an error check should catch this event.

Also, while I like the property/value pair interface, I'd suggest making it allow unambiguous shortenings of the property names. This way one would not need to type out the entire property name.

I'll look forward to see other metrics provided.

[Richard Brown]

New version released which allows neighbour search within a radius

Please address bugs etc. to my email rather than here

Thanks,

Richard

[je ciobi]

Does anyone knows how to compute the Gabriel Graph in Matlab?