Как сформировать равномерно распределенные точки на поверхности сферы 3-го блока?

68

Мне интересно, как генерировать равномерно распределенные точки на поверхности 3-й единицы сферы? Кроме того, после генерации этих точек, как лучше всего визуализировать и проверить, являются ли они действительно однородными на поверхности ?x2+y2+z2=1

Цян Ли
источник
Если под униформой вы имеете в виду «обычный», то за пределами = 2, 4, 6, 8, 12, 20 сделать это невозможно .n
Маркос
1
что не так с выборкой из MultiVariateGaussian и этот вектор просто нормализует ее: v = MultivariateNormal(torch.zeros(10000), torch.eye(10000))а затем v = v/v.norm(10000)
Буратино

Ответы:

72

Стандартный метод состоит в том, чтобы сгенерировать три стандартных нормали и построить из них единичный вектор. То есть, когда и , то равномерно распределены по сфере. Этот метод хорошо работает и для мерных сфер.λ 2 = X 2 1 + X 2 2 + X 2 3 ( X 1 / λ , X 2 / λ , X 3 / λ ) dXiN(0,1)λ2=X12+X22+X32(X1/λ,X2/λ,X3/λ)d

В 3D вы можете использовать выборку отклонения: рисовать из равномерного распределения пока длина станет меньше или равна 1, затем - как и в предыдущем методе - нормализовать вектор на единицу длины. Ожидаемое количество испытаний на одну сферическую точку равно = 1,91. В более высоких измерениях ожидаемое количество испытаний становится настолько большим, что быстро становится неосуществимым. [ - 1 , 1 ] ( X 1 , X 2 , X 3 ) 2 3 / ( 4 π / 3 )Xi[1,1](X1,X2,X3)23/(4π/3)

Есть много способов проверить однородность . Аккуратный способ, хотя и несколько вычислительно интенсивный, - это функция Рипли . Ожидаемое количество точек на (3D евклидовом) расстоянии от любого местоположения на сфере пропорционально площади сферы на расстоянии , которая равна . Вычисляя все расстояния между точками, вы можете сравнить данные с этим идеалом.ρ π ρ 2ρρπρ2

Общие принципы построения статистической графики предполагают, что хорошим способом сделать сравнение является построение устойчивых к дисперсии невязок против где - это наименьшее из взаимных расстояний и . Участок должен быть близок к нулю. (Этот подход нетрадиционен.)i = 1 , 2 , , n ( n - 1 ) / 2 = m d [ i ] i th e i = 2 ei(d[i]ei)i=1,2,,n(n1)/2=md[i]ithei=2i/m

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

100 однородных сферических точек

Вот диагностический график расстояний:

Диагностический сюжет

Шкала y предполагает, что все эти значения близки к нулю.

Вот накопление 100 таких графиков, чтобы предположить, какие отклонения по размеру могут быть значимыми индикаторами неравномерности:

Моделируемые значения

(Эти сюжеты очень похожи на броуновские мосты ... здесь могут скрываться интересные теоретические открытия.)

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

Имитация неоднородных значений

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

Whuber
источник
@ Whuber: очень хорошо! Большое спасибо за ваше сообщение! « равномерно распределены по сфере". где я могу найти ссылку на ее доказательство, или это просто доказуемо? (X1/λ,X2/λ,X3/λ)
Цян Ли
23
@Qiang, Вот суть доказательства: пусть где обозначает единичную матрицу. Тогда для любой ортогональной матрицы , . Следовательно, распределение инвариантно относительно вращений. Пусть и заметим , что для любого ортогонального . Поскольку инвариантен к вращениям, как и , и, поскольку почти наверняка, то он должен быть равномерно распределен по сфере. XN(0,In)Inn×nQQXN(0,In)XY=X/X2YQ=QX/QX2=QX/X2QXYY2=1
кардинал
3
@ Майк Нет, потому что равномерное распределение широты не дает равномерного распределения по сфере. (Большая часть поверхности сферы находится в более низких широтах вблизи экватора от полюсов. Вам нужно равномерное распределение .)ϕcos(ϕ)
whuber
1
@Ahsan Поскольку ортогональные матрицы образуют транзитивную группу сохраняющих площадь преобразований сферы, распределение равномерно по подмножеству сферы вида : но это вся сфера. X/||X||2
whuber
1
@ Цезарь "Равномерное распределение" (по сфере).
whuber
19

Вот некоторый довольно простой код R

