MATLAB Answers

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

166 views (last 30 days)
dave
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.
  1 Comment
dave
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.

Sign in to comment.

Accepted Answer

Matt J
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.
  14 Comments

Sign in to comment.

More Answers (3)

Shashank Prasanna
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 Comments
Shashank Prasanna
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.

Sign in to comment.


Image Analyst
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.
  6 Comments
Image Analyst
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

Sign in to comment.


Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!