碰撞檢測複雜度<O（n²）：比網格，四叉樹，BSP更簡單的方法？

Question

我有大量的物體（球，一開始），在空間逐步移動，一次一個，並且不應該重疊。目前，我每檢查一次與其他物體的碰撞情況。 Severalotherquestionshere處理這個，但是，我想到了一個看似簡單的解決方案，似乎沒有出現在這種情況下，我不知道爲什麼。

爲什麼不簡單地保留所有對象的2個集合（對於二維或三維），分別按x和y（和z）座標排序，並且在每個移動中查找給定內的所有其他對象距離（球直徑在這裏）在每個維度，並且只對兩個（或所有3個）結果集中的對象進行實際碰撞檢查？

我意識到這隻適用於大小相等的對象，或者可以使用兩倍數量的集合，按每個維度的每個對象的（1）最高（2）最低座標排序。與從O（n）「成對檢查」到「grid method」或「四/八分之一」相比，這種方法無效的原因或顯着減少的原因？我將這些排序後的集合的更新看作這裏的昂貴操作，但使用例如一個TreeSet（我的實現將使用Java），它仍然要比O（n）小得多，對吧？

Answer 1

檢查兩個結果集中的哪些對象包括查看兩個平面中的所有對象。這是一個更大的區域，因此涉及更多的對象，而不是四邊形樹讓您立即縮小到的封閉正方形。更多的對象意味着它更慢。

Answer 2

您想要使用空間索引或空間填充曲線而不是四叉樹。一個sfc將二維複雜度減少到一維複雜度，並且與四叉樹不同，因爲它只能存儲每個x，y對的一個對象？也許這適用於你的問題？你想搜索Nick的希爾伯特曲線四叉樹空間索引博客。