轴对齐立方体并集体积计算的简易实现方法及伪代码问询

方法一：三维坐标离散化+差分法（最易实现，O(n³)，适合n≤200的场景） #

这个方法逻辑最简单，几乎不需要复杂的数学推导，直接实现即可：

• 第一步：收集所有立方体的三轴坐标，分别存到三个数组中。每个立方体包含x_min, x_max, y_min, y_max, z_min, z_max六个坐标值，把所有x_min/x_max放入x坐标数组，y、z轴同理。分别对三个数组做排序、去重处理，得到离散化后的坐标映射表。
• 第二步：初始化三维差分数组，大小为(len(x_list)-1) * (len(y_list)-1) * (len(z_list)-1)，初始值全为0。
• 第三步：遍历每个立方体，分别找到它的x_min/x_max在x映射表中的索引x1/x2，同理找到y1/y2、z1/z2，按照三维差分规则更新差分数组：

diff[x1][y1][z1] += 1
diff[x2][y1][z1] -= 1
diff[x1][y2][z1] -= 1
diff[x1][y1][z2] -= 1
diff[x2][y2][z1] += 1
diff[x2][y1][z2] += 1
diff[x1][y2][z2] += 1
diff[x2][y2][z2] -= 1

• 第四步：对差分数组做三维前缀和计算，得到每个离散小方块被立方体覆盖的次数。只要次数≥1，就把这个小方块的体积加入总结果：小方块体积为(x_list[i+1]-x_list[i]) * (y_list[j+1]-y_list[j]) * (z_list[k+1]-z_list[k])。

方法二：z轴扫描线+二维矩形并集（O(n² log n)，适合n≤1000的场景） #

这个方法性能更好，实现难度也不高：

• 第一步：收集所有立方体的z_min/z_max坐标，排序去重得到z轴的分段点。
• 第二步：遍历每一段z区间[z_low, z_high]，计算这段的高度h = z_high - z_low，如果h≤0直接跳过。
• 第三步：筛选出所有完全覆盖当前z区间的立方体（满足立方体.z_min ≤ z_low 且 立方体.z_max ≥ z_high），提取这些立方体在xy平面的投影矩形，计算这些矩形的并集面积A。
• 第四步：将A * h加入总结果即可。
  其中二维矩形并集的计算可以直接用二维离散化差分的方法实现，逻辑和上面的三维方法一致，只是少了一个维度，时间复杂度为O(n²)。

不推荐容斥原理的原因 #

你之前想到的容斥思路不适合实际实现，因为容斥需要枚举所有非空立方体子集，时间复杂度是O(2ⁿ)，只要n超过20就完全跑不动，完全没有实用价值。

简易Python实现示例（三维离散化差分法） #

def union_volume(cubes):
    # cubes格式：每个元素是(xmin, xmax, ymin, ymax, zmin, zmax)
    xs = []
    ys = []
    zs = []
    for x1, x2, y1, y2, z1, z2 in cubes:
        xs.append(x1)
        xs.append(x2)
        ys.append(y1)
        ys.append(y2)
        zs.append(z1)
        zs.append(z2)
    # 离散化
    xs = sorted(list(set(xs)))
    ys = sorted(list(set(ys)))
    zs = sorted(list(set(zs)))
    nx, ny, nz = len(xs), len(ys), len(zs)
    # 初始化差分数组
    diff = [[[0]*nz for _ in range(ny)] for __ in range(nx)]
    for x1, x2, y1, y2, z1, z2 in cubes:
        # 找索引
        ix1 = xs.index(x1)
        ix2 = xs.index(x2)
        iy1 = ys.index(y1)
        iy2 = ys.index(y2)
        iz1 = zs.index(z1)
        iz2 = zs.index(z2)
        # 更新差分
        diff[ix1][iy1][iz1] += 1
        diff[ix2][iy1][iz1] -= 1
        diff[ix1][iy2][iz1] -= 1
        diff[ix1][iy1][iz2] -= 1
        diff[ix2][iy2][iz1] += 1
        diff[ix2][iy1][iz2] += 1
        diff[ix1][iy2][iz2] += 1
        diff[ix2][iy2][iz2] -= 1
    # 计算前缀和加总结果
    res = 0
    for i in range(nx-1):
        dx = xs[i+1] - xs[i]
        for j in range(ny-1):
            dy = ys[j+1] - ys[j]
            for k in range(nz-1):
                dz = zs[k+1] - zs[k]
                # 三维前缀和计算当前格点的覆盖次数
                if i > 0: diff[i][j][k] += diff[i-1][j][k]
                if j > 0: diff[i][j][k] += diff[i][j-1][k]
                if k > 0: diff[i][j][k] += diff[i][j][k-1]
                if i>0 and j>0: diff[i][j][k] -= diff[i-1][j-1][k]
                if i>0 and k>0: diff[i][j][k] -= diff[i-1][j][k-1]
                if j>0 and k>0: diff[i][j][k] -= diff[i][j-1][k-1]
                if i>0 and j>0 and k>0: diff[i][j][k] += diff[i-1][j-1][k-1]
                if diff[i][j][k] > 0:
                    res += dx * dy * dz
    return res

内容的提问来源于stack exchange，提问作者MC From Scratch