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

давайте подойдем к этому так, как это сделал бы Архимед.

как мы можем генерировать точку равномерно в треугольнике ABC, где |AB / =|BC/? Давайте сделаем это проще, перейдя к параллелограмму ABCD. Легко генерировать точки равномерно в ABCD. Мы равномерно выбираем случайную точку X на AB и Y на BC и выбираем Z таким образом, что XBYZ является параллелограммом. Чтобы получить равномерно выбранную точку в исходном треугольнике, мы просто складываем все точки, которые появляются в АЦП, обратно в ABC вдоль ПЕРЕМЕННЫЙ ТОК.

Теперь рассмотрим кругу. В пределе мы можем думать о нем, как бесконечно много isoceles треугольников ABC с Б В начале координат, а A и C на окружности исчезающе близко друг к другу. Мы можем выбрать один из этих треугольников, просто выбрав угол тета. Поэтому теперь нам нужно создать расстояние от центра, выбрав точку в Щепке ABC. Опять же, распространитесь на ABCD, где D теперь в два раза больше радиуса от центра окружности.

выбор случайной точки в ABCD является легко с помощью вышеуказанного метода. Выберите случайную точку на AB. Равномерно выберите случайную точку на BC. То есть. выберите пару случайных чисел x и y равномерно на [0, R], дающих расстояния от центра. Наш треугольник-это тонкая щепка, поэтому 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]

вот быстрое и простое решение.

выбрать два случайных числа в диапазоне (0, 1), а именно a и b. Если b < a, поменять их местами. Ваша точка зрения (b*R*cos(2*pi*a/b), b*R*sin(2*pi*a/b)).

вы можете думать об этом решении следующим образом. Если вы возьмете круг, вырежете его, а затем выпрямите, вы получите прямоугольный треугольник. Масштабируйте этот треугольник вниз, и у вас будет треугольник от (0, 0) до (1, 0) до (1, 1) и (0, 0). Все эти преобразования измените плотность равномерно. То, что вы сделали, - это равномерно выбрали случайную точку в треугольнике и перевернули процесс, чтобы получить точку в круге.

обратите внимание на плотность точек, пропорциональную обратному квадрату радиуса, следовательно, вместо выбора r С [0, r_max] С [0, r_max^2], затем вычислите свои координаты как:

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

это даст вам равномерное распределение точек на диске.

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

подумайте об этом таким образом. Если у вас есть прямоугольник, где одна ось-радиус, а одна-угол, и вы берете точки внутри этого прямоугольника, которые находятся рядом с радиусом 0. Они все находятся очень близко к источнику (то есть близко друг к другу по кругу.) Однако точки вблизи радиуса R, все они будут падать вблизи края круга (то есть далеко друг от друга.)

Это может дать вам некоторое представление о том, почему вы получаете такое поведение.

фактор это выведено на этой ссылке говорит вам, сколько соответствующая область в прямоугольнике должна быть скорректирована, чтобы не зависеть от радиуса, как только он отображается на круг.

Edit: так что он пишет в ссылке, которую вы делите, "это достаточно легко сделать, вычисляя обратное кумулятивное распределение, и мы получаем для r:".

основная предпосылка здесь заключается в том, что вы можете создать переменную с желаемым распределением из равномерного путем отображения равномерного на обратное функция кумулятивной функции распределения искомой функции плотности вероятности. Зачем? Просто примите это как должное, но это факт.

вот мое какое-то интуитивное объяснение математики. Функция плотности f (r) по отношению к r должна быть пропорциональна самой r. Понимание этого факта является частью любой основной книги исчисления. См. разделы по элементам полярной области. Некоторые другие плакаты упоминали об этом.

поэтому мы будем называть его f (r) = C*r;

Это, оказывается, большая часть работы. Теперь, поскольку F(r) должна быть плотностью вероятности, вы можете легко увидеть,что, интегрируя f (r) через интервал (0, R), вы получаете C = 2/R^2 (это упражнение для читателя.)

таким образом, f(r) = 2*r/R^2

ОК, так вот как сделать формулу в ссылке.

тогда конечная часть идет от однородной случайной величины u в (0,1), которую вы должны отобразить обратной функцией кумулятивной функция распределения от этой желаемой плотности f (r). Чтобы понять, почему это так, вам нужно найти расширенный вероятностный текст, такой как Papoulis, вероятно (или получить его самостоятельно.)

интегрируя f(r) вы получаете F (r) = r^2/R^2

чтобы найти обратную функцию этого, вы устанавливаете u = r^2/R^2, а затем решаете для r, что дает вам r = R * sqrt (u)

это полностью имеет смысл интуитивно тоже, u = 0 должно соответствовать r = 0. Кроме того, U = 1 shoudl сопоставляется с r = R. Также, он идет по функции квадратного корня, что имеет смысл и соответствует ссылке.

Это действительно зависит от того, что вы подразумеваете под 'абсолютно случайная'. Это тонкий момент, и вы можете прочитать больше об этом на странице wiki здесь:http://en.wikipedia.org/wiki/Bertrand_paradox_%28probability%29, где одна и та же проблема, давая разные интерпретации "равномерно случайным" дает разные ответы!

