當3D形狀未知時，最小邊界矩形只適用於3D矩陣？

Question

我已經搜索了此算法，包括在stackoverflow上，但沒有找到一個。與找到已知3D圖形的最小邊界矩形不同，我試圖爲一個任意的，實心的，連續的3D圖形找到一個軸對齊的圖形...唯一的限制是該圖完全適合3D矩陣給出尺寸，比如說800X800X800。有人可以給我一個有效的算法嗎？

Answer 1

3D圖形如何表示爲一組邊界多邊形或其他？

我假設你可以在3D圖上得到一組頂點，不管它們是否在外表面上。

我假定「最小邊界矩形」是指邊界直線實體（如磚塊），最小體積。

「軸對齊」我假設你的意思是磚的邊緣與預先存在的x，y和z軸對齊。 即你不能通過旋轉來使磚變小。

然後從您的描述中聽起來好像你只想沿每個座標軸的最小值和最大值。 這將需要線性時間的點數。

除非我誤解了這個問題。

編輯：好的，從您澄清，你是從800立方公尺陣列布爾的開始，我能想到的最好的是：

// a lot depends on how you index array a 
// this assumes it is one big block of bools 
#define A(i,j,k) a[(i)*800*800 + (j)*800 + (k)] 
// to get the minimum X value 
for (ix = 0; ix < 800; ix++){ 
    // search over the entire plane at x == ix 
    // this can probably be improved by stepping pointers 
    for (iy = 0; iy < 800; iy++){ 
     for (iz = 0; iz < 800; iz++){ 
      // nobody likes goto, but it's probably the quickest way out 
      // of the 3 nested loops 
      if (A(ix, iy, iz)) goto L100; 
     } 
    } 
} 
L100:; 
// here, ix is minimum x value 

// do similar code for max x, min and max y, min and max z 

大概可以有所改善。 最壞的情況下，如果音量爲空，則會進行3^800^3測試。 最好的情況下，它會做6 * 800^2測試，如果音量已滿。