当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测试，如果音量已满。