Shortest Path in a 3D Matrix

14 views (last 30 days)
I have a 3D matrix with all 1 or 0 and two random elements. How can I calculate the shortest path between them and check how many elements with 1 are in the path? Thanks in advance.
Image Analyst
Image Analyst on 2 Jun 2015
Steve talks about the non-uniqueness of paths in part 2 of his blog:

Sign in to comment.

Accepted Answer

Alfonso Nieto-Castanon
Alfonso Nieto-Castanon on 3 Jun 2015
If you do not really care too much about the 'uniqueness' issue brought up in the comments, and just want to consider a single "straight" trajectory, you could do something like:
BW = rand([50 50 50])>.25; % your 3d matrix
i1 = [3, 2, 20]; % coordinates of initial point
i2 = [6, 10, 25]; % coordinates of end point
n = max(abs(i2-i1))+1; % number of steps
i = arrayfun(@(a,b)round(linspace(a,b,n)),i1,i2,'uni',0);
idx = sub2ind(size(BW),i{:});
sumBW = nnz(BW(idx));
disp(cell2mat(i')); % display trajectory
disp(sumBW); % display number of 1's in path
In this example, the trajectory chosen between [3,2,20] and [6,10,25] would be:
3 3 4 4 5 5 5 6 6
2 3 4 5 6 7 8 9 10
20 21 21 22 23 23 24 24 25
Marta Alcalde
Marta Alcalde on 28 Jun 2022
Yes, it would be useful for me if you explain a little bit the general idea behind your code. I would like to obtain the trajectory (cell2mat(i') in the previous code) but I have no clue how to obtain it.

Sign in to comment.

More Answers (3)

Walter Roberson
Walter Roberson on 2 Jun 2015
The same way as with a 2D matrix; you build a connectivity list and run a shortest path algorithm on it.

Image Analyst
Image Analyst on 2 Jun 2015
Steve has a blog on that: though I don't know if bwdistgeodesic works on 3D images.
Image Analyst
Image Analyst on 3 Jun 2015
Alex, I don't think the documentation is entirely clear. All the help says is "BW is a logical matrix." I've seen some people say "matrix" means only a 2-D array whereas anything 3-D or higher should be called "array" instead of "matrix." I'm not sure I agree with that, and sometimes I use them interchangeably. But nonetheless I think the documentation could be clearer on the dimensionality that it accepts. If it works for a n-D array where n can be any integer, then it might say that explicitly. Sometime you have separate n versions of functions, like convhull and convhulln, and bwlabel and bwlabeln. So sometimes people assume it's only 2-D unless it makes it clear in the documentation that it's for n-D.

Sign in to comment.

ahmad karim
ahmad karim on 3 Jun 2015
Plese, i have travelling salesman cost function but its give me error when i implement it plese can any one help me ?
% cost function for traveling salesperson problem % Haupt & Haupt % 2003 function dist=tspfun(pop) global iga x y [Npop,Ncity]=size(pop); tour=[pop pop(:,1)]; %distance between cities for ic=1:Ncity for id=1:Ncity dcity(ic,id)=sqrt((x(ic)-x(id))^2+(y(ic)-y(id))^2); end % id end %ic % cost of each chromosome for ic=1:Npop dist(ic,1)=0; for id=1:Ncity dist(ic,1)=dist(ic)+dcity(tour(ic,id),tour(ic,id+1)); end % id end % ic
  1 Comment
Image Analyst
Image Analyst on 3 Jun 2015
The traveling salesman problem is not really related to the shortest path algorithm in imaging. TSP has to visit every node, in imaging we don't. I suggest you start your own question in a new discussion thread.

Sign in to comment.

Community Treasure Hunt

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

Start Hunting!