в зависимости от того, как вы выбираете точки, распределение может варьироваться, даже если они равномерно случайны в некоторые чувство.

похоже, что запись в блоге пытается сделать ее равномерно случайной в следующем смысле: если вы берете подкруг круга с тем же центром, то вероятность того, что точка попадает в эту область, пропорциональна площади области. Это, я считаю, пытается следовать теперь стандартной интерпретации "равномерно случайного" для 2D-областей с области, определенные на них: вероятность падения точки в любом регионе (с областью хорошо определено) пропорционально площади этого региона.

причина, по которой наивное решение не работает, заключается в том, что оно дает более высокую плотность вероятности точкам ближе к центру круга. Другими словами, окружность, имеющая радиус r/2, имеет вероятность R/2 получить выбранную в ней точку, но она имеет площадь (количество точек) pi*r^2/4.

поэтому мы хотим, чтобы плотность вероятности радиуса имела следующее свойство:

вероятность выбора радиуса меньшего или равного заданному r должна быть пропорциональна площадь окружности с радиусом r. (потому что мы хотим иметь равномерное распределение по точкам и большие площади означают больше точек)

теперь приходит математика:

вероятность выбора радиуса между [0, r] является интегралом p(r) dr от 0 до r (это просто потому, что мы добавляем все вероятности меньших радиусов). Таким образом, мы хотим Интеграл(p(r)dr) = r^2/R^2. Мы ясно видим, что R^2 является константой, поэтому все, что нам нужно сделать, это выяснить, какой p(r) при интегрировании даст нам что-то вроде r^2. Ответ явно Р * постоянный. Интеграл (r * константа dr) = r^2/2 * константа. Это должно быть равно r^2/R^2, поэтому Константа = 2 / R^2. Таким образом, у вас есть распределение вероятности p(r) = r * 2/R^2

Примечание:

вот мой код Python для генерации num случайные точки из окружности радиуса rad:

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

пусть ρ (радиус) и φ (Азимут) - две случайные величины, соответствующие полярным координатам произвольной точки внутри окружности. Если точки распределены равномерно, то какова функция распределения ρ и φ?

для любого r: 0

P[ρ 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 случайная величина sqrt(X), где X является равномерным на [0, 1), имеет этот точный CDF (потому что P[sqrt(X)

распределение φ очевидно равномерно от 0 до 2*π. Теперь вы можете создавать случайные полярные координаты и преобразовывать их в декартовы с помощью тригонометрических уравнений:

x = ρ * cos(φ)
y = ρ * sin(φ)

не могу устоять сообщение кода python для R=1.

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)

вы получите

решение на 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

Я думаю, что в этом случае использование полярных координат является способом усложнения проблемы, было бы намного проще, если бы вы выбрали случайные точки в квадрат со сторонами длины 2R, а затем выбрали точки (x,y) такое, что x^2+y^2<=R^2.

Сначала мы генерируем 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 deg}

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

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

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. В то время как phi распределен плоско, r не является, но плоский в 1/r (т. е. вы с большей вероятностью попадете в границу, чем "глаз быка").

таким образом, чтобы генерировать точки, равномерно распределенные по окружности, выберите phi из плоского распределения и r из распределения 1/R.

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

EDIT

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

для вычисления случайного phi выберите случайный x из интервала [0, 1] и вычислите phi=2 * pi * x.

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

для того, чтобы два элемента поверхности круга были равны, предполагая равные dr, мы должны иметь dtheta1/dtheta2 = r2/r1. Написание выражения вероятность этого элемента как P(R, тета) = Р{ Р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];
} // ()

Я все еще не уверен в точном "(2 / R2)×r", но очевидно, что количество точек, необходимых для распределения в данной единице "dr", т. е. увеличение r будет пропорционально r2, а не r.

проверить таким образом...количество точек под некоторым углом тета и между r (0,1 r до 0,2 r) т. е. доля r и количество точек между r (0,6 r до 0,7 r) будут равны, если вы используете стандартную генерацию, так как разница составляет всего 0,1 r между двумя интервалами. но так как область покрытый между точками (от 0,6 до 0,7 r) будет намного больше, чем площадь, покрытая от 0,1 до 0,2 r, равное количество точек будет разрежено на большей площади, это я предполагаю, что вы уже знаете, поэтому функция для генерации случайных точек должна быть не линейной, а квадратичной (поскольку количество точек, необходимых для распределения в данной единице "dr", т. е. увеличение r будет пропорционально r2, а не r), поэтому в этом случае она будет обратной квадратичной, поскольку Дельта у нас есть (0,1 r) в обоих интервалы должны быть квадратными некоторой функции, чтобы она могла действовать как начальное значение для линейной генерации точек (поскольку послесловия, это семя используется линейно в функции sin и cos), поэтому мы знаем, что dr должен быть квадратичным значением, и чтобы сделать это семя квадратичным, нам нужно получить эти значения из квадратного корня r не самого r, я надеюсь, что это делает его немного более ясным.

такая забавная проблема.
Обоснование вероятности того, что выбранная точка будет понижаться по мере увеличения расстояния от начала оси, объясняется выше в несколько раз. Мы учитываем это, беря корень из 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])

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

площадь окружности 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 больше не равномерно распределяется, но вектор теперь будет равномерно распределенный.

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;