2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Равновероятный выбор точки на поверхности сферы
Сообщение11.09.2007, 19:59 
Аватара пользователя


11/09/07
21
Volgograd
Вот захотелось нарисовать сферу в трехмерном пространстве точками. С помощью одного из языков программирования.

Формула координат точек поверхности сферы проста:
x = R * cos(lat) * cos(long)
y = R * cos(lat) * sin(long)
z = R * sin(lat)

, где R - радиус, lat - широта (-90 <= lat <= 90), long - долгота (-180 <= long <= 180).

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

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

 Профиль  
                  
 
 
Сообщение11.09.2007, 20:10 
Модератор
Аватара пользователя


11/01/06
5660
Выбирайте равномерно высоту z из [-R,R] и долготу long из [-180,180]. Тогда точка будет равномерно распределена на поверхности сферы в виду того, что площадь поверхности сферического сегмента зависит только от его высоты и радиуса сферы, но не от местоположения: http://mathworld.wolfram.com/Zone.html

 Профиль  
                  
 
 
Сообщение11.09.2007, 23:02 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
Можно еще вспомнить следующий факт: площадь участка единичной сферы, задаваемого в сферических координатах условиями \[
\varphi _1  \le \varphi  \le \varphi _2 \;;\;\theta _1  \le \theta  \le \theta _2 
\] , где \[
\left\{ {\begin{array}{*{20}c}
   {x = \cos \varphi \cos \theta }  \\
   {y = \sin \varphi \cos \theta }  \\
   {x = \sin \theta }  \\
\end{array}} \right.
\] вычисляется по формуле \[
S = (\varphi _1  - \varphi _2 )(\sin \theta _1  - \sin \theta _2 )
\] Отсюда следует, что Вам нужно использовать такое распределение угла \[
\theta 
\], при котором равномерно распределён будет \[
{\sin \theta }\]. Понятно, что это не то же самое, что и равномерное распределение самого угла. Думаю, что получится хорошо, если в качестве распределения угла \[
{\sin \theta }\] взять арксинус равномерного распределения. Попробуйте, должно получиться.

 Профиль  
                  
 
 
Сообщение11.09.2007, 23:09 
Модератор
Аватара пользователя


11/01/06
5660
Brukvalub писал(а):
Думаю, что получится хорошо, если в качестве распределения угла \[
{\sin \theta }\] взять арксинус равномерного распределения.

Это то же самое, что я предложил выше. Если z равномерно распределено в [-R,R], то lat (он же $\theta$) = arcsin(z/R) и есть арксинус равномерного распределения.

 Профиль  
                  
 
 
Сообщение11.09.2007, 23:11 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
maxal писал(а):
Это то же самое, что я предложил выше. Если z равномерно распределено в [-R,R], то lat (он же $\theta$) = arcsin(z/R) и есть арксинус равномерного распределения.
Полностью согласен, просто я хотел указать путь, который позволяет сохранить вычисления в сферических координатах.

 Профиль  
                  
 
 
Сообщение12.09.2007, 04:36 


25/01/06
102
Вот еще один простой алгоритм.

Первый шаг - генерить случайные точки в кубе куда вписана сфера, отбрасывать точки, которые дальше от центра сферы, чем ее радиус, и те, что слишком близко к центру сферы. (Это чтоб избежать вычислительной неустойчивости на втором шаге)

Второй шаг - проецировать сгенеренные точки на поверхность сферы.

Доказательство равномерной распределенности по поверхности очевидно.

 Профиль  
                  
 
 
Сообщение12.09.2007, 15:13 
Аватара пользователя


11/09/07
21
Volgograd
Большое спасибо всем за ответы!!!

Я так понял, что мне надо угол фи выбирать произвольно, а угол тэта выбирать по формуле arcsin(x), где x - случайное число от -1 до +1.

Этот спороб действительно сработал :D Но...
В программировании числа дискретны, нельзя выбрать случайное число от -1 до 1. Там можно выбрать, например, случайное целое число от -10000 и до 10000, а потом поделить его на 10000.

Я сначала поставил от -100 и до 100 и у меня нарисовался шар с видимыми широтами :? Но потом дошло, что надо увеличить диапазон... Кольца перестали быть заметными. Но если увеличить количество случайных точек, то казус вернется. Во всяком случае, в моем варианте это подходящее решение.

Здесь подошел бы способ, который предложил Igor Borovikov, но такое решение работает гораздо медленней предыдущего (для большого количества точек) и не известно изначально точное колличество точек, которые будут спроецированы на поверхность сферы.

 Профиль  
                  
 
 
Сообщение12.09.2007, 15:39 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
Jaranero писал(а):
В программировании числа дискретны, нельзя выбрать случайное число от -1 до 1. Там можно выбрать, например, случайное целое число от -10000 и до 10000, а потом поделить его на 10000.
"это уже пошло обсуждение способов генерации значений псевдосучайного равномерного распределения? Уверен, что таким способам посвящено море литературы. Для начала, см. Кнут Д.Э. — Искусство программирования (Том 2. Получисленные алгоритмы)

 Профиль  
                  
 
 
Сообщение12.09.2007, 16:02 
Аватара пользователя


11/09/07
21
Volgograd
Brukvalub писал(а):
это уже пошло обсуждение способов генерации значений псевдосучайного равномерного распределения? Уверен, что таким способам посвящено море литературы. Для начала, см.  Кнут Д.Э. — Искусство программирования (Том 2. Получисленные алгоритмы)

Спасибо за пояснение, никогда не задумывался над этим... Попробую узнать!

 Профиль  
                  
 
 
Сообщение12.09.2007, 19:29 


25/01/06
102
Цитата:
Здесь подошел бы способ, который предложил Igor Borovikov, но такое решение работает гораздо медленней предыдущего (для большого количества точек) и не известно изначально точное колличество точек, которые будут спроецированы на поверхность сферы.


Количество "полезных" точек посчитать легко - отношение объема шара к объему куба: $\pi/6$ то есть прмерно половина точек - полезные.

Насчет "гораздо медленней" - ну, наверное, раза в три. Вот грубая прикидка:

"Кубический" способ:

- породить ТРИ случайных числа - координаты точки
- узнать расстояние до центра т.е. посчитать корень квадратный суммы квадратов координат
- сравнить с радиусом
- сравнить с выбранным малым числом - во избежание деления на ноль
- координаты поделить на расстояние

Далее все зависит от того в какой форме нужен ответ - в сферических или декартовых координатах. Мелкая оптимизация - например, сравнивать с радиусом и малым числом _квадрат_ расстояния - не в счет.

"Сферический" способ:

- породить ДВА случайных числа - одно для z другое для угола a
- вычислить радиус r на высоте z т.е. $ r = R  \sqrt{1-z^2/R^2} $
- посчитать y = r*sin(a) и x = r*cos(a)

Вычисление третьего случайного числа, скорее всего, главный недостаток "кубического" алгоритма. Два дополнительных сравнения - тоже не в пользу "кубического" подхода. По остальным операциям - прмерно тоже самое... вопрос только с какой скоростью считается тригонометрия на Вашем железе.

Окончательно, с учетом того, что только половина точек пойдет в дело, видим что "кубический" способ примерно в 2.5-3 раза меделенней.

 Профиль  
                  
 
 
Сообщение13.09.2007, 12:46 
Аватара пользователя


11/09/07
21
Volgograd
to Igor Borovikov
Прикольно 8-) Вечерком попробую спрограммировать :D

 Профиль  
                  
 
 
Сообщение13.09.2007, 12:55 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Igor Borovikov писал(а):
узнать расстояние до центра т.е. посчитать корень квадратный суммы квадратов координат
- сравнить с радиусом


Если уж экономить, то лучше заранее посчитать квадрат радиуса и сравнивать с ним. Тем самым экономится извлечение корня для тех точек, которые не попали в сферу или находятся слишком близко к нулю, т.е. которые не нужно проектировать.

 Профиль  
                  
 
 
Сообщение14.09.2007, 06:17 


25/01/06
102
PAV, Так я и написал
Цитата:
Мелкая оптимизация - например, сравнивать с радиусом и малым числом _квадрат_ расстояния - не в счет.
На фоне третьего случайного числа это мелочь.

 Профиль  
                  
 
 
Сообщение14.09.2007, 06:19 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Да, я не заметил.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group