在有限空間內隨機位置生成100個球（有半徑且不重疊）

Question

例如，限制空間爲100 x 100 x 100大，每個球的半徑爲5，我需要生成100個這樣的球在此空間內的隨機位置和不允許重疊。我想出了兩種方法：

1. 使用函數srand並獲得100個位置，然後做一個檢查，以刪除彼此重疊的球（檢查兩個球中心的距離小於兩倍半徑），然後生成另外的x個球（x是刪除的球的數量）並且繼續重複該過程直到100個球不重疊。

2. 首先將空間分成100個立方體，並使用srand將每個球放置在其分配的立方體內，這樣它們就不會重疊。

我覺得第一種方式是更恰當的隨機方面，但太耗費時間和第二種方式是快速和容易的，但我不知道有關的隨​​機的想法在那裏。這個模型試圖模擬空氣中分子的位置。也許這兩種方式都不好，請讓我知道是否有更好的方法。提前致謝！

編輯： @將提供給我一個類似的選項，但比我原來的第一種方法更清潔;每次添加一個新球時，檢查它是否與任何現有球重疊，如果有，重新生成。複雜度爲1 + 2 + 3 ... +（n-1），約爲O（n^n）。我仍然想知道是否有更快的算法。

EDIT2： 對不起1 + 2 + ... n應爲n^2

Answer 1

代替將所述區域分成100個立方體，則可以把它分成8000 5×5的立方體，然後將中心球成100個這些立方體。這樣球仍然被隨機放置在空間中，但不能重疊。 編輯：此外，當檢查球是否重疊時，您可能需要考慮使用數據結構，以便您只能檢查距離要檢查的球最近的球。檢查它們都是浪費的，因爲在空間的完全不同的側面上沒有球重疊的機會。我不太熟悉八叉樹，但是如果你真的想優化你的代碼，你可能想看看它們。

Answer 2

您可以執行O（（n + f）log n）算法，其中f是失敗嘗試次數。基本上，花時間過長的問題是找到與你重疊的鄰近球。您可以使用稱爲KD樹的外部數據結構來有效地存儲球的位置。然後你可以通過KD樹查找你的「最近」的鄰居球。這將花費O（log n）時間。確定它們是否重疊，然後將球添加到空間和KD樹 - 插入操作是O（log n）操作。總共有n個球取O（log n）爲O（n log n），計算失敗嘗試次數爲O（（n + F）* log n）。 CGAL（計算幾何算法庫）提供了一個很好的KD樹實現。下面是CGAL一個鏈接，鏈接到KD樹：

http://www.cgal.org/

https://en.wikipedia.org/wiki/K-d_tree

還有其他的結構，像KD樹，但這將是最容易使用你的案件。

如果你想避免使用奇特的數據結構，你可以在空間上計算網格。將整個空間中的每個隨機球插入其網格單元格中。然後當檢查重疊時，只需要檢查相鄰單元格中的球（假設球的大小不會重疊多於一個鄰接）。這不會改善總體時間複雜度，但是在計算機圖形學中常用的方法是改進鄰居查找例程的執行時間。

Answer 3

您球體的體積大約是您的空間體積的1/1900，所以如果您只是隨機選擇位置並檢查重疊部分，則不必重新生成許多球體。如果你真的只需要100個，使用像Octrees這樣的花式算法來檢查碰撞將是一種浪費。

當然，只要你編碼，有人會要求你做10000個球而不是100個，所以我剛剛說的一切都是錯誤的。

我喜歡克里斯的建議，只是將它們放入隨機選取的立方體中。不是最現實的，但更接近和更簡單。