我需要在半径为R的圆内生成一个均匀随机点。
我意识到,只要在区间[0…2π),且在区间(0…R)我最终会有更多的点指向中心,因为对于两个给定的半径,小半径内的点会比大半径内的点彼此更接近。
我在这里找到了一篇关于这个的博客文章,但我不明白他的推理。我认为这是正确的,但我真的很想知道他从哪里得到(2/R2)×r以及他如何得到最终解。
更新:在发布这个问题7年之后,关于平方根算法背后的数学问题,我仍然没有得到一个令人满意的答案。所以我花了一天时间自己写了一个答案。链接到我的答案。
我需要在半径为R的圆内生成一个均匀随机点。
我意识到,只要在区间[0…2π),且在区间(0…R)我最终会有更多的点指向中心,因为对于两个给定的半径,小半径内的点会比大半径内的点彼此更接近。
我在这里找到了一篇关于这个的博客文章,但我不明白他的推理。我认为这是正确的,但我真的很想知道他从哪里得到(2/R2)×r以及他如何得到最终解。
更新:在发布这个问题7年之后,关于平方根算法背后的数学问题,我仍然没有得到一个令人满意的答案。所以我花了一天时间自己写了一个答案。链接到我的答案。
当前回答
朴素解不起作用的原因是它给了靠近圆中心的点更高的概率密度。换句话说,半径为r/2的圆被选中点的概率为r/2,但它的面积(点的数量)为*r^2/4。
因此,我们希望半径概率密度具有以下性质:
选择半径小于或等于给定r的概率必须与半径为r的圆的面积成正比(因为我们希望在点上有一个均匀的分布,面积越大意味着点越多)。
换句话说,我们希望在[0,r]之间选择半径的概率等于它在圆的总面积中所占的份额。圆的总面积是*R^2,半径为R的圆的面积是*R^2。因此,我们希望在[0,r]之间选择半径的概率为(pi*r^2)/(pi* r^2) = r^2/ r^2。
现在来算算:
The probability of choosing a radius between [0,r] is the integral of p(r) dr from 0 to r (that's just because we add all the probabilities of the smaller radii). Thus we want integral(p(r)dr) = r^2/R^2. We can clearly see that R^2 is a constant, so all we need to do is figure out which p(r), when integrated would give us something like r^2. The answer is clearly r * constant. integral(r * constant dr) = r^2/2 * constant. This has to be equal to r^2/R^2, therefore constant = 2/R^2. Thus you have the probability distribution p(r) = r * 2/R^2
Note: Another more intuitive way to think about the problem is to imagine that you are trying to give each circle of radius r a probability density equal to the proportion of the number of points it has on its circumference. Thus a circle which has radius r will have 2 * pi * r "points" on its circumference. The total number of points is pi * R^2. Thus you should give the circle r a probability equal to (2 * pi * r) / (pi * R^2) = 2 * r/R^2. This is much easier to understand and more intuitive, but it's not quite as mathematically sound.
其他回答
我仍然不确定确切的“(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.
这样一个有趣的问题。 一个点被选择的概率随着距离轴原点的增加而降低的基本原理在上面已经解释了多次。我们通过取U[0,1]的根来解释这一点。 下面是Python 3中正r的通解。
import numpy
import math
import matplotlib.pyplot as plt
def sq_point_in_circle(r):
"""
Generate a random point in an r radius circle
centered around the start of the axis
"""
t = 2*math.pi*numpy.random.uniform()
R = (numpy.random.uniform(0,1) ** 0.5) * r
return(R*math.cos(t), R*math.sin(t))
R = 200 # Radius
N = 1000 # Samples
points = numpy.array([sq_point_in_circle(R) for i in range(N)])
plt.scatter(points[:, 0], points[:,1])
如何在半径为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()
这就是我们要推导的:-)
我认为在这种情况下,使用极坐标是一种使问题复杂化的方法,如果你在一个边长为2R的正方形中随机选择点,然后选择点(x,y)使x^2+y^2<=R^2,这将会容易得多。
我不知道这个问题是否还有新的答案,但我自己碰巧也遇到过同样的问题。我试着跟自己“讲道理”寻找解决办法,我找到了一个。这可能和一些人在这里提出的建议是一样的,但不管怎样,它是这样的:
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.