5

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

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

例如，卷：

  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) 时间内或更好？）？

4

4 回答 4

3

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

此集合将开始为空。

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

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

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

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

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

于 2012-10-07T17:30:03.960 回答
3

这可以使用平面扫描算法有效地解决，这是此处建议的线扫描算法的直接扩展，用于查找重叠矩形的总面积。

对于每个长方体，在事件队列中添加它的左右 x 坐标并对队列进行排序。现在通过长方体扫描一个 yz 平面（具有恒定的 x 值）并记录事件队列中任意两个连续事件之间的体积。我们通过维护在任何阶段与平面相交的矩形列表来做到这一点

当我们扫描飞机时，我们会遇到两种类型的事件：

(1) 我们看到新长方体开始与扫掠平面相交。在这种情况下，一个新的矩形与平面相交，我们更新与扫描平面相交的矩形面积。

(2) 与平面相交的现有长方体的末端。在这种情况下，我们必须从当前与平面相交的矩形列表中删除相应的矩形，并更新生成的矩形的新区域。

任意两个连续事件 q i和 q i+1之间的长方体的体积等于两个事件之间的水平距离乘以在 q i处与扫描线相交的矩形面积。

通过使用 O(nlogn)算法计算矩形面积作为子程序，我们可以得到一个 O(n 2 logn) 算法来计算长方体的总体积。但是可能有更好的方法来维护矩形（因为我们只在任何阶段添加或删除一个矩形）更有效。

于 2012-10-07T16:48:37.247 回答
0

我最近遇到了同样的问题，发现以下方法易于实现并且适用于n维。

首先建立一个网格，然后检查网格中的每个单元格是否与长方体重叠。重叠长方体的体积是包含在一个或多个长方体中的那些单元的体积之和。

  • 用每个维度的最小值/最大值来描述你的长方体。
  • 对于每个维度，将每个长方体的最小/最大值存储在一个数组中。对该数组进行排序并删除重复项。
  • 现在你有一个非等距网格的网格点。网格的每个单元格要么完全在一个或多个长方体内，要么不在。
  • 遍历网格单元并计算与一个或多个长方体重叠的那些单元的体积。

您可以使用笛卡尔积获取所有网格单元。

于 2019-02-16T11:33:46.773 回答
0

我尝试了@ccssmnn 建议的蜂窝方法；它起作用了，但是太慢了。问题是用于“对于每个维度存储数组中每个长方体的最小/最大值”的数组大小。是O(n)，因此单元格的数量（因此，执行时间）是n^d，例如，n^3对于三个维度。

接下来，按照@krjampani 的建议，我尝试了嵌套扫描线算法；快得多，但仍然太慢。我相信复杂性是n^2*log^3(n).

所以现在，我想知道是否有任何追索权。我读过几篇提到使用interval treesor的帖子augmented interval trees；这种方法可能具有更好的复杂性，例如，n*log^3(n)？

另外，我试图弄清楚在这种情况下增加的价值是多少？在点或范围查询的情况下，我可以看到长方体按它们排序(xlo,ylo,zlo)并使用max(xhi,yhi,zhi)每个子树作为增广值，但无法弄清楚如何扩展它以跟踪长方体的联合及其体积。

于 2019-10-31T15:55:57.750 回答