在特定點之間找到三維空間中最短（最快）的路徑

Question

這是我的問題陳述：

我有一個具有指定尺寸的立方體。隨着時間的推移，這個立方體會產生一些球。我模擬了座標（x，y，z位置），球的生成時間和大小。現在，我需要找到將立方體頂部連接到底部的重疊球的最短路徑，並找出此路徑完成的時間。

我想到現在是找到所有點之間的歐式距離和球半徑的總和。然後將距離與總和進行比較以找到重疊矩陣。然後找到頂部的z尺寸小於0且z +尺寸大於立方體深度的所有對象，然後找到路徑。 我很欣賞任何幫助和想法提前。

例如考慮以下數據和我已經開發到現在的代碼：

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尺寸< 0（在頂部的所有對象具有z尺寸小於0）和offspr_z +大小> 5（在底部對象具有Z +尺寸大於5）：

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

UPDATE：作爲@beaker建議，我也試過弗洛伊德 - 華沙​​，這裏是代碼塔T I使用：

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