Равновероятный выбор точки на поверхности сферы

[Jaranero]

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

Формула координат точек поверхности сферы проста:
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).

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

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

[maxal]

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

[Brukvalub]

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

\[ \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 }\]

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

[maxal]

Brukvalub писал(а):

Думаю, что получится хорошо, если в качестве распределения угла

\[ {\sin \theta }\]

взять арксинус равномерного распределения.

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

[Brukvalub]

maxal писал(а):

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

Полностью согласен, просто я хотел указать путь, который позволяет сохранить вычисления в сферических координатах.

[Igor Borovikov]

Вот еще один простой алгоритм.

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

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

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

[Jaranero]

Большое спасибо всем за ответы!!!

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

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

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

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

[Brukvalub]

Jaranero писал(а):

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

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

[Jaranero]

Brukvalub писал(а):

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

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

[Igor Borovikov]

Цитата:

Здесь подошел бы способ, который предложил 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 раза меделенней.

[Jaranero]

to Igor Borovikov
Прикольно Вечерком попробую спрограммировать

[PAV]

Igor Borovikov писал(а):

узнать расстояние до центра т.е. посчитать корень квадратный суммы квадратов координат
- сравнить с радиусом

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

[Igor Borovikov]

PAV, Так я и написал

Цитата:

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

На фоне третьего случайного числа это мелочь.

[PAV]

Да, я не заметил.