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

Question

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

Предположим, это простая проблема.

Однако на домашней странице RANDOM_DATA я обнаружил следующее примечание:

Однако мы не добьемся равномерного распределения в простом случае. прямоугольника с неравными сторонами [0, A] x [0, B], если мы наивно масштабируем случайные значения (u1, u2) до (A * u1, B * u2). В этом случае ожидаемый плотность точек широкой короткой области будет отличаться от плотности узкий высокий регион. Отсутствие однородности наиболее очевидно, если точки построены.

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

Что мне не хватает?

Edit:

Спасибо, Патрик87 и отсутствует. Я искал теоретическую причину для утверждения. Теперь я понимаю, что причина не теоретическая, а практическая - гранулярность значений с плавающей точкой .

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

Предположим, что между 0 и 1 существует X различных значений. При масштабировании (u1, u2) до (u1,2 * u2) мы получим X различных значений в диапазоне [0, u1] и X различных значений в диапазон [0,2 * у2]. Для однородности области у нас должно быть в два раза больше разных значений в [0,2 * u2], чем в [0, u1].

Учитывая это, позвольте мне изменить мой вопрос:

Как создать случайную точку в прямоугольнике (с равномерным распределением по области)?

Answer 1

Это утверждение неверно, прямое произведение двух независимых единообразных мер является единой мерой.Это может быть показано следующим образом:

Вероятность попадания случайной точки в прямоугольник со сторонами a и b равна вероятности попадания первой координаты в сегмент длиной aи вторая координата, чтобы поразить сегмент с длиной b.(Речь идет о проекциях прямоугольника на оси).

Первая вероятность - a / A, вторая - b / B.Поскольку эти переменные независимы, вероятности умножаются, поэтому результирующая вероятность равна ab / AB, поэтому мы имеем равномерное двумерное распределение, поскольку вероятность пропорциональна площади прямоугольника.Эта формула симметрична относительно a и b, поэтому наблюдение в кавычках неверно в отношении узких и широких прямоугольников.

Answer 2

Как создать случайную точку в прямоугольнике (с равномерным распределением по области)?

Это должно работать:

  // given A, B, dimensions of rectangle
  // given g, granularity of shorter side

  if A > B then
     bm := g
     am := floor(g * A / B)
  else then
     am := g
     bm := floor(g * B / A)

  for i := 1 to n do
     av := A * RandomInt(0..am) / am
     bv := B * RandomInt(0..bm) / bm
     print (av, bb)

РЕДАКТИРОВАТЬ: более простой альтернативой было бы просто масштабировать случайные значения с плавающей запятой на один и тот же коэффициент, выбирать точки случайным образом и отбрасывать точки, которые выходят за пределы вашего прямоугольника. Однако вы не знаете, сколько испытаний вам понадобится, прежде чем вы получите N точек в прямоугольнике ...

Answer 3

Ascii art:

Возьмите прямоугольник 3х3:

***
***
***

И распределить одну из сторон в 3 раза:

*..*..*..*
*..*..*..*
*..*..*..*

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

Answer 4

Самый простой способ справиться с этим - через отбраковку:

http://en.wikipedia.org/wiki/Rejection_sampling

// Given dimensions of the rectangle A, B where A <= B
boolean flag = true
while (flag) do:
  double a = NextRandomDouble(0,B)
  double b = NextRandomDouble(0,B)
  if (a <= A)
    return(a, b)
  else
    next

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