檢測多面體之間相交的*最快*算法是什麼？

假設有n三維物體（多面體）。計算所有對象O（n^2）的交集是最快的方法嗎？檢測多面體之間相交的*最快*算法是什麼？

現在，我使用的基本上迫使T（N）等於N^2庫：

for each object: // there are n objects 
    get list of intersecting objects // this takes n steps

，從字面上需要N^2層的步驟。我可以想到的方式仍然是O（n^2），但是T（n）= n（n + 1）/ 2或者（n * n + n）/ 2。

這裏是僞代碼：

for(int i = 0; i < len(objects) - 1; i++) 
    for(int j = i + 1; j < len(objects); j++) 
     if object at i intersects object at j: 
      object at i . addToIntersectList (object at j) 
      object at j . addToIntersectList (object at i)

這樣，我們就不必檢查是否兩個對象相交兩次。我知道我正在迭代的列表中有大約3000個對象。該算法需要4501500步，而原始算法需要接近兩倍，即9000000步。

我錯過了什麼嗎？這是我們能得到的最好的嗎？

來源

2014-06-27 user3745189

如果你能讓GPU做數學運算，4,500,000步可能不會那麼糟糕！看看http://en.wikipedia.org/wiki/Gpgpu，http://en.wikipedia.org/wiki/OpenCL，或者甚至是http://en.wikipedia.org/wiki/CUDA看看如果這在你的情況下可能是可行的。以防萬一其他優化不能使您獲得性能所需的位置。 –

也許[plane sweep]（https://en.wikipedia.org/wiki/Sweep_line_algorithm）的3D變體可用於相交的多邊形。 – phg

雖然有幾種方法可以通過更改循環內容來提高O（n2）性能，但通過更改其他方式來進行碰撞檢查的方式可以做出重大改進。

你的代碼中最主要的低效率之一就是它依靠完全檢查每個多面體對每個其他多面體的方式，而這往往不是必需的。如果兩個形狀甚至不緊密結合在一起，則不需要進行密集的相交測試，並且如果您有兩個形狀集羣被廣闊的空間隔開，則不需要檢查兩個集羣中的每個成員另一個集羣的每個成員也是。一些技術進行這種優化包括：

您可以使用這些技術來majorly加快碰撞搜索。

來源

2014-06-27 19:39:32 AJMansfield

「*真的沒有什麼好的方法可以將WRT固體計數的複雜度降低到低於O（n²）... *」不是真的，Hoey-Shamos是O（nLog（n））。 – RBarryYoung

@RBarryYoung你能提供一個鏈接嗎？我不知道這種技術，我很想了解它是如何工作的。 – AJMansfield

很難在特殊期刊以外找到，但這是我可以找到的最開放的在線鏈接：https：//en.wikipedia.org/wiki/Sweep_line_algorithm。 – RBarryYoung

不管你信不信，我已經有效地在StackOVerflow上回答了這個問題，在這裏：https://stackoverflow.com/a/19172550/109122。問題和答案適用於多邊形（2D），但它應該適用於多面體（3D）。

這裏的問題也提到了什麼被認爲是最快的算法，即Hoey Shamos掃描線技術，它是O（n Log n）。你可以研究和實現它，但它非常複雜。

我在答案中演示的更簡單的算法具有高度依賴於「良好行爲」形狀及其定位的性能。越來越多的形狀和更密集的包裝/重疊，它會表現得越差。然而，如果交叉點很少且包裝不太密集，則表現良好的形狀（即凸面或主要如此），我發現它的性能比O（n sqrt（n））好。代碼和討論主要是關於兩個多邊形內的線條，但這也是泛化到多邊形本身。

除了相對簡單之外，我的方法對於您的案例的一大優點是，它可以獨立於您用來檢測兩個多邊形之間重疊的任何函數來應用。它只是用一系列更復雜的預測試代替你的雙重嵌套循環。

來源

2014-06-27 21:36:20 RBarryYoung

您可以將所有對象放入3D樹形結構中。那麼你只需要檢查在某種意義上彼此「接近」的配對。

這是存儲空間信息的典型方法。例如。 neo4j空間下有一個k樹，用於存儲位置並執行「接近」類型的查詢。

來源

2014-06-27 22:16:09

檢測多面體之間相交的*最快*算法是什麼？

回答

相關問題

檢測多面體之間相交的最快算法是什麼？