我需要在半径为R的圆内生成一个均匀随机点。
我意识到,只要在区间[0…2π),且在区间(0…R)我最终会有更多的点指向中心,因为对于两个给定的半径,小半径内的点会比大半径内的点彼此更接近。
我在这里找到了一篇关于这个的博客文章,但我不明白他的推理。我认为这是正确的,但我真的很想知道他从哪里得到(2/R2)×r以及他如何得到最终解。
更新:在发布这个问题7年之后,关于平方根算法背后的数学问题,我仍然没有得到一个令人满意的答案。所以我花了一天时间自己写了一个答案。链接到我的答案。
我需要在半径为R的圆内生成一个均匀随机点。
我意识到,只要在区间[0…2π),且在区间(0…R)我最终会有更多的点指向中心,因为对于两个给定的半径,小半径内的点会比大半径内的点彼此更接近。
我在这里找到了一篇关于这个的博客文章,但我不明白他的推理。我认为这是正确的,但我真的很想知道他从哪里得到(2/R2)×r以及他如何得到最终解。
更新:在发布这个问题7年之后,关于平方根算法背后的数学问题,我仍然没有得到一个令人满意的答案。所以我花了一天时间自己写了一个答案。链接到我的答案。
当前回答
这可能会帮助那些对选择速度算法感兴趣的人;最快的方法是(可能?)拒绝抽样。
只需在单位正方形内生成一个点,并拒绝它,直到它在圆内。如(伪代码),
def sample(r=1):
while True:
x = random(-1, 1)
y = random(-1, 1)
if x*x + y*y <= 1:
return (x, y) * r
虽然有时它可能运行不止一次或两次(而且它不是常量时间,也不适合并行执行),但它要快得多,因为它不使用像sin或cos这样复杂的公式。
其他回答
首先我们生成一个cdf[x]
一点到圆心的距离小于x的概率。假设圆的半径为R。
显然,如果x = 0,那么cdf[0] = 0
显然,如果x是R,则cdf[R] = 1
显然,如果x = r,则cdf[r] = (r^2)/(r^2)
这是因为圆上的每个“小区域”都有相同的被选中的概率,所以概率与问题区域成比例。距离圆心x的面积是r^2
所以cdf[x] = x^2/R^2因为两者相互抵消了
我们有cdf[x]=x^2/R^2其中x从0到R
我们解出x
R^2 cdf[x] = x^2
x = R Sqrt[ cdf[x] ]
现在我们可以用一个从0到1的随机数来替换cdf
x = R Sqrt[ RandomReal[{0,1}] ]
最后
r = R Sqrt[ RandomReal[{0,1}] ];
theta = 360 deg * RandomReal[{0,1}];
{r,theta}
我们得到极坐标 {0.601168 R, 311.915°}
我不知道这个问题是否还有新的答案,但我自己碰巧也遇到过同样的问题。我试着跟自己“讲道理”寻找解决办法,我找到了一个。这可能和一些人在这里提出的建议是一样的,但不管怎样,它是这样的:
in order for two elements of the circle's surface to be equal, assuming equal dr's, we must have dtheta1/dtheta2 = r2/r1. Writing expression of the probability for that element as P(r, theta) = P{ r1< r< r1 + dr, theta1< theta< theta + dtheta1} = f(r,theta)*dr*dtheta1, and setting the two probabilities (for r1 and r2) equal, we arrive to (assuming r and theta are independent) f(r1)/r1 = f(r2)/r2 = constant, which gives f(r) = c*r. And the rest, determining the constant c follows from the condition on f(r) being a PDF.
我仍然不确定确切的“(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.
这里有一个快速而简单的解决方案。
在(0,1)范围内选择两个随机数,即a和b。如果b < a,则交换它们。你的观点是(b * R * cos(2 *π* a / b), b * R * sin(2 *π* a / b))。
您可以这样考虑这个解决方案。如果你把圆切开,然后把它拉直,你会得到一个直角三角形。把这个三角形缩小,你会得到一个从(0,0)到(1,0)到(1,1)再回到(0,0)的三角形,所有这些变换都会均匀地改变密度。你所做的就是在三角形中随机取一个点然后反过来得到圆中的一个点。
让我们像阿基米德那样处理这个问题。
我们如何在三角形ABC中均匀地生成一个点,其中|AB|=|BC|?让我们把它扩展到平行四边形ABCD。在ABCD中很容易均匀地生成点。我们均匀地选择AB上的X点和BC上的Y点并选择Z使XBYZ是一个平行四边形。为了在原始三角形中得到一个均匀选择的点,我们只需将ADC中出现的任何点沿AC折叠回ABC。
现在考虑一个圆。在极限情况下,我们可以把它想象成无穷多个等腰三角形ABC, B在原点,A和C在周长上,彼此逐渐接近。我们可以从这些三角形中选择一个角。所以我们现在需要通过在ABC条上选择一点来生成到中心的距离。同样,延伸到ABCD, D现在是圆中心半径的两倍。
使用上述方法可以很容易地在ABCD中选择一个随机点。在AB上随机选一个点,在BC上随机选一个点。Ie。在[0,R]上取一对随机数字x和y,给出离中心的距离。三角形是一条细条AB和BC本质上是平行的。所以Z点到原点的距离是x+y。如果x+y >r我们向下折叠。
这是R=1的完整算法。我希望你同意这很简单。它使用三角函数,但您可以保证它需要多长时间,以及需要多少次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]