| ** westpine |
 Отправлено: 31.07.2004, 01:12 |
|
Не зарегистрирован
|
Всем доброго времени суток... вопрос такой. Нужен эффективный алгоритм нахождения случайной точки на поверхности сферы. Именно на поверхности а не внутри. Всем заранее спасиба |
|
| timson |
| Отправлено: 31.07.2004, 09:37 |
|
Станционный диспетчер
Группа: Участник
Сообщений: 82
|
| QUOTE | | Нужен эффективный алгоритм нахождения случайной точки на поверхности сферы |
вопрос не вполне ясен, постав коректнее..
надо чтоли просто найти точку на поверхности сферы случайным образом?? да??
а для эффективного алгоритма не достаточно дано условий.. надо под конкретные условия настраивать алгоритм:
- по каким плоскостям случайно (xy, xz, yz) — тогда в уравнении случайные параметры x, y, z;
- по какой плоскости первой, или тоже случайно — далее все выражается через уравнение сферы;
- и т.д. (даже какой алгоритм генератора случайных чисел использовать)..
надо бы уточнить...
|
|
| Георгий |
| Отправлено: 31.07.2004, 11:42 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
сфера это нечто x^2 + y^2 + z^2 = R^2 ?
тогда точку на её поверхности можно определить по углам 2х направляющих:
a [0,2PI)
b [0,2PI)
в этом случае равновероятны будут все точки сферы
в сечении плоскостью || оси z будет такое уравнение
х^2 + y^2 = R^2
пусть 'a' это случайное число равномерно распреденное в диапазоне [0, 2PI)
тогда (x,y) будут такими
x` = R*sin( a );
y` = R*cos( a );
теперь проводим прямую, проходящей через точки (0,0) && (x`,y`)
вычисляем координату проекции будущей случайной точки на эту прямую
пусть 'b' это случайное число равномерно распреденное в диапазоне [0, 2PI)
тогда координата этой бедной случайной точки на найденной прямой будет иметь координату
d = R * cos( b );
находим (x,y) на плоскости || оси z
x = d * cos( a );
y = d * sin( a );
и теперь из уравнения сферы получаем и заветный z:
z = sqrt( R^2 — d^2 );
итого:
x,y — случайны и зависят от угла 'a'
z — случаен и зависит от угла 'b'
несмотря на неестественный вид уравнений (какие то они угловатые) ни одна из точек поверхности сферы не обделена вниманием — все они будут выбраны с одинаковой вероятностью
а вот и код, реализующий этот алгоритм
| CODE | const int shift = 10000;
const double R = 666.666;
const double a = double(random( 2*M_PI * shift )) / double( shift );
const double b = double(random( 2*M_PI * shift )) / double( shift );
const double d = R * cos( b );
const double x = d * cos( a );
const double y = d * sin( a );
const double z = sqrt( R*R — d*d ); |
PS. правда вспоминается Кнут и то, что произведение 2х псевдослучайных величин не совсем случайная величина, поэтому с осторожностью пользуйтесь этим кодом. |
|
| exp |
| Отправлено: 31.07.2004, 23:11 |
|
Мастер участка
Группа: Участник
Сообщений: 304
|
Упрощение, хотя и небольшое.
Формулы преобразования координат из сферических в декартовы помните?
| CODE |
x= R*cos(gamma)*cos(A)
y= R*cos(gamma)*sin(A)
z= R*sin(gamma)
|
Если теперь Подкорректировать Георгия, то будет так
| CODE |
const int shift = 10000;
const double R = 666.666;
const double A = 2*M_PI * double(random(shift )) / double( shift );
const double gamma = 2*M_PI * double(random(shift )) / double( shift );
const double x = R * cos(gamma ) * cos( A );
const double y = R * cos(gamma ) * sin( A );
const double z = R * sin(gamma );
|
Кстати, таким образом мы избегаем перемножения псевдослучайных величин. (У Кнута там ничего не написанно про перемножение тригонометрических функций этих величин, надеюсь?)
Paint — и пусть весь мир подождет....
Отредактировано exp — 01/08/2004, 00:14
Присоединить изображение
|
|
| Георгий |
| Отправлено: 01.08.2004, 10:18 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
| QUOTE | | Кстати, таким образом мы избегаем перемножения псевдослучайных величин. (У Кнута там ничего не написанно про перемножение тригонометрических функций этих величин, надеюсь?) |
всё равно плохо. Что сами величины, что функции от них. некоторые разряды, в худшем случае, могут вообще не изменяться или изменеяться, но по некоторому закону.
дискретность значение целочисленного генератора ПСП удалось замаскировать масштабным коэффициентом shift — если угол требуется с точностью до градуса, то 10 000 хватает, а вот от перемножения уйти, при подобном методе решения, похоже не удастся.
Нужна идея! 
Кстати — спасибо за избавление от угловатости и хороший рисунок.
PS. приступаем к элипсоиду?
|
|
| exp |
| Отправлено: 02.08.2004, 00:50 |
|
Мастер участка
Группа: Участник
Сообщений: 304
|
Давайте и с эллипсоидом разберемся.
Только поздно уже. Денек посмотрю. Вечером напишу.
|
|
| exp |
| Отправлено: 03.08.2004, 01:11 |
|
Мастер участка
Группа: Участник
Сообщений: 304
|
Тааак. Чем эллипс оличается от сферы? Тем, что у него радиус изменяется.
Значит формулы для пересчета координат примут вид:
| CODE |
x= R(A,gamma) * cos(gamma)*cos(A)
y= R(A,gamma) * cos(gamma)*sin(A)
z= R(A,gamma) * sin(gamma)
|
!!!! Существенное замечание !!!!
Угол gamma условимся брать в плоскости zOy, т. к. для разных точек эллипса, лежащих в сечении этого эллипса плоскостью, параллельной xOy, этот угол будет разным.
Здесь R — уже не постоянная величина а функция двух углов A и gamma.
Найдя вид этой функции, сможем решить задачу.
Итак, после 1.5 часов гемора и проверок была получена эта формула.
Где a,b,c — полуоси эллипсоида.
Тперь надо добавить в код еще строчку для вычисления R по этой ф-ле. и усе.
Maple 4ever!!!!
Отредактировано exp — 03/08/2004, 02:16
Присоединить изображение
|
|
| Георгий |
| Отправлено: 03.08.2004, 07:08 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
спешу тебя обрадовать — точка перестала быть равномерно распределённой по поверхности
вероятность выше на полюсах |
|
| exp |
| Отправлено: 06.08.2004, 11:56 |
|
Мастер участка
Группа: Участник
Сообщений: 304
|
Тоже спешу обрадовать. Я нашел ошибку в формуле. Поэтому пришлось поменять систему координат. Теперь она вот такая. Я поменял угол gamma. Теперь это угол между осью Oz и радиус-вектором.
Отредактировано exp — 06/08/2004, 13:06
Присоединить изображение
|
|
| exp |
| Отправлено: 06.08.2004, 12:05 |
|
Мастер участка
Группа: Участник
Сообщений: 304
|
Формула для длины радиус вектора такая:
Присоединить изображение
|
|
| exp |
| Отправлено: 06.08.2004, 12:07 |
|
Мастер участка
Группа: Участник
Сообщений: 304
|
Формулы преобразования тоже изменятся:
| CODE |
x= R(A,gamma) * sin(gamma)*cos(A)
y= R(A,gamma) * sin(gamma)*sin(A)
z= R(A,gamma) * cos(gamma)
|
Теперь все. Георгий, по идее точки теперь должны быть равномерно распределены.
|
|
| Георгий |
| Отправлено: 06.08.2004, 19:17 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
меня вот что смущает:
при не равных углах альфа и бета соответствующие дуги равны. и при выборе угла по равномерно распределённому закону получится, что вероятность точек на этих 2х дугах не равна.
ЗЫ. эти рассуждения основаны только на эмпирических выводах — если ошибаюсь, то буду рад если поправите.
|
|
| exp |
| Отправлено: 28.08.2004, 23:47 |
|
Мастер участка
Группа: Участник
Сообщений: 304
|
Здравствуйте. После перерыва я снова в строю.
Георгий, картинки нет. Не могли бы вы еще раз ее прикрепить. А то мысль не вполне ясна.
ЗЫ: что-то наш заказчик не объявляется...
Отредактировано exp — 29/08/2004, 00:52
|
|
| Георгий |
| Отправлено: 29.08.2004, 01:55 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
да он уже давно в ауте  емуто всего то надо было, а тут такое развернулось
а вот так видно?
Отредактировано Георгий — 29/08/2004, 03:01 |
|
| Георгий |
| Отправлено: 29.08.2004, 02:01 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
а так?
Присоединить изображение
|
|
| klen |
| Отправлено: 29.08.2004, 10:21 |
|
Машинист паровоза
Группа: Участник
Сообщений: 239
|
Здорово мужики,ж попробую решить проблему с псевдослучайными числами, и вставлю свой пяточек.
1. Встроеный конгруентный генератор — на свалку истории.
2. Будем пользоватся генератром Фиббоначи, выдающим действительные числа double на интервале [0,1), он характеризуется лагами 97 и 33, дает период последовательной корреляции 10^19 шагов (встроенный иеет 4.9*10^9, почувствуте разницу)
| CODE |
double fibonachi_rand_values[97];
UINT fibonachi_rand_value_cur_pointer = 0;
// инициализация генератора Фибоначчи
void __fastcall initfrnd ()
{
srand( GetTickCount() );
// генерация начальных значений массива
for ( int element = 0; element < 97; element ++ )
{
fibonachi_rand_values[element] = (double)rand()/ RAND_MAX;
}
}
double __fastcall frnd()
{
fibonachi_rand_value_cur_pointer = (fibonachi_rand_value_cur_pointer + 1 )% 97;
fibonachi_rand_values[ fibonachi_rand_value_cur_pointer ] =
fibonachi_rand_values[ (fibonachi_rand_value_cur_pointer — 97) % 97 ] -
fibonachi_rand_values[ (fibonachi_rand_value_cur_pointer — 33) % 97 ];
if ( fibonachi_rand_values[ fibonachi_rand_value_cur_pointer ] < 0 )
fibonachi_rand_values[ fibonachi_rand_value_cur_pointer ] = 1 + fibonachi_rand_values[ fibonachi_rand_value_cur_pointer ];
return fibonachi_rand_values[ fibonachi_rand_value_cur_pointer ];
}
|
единственное ограничение это GetTickCount() которая работает толко под Win, но для получения случайного начального значения для запуска генератора можно воспользоватся счетчиком тактов процессора:
| CODE |
DWORD HightCount; // использовать для инициализации
DWORD LowCount ; .. или это число, или их комбинацию
__asm
{
rdtsc
mov HightCount , edx
mov LowCount , eax
}
|
ЗЫ. Пора на AMD64 пересаживатся, а то с 32 разраядым double' ом слишком часто сингулярные матрицы "всплывают"
Отредактировано klen — 29/08/2004, 11:27 |
|
| exp |
| Отправлено: 29.08.2004, 13:57 |
|
Мастер участка
Группа: Участник
Сообщений: 304
|
Да. Верно, Георгий, из двух дуг равной длины вероятность попадания в дугу с большей кривизной меньше, т. к. меньше угол, на который она опирается.
Вы, вероятно, хотите сделать, чтоб на единицу длины дуги эллипса приходилось одинаковое число точек? Тогда нужно не равномерное распределение для угла, а некоторое другое. Какое, пока не знаю.
|
|
| Георгий |
| Отправлено: 29.08.2004, 20:16 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
может стоит попробовать случайное число из интервала [0,1) масштабировать по длине окружности (эллипса) ? а потом перевести в угол, а угол в координаты?
правда в 3х мерном случае, кажется, опять какие то неравномерности получатся.. |
|
| exp |
| Отправлено: 30.08.2004, 23:39 |
|
Мастер участка
Группа: Участник
Сообщений: 304
|
| QUOTE |
может стоит попробовать случайное число из интервала [0,1) масштабировать по длине окружности (эллипса) ? а потом перевести в угол, а угол в координаты?
|
С окружностью проблем нет при таком подходе, но с элипсом...
ОЧЧЧЕНЬ большие проблемы с первым переводом.
|
|
