在2D中分配隨機點

我正在嘗試做一個簡單的「人羣」模型，並需要在二維區域內分佈隨機點。這個半僞代碼是我最好的嘗試，但即使在我運行它之前，我也可以看到大問題，對於密集人羣來說，新點過於接近的機會可能會非常快地變得非常高，使得它非常低效並且容易失敗，除非這些值被微調。可能與已簽名的值有關，但爲了簡單起見，我將其留下。在2D中分配隨機點

int numPoints = 100; 
int x[numPoints]; 
int y[numPoints]; 
int testX, testY; 

tooCloseRadius = 20; 
maxPointChecks = 100; 
pointCheckCount = 0; 

for (int newPoint = 0; newPoint < numPoints; newPoint++){ 

    //Keep checking random points until one is found with no other points in close proximity, or maxPointChecks reached. 
    while (pointCheckCount < maxPointChecks){ 
     tooClose = false; 
     // Make a new random point and check against all previous points 
     testX = random(1000); 
     testY = random(1000); 
     for (testPoint = 0; testPoint < newPoint; testPoint++){ 
      if ((isTooClose (x[testPoint] , y[testPoint], textX, testY, tooCloseRadius)) { 
      tooClose = true; 
      break; // (exit for loop) 
     } 
     if (tooClose == false){ 
      // Yay found a point with some space! 
      x[newPoint] = testX; 
      y[newPoint] = testY; 
      break; // (exit do loop) 
     } 
     //Too close to one of the points, start over. 
     pointCheckCount++; 
    } 
    if (tooClose){ 
     // maxPointChecks reached without finding a point that has some space. 
     // FAILURE DEPARTMENT 
    } else { 
     // SUCCESS 
    } 
} 

// Simple Trig to check if a point lies within a circle. 
(bool) isTooClose(centerX, centerY, testX, testY, testRadius){ 
    return (testX - centreX)^2 + (testY - centreY)^2) < testRadius ^2 
}

谷歌搜索的主題後，我相信我做了什麼叫做拒絕採樣（？），以及自適應拒絕抽樣可能是一個更好的辦法，但數學是過於複雜。

是否有任何優雅的方法來實現這一點，不需要統計學學位？

來源

2017-03-05 Kez

對於您提出的生成隨機樣本的最佳方法的問題是使用泊松磁盤採樣。

https://www.jasondavies.com/poisson-disc

現在，如果你想在一個矩形取樣隨機點的簡單方法。只需從0到最大尺寸長度的每個點的兩個取樣值。

如果表示較小維度的值大於維度，則將該對移開並再次嘗試。

僞代碼：

while (need more points) 
begin 
    range = max (rect_width, rect_height); 

    x = uniform_random(0,range); 
    y = uniform_random(0,range); 

    if (x > rect_width) or (y > rect_height) 
    continue; 
    else 
    insert point(x,y) into point_list; 
end

你採樣多達兩個長度的較大的原因，是爲了使均勻的選擇標準時等效的長度是不同的。

例如，假設一邊的長度爲K，另一邊的長度爲10K。假設所使用的數字類型的分辨率爲K的1/1000，那麼對於較短的一側，只有1000個可能的值，而較長的一側有10000個可能的值可供選擇。 1/1000的概率與1/10000不一樣。簡單地說，短邊的座標值比長邊的座標值要大10倍 - 這意味着抽樣並不是真正一致的。爲要確保產生的點不超過一定的距離更近於任何已產生的點的情況下

僞代碼：

while (need more points) 
begin 
    range = max (rect_width, rect_height) 

    x = uniform_random(0,range); 
    y = uniform_random(0,range); 

    if (x > rect_width) or (y > rect_height) 
    continue; 

    new_point = point(x,y); 

    too_close = false; 

    for (p : all points) 
    begin 
    if (distance(p, new_point) < minimum_distance) 
    begin 
     too_close = true; 
     break; 
    end 
    end 

    if (too_close) 
     continue; 

    insert point(x,y) into point_list; 
end

來源

2017-03-05 02:21:22

您能解釋uniform_random嗎？這是從0->範圍的標準隨機函數嗎？ – Kez

@凱茲是的。它將在[0，upper_bound]範圍內返回一致的數值概率，其中upper_bound是最大邊的長度。 –

好的，但爲什麼使用range而不只是x = uniform_random（0，rect_width）;等等？ – Kez

雖然泊松磁盤解決方案通常是罰款和花花公子，我想指出一個使用準隨機數的替代方案。對於準隨機Sobol序列，有一個聲明表示點之間的最小正距離等於0.5 * sqrt（d）/ N，其中d是問題的維數（在您的情況下爲2），N是數字在超立方體中採樣的點數。紙張從這個人自己http://www.sciencedirect.com/science/article/pii/S0378475406002382。

爲什麼我認爲它應該是Python？對不起這是我的錯。對於最好稱爲GSL的類C語言，函數名稱爲gsl_qrng_sobol。在d = 2處使用它的示例鏈接here

來源

2017-03-08 01:55:14

謝謝Severin Pappadeux，這是另一個很棒的小竅門，儘管我必須讓我的腦袋圍繞這個數學。泊松圓盤解決方案的一個問題是你總是得到'緊密'點，這可能並不理想。 – Kez

@凱斯Poisson Disc實際上存在很多問題。首先，它是O（N）算法，這使得實際模擬速度變慢（例如，百萬分）。其次，目前還不清楚底層分佈是什麼，例如，用於蒙特卡羅整合。對於U（0,1），你將得到通常的蒙特卡羅收斂爲sqrt（N）的反函數。對於準隨機，它更接近逆N。誰知道...更多的鏈接來看看[準隨機]（https://en.wikipedia.org/wiki/Low-discrepancy_sequence），你可以看看點的一致性。另一個鏈接：https：//en.wikipedia.org/wiki/Supersampling –

在2D中分配隨機點

回答

相關問題