n     <- 100000                  # large enough for meaningful tests
z     <- 2*runif(n) - 1          # uniform on [-1, 1]
theta <- 2*pi*runif(n) - pi      # uniform on [-pi, pi]
x     <- sin(theta)*sqrt(1-z^2)  # based on angle
y     <- cos(theta)*sqrt(1-z^2)     

Из конструкции очень просто увидеть, что и, следовательно, но если это необходимо проверить, тоx2+y2=1z2x2+y2+z2=1

mean(x^2+y^2+z^2)  # should be 1
var(x^2+y^2+z^2)   # should be 0

и легко проверить, что каждый из и равномерно распределен на ( очевидно, )xy[1,1]z

plot.ecdf(x)  # should be uniform on [-1, 1]
plot.ecdf(y)
plot.ecdf(z)

Очевидно, что при заданных значениях , и равномерно распределены по окружности радиуса и это можно проверить, посмотрев на распределение арктангенса их отношения. Но поскольку имеет то же предельное распределение, что и и , аналогичное утверждение верно для любой пары, и это тоже можно проверить. zxy1z2zxy

plot.ecdf(atan2(x,y)) # should be uniform on [-pi, pi]
plot.ecdf(atan2(y,z))
plot.ecdf(atan2(z,x))

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

Генри
источник
Мне просто интересно, если ваш метод генерации точек (x, y, z) по сути такой же, как метод Вубера?
Цян Ли
3
Нет, это не так: whuber использует три случайных числа, а я использую два. Мой является частным случаем «создать точку на с подходящей плотностью [пропорциональной ]] и затем уменьшить размер». Здесь удобно поскольку это формально 2-сфера . [1,1](1z2)n/21n=2
Генри
3
Или, в более общем случае, сгенерируйте однородные точки на карте, используя любую проекцию равной площади (ваша - цилиндрическую равную площадь), а затем спроецируйте обратно. (+1)
whuber
@whuber: Действительно. Оффтопик, но для тех , кто заинтересован меня есть интерактивный выбор мировых картографических проекций здесь , некоторые из которых равны область
Генри
2
Это в значительной степени стандартный подход, используемый в компьютерной графике, основанный на теореме Архимеда о шляпной
Эдвард КМЕТТ,
10

Если вы хотите сэмплировать точки, равномерно распределенные на трехмерной сфере (т. Е. На поверхности трехмерного шара), используйте простое отклонение или метод Marsaglia (Ann. Math. Statist., 43 (1972), с. 645–. 646). Для низких размеров коэффициент браковки довольно низок.

Если вы хотите сгенерировать случайные точки из сфер и шаров большего размера, то это зависит от цели и масштаба симуляции. Если вы не хотите выполнять большие симуляции, используйте метод Мюллера (Commun. ACM, 2 (1959), pp. 19–20) или его «шариковую» версию (см. Статью Harman & Lacko, приведенную выше). Это:

чтобы получить образец, равномерно распределенный по n-сфере (поверхности) 1) сгенерировать X из n-мерного стандартного нормального распределения 2) разделить каждый компонент X на евклидову норму X

чтобы получить образец, равномерно распределенный на n-шаре (внутренности) 1) сгенерировать X из (n + 2) -мерного стандартного нормального распределения 2) разделить каждый компонент X на евклидову норму X и взять только первые n компонентов

