Shortest Path in a 3D Matrix

14 visualizzazioni (ultimi 30 giorni)
jan smith
jan smith il 2 Giu 2015
Commentato: Marta Alcalde il 28 Giu 2022
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.
  4 Commenti
Alfonso Nieto-Castanon
Alfonso Nieto-Castanon il 2 Giu 2015
that definition does not lead to unique trajectories. Consider in 2d-space:
0 0 1 2 3 0
0 0 0 0 0 4
or
0 0 1 0 0 0
0 0 0 2 3 4
or
0 0 1 2 0 0
0 0 0 0 3 4
all have the same number of elements. What should the algorithm do with these multiple optimal paths?
Image Analyst
Image Analyst il 2 Giu 2015
Steve talks about the non-uniqueness of paths in part 2 of his blog: http://blogs.mathworks.com/steve/2011/11/26/exploring-shortest-paths-part-2/

Accedi per commentare.

Risposta accettata

Alfonso Nieto-Castanon
Alfonso Nieto-Castanon il 3 Giu 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
  6 Commenti
ROY EL ZEGHONDI
ROY EL ZEGHONDI il 23 Set 2020
this worked for me, and i think i understand the general idea behind it but if possible can u explain how the steps work ?
thank you
Marta Alcalde
Marta Alcalde il 28 Giu 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.

Accedi per commentare.

Più risposte (3)

Walter Roberson
Walter Roberson il 2 Giu 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 il 2 Giu 2015
Steve has a blog on that: http://blogs.mathworks.com/steve/2011/11/01/exploring-shortest-paths-part-1/ though I don't know if bwdistgeodesic works on 3D images.
  3 Commenti
Alex Taylor
Alex Taylor il 3 Giu 2015
bwdistgeodesic does work on 3-D data.
Image Analyst
Image Analyst il 3 Giu 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.

Accedi per commentare.


ahmad karim
ahmad karim il 3 Giu 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 Commento
Image Analyst
Image Analyst il 3 Giu 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.

Accedi per commentare.

Community Treasure Hunt

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

Start Hunting!

Translated by