如何计算多个重叠长方体的总体积

Question

我有一个长方体列表，由它们的左下后角和右上角前角的坐标定义，边缘平行于轴。坐标是双精度值。这些长方体密集，会与一个或多个其他长方体重叠，甚至完全包含其他长方体。

我需要计算所有给定长方体所包含的总体积。重叠（甚至多次）的区域应该只计算一次。

例如，卷：

1. ((0,0,0)(3,3,3))
2. ((0,1,0) (2,2,4))
3. ((1,0,1) (2,5,2))
4. ((6,6,6)(8,8,8))

总体积为 27 + 1 + 2 + 8 = 38。有没有一种简单的方法可以做到这一点（在 O(n^3) 时间内或更好？）？

Answer 1

在处理每个长方体时维护一组不相交的长方体怎么样？

\n

这个集合一开始是空的。

\n

第一个长方体将被添加到集合 \xe2\x80\x93 中，它将是唯一的元素，因此保证不会与其他任何元素相交。

\n

将根据集合中的元素检查第二个和后续的长方体。对于每个新的长方体N，对于集合中已有的每个元素E ：

\n

\n
• 如果N完全被E包含，则丢弃N并在下一个新长方体处恢复处理。
\n
• 如果N完全包含E，则从集合中删除E并继续针对集合中的其他元素测试N 。
\n
• 如果N与E相交，则将N分成最多五个（请参阅下面的注释）较小的长方体（取决于它们相交的方式），表示不相交的体积，并继续针对集合中的其他元素测试这些较小的长方体。
\n

\n

如果我们对具有由N生成的一个或多个长方体的非相交元素进行测试结束（表示N贡献的体积不在之前的任何长方体中），则将它们全部添加到集合中并进行处理下一个长方体。

\n

处理完所有长方体后，总体积将是已建立的不相交长方体集合中的体积之和。

\n