algorithm - 如何计算多个重叠的平行六面体的总体积？

Question

我们在空间中有许多平行六面体，所有边都平行于轴。每个平行六面体由6个整数值表征，其两个顶点的坐标

(x1; y1; z1); (x2; y2; z2) with x1 < x2; y1 < y2 and z1 < z2; 

我必须找出两个或多个平行六面体同时占据的总体积。

Answer 1

让我们首先看一下对所有长方体的体积求和，同时只计算一次重叠区域。

您可以使用由所有长方体的起点和终点组成的新网格覆盖您的空间。然后，您可以根据该网格有效地将所有长方体切成子长方体，如下图所示(对于矩形):

例如，图中右下角的矩形是由六个不相交的子矩形组成的，它们的体积可以分别计算。

所以:

• 为每个轴构建一个数组，其中包含长方体的起点和终点。对数组进行排序。
• 创建一个三维数组，其长度对应于每个轴的坐标数组的长度。该数组保存了新网格中的一个长方体是否被占用的信息。
• 现在遍历长方体并将构成长方体的网格中的所有子长方体标记为已占用。
• 遍历标记数组并对所有标记的长方体的体积求和。

当你想获得重叠子长方体的体积时，你可以构建一个长方体交集列表并对其进行处理，或者你可以使标记数组成为计数数组并仅对计数的子体积求和至少为 2。

上述方法适用于任意坐标值，甚至 float 。如果您的长方体仅限于小范围内的整数，您可以不使用新网格而只使用自然整数网格作为“体素”。