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

Question

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

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

例如，卷:

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，对于集合中已有的每个元素 E:

• 如果N完全被E包含，则丢弃N并在下一个新长方体处继续处理。
• 如果N完全包含E，则从集合中删除E并继续针对其他元素测试N在集合中。
• 如果N与E相交，则将N分成最多五个(见下面的评论)较小的长方体(取决于它们相交的方式)不相交的体积并继续针对集合中的其他元素测试这些较小的长方体。

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

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