在圆内生成随机点(均匀)

Question

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

我意识到,通过在区间[0 ...2π)中选择一个均匀的随机角度,并且在区间(0 ... R)中均匀随机半径,我会得到更多的点朝向中心,因为两个给定半径,较小半径中的点将比较大半径中的点更接近彼此.

我在这里发现了一篇关于此的博客文章,但我不理解他的推理.我想它是正确的,但我真的想从他得到的地方(2/R ²)× r以及他如何得出最终解决方案中理解.

---

更新:发布此问题7年后,我仍然没有收到有关平方根算法背后数学的实际问题的满意答案.所以我花了一天时间自己写答案.链接到我的答案.

Answer 1

让我们像阿基米德那样接近这个.

我们如何在三角形ABC中统一生成一个点,其中| AB | = | BC |？让我们通过扩展到平行四边形ABCD来简化这一过程.在ABCD中统一生成点很容易.我们在BC上的AB和Y上均匀地选取随机点X并选择Z使得XBYZ是平行四边形.要在原始三角形中获得统一选择的点,我们只需将ADC中出现的任何点折叠回AC沿ABC.

现在考虑一个圆圈.在极限中,我们可以将其视为无限多的等腰三角形ABC,其原点为B,圆周上的A和C消失得彼此相近.我们可以通过选择角度θ来选择这些三角形中的一个.因此,我们现在需要通过在棉条A​​BC中选取一个点来生成距离中心的距离.再次,延伸到ABCD,其中D现在是圆心的半径的两倍.

使用上述方法很容易在ABCD中挑选一个随机点.在AB上选择一个随机点.在BC上统一选择一个随机点.IE浏览器.在[0,R]上均匀地选择一对随机数x和y,给出距离中心的距离.我们的三角形是一个薄的条子,因此AB和BC基本上是平行的.所以Z点只是距离原点的距离x + y.如果x + y> R,我们会向下折叠.

这是R = 1的完整算法.我希望你同意这很简单.它使用trig,但你可以保证它需要多长时间,以及random()它需要多少次呼叫,这与拒绝采样不同.

t = 2*pi*random()
u = random()+random()
r = if u>1 then 2-u else u
[r*cos(t), r*sin(t)]

这是在Mathematica.

f[] := Block[{u, t, r},
  u = Random[] + Random[];
  t = Random[] 2 Pi;
  r = If[u > 1, 2 - u, u];
  {r Cos[t], r Sin[t]}
]

ListPlot[Table[f[], {10000}], AspectRatio -> Automatic]

Answer 2

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

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

(假设random()统一给出介于0和1之间的值)

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

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

为什么sqrt(random())？

让我们来看看导致的数学sqrt(random()).为简单起见,假设我们正在使用单位圆,即R = 1.

无论我们看中心多远,点之间的平均距离应该相同.这意味着,例如,在周长为2的圆的周长上,我们应该找到两倍于周长为1的圆的周长点的点数.

                

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

                

因此,我们知道随机值的所需密度应该如何.现在:当我们拥有的是0到1之间的均匀随机值时,我们如何生成这样的随机值？

我们使用称为逆变换采样的技巧

1. 从PDF中,创建累积分布函数(CDF)
2. 沿y = x镜像
3. 将结果函数应用于0到1之间的统一值.

听起来很复杂？让我插入一个黄色的盒子,带有一个传达直觉的小侧轨:

假设我们想要生成具有以下分布的随机点:

                

那是

• 1/5的点均匀地在1和2之间,和
• 4/5的点均匀地在2和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步:沿y = x镜像CDF:

在数学上,这归结为交换x和y并求解y:

CDF:      ÿ = X ²
交换:    X = ÿ ²
解:    Ý =√ X
CDF ^-1:   Ý =√ X

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

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

这是我们打算推出的:-)

Answer 3

这是一个快速而简单的解决方案.

选择范围(0,1)中的两个随机数,即a和b.如果b < a,交换它们.你的意思是(b*R*cos(2*pi*a/b), b*R*sin(2*pi*a/b)).

您可以按如下方式考虑此解决方案.如果你拿圆圈,剪掉它,然后将它拉直,你会得到一个直角三角形.规模是倒三角形,而且你从有一个三角形(0, 0),以(1, 0)对(1, 1),然后再返回来(0, 0).所有这些变换均匀地改变了密度.你所做的是在三角形中统一选取一个随机点并反转过程以获得圆圈中的一个点.

Answer 4

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

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

这将为您提供磁盘上的统一点分布.

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

Answer 5

这样想吧.如果你有一个长方形,其中一个轴是半径和一个角度,你利用这个矩形是附近半径0.这些都将落在非常接近原点内点(即紧靠在一起的圆圈.)然而,在半径R附近的点,这些点都会落在圆的边缘附近(也就是彼此相距很远).

这可能会让您知道为什么会出现这种行为.

在该链接上导出的因子告诉您矩形中需要调整多少相应区域,以便在它映射到圆后不依赖于半径.

