我需要在半径为R的圆内生成一个均匀随机点。
我意识到,只要在区间[0…2π),且在区间(0…R)我最终会有更多的点指向中心,因为对于两个给定的半径,小半径内的点会比大半径内的点彼此更接近。
我在这里找到了一篇关于这个的博客文章,但我不明白他的推理。我认为这是正确的,但我真的很想知道他从哪里得到(2/R2)×r以及他如何得到最终解。
更新:在发布这个问题7年之后,关于平方根算法背后的数学问题,我仍然没有得到一个令人满意的答案。所以我花了一天时间自己写了一个答案。链接到我的答案。
我需要在半径为R的圆内生成一个均匀随机点。
我意识到,只要在区间[0…2π),且在区间(0…R)我最终会有更多的点指向中心,因为对于两个给定的半径,小半径内的点会比大半径内的点彼此更接近。
我在这里找到了一篇关于这个的博客文章,但我不明白他的推理。我认为这是正确的,但我真的很想知道他从哪里得到(2/R2)×r以及他如何得到最终解。
更新:在发布这个问题7年之后,关于平方根算法背后的数学问题,我仍然没有得到一个令人满意的答案。所以我花了一天时间自己写了一个答案。链接到我的答案。
当前回答
这样一个有趣的问题。 一个点被选择的概率随着距离轴原点的增加而降低的基本原理在上面已经解释了多次。我们通过取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])
其他回答
程序员解决方案:
创建一个位图(布尔值的矩阵)。你想要多大就有多大。 在位图中画一个圆。 创建一个圆的点查找表。 在这个查找表中选择一个随机索引。
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];
} // ()
我曾经用过这个方法: 这可能是完全未优化的(即它使用了一个点数组,所以它不能用于大圆圈),但它提供了足够的随机分布。如果你愿意,你可以跳过矩阵的创建,直接绘制。方法是随机化矩形中落在圆内的所有点。
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。这个额外的因子r破坏了你随机选择r和的想法。虽然phi分布平坦,但r不是,而是在1/r内平坦(也就是说,你更有可能击中边界而不是“靶心”)。
为了生成在圆上均匀分布的点从平面分布中选取r从1/r分布中选取。
或者使用Mehrdad提出的蒙特卡罗方法。
EDIT
要在1/r中选择一个随机的r,你可以从区间[1/ r,无穷]中选择一个随机的x,并计算r=1/x。R以1/ R为单位平坦分布。
为了计算一个随机的,从区间[0,1]中选择一个随机的x,并计算=2*pi*x。
首先我们生成一个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°}
1)在-1和1之间随机选择一个X。
var X:Number = Math.random() * 2 - 1;
2)利用圆公式,在X和半径为1的情况下,计算Y的最大值和最小值:
var YMin:Number = -Math.sqrt(1 - X * X);
var YMax:Number = Math.sqrt(1 - X * X);
3)在这两个极端之间随机选择一个Y:
var Y:Number = Math.random() * (YMax - YMin) + YMin;
4)将您的位置和半径值合并到最终值中:
var finalX:Number = X * radius + pos.x;
var finalY:Number = Y * radois + pos.y;