如何用它們之間的最小距離生成「隨機」點

Question

我正在嘗試使用點（城市）生成「地圖」的程序。只生成隨機城市（用圖表表示）不成問題，但我需要在它們之間設置一些最小距離（例如，城市之間的距離爲5或更多）。 大約有3000個城市，所以我正在尋找一些有效的解決方案。

我無法想出如何解決它，所以我會很感激任何幫助。

Answer 1

如果將地圖劃分爲10x10個方格，則任何位於給定點的五個單位內的點必須位於由（x +/- 5，y +/- 5）定義的四個方格之一內）。 10×10平方可能包含多達8個點，但是檢查每個新點與四個平方每個點最多8個點可能比檢查數千個點更快。

這種方法需要注意的最重要的事情是，因爲整數除法運算符浮點數到整數轉換運算符的負數行爲被選擇爲對處理程序而言非常簡單，而不是對程序員有用，如果一些座標是正的，而一些是負的，則必須注意異常情況。例如，如果x是int並且一個計算int col = x/10;,col對於從-9到+9的x值將爲零（意味着包含點（0,0）的框在每個維中將幾乎是它們應該的兩倍是）。如果座標可能變爲負值，則必須在執行分割之前將其調整爲正值。

Answer 2

如果是大約3000個城市，它可能不是那不合理將它們放入您的地圖，然後檢查您的最小距離標準。檢查時間上升爲O（n），並且您在地圖上的點數越多，您就越有可能發生「碰撞」。

你需要「隨機」嗎？如果您將地圖劃分爲5x5的正方形網格，並且隨機將2.5x2.5的正方形放置在中心的2.5x2.5中，您是否可以通過？那會很快，你不會碰到任何碰撞。

這可能是值得的，看看真正有多少隨機性在你需要的城市位置。

Answer 3

如果您的程序使用x軸和y軸，則應參考距離公式。 Here是它的鏈接。 Circle Equation也可能派上用場。 把你的第一個城市看作圓圈的中心。具有最小距離的第二個城市應該位於圓的圓周上，最小距離是該圓的半徑。你有第二個城市應該在哪裏的無限可能性。但是，再次假設您正在使用x和y軸。