Code covered by the BSD License  

Highlights from
nearestneighbour.m

5.0

5.0 | 3 ratings Rate this file 106 Downloads (last 30 days) File Size: 29.9 KB File ID: #12574
image thumbnail

nearestneighbour.m

by

 

08 Oct 2006 (Updated )

Computes nearest neighbour(s) by Euclidean distance

| Watch this File

File Information
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 file inspired Cluster Generator, Kirchhoff Vortex Contour Dynamics Simulation, Efficient K Nearest Neighbor Search Using Jit, and 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.
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (6)
21 Jun 2011 Daniel Lagos

Amazing code Richard!. I'm doing a simulation of a cristal lattice, How can i add PBC(periodic boundary conditions) into the code?.

29 Dec 2010 sjye  
26 Nov 2009 Chris

cheers for the code, however just wondering a few things. in the program i am writing i have bacteria particles and fluid particles, with there initial coordinates in 2 seperate matrices. i need the neighbours lists for each point, both bacteria and fluid particles. i am using the radiusa round a point approach in the program

i can run the nearestneighbour file 4 different times and get bacteria/bacteria neighbours, fluid/fluid neighbours, fluid/bacteria neighbours and bacteria/fluid neighbours. this is very time consuming as well it always comes up that each particle is a neighbour of itself which is no good, just wondering if have any ideas about how to fix this, thanks, chris

19 Dec 2007 je ciobi

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

03 Sep 2007 Richard Brown

New version released which allows neighbour search within a radius

Please address bugs etc. to my email rather than here

Thanks,

Richard

11 Dec 2006 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.

Updates
10 Oct 2006

Tidied FEX Description

20 Nov 2006

Fixed a bug which meant searching by index didn't work if the Delaunay Triangulation was used

13 Dec 2006

Thanks JD for some useful suggestions:
Added single input case. Now allows property names to be specified by an unambiguous case-insensitive shortening.
If a triangulation is supplied the program now automatically attempts to use it

29 May 2007

Changed search keywords to accommodate American spelling

29 Aug 2007

Added (finally) ability to search for neighbours within a certain radius

Contact us