我有一個長方體的列表，它們的左下角和右上角的座標定義爲平行於軸的邊。座標是雙重值。這些長方體密集排列，與一個或多個其他部分重疊，甚至完全包含其他部分。如何計算多個重疊的長方體的總體積
我需要計算所有給定長方體所包含的總體積。重疊的區域（甚至多次）應該只計算一次。
例如，卷：
的總體積爲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：按行我想你的意思是飛機 –