Дан круг с центром в начале координат, и радиуса R. Нужно заполнять его случайными точками, равномерно, но при этом используя полярные координаты. Т.е. нужно случайно выбирать угол f и расстояние от центра r так, чтобы точки заполняли круг равномерно.
1. Как это сделать?
2. Как это сделать, если в наличии имеется только ГСЧ с равномерным распределением (на заданном отрезке) ?
ЗЫ.
Просьба к тем, кто просто знает, как это делается, дать возможность подумать остальным.
Здравствуйте, rus blood, Вы писали:
RB>1. Как это сделать? RB>2. Как это сделать, если в наличии имеется только ГСЧ с равномерным распределением (на заданном отрезке) ?
Можно в лоб
Берём два случайных числа x и y, <=R. Переводим (x, y) в (r, fi). Если я не ошибаюсь, fi = arctg(y/x), r = sqrt(x^2+y^2) Если r>R, число отбрасываем. Если нет — плюём на экран
А вообще, нужно достать учебник по теорверу и посмотреть, как работать со случайными векторами...
Это не наезды, это вопросы. И вообще, над ламерами смеяться грешно.
A>Можно в лоб A>Берём два случайных числа x и y, <=R. Переводим (x, y) в (r, fi). Если я не ошибаюсь, fi = arctg(y/x), r = sqrt(x^2+y^2) Если r>R, число отбрасываем. Если нет — плюём на экран
Нет, нужно случайно брать угол и расстояние от центра. Скажем так, способ с квадратом плох тем, что его КПД равно pi/4. Если использовать полярные координаты, то КПД будет 1.
A>>Можно в лоб A>>Берём два случайных числа x и y, <=R. Переводим (x, y) в (r, fi). Если я не ошибаюсь, fi = arctg(y/x), r = sqrt(x^2+y^2) Если r>R, число отбрасываем. Если нет — плюём на экран
RB>Нет, нужно случайно брать угол и расстояние от центра. Скажем так, способ с квадратом плох тем, что его КПД равно pi/4. Если использовать полярные координаты, то КПД будет 1.
Это неправильно, т.к. в этом случае распределение не будет равномерным.
Наиболее лучшим здесь будет вот что:
Берем случайно x из отрезка [-R, R], а y из отрезка [-sqrt(R^2 — x^2), sqrt(R^2 — x^2)].
А далее, как уже было сказано, переходим в полярные координаты.
N>Берем случайно x из отрезка [-R, R], а y из отрезка [-sqrt(R^2 — x^2), sqrt(R^2 — x^2)]. N>А далее, как уже было сказано, переходим в полярные координаты.
Вот это точно неправильно...
Имею скафандр — готов путешествовать!
Re: Задача экспромт
От:
Аноним
Дата:
21.06.04 08:21
Оценка:
Здравствуйте, rus blood, Вы писали:
RB>Задачка навеянная парадом самолетов
.
RB>Дан круг с центром в начале координат, и радиуса R. Нужно заполнять его случайными точками, равномерно, но при этом используя полярные координаты. Т.е. нужно случайно выбирать угол f и расстояние от центра r так, чтобы точки заполняли круг равномерно.
RB>1. Как это сделать? RB>2. Как это сделать, если в наличии имеется только ГСЧ с равномерным распределением (на заданном отрезке) ?
RB>ЗЫ. RB>Просьба к тем, кто просто знает, как это делается, дать возможность подумать остальным.
Что-то я не понял в чем проблема...
Я бы делал так :
0) Так как круг в полярных коорд есть квадрат, то задача сводится к выбору случайной точки на квадрате [0, R]x[0, 2*Pi]
А>0) Так как круг в полярных коорд есть квадрат, то задача сводится к выбору случайной точки на квадрате [0, R]x[0, 2*Pi]
А>Тогда :
А>1) Берем
А>х1 ~ U[0, R] А>x2 ~ U[0, 2*Pi]
А>2) x = (x1, x2) — искомая случ. величина.
Это неверно... Двойка...
А>Можно делать методом исключения(Неймана) :
А>строим случ величину по правилу : А>1) А>y1 ~ U[-R, R] А>y2 ~ U[-R, R]
А>2) если точка y = (y1, y2) удалена от точки (0, 0) более чем на R, то переходим к 1) иначе 3)
А>3) полагаем x = y, x — искомая случ величина..
А>>0) Так как круг в полярных коорд есть квадрат, то задача сводится к выбору случайной точки на квадрате [0, R]x[0, 2*Pi]
А>>Тогда :
А>>1) Берем
А>>х1 ~ U[0, R] А>>x2 ~ U[0, 2*Pi]
А>>2) x = (x1, x2) — искомая случ. величина.
RB>Это неверно... Двойка...
А>>>0) Так как круг в полярных коорд есть квадрат, то задача сводится к выбору случайной точки на квадрате [0, R]x[0, 2*Pi]
А>>>Тогда :
А>>>1) Берем
А>>>х1 ~ U[0, R] А>>>x2 ~ U[0, 2*Pi]
А>>>2) x = (x1, x2) — искомая случ. величина.
RB>>Это неверно... Двойка...
А>С чего это ?
А>P(dS) = dF*dR = dS
Наверное непонятно...
Ну вот смотри...
если
Fх — функция распределения величины x,
P — вероятность
то
Fx( dS ) = P( x из dS ) = P( x1 из dS1, x2 из dS2 ) = P(x1 из dS1)*P(x2 из dS2) = dS1*dS2 = dS
то есть распредление равномерно.
А>Наверное непонятно...
А>Ну вот смотри... А>если А>Fх — функция распределения величины x, А>P — вероятность А>то А>Fx( dS ) = P( x из dS ) = P( x1 из dS1, x2 из dS2 ) = P(x1 из dS1)*P(x2 из dS2) = dS1*dS2 = dS А>то есть распредление равномерно.
А>Где неправ ?
Неправ во время замены координат (с полярной на прямоугольную).
Площадь сегмента уже не равна произведению ds1*ds2...
Имею скафандр — готов путешествовать!
Re[6]: Задача экспромт
От:
Аноним
Дата:
21.06.04 09:29
Оценка:
А>>Ну вот смотри... А>>если А>>Fх — функция распределения величины x, А>>P — вероятность А>>то А>>Fx( dS ) = P( x из dS ) = P( x1 из dS1, x2 из dS2 ) = P(x1 из dS1)*P(x2 из dS2) = dS1*dS2 = dS А>>то есть распредление равномерно.
А>>Где неправ ?
RB>Неправ во время замены координат (с полярной на прямоугольную). RB>Площадь сегмента уже не равна произведению ds1*ds2...
Бр-р-р-р... Я нигде никаких коорд не заменял.
Ну да ладно...
Что значит, что случ величина x распределна равномерно в круге ?
Значит что P( x из dS ) = dS, где dS — элемент круга. так ?
Что такое dS ?
dS = dR*dFi, где dR — есть радиус, dFi — есть угол. Почему так ?
Так как площадь сегмента круга есть радиус*длина_дуги, отсюда площадь элемента круга = изменение_радиуса*длина_дуги и равно с учетом малости угла = dR*dFi. Так ? (чувствую что твоя загвоздка здесь)
Тогда строим случ величину x(см. выше) и получаем, что она равномерно распределена в круге. Естественно необходимо заменить dS1 на dR и dS2 на dFi...
Нигде ни откаких коорд ни к какими я не переходил...
А>Так как площадь сегмента круга есть радиус*длина_дуги, отсюда площадь элемента круга = изменение_радиуса*длина_дуги и равно с учетом малости угла = dR*dFi. Так ? (чувствую что твоя загвоздка здесь)
Угу, примерно здесь ты и не прав.
Посчитай, например, площадь круга по твоей формуле dS = dR*dFi ...
Здравствуйте, Аноним, Вы писали:
А>Что такое dS ?
А>dS = dR*dFi, где dR — есть радиус, dFi — есть угол. Почему так ? А>Так как площадь сегмента круга есть радиус*длина_дуги, отсюда площадь элемента круга = изменение_радиуса*длина_дуги и равно с учетом малости угла = dR*dFi. Так ? (чувствую что твоя загвоздка здесь)
нууу... либо ты описАлся дваждвы, либо здесь твоя загвоздка
хоть по размерности не чувствуешь что формула для площади не верна?
vox clamantis in deserto
Re[6]: Задача экспромт
От:
Аноним
Дата:
21.06.04 09:45
Оценка:
RB>Неправ во время замены координат (с полярной на прямоугольную). RB>Площадь сегмента уже не равна произведению ds1*ds2...
Кстати еще вот вспомнил... Если что напутал сильно не бить
1)
Чтобы получить случайное напрвление в пространстве необходимо брать вектор с нормальными компонентами. Тогда в нашем случае компонент всего две и следовательно необходимо получить пару нормально распределнных сл. величин, имея лишь равномерно рапсредленные.
2) а это делается используя формулы какого-то двольно известного мужика.. что-то типа
эх... не помню...
что-то типа так :
a1 = 2*r1 — 1
a2 = 2*Pi*r2
x1 = cos(a2)*sqrt( 1 — a1*a1 )
x2 = sin(a2)*sqrt( 1 — a1*a1 )
ага точно так... то есть x1 и x2 есть пара нормально распределнных случ величин, где r1 r2 — равномерно распределнные с.в.
Ну вот типа тогда за искомую величину можно положить x = ( x1, x2 )
Опять не прав ?
Re[8]: Задача экспромт
От:
Аноним
Дата:
21.06.04 10:12
Оценка:
А>>Что такое dS ?
А>>dS = dR*dFi, где dR — есть радиус, dFi — есть угол. Почему так ? А>>Так как площадь сегмента круга есть радиус*длина_дуги, отсюда площадь элемента круга = изменение_радиуса*длина_дуги и равно с учетом малости угла = dR*dFi. Так ? (чувствую что твоя загвоздка здесь) H>нууу... либо ты описАлся дваждвы, либо здесь твоя загвоздка H>хоть по размерности не чувствуешь что формула для площади не верна?
цыц (надо было где-то положить что r=1, эх... ) уели...
но не сильно, так как я работал в полярных коорд и никуда не переходил... моя точка x=(x1, x2) — это точка в поляр коорд. и давайте вспомним задачу : "Т.е. нужно случайно выбирать угол f и расстояние от центра r так, чтобы точки заполняли круг равномерно"
Тогда :
Если брать
f ~ U[0, 2*Pi]
r ~ U[-R, R]
и ставить точку с полярными коорд (r, f), то она будет распределена равномерно в круге.
Это кстати согласуется с теми формулами которые я привел здесь
Здравствуйте, <Аноним>, Вы писали:
А>Что такое dS ? А>dS = dR*dFi, где dR — есть радиус, dFi — есть угол. Почему так ? А>Так как площадь сегмента круга есть радиус*длина_дуги, отсюда площадь элемента круга = изменение_радиуса*длина_дуги и равно с учетом малости угла = dR*dFi. Так ? (чувствую что твоя загвоздка здесь)
dS = r dr dFi. И r здесь НЕ равно R. r меняется от 0 до R. Чем ближе к центру, тем этот элемент имеет меньшую площадь.
Здравствуйте, Аноним, Вы писали:
А>Если брать А>f ~ U[0, 2*Pi] А>r ~ U[0, R]
А>и ставить точку с полярными коорд (r, f), то она будет распределена равномерно в круге.
Давайте посмотрим. В круг с центром в начале координат и радиусом r = R / 100 мы попадём с вероятностью 1/100 (достаточно того, что r < R/100, f — любое). Теперь рассмотрим такой же маленький круг, но возле границы исходного. Посчитать вероятность попадания точки в этот круг не могу, но явно видно, что она меньше 1/100. Т.к. для этого должно выполниться 2 условия:
R * 98 / 100 < r < R (вероятность 2/100)
f_1 < f < f_2, где f_2 — f_1 меньше какого-то числа, которое явно меньше чем Pi/2, т.е. вероятность этого меньше 1/4.
P(попадания в круг у границы) < 2/100 * 1/4 < 1/100 = P(попадания в круг того же радиуса, но в центре), т.е. распределение не будет равномерным.
.
RB>Дан круг с центром в начале координат, и радиуса R. Нужно заполнять его случайными точками, равномерно, но при этом используя полярные координаты. Т.е. нужно случайно выбирать угол f и расстояние от центра r так, чтобы точки заполняли круг равномерно.
RB>1. Как это сделать? RB>2. Как это сделать, если в наличии имеется только ГСЧ с равномерным распределением (на заданном отрезке) ?
Я конечно извиняюсь, но почему просто не выбрать случайные координаты и если они попадают в круг, то посчитать угол и расстояние от центра. Получим функцию генерации f & r что удовлетворяет условию.
