☰

Generate a random point within a circle (uniformly) Ask Question

tag-icon • tag-icon math random geometry probability
Generate a random point within a circle (uniformly) Ask Question

I need to generate a uniformly random point within a circle of radius R.

I realize that by just picking a uniformly random angle in the interval [0 ... 2π), and uniformly random radius in the interval (0 ... R) I would end up with more points towards the center, since for two given radii, the points in the smaller radius will be closer to each other than for the points in the larger radius.

I found a blog entry on this over here but I don't understand his reasoning. I suppose it is correct, but I would really like to understand from where he gets (2/R2)×r and how he derives the final solution.

Update: 7 years after posting this question I still hadn't received a satisfactory answer on the actual question regarding the math behind the square root algorithm. So I spent a day writing an answer myself. Link to my answer.

ベストアンサー1

How to generate a random point within a circle of radius R:

r = R * sqrt(random())
theta = random() * 2 * PI

(Assuming random() gives a value between 0 and 1 uniformly)

If you want to convert this to Cartesian coordinates, you can do

x = centerX + r * cos(theta)
y = centerY + r * sin(theta)


Why sqrt(random())?

Let's look at the math that leads up to sqrt(random()). Assume for simplicity that we're working with the unit circle, i.e. R = 1.

The average distance between points should be the same regardless of how far from the center we look. This means for example, that looking on the perimeter of a circle with circumference 2 we should find twice as many points as the number of points on the perimeter of a circle with circumference 1.


                

Since the circumference of a circle (2πr) grows linearly with r, it follows that the number of random points should grow linearly with r. In other words, the desired probability density function (PDF) grows linearly. Since a PDF should have an area equal to 1 and the maximum radius is 1, we have


                

So we know how the desired density of our random values should look like. Now: How do we generate such a random value when all we have is a uniform random value between 0 and 1?

We use a trick called inverse transform sampling

  1. From the PDF, create the cumulative distribution function (CDF)
  2. Mirror this along y = x
  3. Apply the resulting function to a uniform value between 0 and 1.

Sounds complicated? Let me insert a blockquote with a little side track that conveys the intuition:

Suppose we want to generate a random point with the following distribution:

                

That is

  • 1/5 of the points uniformly between 1 and 2, and
  • 4/5 of the points uniformly between 2 and 3.

CDF は、その名前が示すように、 PDF の累積バージョンです。直感的に言うと、 PDF( x ) はx におけるランダム値の数を表しますが、 CDF( x ) はx 未満のランダム値の数を表します。

この場合、CDF は次のようになります。

                

これがどのように役立つかを知るには、等間隔の高さで左から右に弾丸を発射することを想像してください。弾丸が線に当たると、地面に落ちます。

                

地面の弾丸の密度が、私たちが望む分布と一致していることを確認してください。もうすぐ完成です!

問題は、この関数では、y軸が出力で、x軸が入力であることです。 「地面から真上に弾丸を撃つ」ことしかできません。 逆関数が必要です。

これが全体をミラーリングする理由です。xはyになり、y はxになります。

                

これをCDF -1と呼びます。目的の分布に従って値を取得するには、 CDF -1 (random()) を使用します。

…それでは、PDF が 2 xに等しいランダムな半径値の生成に戻ります。

ステップ 1: CDF を作成する:

実数を扱うため、CDF は PDF の積分として表現されます。

CDF ( x ) = ∫ 2 x = x 2

ステップ2: CDFをy = xに沿ってミラーリングします。

数学的には、 xとyを入れ替えてyを解くことになります。

CDF :      y = x 2
スワップ:    x = y 2
解く:    y = √ x
CDF -1 :   y = √ x

ステップ3: 結果の関数を0から1の間の均一な値に適用する

CDF -1 (ランダム()) = √ランダム()

それが私たちが導き出そうとしたものでした :-)

おすすめ記事