minimum - 最小边界矩形，当 3D 形状未知时......仅它适合 3D 矩阵？

Question

我已经搜索过这个算法，包括在 stackoverflow 上，但没有找到。与为已知 3D 图找到最小边界矩形不同，我试图为任意、实心、连续的 3D 图找到一个轴对齐的...唯一的限制是该图完全适合 3D 矩阵给定大小，例如 800X800X800。有人可以给我一个有效的算法吗？

Answer 1

3D 图形如何表示为一组边界多边形或其他？

我假设您可以在 3D 图形上获得一组顶点，无论它们是否在其外表面上。

我假设“最小边界矩形”是指具有最小体积的边界直线实体（如砖块）。

“轴对齐”我假设您的意思是砖的边缘与预先存在的 x、y 和 z 轴对齐。即你不能通过旋转它来使砖变小。

然后根据您的描述，听起来您只需要沿每个坐标轴的最小值和最大值。这将花费点数的线性时间。

除非我误解了这个问题。

编辑：好的，根据您的说明，您从 800^3 的布尔数组a开始，我能想到的最好的是：

// 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 次测试。