# How to find all neighbours of an element in N-dimensional matrix

166 views (last 30 days)
dave on 11 Sep 2013
Commented: Image Analyst on 31 Oct 2017
I just can't wrap my head around how to find all neighbours of an element in a N-dimensional matrix. After reading through the documentation on spatial searching I think it could be done using the Delaunay triangulation. However, these topics are still a bit too advanced for me, so any help would be appreciated.
dave on 12 Sep 2013
Update: Thanks everybody for your suggestions. After all Shashank's hint with the knnsearch turned out to be the easiest solution in my case, since I have the statistics toolbox. If you don't have it, the solutions provided by Matt J and Image Analyst are also very useful.

Matt J on 11 Sep 2013
Edited: Matt J on 11 Sep 2013
What I often like to do is make an offset mask, as follows
s=size(yourmatrix);
N=length(s);
[c1{1:N}]=ndgrid(1:3);
c2(1:N)={2};
offsets=sub2ind(s,c1{:}) - sub2ind(s,c2{:})
Now, for any linear index in your matrix L, you can get all its neighbors by doing
neighbors = yourmatrix(L+offsets)
It won't work at the edges of the matrix, but you can take care of that by padding the edges first.
Image Analyst on 31 Oct 2017

Shashank Prasanna on 11 Sep 2013
If you have the Statistics Toolbox installed, there are couple of nearest neighbor searching tools that you might find very useful. Although some of these concepts may be advanced for a casual user, the functionality itself is very quite easy to use, that's really the power of MATLAB:
One way to speed up higher dimensional neighbor searching is to use an optimized data structure such as k dimensional trees, and this is easy to do so as below:
kdtreeNS = KDTreeSearcher(x);
[n,d]=knnsearch(kdtreeNS,x);
Here is the page from the doc:
##### 2 CommentsShowHide 1 older comment
Shashank Prasanna on 11 Sep 2013
Michael, I misunderstood your question. I made the assumption that you were referring to the columns as dimensions in |R^n space .
None of these function work on multidimensional matrices. If you have data in some n dimensional space each instance or observation can be represented as a vector with n entries. I am not sure how your data is represented but if you are able to represent it in a why described you can use all the functionality that I mentioned to do your neighbor search.

Image Analyst on 11 Sep 2013
You just take the index, the index plus one, and the index minus one, for every other dimension, but exclude the index of where you're at. For example if you have a 3D matrix, and you're at x=3, y=6, and z=9, you'd have all permutations of x in [2,3,4] with y in [5,6,7] with z in [8,9,10] but don't include the point itself with x=3,y=6, z=9. So that's 3*3*3-1 neighbors in 3D. For N dimensions you'd have 3 * 3 * 3 * ....(a total N times) * 3 -1 neighbors. So 2D gives 3*3-1 = 8 neighbors, 3D gives 26 neighbors, 4D gives 80 neighbors, etc.
Image Analyst on 11 Sep 2013
I'd use loops over each dimension, so for 5 dimensions like my example
for d1=1:d1max
for d2=1:d2max
for d3=1:d3max
for d4=1:d4max
for d5=1:d5max
subHyperVolume = hyperVolume(...
d1-1:d1+1,...
d2-1:d2+1,...
d3-1:d3+1,...
d4-1:d4+1,...
d5-1:d5+1,...
);
end
end
end
end
end

Sean de Wolski on 24 Jun 2014