Создать случайную точку внутри круга (равномерно) - PullRequest
Новая
       84

Создать случайную точку внутри круга (равномерно)

186 голосов
/ 30 апреля 2011

Мне нужно создать равномерно случайную точку в круге радиуса R .

Я понимаю, что, просто выбрав равномерно случайный угол в интервале [0 ... 2π)и равномерно случайный радиус в интервале (0 ... R ) я бы в итоге получил больше точек к центру, поскольку для двух заданных радиусов точки в меньшем радиусе будут ближе друг к другучем для точек в большем радиусе.

Я нашел запись в блоге об этом здесь , но я не понимаю его рассуждения.Я полагаю, это правильно, но Мне бы очень хотелось понять, откуда он берется (2 / R 2 ) × r и как он получаетокончательное решение.

Обновление: 7 лет после публикации этого вопроса я до сих пор не получил удовлетворительного ответа на вопрос о математике за квадратным корнемалгоритм.Так что я потратил день на написание ответа сам. Ссылка на мой ответ .

Ответы [ 21 ]

3 голосов
/ 13 июня 2017

Решение на 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);
}

Distribution 2000 points

на основе предварительного решения https://stackoverflow.com/a/5838055/5224246 от @ sigfpe

2 голосов
/ 13 декабря 2017

Сначала мы генерируем cdf [x], который равен

Вероятность того, что точка меньше расстояния x от центра круга.Предположим, что круг имеет радиус R.

очевидно, если x равен нулю, то cdf [0] = 0

очевидно, если x равен R, то cdf [R] = 1

очевидно, что если x = r, то cdf [r] = (Pi r ^ 2) / (Pi R ^ 2)

Это потому, что каждая «малая область» на круге имеет одинаковую вероятность бытьвыбрал, так что вероятность пропорциональна рассматриваемой области.И область, заданная расстоянием x от центра круга, равна Pi r ^ 2

, поэтому cdf [x] = x ^ 2 / R ^ 2, потому что Pi компенсирует друг друга

у нас есть cdf [x] = x ^ 2 / R ^ 2, где x переходит от 0 до R

Итак, мы решаем для x 

R^2 cdf[x] = x^2

x = R Sqrt[ cdf[x] ]

Теперь мы можем заменить cdf случайным числомот 0 до 1 

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 голос
/ 30 апреля 2011

Я однажды использовал этот метод: он может быть полностью неоптимизирован (т.е. он использует массив точек, поэтому его нельзя использовать для больших кругов), но дает достаточно случайное распределение.Вы можете пропустить создание матрицы и рисовать напрямую, если хотите.Метод состоит в том, чтобы рандомизировать все точки в прямоугольнике, которые попадают в круг. 

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

enter image description here

1 голос
/ 30 апреля 2011

Элементом площади в круге является dA = rdr * dphi.Этот дополнительный фактор r разрушил вашу идею случайного выбора ar и phi.Хотя phi распределено ровно, r - нет, но ровно в 1 / r (т. Е. Вы, скорее всего, попадете на границу, чем «яблочко»).

Таким образом, для создания точек, равномерно распределенных по пикуфи из плоского распределения и r из распределения 1 / r.

В качестве альтернативы используйте метод Монте-Карло, предложенный Мехрдадом.

EDIT

Toвыберите случайную r-квартиру в 1 / r, вы можете выбрать случайный x из интервала [1 / R, бесконечность] и вычислить r = 1 / x.Затем r равномерно распределяется в 1 / r.

. Для вычисления случайного фи выберите случайный х из интервала [0, 1] и вычислите фи = 2 * пи * х.

1 голос
/ 30 апреля 2011

Существует линейная зависимость между радиусом и количеством точек, "близких" к этому радиусу, поэтому он должен использовать распределение радиуса, которое также делает число точек данных рядом с радиусом r пропорциональным r .

0 голосов
/ 14 июля 2018

Вы также можете использовать свою интуицию.

Площадь круга pi*r^2

Для r=1

Это дает нам площадь pi. Предположим, что у нас есть какая-то функция f, которая равномерно распределит N=10 точек внутри круга. Соотношение здесь 10 / pi

Теперь мы удваиваем площадь и количество точек

Для r=2 и N=20

Это дает площадь 4pi, а соотношение теперь равно 20/4pi или 10/2pi. Отношение будет становиться все меньше и меньше, чем больше радиус, потому что его рост является квадратичным, а N масштабируется линейно.

Чтобы это исправить, мы можем просто сказать 

x = r^2
sqrt(x) = r

Если вы сгенерируете вектор в полярных координатах, как это 

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

Больше точек приземлится вокруг центра. 

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

length больше не распределяется равномерно, но вектор теперь будет распределяться равномерно.

0 голосов
/ 15 мая 2013

Я не знаю, открыт ли этот вопрос для нового решения с уже полученным ответом, но я сам столкнулся с точно таким же вопросом.Я попытался «найти» решение для себя, и я нашел его.Это может быть то же самое, что некоторые уже предложили здесь, но в любом случае здесь это так:

для того, чтобы два элемента поверхности круга были равны, предполагая равные dr, мы должны иметь dtheta1 / dtheta2 = r2/ r1.Запись выражения вероятности для этого элемента как P (r, theta) = P {r1

0 голосов
/ 04 июня 2018

Такая забавная проблема.
Обоснование вероятности снижения выбранной точки по мере увеличения расстояния от начала координат объясняется многократно выше. Мы учтем это, взяв корень U [0,1]. Вот общее решение для положительного r в Python 3. 

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

enter image description here

0 голосов
/ 21 января 2014

1) Выберите случайный X между -1 и 1. 

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) Выберите случайный Y между этими крайностями: 

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

4) Включите значения вашего местоположения и радиуса в окончательное значение: 

var finalX:Number = X * radius + pos.x;
var finalY:Number = Y * radois + pos.y;
0 голосов
/ 12 декабря 2014

Программное решение:

  • Создать битовую карту (матрицу логических значений). Он может быть настолько большим, насколько вы хотите.
  • Нарисуйте круг в этой битовой карте.
  • Создать таблицу поиска точек круга.
  • Выберите случайный индекс в этой таблице поиска. 
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];
} // ()
Страница:
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...