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

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

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

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

最佳答案

我们先看一下所有长方体的体积之和，同时只考虑一次重叠区域。
你可以用一个新的网格覆盖你的空间，这个网格由所有长方体的起点和终点组成。然后根据该网格将所有长方体有效地分割为子长方体，如下所示（对于矩形）：
例如，图像右下角的矩形由六个不相交的子矩形组成，可以分别计算其体积。
所以：
对于每个轴，构建一个包含长方体的起始点和结束点的数组。对数组排序。
创建一个三维数组，其长度对应于每个轴的坐标数组的长度。这个数组保存新网格中的长方体是否被占用的信息。
现在在长方体上迭代，并将构成长方体的网格中的所有子长方体标记为已占用。
遍历标记数组并求出所有标记长方体的体积之和。
当你想得到重叠的子长方体的体积时，你可以建立一个长方体交集的列表并对其进行处理，或者你可以使标记数组成为一个计数数组，并且只对计数至少为2的子体积求和。
上面的方法应该适用于任意坐标值，甚至是浮点数如果长方体仅限于小范围内的整数，则可以不使用新的网格，只使用自然整数网格作为“体素”。

关于algorithm - 如何计算多个重叠的平行六面体的总体积？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28146260/