我需要在半径为R的圆内生成一个均匀随机点。
我意识到,只要在区间[0…2π),且在区间(0…R)我最终会有更多的点指向中心,因为对于两个给定的半径,小半径内的点会比大半径内的点彼此更接近。
我在这里找到了一篇关于这个的博客文章,但我不明白他的推理。我认为这是正确的,但我真的很想知道他从哪里得到(2/R2)×r以及他如何得到最终解。
更新:在发布这个问题7年之后,关于平方根算法背后的数学问题,我仍然没有得到一个令人满意的答案。所以我花了一天时间自己写了一个答案。链接到我的答案。
我需要在半径为R的圆内生成一个均匀随机点。
我意识到,只要在区间[0…2π),且在区间(0…R)我最终会有更多的点指向中心,因为对于两个给定的半径,小半径内的点会比大半径内的点彼此更接近。
我在这里找到了一篇关于这个的博客文章,但我不明白他的推理。我认为这是正确的,但我真的很想知道他从哪里得到(2/R2)×r以及他如何得到最终解。
更新:在发布这个问题7年之后,关于平方根算法背后的数学问题,我仍然没有得到一个令人满意的答案。所以我花了一天时间自己写了一个答案。链接到我的答案。
当前回答
设ρ(半径)和φ(方位角)是两个随机变量,对应于圆内任意一点的极坐标。如果这些点是均匀分布的,那么ρ和φ的分布函数是什么?
对于任意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
让我们像阿基米德那样处理这个问题。
我们如何在三角形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]
我曾经用过这个方法: 这可能是完全未优化的(即它使用了一个点数组,所以它不能用于大圆圈),但它提供了足够的随机分布。如果你愿意,你可以跳过矩阵的创建,直接绘制。方法是随机化矩形中落在圆内的所有点。
bool[,] getMatrix(System.Drawing.Rectangle r) {
bool[,] matrix = new bool[r.Width, r.Height];
return matrix;
}
void fillMatrix(ref bool[,] matrix, Vector center) {
double radius = center.X;
Random r = new Random();
for (int y = 0; y < matrix.GetLength(0); y++) {
for (int x = 0; x < matrix.GetLength(1); x++)
{
double distance = (center - new Vector(x, y)).Length;
if (distance < radius) {
matrix[x, y] = r.NextDouble() > 0.5;
}
}
}
}
private void drawMatrix(Vector centerPoint, double radius, bool[,] matrix) {
var g = this.CreateGraphics();
Bitmap pixel = new Bitmap(1,1);
pixel.SetPixel(0, 0, Color.Black);
for (int y = 0; y < matrix.GetLength(0); y++)
{
for (int x = 0; x < matrix.GetLength(1); x++)
{
if (matrix[x, y]) {
g.DrawImage(pixel, new PointF((float)(centerPoint.X - radius + x), (float)(centerPoint.Y - radius + y)));
}
}
}
g.Dispose();
}
private void button1_Click(object sender, EventArgs e)
{
System.Drawing.Rectangle r = new System.Drawing.Rectangle(100,100,200,200);
double radius = r.Width / 2;
Vector center = new Vector(r.Left + radius, r.Top + radius);
Vector normalizedCenter = new Vector(radius, radius);
bool[,] matrix = getMatrix(r);
fillMatrix(ref matrix, normalizedCenter);
drawMatrix(center, radius, matrix);
}
朴素解不起作用的原因是它给了靠近圆中心的点更高的概率密度。换句话说,半径为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.
我不知道这个问题是否还有新的答案,但我自己碰巧也遇到过同样的问题。我试着跟自己“讲道理”寻找解决办法,我找到了一个。这可能和一些人在这里提出的建议是一样的,但不管怎样,它是这样的:
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.