Если вы хотите выполнить большое моделирование, то вам следует изучить более специализированные методы. По запросу я могу выслать вам статью Хармана и Лацко о методах условного распределения, в которой приводится классификация и обобщения некоторых алгоритмов, упомянутых в этом обсуждении. Контакт можно найти на моем сайте (http://www.iam.fmph.uniba.sk/ospm/Lacko).

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

V Lacko
источник
что не так с выборкой из MultiVariateGaussian и этот вектор просто нормализует ее: v = MultivariateNormal(torch.zeros(10000), torch.eye(10000))а затем v = v/v.norm(10000)
Буратино
8

У меня была похожая проблема (n-сфера) во время моей докторской диссертации, и один из местных «экспертов» предложил отбирать пробы из n-куба! Это, конечно, взяло бы возраст вселенной, поскольку я смотрел на n в порядке сотен.

Алгоритм, который я в итоге использовал, очень прост и опубликован в:

В.П. Петерсен и А. Бернасконик. Равномерный отбор проб из n-сферы: изотропный метод. Технический отчет, TR-97-06, Швейцарский центр научных вычислений.

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

Харман Р. и Лацко В. О алгоритмах декомпозиции для равномерной выборки из сфер и шаров Журнал многомерного анализа, 2010nn

emakalic
источник
Можно ли разместить ссылки, где я могу найти полный текст этих ссылок? Благодарю.
Цян Ли
У меня нет бумаги для меня, но эта страница, кажется, описывает алгоритм (и несколько других) mlahanas.de/Math/nsphere.htm
emakalic
3
Как я понимаю, (из статьи Петерсена и Бернасконика) для d-мерного шара можно генерировать радиус, повышая переменную U (0,1) до степени (1 / d), а последний угол как U (0,2 ) варьируется. Промежуточные углы могут быть получены как , где равен . Для меня это звучит довольно просто. Что меня интересует, так это: если я использую квазислучайную последовательность для своей формы, получу ли я также и милость в мяче? πC.asin(uk)C1
πΓ(k2+0.5)Γ(k2+1)
Мохит
3

У меня была эта проблема раньше, и вот альтернатива, которую я нашел,

Что касается самого распределения, формула, которую я нашел, которая работает прилично, состоит в том, чтобы использовать полярные координаты (я на самом деле использую вариацию развернутых координат поляра), а затем преобразовать в декартовы координаты.

Радиус - это, конечно, радиус сферы, на которой вы строите график. Затем у вас есть второе значение угла на плоской плоскости, за которым следует третье значение, которое представляет собой угол над или под этой плоскостью.

Чтобы получить приличное распределение, предположим, что U - это равномерно распределенное случайное число, r - радиус, a - вторая полярная координата, а b - третья полярная координата,

a = U * 360 b = U + U-1, а затем преобразовать в декартову через x = r * sin (b) sin (a) z = r sin (b) cos (a) y = r sin (b)

Недавно я нашел следующее, что лучше математически говоря, а = 2 (пи) * U b = cos ^ -1 (2U-1)

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

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

Хотя я проверяю однородность визуально с помощью довольно дешевого метода создания карт для Homeworld 2, а затем «разыгрываю» эти карты. Фактически, поскольку карты сделаны с помощью сценариев lua, вы можете встроить свою формулу прямо в карту и, таким образом, проверить несколько выборок, даже не выходя из игры. Возможно, не научно, но это хороший метод для визуального просмотра результатов.

TheDerpyAlicorn
источник
2

Вот псевдокод:

  1. vMultiVariateGaussian(μ,σI)
  2. v=vv

В пыторхе:

v = MultivariateNormal(torch.zeros(10000), torch.eye(10000))
v = v/v.norm(2)

Я не очень хорошо понимаю это, но мне сказали, что:

v = torch.normal(torch.zeros(10000), torch.eye(10000))
v = v/v.norm(2)

также правильно, т.е. выборка из одномерной нормали для каждой координаты.

Пиноккио
источник
0

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

Вам, вероятно, придется смешивать и сопоставлять способ, которым вы генерируете точки, и способ их отображения. С точки зрения генерации 2D-точек, я думаю, что скремблированные последовательности с низким расхождением были бы хорошим местом для начала (т. Е. Скремблированная последовательность Соболя), поскольку она обычно создает точки, которые не «объединяются». Я не уверен в том, какой тип карт использовать, но Вофлрам показал гномическую проекцию ... так что, может, это сработает?

MATLAB имеет достойную реализацию последовательностей с низким расхождением, которые вы можете генерировать используя q = sobolset(2)и скремблировать используя q = scramble(q). В MATLAB также есть набор инструментов для картирования с множеством различных функций проецирования, которые вы можете использовать, если не хотите самостоятельно кодировать отображение и графику.

Берк У.
источник
1
может ли какая-либо из этих проекций сохранить однородность случайности? Опять же, как я могу проверить, действительно ли окончательное распределение этих точек равномерно распределено по поверхности сферы? Благодарю.
Цян Ли
Извините, я просто говорил гипотетически ... Я думаю, что функции отображения в MATLAB позволят вам проверить это, поскольку в них встроены некоторые визуализации. Если нет, я также нашел хороший сайт, который рассказывает о том, как генерировать равномерно распределенные точки на сфере в 3D, используя такие вещи, как рандомизированные углы и т. Д. У них там тоже есть некоторый C-код. Взгляните
Берк U.
3
Однородные случайные точки на гномонической проекции не будут однородными на сфере, потому что гномоническая область не равна. Проекция , предложенный Генри, -> (от долготы-широты до прямоугольника в ), является равной площади. ( λ , sin ( ϕ ) ) R 2(λ,ϕ)(λ,sin(ϕ))R2
whuber