编辑:所以他在你所分享的链接中写道,"通过计算累积分布的倒数,这很容易做到,我们得到r:".

这里的基本前提是,您可以通过所需概率密度函数的累积分布函数的反函数映射均匀来创建具有所需分布的变量.为什么？现在就把它视为理所当然,但这是事实.

这是我对数学的直观解释.相对于r的密度函数f(r)必须与r本身成比例.理解这一事实是任何基础微积分书籍的一部分.请参阅极区元素部分.其他一些海报也提到了这一点.

所以我们称之为f(r)= C*r;

事实证明这是大部分工作.现在,由于F(R)应的概率密度,就可以很容易地看到,通过在区间(0,R)积分F(R)你得到C = 2/R ^ 2(这是为读者的练习.)

因此,f(r)= 2*r/R ^ 2

好的,这就是你如何在链接中获得公式.

然后,最后一部分来自(0,1)中的均匀随机变量u,你必须通过累积分布函数的反函数从该期望密度f(r)进行映射.要了解为什么会出现这种情况,您需要找到像Papoulis这样的高级概率文本(或者自己推导出来).

积分f(r)得到F(r)= r ^ 2/R ^ 2

要找到它的反函数,你设置u = r ^ 2/R ^ 2然后求解r,这给你r = R*sqrt(u)

这也完全有意义,u = 0应映射到r = 0.此外,u = 1 shoudl映射到r = R.此外,它通过平方根函数,这是有意义的并匹配链接.

Answer 6

天真解决方案不起作用的原因是它给靠近圆心的点提供了更高的概率密度.换句话说,具有半径r/2的圆具有获得在其中选择的点的概率r/2,但是其具有面积(点数)pi*r ^ 2/4.

因此,我们希望半径概率密度具有以下属性:

选择小于或等于给定r的半径的概率必须与半径为r的圆的面积成比例.(因为我们希望在点上有均匀的分布,而更大的区域意味着更多的点)

换句话说,我们希望选择[0,r]之间的半径的概率等于它在圆的整个区域中的份额.总圆面积是pi*R ^ 2,半径为r的圆的面积是pi*r ^ 2.因此,我们希望选择[0,r]之间的半径的概率为(pi*r ^ 2)/(pi*R ^ 2)= r ^ 2/R ^ 2.

数学来了:

在[0,r]之间选择半径的概率是p(r)dr从0到r的积分(这只是因为我们加上了所有较小半径的概率).因此,我们想要积分(p(r)dr)= r ^ 2/R ^ 2.我们可以清楚地看到R ^ 2是一个常数,所以我们需要做的就是找出哪个p(r),当积分时会给出类似r ^ 2的东西.答案显然是r*不变的.积分(r*常数dr)= r ^ 2/2*常数.这必须等于r ^ 2/R ^ 2,因此常数= 2/R ^ 2.因此,你有概率分布p(r)= r*2/R ^ 2

注意:考虑问题的另一种更直观的方法是想象你试图给每个圆的半径ra概率密度等于它在圆周上的点数的比例.因此,具有半径r的圆将在其圆周上具有2*pi*r"点".总点数是pi*R ^ 2.因此,你应该给出等于(2*pi*r)/(pi*R ^ 2)= 2*r/R ^ 2的圆ra概率.这更容易理解和更直观,但它并不像数学上那么合理.

Answer 7

这实际上取决于"均匀随机"的含义.这是一个微妙的观点,您可以在维基页面上阅读更多相关内容:http://en.wikipedia.org/wiki/Bertrand_paradox_%28probability%29,其中同样的问题,对"均匀随机"给出不同的解释不同的答案!

这取决于你如何选点,分布可能会发生变化,即使他们是在同样的随机一些感觉.

这似乎是博客条目正在努力使其在以下意义上的均匀随机:如果你把圆的子圈,具有相同的中心,那么该点落在该区域的概率是成正比的区域该区域.也就是说,我认为,试图遵循"统一随机"现在标准解释为2D范围与上定义的区域:在任何地区下降(具有明确的区域)上的点的概率正比于该区域的面积.

Answer 8

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

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

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

其中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倍的随机变量的sqrt(X),其中X是均匀的[0,1)具有此确切CDF(因为P [SQRT(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)

你会得到

Answer 9

这是我num从半径圆中生成随机点的Python代码rad:

import matplotlib.pyplot as plt
import numpy as np
rad = 10
num = 1000

t = np.random.uniform(0.0, 2.0*np.pi, num)
r = rad * np.sqrt(np.random.uniform(0.0, 1.0, num))
x = r * np.cos(t)
y = r * np.sin(t)

plt.plot(x, y, "ro", ms=1)
plt.axis([-15, 15, -15, 15])
plt.show()

Answer 10

我认为在这种情况下，使用极坐标会使问题复杂化，如果您将随机点选入边长为 2R 的正方形，然后选择(x,y)使得x^2+y^2<=R^2.