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

我意识到,只要在区间[0…2π),且在区间(0…R)我最终会有更多的点指向中心,因为对于两个给定的半径,小半径内的点会比大半径内的点彼此更接近。

我在这里找到了一篇关于这个的博客文章,但我不明白他的推理。我认为这是正确的,但我真的很想知道他从哪里得到(2/R2)×r以及他如何得到最终解。


更新:在发布这个问题7年之后,关于平方根算法背后的数学问题,我仍然没有得到一个令人满意的答案。所以我花了一天时间自己写了一个答案。链接到我的答案。


当前回答

Java解决方案和分发示例(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);
}

基于以前的解决方案https://stackoverflow.com/a/5838055/5224246从@sigfpe

其他回答

半径和“靠近”该半径的点的数量之间存在线性关系,因此他需要使用半径分布,这也使得半径r附近的数据点的数量与r成正比。

我认为在这种情况下,使用极坐标是一种使问题复杂化的方法,如果你在一个边长为2R的正方形中随机选择点,然后选择点(x,y)使x^2+y^2<=R^2,这将会容易得多。

你也可以用你的直觉。

圆的面积是*r^2

为r = 1

得到的面积是。让我们假设我们有某种函数f,它将N=10个点均匀分布在一个圆内。这个比值是10 /

现在我们把面积和点数翻倍

对于r=2和N=20

面积是4,比值是20/4或10/2。半径越大,比值就越小,因为它的增长是二次的,N是线性的。

为了解决这个问题,我们可以说

x = r^2
sqrt(x) = r

如果在极坐标下生成一个向量

length = random_0_1();
angle = random_0_2pi();

更多的点会落在中心周围。

length = sqrt(random_0_1());
angle = random_0_2pi();

长度不再是均匀分布的,但是向量现在是均匀分布的。

程序员解决方案:

创建一个位图(布尔值的矩阵)。你想要多大就有多大。 在位图中画一个圆。 创建一个圆的点查找表。 在这个查找表中选择一个随机索引。

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];
} // ()

这里有一个快速而简单的解决方案。

在(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)的三角形,所有这些变换都会均匀地改变密度。你所做的就是在三角形中随机取一个点然后反过来得到圆中的一个点。