matlab - Find the shortest (soonest) path in three dimensions between specific points -

here problem statement:

i have cube specified dimensions. time passes, balls generated in cube. have simulated the coordinates (x,y,z location), time of generation , size of balls. need find shortest path of overlapped balls connect upper side of cube lower , find time path completed.

what thought find pair euclidean distance between points , pair sum of ball radius. compare distance sum find overlapping matrix. find objects @ top have z-size less 0 , z+size greater depth of cube , should find path. appreciate , idea in advance.

for example consider following data , code i've developed now:

offspr_x = [1 3 5 1 2] offspr_y = [3 3 1 8 2] offspr_z = [1 4 5 3 2] size = [2 1 4 6 3] time = [2 5 6 3 8]  pos= [offspr_x' offspr_y' offspr_z'] dd=pdist(pos,'euclidean') ddm = squareform(dd)   % compute similar matrix based on sum of object sizes (assumes size radius)  drad = meshgrid(size)+ meshgrid(size)'; dadj = ddm.*(ddm <= drad); 

now need convert overlap matrix graph object , try find shortest path between points offspr_z-size < 0 (all objects @ top have z-size less 0) , offspr_z+size > 5 (objects @ bottom have z+size greater 5):

starts = find(offspr_z-size < 0) ends = find(offspr_z+size > 5) 

update: @beaker suggested, tried floyd–warshall , here code used:

function d = fastfloyd(d)  n = size(d, 1);   k=1:n      i2k = repmat(d(:,k), 1, n);     k2j = repmat(d(k,:), n, 1);      d = min(d, i2k+k2j);  end  end 

therefore, for:

 dadj(dadj==0)=inf  d = fastfloyd(dadj) 

i got following result:

d =  3.4641    4.1815    6.0000    5.3852    1.7321 4.1815    4.8990    3.0000    5.4772    2.4495 6.0000    3.0000    6.0000    8.3066    4.3589 5.3852    5.4772    8.3066   10.7703    6.1644 1.7321    2.4495    4.3589    6.1644    3.4641 

but need find shortest (soonest) path between starts , ends vectors (those points overlap upper , lower surface of cube). soonest because i'm not interested in least distance in least time of generation ...

you're off start:

offspr_x = [1 3 5 1 2] offspr_y = [3 3 1 8 2] offspr_z = [1 4 5 3 2] size = [2 1 4 6 3] time = [2 5 6 3 8]  pos= [offspr_x' offspr_y' offspr_z'] dd=pdist(pos,'euclidean') 

pdist gives vector of distances. change recognizable, use squareform:

ddm = squareform(dd) 

now use calculation radius matrix , on adjacency matrix:

% compute similar matrix based on sum of object sizes (assumes size radius)  drad = meshgrid(size)+ meshgrid(size)'; adj = ddm.*(ddm <= drad); 

this finds values in ddm less respective radius distances , uses mask values ddm.

here's output test case:

adj =     0.00000   0.00000   6.00000   5.38516   1.73205    0.00000   0.00000   3.00000   5.47723   2.44949    6.00000   3.00000   0.00000   8.30662   4.35890    5.38516   5.47723   8.30662   0.00000   6.16441    1.73205   2.44949   4.35890   6.16441   0.00000