在特定点之间的三个维度中找到最短（最快）路径

Question

这是我的问题陈述：

我有一个指定尺寸的立方体。随着时间的推移，这个立方体中会生成一些球。我模拟了球的坐标（x、y、z 位置）、生成时间和大小。现在我需要找到连接立方体上侧和下侧的重叠球的最短路径，并找出这条路径完成的时间。

我到现在想的就是求所有点之间的对欧距离和球半径的对和。然后将距离与总和进行比较以找到重叠矩阵。然后在顶部找到所有 z-size 小于 0 且 z+size 大于立方体深度的对象，然后我应该找到路径。感谢提前提供的任何帮助和想法。

例如考虑以下数据和我到目前为止开发的代码：

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 is radius)

drad = meshgrid(size)+ meshgrid(size)';
dadj = ddm.*(ddm <= drad);

现在我需要将重叠矩阵转换为图形对象并尝试找到 offspr_z-size < 0 的那些点之间的最短路径（顶部的所有对象的 z 大小都小于 0）和offspr_z+size > 5（底部对象的 z+size 大于 5）：

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

更新：正如@beaker 所建议的，我也尝试了 Floyd–Warshall，这是我使用的代码：

function D = FastFloyd(D)

n = size(D, 1); 

for k=1:n

    i2k = repmat(D(:,k), 1, n);
    k2j = repmat(D(k,:), n, 1);

    D = min(D, i2k+k2j);

end

end

因此，对于：

 dadj(dadj==0)=Inf
 D = FastFloyd(dadj)

我得到以下结果：

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

但我需要找到起点和终点向量（与立方体上表面和下表面重叠的那些点）之间的最短（最快）路径。我说最快是因为我对最短距离不感兴趣，但对最短生成时间不感兴趣...

Answer 1

你有了一个好的开始：

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 给你一个距离向量。要将其更改为可识别的内容，请使用 squareform:

ddm = squareform(dd)

现在我们使用您计算的半径矩阵，然后是邻接矩阵：

% compute similar matrix based on sum of object sizes (assumes size is radius)

drad = meshgrid(size)+ meshgrid(size)';
adj = ddm.*(ddm <= drad);

这会找到 ddm 中小于其各自半径距离的值，并将其用作掩码以从 ddm.

中获取值

这是您的测试用例的输出：

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

在特定点之间的三个维度中找到最短（最快）路径

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

3d

matlab

graph

shortest-path

floyd-warshall