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

Question

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

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

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

---

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

Answer 1

Давайте подойдем к этому так, как Архимед.

Как мы можем сгенерировать точку равномерно в треугольнике ABC, где | AB | = | BC |? Давайте сделаем это проще, расширив параллелограмм ABCD. В ABCD легко генерировать точки равномерно. Мы равномерно выбираем случайную точку X на AB и Y на BC и выбираем Z таким, что XBYZ является параллелограммом. Чтобы получить равномерно выбранную точку в исходном треугольнике, мы просто складываем любые точки, которые появляются в АЦП, обратно в ABC вдоль AC.

Теперь рассмотрим круг. В пределе мы можем думать о нем как о бесконечном числе равнобедренных треугольников ABC с B в начале координат и 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]

Answer 2

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

r = R * sqrt(random())
theta = random() * 2 * PI

(Предположим, random() дает значение от 0 до 1 равномерно)

Если вы хотите преобразовать это в декартовы координаты, вы можете сделать

x = centerX + r * cos(theta)
y = centerY + r * sin(theta)

Почему sqrt(random())?

Давайте посмотрим на математику, которая приводит к sqrt(random()). Предположим для простоты, что мы работаем с единичным кругом, т.е. R = 1.

Среднее расстояние между точками должно быть одинаковым независимо от того, как далеко от центра мы смотрим. Это означает, например, что, глядя на периметр окружности с окружностью 2, мы должны найти вдвое больше точек, чем количество точек на периметре окружности с окружностью 1.

Since the circumference of a circle (2πr) grows linearly with r, it follows that the number of random points should grow linearly with r. In other words, the desired функция плотности вероятности (PDF) растет линейно. Так как PDF должен иметь площадь, равную 1, а максимальный радиус равен 1, мы имеем

So we know how the desired density of our random values should look like. Now: How do we generate such a random value when all we have is a uniform random value between 0 and 1?

We use a trick called выборка с обратным преобразованием

1. Из PDF создайте совокупную функцию распределения (CDF)
2. Отразите это вдоль y = x
3. Примените полученную функцию к одинаковому значению от 0 до 1.

Звучит сложно? Позвольте мне вставить желтую коробку с небольшим отступлением, которое передает интуицию:

Предположим, мы хотим сгенерировать случайную точку со следующим распределением:

То есть

• 1/5 из точек равномерно между 1 и 2, и
• 4/5 баллов равномерно между 2 и 3.

CDF - это, как следует из названия, кумулятивная версия PDF. Интуитивно понятно: в то время как PDF ( x ) описывает количество случайных значений при x , CDF ( x ) описывает количество случайных значений меньше x .

В этом случае CDF будет выглядеть так:

Чтобы увидеть, как это полезно, представьте, что мы стреляем пулями слева направо на равномерно распределенных высотах. Когда пули попадают в линию, они падают на землю:

Посмотрите, как плотность пуль на земле соответствует нашему желаемому распределению! Мы почти у цели!

Проблема в том, что для этой функции ось y представляет собой output , а ось x представляет собой input . Мы можем только «стрелять пулями прямо с земли»! Нам нужна обратная функция!

Вот почему мы отражаем все это; x становится y и y становится x :

Мы называем это CDF ^-1 . Чтобы получить значения в соответствии с желаемым распределением, мы используем CDF ^-1 (random ()).

& hellip; итак, вернемся к генерации случайных значений радиуса, где наш PDF равен 2 x .

Шаг 1. Создайте CDF:

Поскольку мы работаем с реалами, CDF выражается как интеграл PDF.

CDF ( x ) = 2 x = x ²

Шаг 2: Зеркально отразить CDF вдоль y = x :

Математически это сводится к обмену x и y и решению для y :

CDF : y = x ²
Обмен: x = y ²
Решить: y = & radic; x
CDF ^-1 : y = & radic; x

Шаг 3: применить результирующую функцию к равномерному значению от 0 до 1

CDF ^-1 (random ()) = √random ()

Вот что мы намереваемся получить: -)

Answer 3

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

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

Answer 4

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

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

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

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

Answer 5

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

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

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

Редактировать: То, что он пишет в ссылке, которой вы делитесь, таково: «Это достаточно легко сделать, рассчитав обратное кумулятивному распределению, и мы получим для 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). Чтобы понять, почему это так, вам нужно найти расширенный вероятностный текст, такой как, вероятно, папулис (или получить его самостоятельно).

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

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

Это также имеет смысл интуитивно, u = 0 должно отображаться на r = 0. Кроме того, u = 1 должно отображаться на r = R. Кроме того, оно идет по функции квадратного корня, которая имеет смысл и соответствует ссылке.

Answer 6

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

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

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

Другими словами, мы хотим, чтобы вероятность выбора радиуса между [0, r] была равна его долеобщая площадь круга.Общая площадь круга равна pi * R ^ 2, а площадь круга с радиусом r равна pi * r ^ 2.Таким образом, мы хотели бы, чтобы вероятность выбора радиуса между [0, r] была (pi * r ^ 2) / (pi * R ^ 2) = r ^ 2 / R ^ 2.

Теперь наступаетматематика:

Вероятность выбора радиуса между [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

Примечание: Еще один более интуитивный способ решения проблемы - представить, что вы пытаетесь датькаждая окружность радиуса ra имеет плотность вероятности, равную доле числа точек, которые она имеет на своей окружности.Таким образом, окружность с радиусом r будет иметь 2 * pi * r "точки" на своей окружности.Общее количество баллов: pi * R ^ 2.Таким образом, вы должны дать окружности ra вероятность, равную (2 * pi * r) / (pi * R ^ 2) = 2 * r / R ^ 2.Это намного проще для понимания и более интуитивно понятно, но не совсем математически правильно.

Answer 7

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

Для любого 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)

Вы получите

Answer 8

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

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

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

Answer 9

Вот мой код 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()

Answer 10

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