我需要在半径为R的圆内生成一个均匀随机点。

我意识到,只要在区间[0…2π),且在区间(0…R)我最终会有更多的点指向中心,因为对于两个给定的半径,小半径内的点会比大半径内的点彼此更接近。

我在这里找到了一篇关于这个的博客文章,但我不明白他的推理。我认为这是正确的,但我真的很想知道他从哪里得到(2/R2)×r以及他如何得到最终解。


更新:在发布这个问题7年之后,关于平方根算法背后的数学问题,我仍然没有得到一个令人满意的答案。所以我花了一天时间自己写了一个答案。链接到我的答案。


当前回答

半径和“靠近”该半径的点的数量之间存在线性关系,因此他需要使用半径分布,这也使得半径r附近的数据点的数量与r成正比。

其他回答

圆中的面积元是dA=rdr*dphi。这个额外的因子r破坏了你随机选择r和的想法。虽然phi分布平坦,但r不是,而是在1/r内平坦(也就是说,你更有可能击中边界而不是“靶心”)。

为了生成在圆上均匀分布的点从平面分布中选取r从1/r分布中选取。

或者使用Mehrdad提出的蒙特卡罗方法。

EDIT

要在1/r中选择一个随机的r,你可以从区间[1/ r,无穷]中选择一个随机的x,并计算r=1/x。R以1/ R为单位平坦分布。

为了计算一个随机的,从区间[0,1]中选择一个随机的x,并计算=2*pi*x。

如何在半径为R的圆内随机生成一个点:

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

(假设random()均匀地给出0到1之间的值)

如果你想把它转换成笛卡尔坐标,你可以做到

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

为什么sqrt(随机())?

让我们看看sqrt(random())之前的数学运算。为简单起见,假设我们是在单位圆上工作,即R = 1。

点与点之间的平均距离应该是相同的,不管我们看的距离中心有多远。这意味着,例如,观察一个周长为2的圆的周长,我们应该找到的点的数量是周长为1的圆周长上点的数量的两倍。


                

由于圆的周长(2πr)随r线性增长,因此随机点的数量应该随r线性增长。换句话说,期望的概率密度函数(PDF)线性增长。由于PDF的面积应该等于1,最大半径是1,我们有


                

所以我们知道随机值的理想密度应该是什么样的。 现在:当我们只有一个0到1之间的均匀随机值时,我们如何生成这样一个随机值?

我们用了一个叫做反变换采样的技巧

从PDF中创建累积分布函数(CDF) 沿着y = x镜像 将得到的函数应用于0到1之间的统一值。

听起来复杂吗?让我插入一段带有小侧轨的引语来传达直觉:

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. The CDF is, as the name suggests, the cumulative version of the PDF. Intuitively: While PDF(x) describes the number of random values at x, CDF(x) describes the number of random values less than x. In this case the CDF would look like:                  To see how this is useful, imagine that we shoot bullets from left to right at uniformly distributed heights. As the bullets hit the line, they drop down to the ground:                  See how the density of the bullets on the ground correspond to our desired distribution! We're almost there! The problem is that for this function, the y axis is the output and the x axis is the input. We can only "shoot bullets from the ground straight up"! We need the inverse function! This is why we mirror the whole thing; x becomes y and y becomes x:                  We call this CDF-1. To get values according to the desired distribution, we use CDF-1(random()).

所以,回到生成随机半径值,其中PDF等于2x。

步骤1:创建CDF: 由于我们处理的是实数,CDF表示为PDF的积分。

CDF(x) = ∫ 2x = x2

步骤2:沿y = x镜像CDF:

从数学上讲,这可以归结为交换x和y并求解y:

CDF: y = x2 交换:x = y2 解:y =√x CDF-1: y =√x

步骤3:将得到的函数应用于0到1之间的统一值

CDF-1(random()) =√random()

这就是我们要推导的:-)

我仍然不确定确切的“(2/R2)×r”,但显而易见的是,在给定的单位“dr”中需要分配的点的数量,即r的增加将与R2成正比,而不是r。

check this way...number of points at some angle theta and between r (0.1r to 0.2r) i.e. fraction of the r and number of points between r (0.6r to 0.7r) would be equal if you use standard generation, since the difference is only 0.1r between two intervals. but since area covered between points (0.6r to 0.7r) will be much larger than area covered between 0.1r to 0.2r, the equal number of points will be sparsely spaced in larger area, this I assume you already know, So the function to generate the random points must not be linear but quadratic, (since number of points required to be distributed in given unit 'dr' i.e. increase in r will be proportional to r2 and not r), so in this case it will be inverse of quadratic, since the delta we have (0.1r) in both intervals must be square of some function so it can act as seed value for linear generation of points (since afterwords, this seed is used linearly in sin and cos function), so we know, dr must be quadratic value and to make this seed quadratic, we need to originate this values from square root of r not r itself, I hope this makes it little more clear.

设ρ(半径)和φ(方位角)是两个随机变量,对应于圆内任意一点的极坐标。如果这些点是均匀分布的,那么ρ和φ的分布函数是什么?

对于任意r: 0 < r < r,半径坐标ρ小于r的概率为

P[ρ < r] = P[点在半径r的圆内]= S1 / S0 =(r/ r)2

其中S1和S0分别是半径为r和r的圆的面积。 因此,CDF可表示为:

          0          if r<=0
  CDF =   (r/R)**2   if 0 < r <= R
          1          if r > R

和PDF格式:

PDF = d/dr(CDF) = 2 * (r/R**2) (0 < r <= R).

请注意,对于R=1随机变量根号(X),其中X在[0,1]上是一致的,有这个确切的CDF(因为P[根号(X) < y] = P[X < y**2] = y**2对于0 < y <= 1)。

φ在0 ~ 2*π范围内分布明显均匀。现在你可以创建随机极坐标,并使用三角方程将其转换为笛卡尔坐标:

x = ρ * cos(φ)
y = ρ * sin(φ)

忍不住要发布R=1的python代码。

from matplotlib import pyplot as plt
import numpy as np

rho = np.sqrt(np.random.uniform(0, 1, 5000))
phi = np.random.uniform(0, 2*np.pi, 5000)

x = rho * np.cos(phi)
y = rho * np.sin(phi)

plt.scatter(x, y, s = 4)

你会得到

注意点密度与半径的平方反比成正比,因此不是从[0,r_max]中选择r,而是从[0,r_max^2]中选择r,然后计算你的坐标:

x = sqrt(r) * cos(angle)
y = sqrt(r) * sin(angle)

这就得到了圆盘上均匀的点分布。

http://mathworld.wolfram.com/DiskPointPicking.html