我有一个长方体的列表，它们的左下角和右上角的坐标定义为平行于轴的边。坐标是双重值。这些长方体密集排列，与一个或多个其他部分重叠，甚至完全包含其他部分。如何计算多个重叠的长方体的总体积
我需要计算所有给定长方体所包含的总体积。重叠的区域（甚至多次）应该只计算一次。
例如，卷：
的总体积为27 + 1 + 2 + 8 = 38. 有没有简单的方法来做到这一点（在O（n^3）时间或更好？）？
如何处理每个处理的非相交长方体的集合？
此集合将开始为空。
第一个长方体将被添加到集合–它将是唯一的元素，因此保证不交叉其他任何东西。
第二个和后续的长方体将与集合中的元素进行检查。对于每一个新的长方体ñ，每个元素Ë已经在收藏里：
如果我们得到针对与一个或多个长方体从Ñ（表示体积所产生的非交叉元件测试贡献的端部通过Ñ，这不是在任何以前的长方体），然后将它们全部添加到集合中并处理下一个长方体。
一旦处理完所有长方体，总体积将为已建立的非相交长方体集合体积的总和。
最终我使用这个解决方案（根据E的位置将N分成多达26个更小的长方体），因为这个功能已经内置到系统中。 – Trasvi
这可以使用平面扫描算法有效地解决，该算法是线扫描算法的直接扩展，建议使用here来找出重叠矩形的总面积。
对于每个长方体，将它的左右x坐标添加到事件队列中并对队列进行排序。现在通过长方体扫描yz平面（具有常量x值）并记录事件队列中任意两个连续事件之间的音量。为此，我们坚持认为在任何阶段
相交平面矩形的名单我们扫面，我们遇到两种类型的事件：
（1）我们看到新的长方体开始启动相交的清扫飞机。在这种情况下，一个新的矩形与平面相交，我们更新与扫平面相交的矩形区域。
（2）与平面相交的现有长方体的末端。在这种情况下，我们必须从当前与平面相交的矩形列表中删除相应的矩形，并更新所得矩形的新区域。
长方体的任意两个连续事件q 我和q之间的体积 i + 1的等于两个事件之间的水平距离倍矩形相交的扫描线以Q 的面积我。
通过使用O（nlogn）algorithm用于计算矩形的区域作为子例程，我们可以得到O（N 2 logn）时间算法用于计算长方体的总体积。但是可能有更好的方法来维护矩形（因为我们只在任何阶段添加或删除矩形），效率更高。
n^3我猜是不够的。 – Trasvi
尝试一种分而治之的方法。根据它们所属的垂直线的哪一侧将长方体列表分为两组，并将与该线相交的那些长方体分成两部分。这可能会导致运行时间看起来像T（n）= 2T（n/2）+ cn。 – krjampani
@krjampani：按行我想你的意思是飞机 –