2017-03-05 29 views
2

私は単純な単純な「群衆」モデルを作成しようとしており、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 
} 

、私は私が何をやったかと考えているが棄却サンプリングと呼ばれている(?)、およびアダプティブ棄却サンプリングは、より良い方法かもしれないが、数学はあまりにも複雑です。

これを達成するための統計的な学位を必要としない優雅な方法はありますか?

答えて

5

ランダムサンプルを生成する最良の方法を提案する問題は、ポアソンディスクサンプリングを使用することです。

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

今、あなたは長方形で簡単な方法をランダムな点をサンプリングしたい場合。単に 0から最大の次元の長さまで、ポイントごとに2つの値をサンプリングします。

小さい方の大きさを表す値が小さい方の値が大きい方の値が大きい場合は、もう一度試してみてください。

擬似コード:

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 

あなたは2つの長さの大きい方までサンプリングした理由は、長さが異なる場合均一な選択基準が同等にすることです。

たとえば、一方の辺の長さが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 
+0

uniform_randomについて説明できますか?これは0-> rangeの標準ランダム関数ですか? – Kez

+1

@Kezはい。 [0、upper_bound]の範囲で値の一様確率を返します。ここで、upper_boundは最大の辺の長さです。 –

+0

でも、x = uniform_random(0、rect_width)だけでなく、なぜ範囲を使うのか。等? – Kez

0

、疑似乱数を使って代替を指摘したいと思います。疑似ランダムSobolシーケンスでは、問題の次元(あなたの場合は2)がdであり、数字がNである点が0.5 * sqrt(d)/ Nになる点の間に最小の正の距離があるという声明があります。ハイパーキューブでサンプリングされたポイントの数。彼自身からのペーパーhttp://www.sciencedirect.com/science/article/pii/S0378475406002382

私はそれがPythonであるべきだと思ったのはなぜですか?申し訳ありませんが、私の悪い。 GSLを呼び出すのに最適なCのような言語では、関数名はgsl_qrng_sobolです。 d = 2で使用する例がリンクされていますhere

+0

Severin Pappadeuxさん、ありがとうございました。私はその数学の周りに頭を浮かべなければなりません。 Poisson Discソリューションの1つの問題は、あなたが常に「しっかりと詰め込まれた」点を得ることであり、それは望ましくない可能性があります。 – Kez

+0

@Kez Poisson Discには実際に多くの問題があります。まず、それはO(N)アルゴリズムであり、実際のシミュレーション(数百万点のような)では遅くなります。第二に、モンテカルロ統合との使用のために、根底にあるディストリビューションが何であるかは不明である。 U(0,1)に対して、通常のモンテカルロ収束を逆sqrt(N)として得るでしょう。準ランダムの場合、それは逆N.PDに近いですか?誰が知っているかもっと見るためのリンク:[疑似ランダム](https://en.wikipedia.org/wiki/Low-discrepancy_sequence)では、ポイントの一貫性を見ることができます。別のリンク:https://en.wikipedia.org/wiki/Supersampling –