在一个圆圈内(均匀地)生成一个随机点

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

我意识到,通过在区间[0 …2π)中select一个均匀的随机angular度,并且在区间(0 … R )中的均匀随机半径,我将以更多点为中心,因为对于两个给定的半径小的半径中的点将比在较大的半径中的点更接近彼此。

我在这里发现了一个博客条目,但我不明白他的推理。 我认为这是正确的,但是我真的很想从他(2 / R 2 )× r以及他如何得出最终解决scheme中得到解释。


关于拒绝抽样:我可以一次又一次地在R × R广场内生成一个随机点,直到我在圆圈内find一个点。 这种方法有一个明显的缺点,即它不能提供终止保证(尽pipe它很可能不会持续很长时间)。

让我们来看看阿基米德会有的。

我们如何在三angular形ABC中均匀地生成一个点,其中| AB | = | BC |? 让我们通过扩展到平行四边形ABCD来简化这个过程。 在ABCD中统一生成点很容易。 我们统一在AB上select一个随机点X,在BC上selectY,selectZ使得XBYZ是平行四边形。 为了在原始三angular形中获得一个统一的select点,我们只需将出现在ADC中的任何点沿着AC折回到ABC。

现在考虑一个圆圈。 在极限中,我们可以把它看作无限多的等边三angular形ABC,其中B在原点处,A和C在圆周上互不相干。 我们可以简单地通过select一个angular度θ来挑选其中的一个三angular形。 所以我们现在需要通过挑选条子ABC中的一个点来从中心产生一个距离。 再次延伸到ABCD,其中D现在是离圆心的半径的两倍。

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

这是R = 1的完整algorithm。 我希望你同意这很简单。 它使用了trig,但你可以保证它需要多长时间,以及它需要多less次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] 

在这里输入图像描述

这是一个快速和简单的解决scheme。

在范围(0,1)中选取两个随机数,即ab 。 如果b < a ,交换它们。 你的观点是(b*R*cos(2*pi*a/b), b*R*sin(2*pi*a/b))

您可以考虑如下的解决scheme。 如果你拿了这个圆圈,把它剪断,然后把它弄直,你会得到一个直angular三angular形。 将三angular形向下缩放,您将有一个从(0, 0)(1, 0)(1, 1)再回到(1, 1) (0, 0)的三angular形。 所有这些转换均匀地改变密度。 你所做的就是在三angular形中均匀地选取一个随机点,并将这个过程颠倒过来,从而得到一个圆点。

想想这样。 如果您有一个矩形,其中一个轴是半径,一个是angular度,并且您将这个矩形内的点接近半径0,这些点将全部下降得非常接近原点(即在圆上靠近)。但是,接近半径R的点将全部落在圆的边缘附近(即彼此远离)。

这可能会给你一些你为什么得到这种行为的想法。

在该链接上派生的因素告诉您矩形中的相应区域需要调整多less,以便在映射到圆时不依赖于半径。

编辑:所以他写在你分享的链接是,“通过计算累积分布的倒数很容易,我们得到r:”。

这里的基本前提是,可以通过将期望的概率密度函数的累积分布函数的反函数映射到均匀点来创build具有期望的均匀分布的variables。 为什么? 现在就理所当然,但这是事实。

这是我对math的直觉解释。 密度函数f(r)相对于r必须与r本身成比例。 理解这个事实是任何基本微积分书籍的一部分。 参见有关极地地区元素的部分。 其他一些海报已经提到这一点。

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

这原来是大部分的工作。 现在,由于f(r)应该是一个概率密度,你可以很容易地看到,通过在区间(0,R)上积分f(r)得到C = 2 / R ^ 2(这是读者的练习。)

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

好的,这就是你如何得到链接中的公式。

然后,最后一部分从(0,1)中的统一随机variablesu开始,必须由这个期望密度f(r)的累积分布函数的反函数映射。 要理解为什么这种情况下,你需要find一个像帕普利斯这样的高级概率文本(或者自己推导出来)。

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

