Shortest Path in a 3D Matrix

14 Ansichten (letzte 30 Tage)
jan smith
jan smith am 2 Jun. 2015
Kommentiert: Marta Alcalde am 28 Jun. 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 Kommentare
Alfonso Nieto-Castanon
Alfonso Nieto-Castanon am 2 Jun. 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 am 2 Jun. 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/

Melden Sie sich an, um zu kommentieren.

Akzeptierte Antwort

Alfonso Nieto-Castanon
Alfonso Nieto-Castanon am 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
  6 Kommentare
ROY EL ZEGHONDI
ROY EL ZEGHONDI am 23 Sep. 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 am 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.

Melden Sie sich an, um zu kommentieren.

Weitere Antworten (3)

Walter Roberson
Walter Roberson am 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 am 2 Jun. 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 Kommentare
Alex Taylor
Alex Taylor am 3 Jun. 2015
bwdistgeodesic does work on 3-D data.
Image Analyst
Image Analyst am 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.

Melden Sie sich an, um zu kommentieren.


ahmad karim
ahmad karim am 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 Kommentar
Image Analyst
Image Analyst am 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.

Melden Sie sich an, um zu kommentieren.

Community Treasure Hunt

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

Start Hunting!

Translated by