为了find这个反函数,你设定u = r ^ 2 / R ^ 2然后求解r,这就给出了r = R * sqrt(u)

这也完全有道理,u = 0应该映射到r = 0。另外,u = 1 shoudl映射到r = R。另外,它通过平方根函数,这是有道理的,匹配链接。

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

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

这将给你在磁盘上的统一点分布。

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

这真的取决于你的意思是“一致随机”。 这是一个微妙的点,你可以在这里的维基页面上阅读更多关于它: http : //en.wikipedia.org/wiki/Bertrand_paradox_%28probability%29 ,同样的问题,给予“一致随机”不同的解释给出不同的答案!

根据你select的点数,分布可能会有所不同,即使它们在某种意义上是一致的随机数。

看起来好像这个博客条目试图使它在以下意义上是一致的随机的:如果你拿一个圆圈的子圆,中心相同,那么该点落在该区域的概率与该区域。 我相信,我们正试图按照现在的标准解释“均匀随机”的方式来对二维区域进行区域定义 :在任何区域(具有明确定义的区域)下落的点的概率与该区域的面积成正比。

天真的解决scheme不起作用的原因是它给更接近圆心的点的概率密度更高。 换句话说,半径为r / 2的圆的概率是r / 2,但它有面积(点数)pi * r ^ 2/4。

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

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

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

现在是math:

select[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。 因此,你应该给圆圈ra的概率等于(2 * pi * r)/(pi * R ^ 2)= 2 * r / R ^ 2。 这是更容易理解,更直观,但它不像math上的声音。

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

 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() 

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

对于任何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<sup>2</sup>) (0 < r <= R). 

请注意,对于R = 1的随机variablessqrt(X),其中X在[0,1]上是均匀的具有这个确切的CDF(因为P [sqrt(X)<y] = P [x <y ** 2] = y * * 2,0 <y <= 1)。

φ的分布从0到2 *π明显是均匀的。 现在,您可以创build随机极坐标,并使用三angular方程将其转换为笛卡尔坐标:

 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) 

你会得到

半径与“接近”半径的点数之间存在线性关系,所以他需要使用半径分布,这也使得接近半径r的数据点的数量与r成正比。

我曾经使用这种方法:这可能是完全没有优化的(即它使用一个点的数组,因此它不能用于大圆圈),但足够的随机分布。 如果你愿意的话,你可以跳过matrix的创build并直接绘制。 该方法是随机化一个矩形落在圆内的所有点。

 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); } 

在这里输入图像描述

圆中的面元素为dA = rdr * dphi。 这个额外的因素摧毁了你的想法,随机selectAR和PHI。 虽然phi是分布式的,但r不是,而是平坦于1 / r(即比“牛眼”更可能碰到边界)。

所以要生成均匀分布在圆上的点,从平坦分布中selectphi,从1 / r分布中生成r。

或者使用Mehrdad提出的Monte Carlo方法。

编辑

要在1 / r中select一个随机平面,可以从区间[1 / R,无穷远]中select一个随机x并计算r = 1 / x。 r然后以1 / r分布。

计算一个随机phi从区间[0,1]中选取一个随机x并计算phi = 2 * pi * x。

我认为在这种情况下,使用极坐标是一个复杂的问题,如果你select随机点到2R的正方形,然后select点(x,y),使得x ^ 2 + y ^ 2 <= R ^ 2。

Java中的解决scheme和分发示例(2000分)

 public void getRandomPointInCircle() { double t = 2 * Math.PI * Math.random(); double r = Math.sqrt(Math.random()); double x = r * Math.cos(t); double y = r * Math.sin(t); System.out.println(x); System.out.println(y); } 

分布2000点

基于@sigfpe的previus解决schemehttps://stackoverflow.com/a/5838055/5224246

我不知道这个问题是否还有一个新的解决scheme,已经给出了所有的答案,但是我碰巧遇到了同样的问题。 我试图用自己的理由来解决问题,并find一个解决scheme。 这可能是一些已经build议在这里相同的东西,但无论如何这里是:

为了圆的表面的两个元素相等,假设等于dr,我们必须有dthe1 / dthe2 = r2 / r1。 将该元素的概率expression式写为P(r,theta)= P {r1 <r <r1 + dr,theta1 <theta <theta + dtheta1> = f(r,theta)* dr * dtheta1, (r1和r2)相等,我们到达(假定r和theta是独立的)f(r1)/ r1 = f(r2)/ r2 =常数,给出f(r)= c * r。 其余的,根据f(r)是一个PDF的条件来确定常数c。

程序员解决scheme:

  • 创build一个位图(一个布尔值matrix)。 它可以像你想要的一样大。
  • 在该位图中绘制一个圆。
  • 创build一个圈子点的查找表。
  • 在此查找表中select一个随机索引。
 const int RADIUS = 64; const int MATRIX_SIZE = RADIUS * 2; bool matrix[MATRIX_SIZE][MATRIX_SIZE] = {0}; struct Point { int x; int y; }; Point lookupTable[MATRIX_SIZE * MATRIX_SIZE]; void init() { int numberOfOnBits = 0; for (int x = 0 ; x < MATRIX_SIZE ; ++x) { for (int y = 0 ; y < MATRIX_SIZE ; ++y) { if (x * x + y * y < RADIUS * RADIUS) { matrix[x][y] = true; loopUpTable[numberOfOnBits].x = x; loopUpTable[numberOfOnBits].y = y; ++numberOfOnBits; } // if } // for } // for } // () Point choose() { int randomIndex = randomInt(numberOfBits); return loopUpTable[randomIndex]; } // () 

位图仅用于解释逻辑。 这是没有位图的代码:

 const int RADIUS = 64; const int MATRIX_SIZE = RADIUS * 2; struct Point { int x; int y; }; Point lookupTable[MATRIX_SIZE * MATRIX_SIZE]; void init() { int numberOfOnBits = 0; for (int x = 0 ; x < MATRIX_SIZE ; ++x) { for (int y = 0 ; y < MATRIX_SIZE ; ++y) { if (x * x + y * y < RADIUS * RADIUS) { loopUpTable[numberOfOnBits].x = x; loopUpTable[numberOfOnBits].y = y; ++numberOfOnBits; } // if } // for } // for } // () Point choose() { int randomIndex = randomInt(numberOfBits); return loopUpTable[randomIndex]; } // () 

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

检查这种方式…在某个angular度theta和r之间(0.1r至0.2r)的点数,即r之间的分数和r(0.6r到0.7r)之间的点数将是相等的,如果你使用标准的代,因为两个区间之间的差值只有0.1r。 但是由于覆盖点(0.6r到0.7r)之间的区域要比覆盖0.1r到0.2r之间的区域大得多,相同的点数将会在更大的区域内被稀疏地隔开,所以我假设你已经知道了。生成随机点必须不是线性的而是二次的(因为需要以给定单位dr分配的点的数量,即r的增加将与r2成正比,而不是r),所以在这种情况下,它将是二次方,因为在这两个区间内我们有(0.1r)的三angular必须是某个函数的平方,所以它可以作为点的线性生成的种子值(因为后面的这个种子在sin和cos函数中线性地使用),所以我们知道,博士必须是二次的价值,并使这个种子二次,我们需要从r本身的平方根发起这个价值观,我希望这使得它更加清楚。

1)在-1和1之间select一个随机X.

 var X:Number = Math.random() * 2 - 1; 

2)使用圆周公式,计算Y的最大值和最小值,假设X和半径为1:

 var YMin:Number = -Math.sqrt(1 - X * X); var YMax:Number = Math.sqrt(1 - X * X); 

3)在这两个极端之间select一个随机数Y:

 var Y:Number = Math.random() * (YMax - YMin) + YMin; 

4)将您的位置和半径值合并到最终值中:

 var finalX:Number = X * radius + pos.x; var finalY:Number = Y * radois + pos.y;