PatientZero 22 июл 2019 в 08:56

Равномерное распределение точек на сфере

8 мин

22K

Алгоритмы*Математика*Работа с 3D-графикой*

Перевод

Как можно более равномерное распределение точек на сфере — невероятно важная задача в математике, науке и компьютерных системах, а наложение сетки Фибоначчи на поверхность сферы при помощи равновеликой проекции — чрезвычайно быстрый и эффективный метод аппроксимации для её решения. Я покажу, как благодаря незначительным изменениям его можно сделать ещё лучше.

Какое-то время назад этот пост появился на главной странице Hacker News. Его обсуждение можно прочитать здесь.

Введение

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

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

Упаковка и покрытие
Выпуклые оболочки, ячейки Вороного и треугольники Делоне
Ядра $inline$ -энергии Риса
Кубатура и определители

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

Ради краткости в этом посте мы рассмотрим только два критерия: минимальное расстояние упаковки и выпуклую оболочку/сетку Делоне (объём и площадь).

В разделе 1 мы покажем, как можно изменить каноническую сетку Фибоначчи для построения улучшенного распределения упаковки. В разделе 2 мы покажем, как можно изменить каноническую сетку Фибоначчи для построения улучшенных параметров выпуклых оболочек (объёма и площади поверхности).

Раздел 1. Оптимизация расстояния упаковки

Часто эту задачу называют задачей Тэммса в честь ботаника Тэммса, искавшего объяснение структуры поверхности пыльцевых зёрен. Критерий упаковки требует от нас максимизировать наименьшее расстояние между соседями для $inline$ точек. То есть

$d_N = \min_{i \neq j} | x_i – x_j |$

Это значение уменьшается со скоростью $~ 1/\sqrt{N}$ , поэтому полезно будет определить нормализованное расстояние, а также асимптотический предел нормализованного расстояния как

$d^*_N = \sqrt{N} d_N ,\quad \quad d^* = \lim_{N \rightarrow \infty} d^*_N$

Сетка Фибоначчи

Одно очень элегантное решение моделирует узлы, встречающиеся в природе, например, распределение семян в подсолнухе или сосновой шишке. Это явление называется спиральным филлотаксисом. Коксетер показал, что такие структуры имеют фундаментальную связь с рядом Фибоначчи, $F_k =\{1, 1, 2, 3, 5, 8, 13, …\}$ и золотым сечением $\phi = (1+\sqrt{5})/2$ .

В литературе встречается два схожих определения множества точек сферической сетки Фибоначчи. Исходное определено строго для $inline$ , равного одному из членов ряда Фибоначчи, $inline$ , и хорошо изучено в теории чисел.

$t_i = \left( \frac{i}{F_m}, \frac{i F_{m-1}}{F_m} \right) \quad \textrm{for }\; 0 \leq i \leq N-1$

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

$t_i = \left( \frac{i}{N}, \frac{i }{\phi} \right) \quad \textrm{for }\; 0 \leq i \leq N \tag{1}$

где

$\phi = \frac{1+\sqrt{5}}{2} = \lim_{n \rightarrow \infty} \left( \frac{F_{n+1}}{F_n} \right)$

Ниже показан пример таки сеток Фибоначчи. Преобразованием можно превратить эти множества точек в хорошо известные нам спирали Фибоначчи

$(r,\theta) = (\sqrt{x_1}, 2\pi x_2)$

Аналогичным образом эти множества точек можно перенести из единичного квадрата $inline$ на сферу при помощи цилиндрической равновеликой проекции:

$(x,y) \rightarrow (\theta, \phi) : \quad \left( \cos^{-1}(2x-1) – \pi/2, 2\pi y \right)$

$(\theta,\phi) \rightarrow (x,y,z) : \quad \left (\cos\theta \cos\phi, \cos \theta \sin \phi, \sin \theta \right)$

Множество различный версий код на Python для неё можно найти на stackoverflow: Evenly distributing points on a sphere.

Даже несмотря на то, что сферические множества Фибоначчи глобально не являются наилучшим распределением сэмплов на сфере (потому что их решения не совпадают с решениями для платоновых тел при $inline$ ), они обладают превосходными свойствами сэмплирования и очень легки в построении по сравнению с другими, более сложными схемами сферического сэмплирования.

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

Такой перенос страдает от двух различных, но взаимосвязанных проблем.

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

Вторую проблему сложнее всего решить с точки зрения практики: наложение имеет на каждом полюсе две вырожденные точки. Рассмотрим две точки, находящиеся очень близко к полюсу, но отличающиеся на 180 градусов по долготе. На единичном квадрате (и на цилиндрической проекции) они будут соответствовать двум очень далёким друг от друга точкам, однако при наложении на поверхность сферы они могут быть соединены очень малой дугой, проходящей через северный полюс. Из-за этой конкретной проблемы многие спиральные наложения оказываются недостаточно оптимальными.

Сферическая спираль Фибоначчи, полученная из уравнения 1, даёт значение $inline$ для всех $inline$ , то есть $inline$ .

Сетка 1

Более распространённая версия (особенно в компьютерных системах), создающая более хорошее значение $inline$ , имеет вид:

$t_i = \left( \frac{i+1/2}{N}, \frac{i}{\phi} \right) \quad \textrm{for }\; 0 \leq i \leq N-1 \tag{2}$

Она располагает точки в средних точках интервалах (по правилу средней точки в квадратной формуле Гаусса), поэтому для $inline$ , значения первой координаты будут такими:

$\{ \frac{0.5}{100},\frac{1.5}{100},\frac{2.5}{100},\ldots, \frac{97.5}{100},\frac{98.5}{100},\frac{99.5}{100} \}$

Сетка 2.

Ключевым моментом для дальнейшего улучшения уравнения 2, является осознание того, что $inline$ всегда соответствует расстоянию между точками $inline$ и $inline$ , которые находятся на полюсах. То есть для улучшения $inline$ точки рядом с полюсами должны быть разнесены ещё дальше.

Если мы определим следующее распределение:

$t_i(\varepsilon) = \left( \frac{i+1/2+ \varepsilon}{N+2\varepsilon}, \frac{i}{\phi} \right) \quad \textrm{for }\; 0 \leq i \leq N-1$

$inline$ — кривые для различных значений. $\varepsilon=0$ (синяя); $\varepsilon=\frac{1}{2}$ (оранжевая); $\varepsilon=\frac{3}{2}$ (зелёная); и $\varepsilon=\frac{5}{2}$ (красная). Можно увидеть, что $\varepsilon = \frac{5}{2}$ даёт результаты ближе к асимптотическим результатам. То есть при $inline$ следующее простое выражение генерирует значительно более хорошие результаты $inline$ по сравнению с канонической сферической сеткой Фибоначчи:

$t_i = \left( \frac{i+3}{N+5}, \frac{i}{\phi} \right) \quad \textrm{for }\; 0 \leq i \leq N-1 \tag{3}$

То есть при $inline$ значения первой координаты будут равны:

$\{ \frac{3}{105},\frac{4}{105},\frac{5}{105},\ldots, \frac{100}{105},\frac{101}{105},\frac{102}{105} \}$

Рисунок 1. Различные значения $inline$ при разных значениях $\epsilon$ . Чем больше значение, тем оптимальнее конфигурации. Мы видим, что $\epsilon \simeq 2.5$ обеспечивает решение, близкое к оптимальному.

Сетка 3.

Как сказано выше, одна из самых серьёзных проблем равномерного распределения точек на сфере заключается в том, что оптимальность распределения критически зависит от используемой целевой функции. Оказывается. что локальные величины наподобие $inline$ иногда почти «не прощают ошибок» — единственная точка в недостаточно оптимальной позиции может катастрофически снизить оценку всего распределения точек.

В нашем случае вне зависимости от величины $inline$ значение $inline$ обычно определяется четырьмя точками, наиболее близкими к каждому из полюсов, особенно $inline$ и $inline$ . Однако об этой сетке также известно то, что наибольший многоугольник Вороного находится на полюсе. Таким образом, пытаясь максимизировать $inline$ разделением изначальных полярных точек в ряду, мы на самом деле ещё больше увеличиваем пустоту на полюсе! Поэтому мы представили альтернативу сетке 2, которая в общем случае более предпочтительна, потому что она не демонстрирует такой большой пустоты рядом с полюсами.

Она почти идентична сетке 2, но имеет два отличия. Во-первых, она использует $\varepsilon = 11/2$ при $1 \leq i \leq N-2$ . Во-вторых, кроме этих $inline$ точек первая и последняя точки располагаются на каждом из полюсов.

То есть:

$t_0=(0,0); \; t_n = (1,0); \quad t_i = \left( \frac{i+6}{N+11}, \frac{i}{\phi} \right) \quad \textrm{for }\; 1 \leq i \leq N-2 \tag{4}$

Удивительное свойство этого метода построения заключается в том, что несмотря на то, что его создание было мотивировано желанием минимизировать пустоты на полюсах, он на самом деле имеет наилучшее среди всех методов значение $inline$ и $inline$ с $inline$ !

То есть при $inline$ значения первой координаты будут такими:

$\{ 0; \; \frac{7}{111},\frac{8}{111},\frac{9}{1111},\ldots, \frac{102}{111},\frac{103}{111},\frac{104}{111} ; \; 1\}$

Рисунок 2. Различные конфигурации сеток. Каноническая сетка Фибоначчи слева. Заметьте, что несмотря на то, что у средней сетки $inline$ улучшено, на полюсе у неё есть заметная пустота. Сетка 3 не имеет пустоты на полюсе и обладает наилучшим значением $inline$ .

Сравнение

При больших значениях $inline$ это значение $inline$ чрезвычайно хорошо сравнимо с другими методами, например, геодезическими куполами, которые основаны на триангулированных проекциях с граней платоновых тел на поверхность сферы. Неудивительно что самые качественные геодезические купола построены на основе икосаэдра или додекаэдра.

Основанные на икосаэдре геодезические купола при различных значениях $inline$ .

$\begin{array}{|c|cccccccccc|} \hline N & 12 & 42 & 92 & 162 & 252& 362 & 492 & 642 & 812 & 1002 \\ \hline d^* & 3.64 & 3.54 & 3.34 & 3.22 & 3.15 & 3.09 & 3.06 & 3.03 & 3.00 & 2.99 \\ \hline \end{array}$

Основанные на додекаэдре геодезические купола при различных значениях $inline$ .

$\begin{array}{|c|ccccccc|} \hline N & 20 & 32 & 122 & 272 & 482 & 752 & 1082\\ \hline d^* & 3.19 & 3.63 & 3.16 & 2.99 & 2.90 & 2.84 & 2.81 \\ \hline \end{array}$

Кроме того, усечённый икосаэдр, соответствующий форме фуллерена $C_{60}$ , имеет всего лишь $inline$ .

То есть при $inline$ сетки на основе уравнения 3 лучше любых геодезических многограннико.

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

$\begin{array}{|lr|} \hline \text{Lattice 1} & 3.09\\ \hline \text{Max Determinant} & 3.19 \\ \hline \text{Lattice 2} & 3.28 \\ \hline \text{Lattice 3} & 3.31 \\ \hline \text{Zonal Equal Area} & 3.32 \\ \hline \text{Coulomb} & 3.37 \\ \hline \text{Log Energy} & 3.37\\ \hline \end{array}$

Вывод из раздела 1

Сетка 3, созданная по уравнению 3, является модификацией канонической сетки Фибоначчи, обеспечивающей гораздо более качественную упаковку распределения точек. То есть

$t_0 = (0,0); \; \; t_i = \left( \frac{i+6}{N+11}, \frac{i}{\phi} \right); \;\; t_{N-1} = (0,1); \quad \textrm{for }\; 1 \leq i \leq N-2$

Раздел 2. Оптимизация выпуклой оболочки (сетки Делоне)

В предыдущем разделе мы оптимизировали распределение по $inline$ , однако эти модификации ухудшают другие показатели, например объём выпуклой оболочки (сетки Делоне). В этом разделе рассказывается, как равномерно распределить точки на сфере таким образом чтобы оптимизировать (максимизировать) такой более глобальный показатель, как объём выпуклой оболочки.

Обозначим $inline$ как выпуклую оболочку $inline$ точек,

$\epsilon_N = N \left( \frac{4\pi }{3} \; – \textrm{Vol}(C_N) \right)$

сюда включён фактор нормализации $inline$ , потому что абсолютное расхождение снижается со скоростью $inline$ .

Поведение $\epsilon_N$ при различных $inline$ можно увидеть на рисунке 3 (синяя линия).

Для снижения рассогласованности объёмов необходимо заметить, что несмотря на использование $\phi$ , из логичности золотого сечения при $N \rightarrow \infty$ необязательно следует, что оно является наилучшим значением для конечного $inline$ . Говоря по-научному, можно сказать, что нужно учесть влияние коррекции конечности членов.

Давайте обобщим уравнение 1 следующим образом:

$t_i = \left( \frac{i+1/2}{N}, \frac{i}{g(N)} \right) \quad \textrm{for }\; 0 \leq i \leq N-1 \tag{4}$

где определим $inline$ как

$g(n) = \begin{cases} 3-\phi, & \text{if $k$ is even} \\ \phi, & \text{if $k$ is odd} \end{cases} \tag{5}$

где

$k = \left\lfloor \textrm{log}_{\phi}(\frac{n}{1.5}) \right\rfloor = \left\lfloor \frac{\ln (n/1.5)}{\ln \phi } \right\rfloor$

где $\lfloor x \rfloor$ — функция округления до ближайшего целого в меньшую сторону.

На рисунке 3 показано, насколько значительно оптимизируется рассогласованность объёмов для половины значений $inline$ .

Причина этого заключается в малоизвестном факте: все числа $inline$ , удовлетворяющие особому преобразованию Мёбиуса, исходя из иррациональности эквивалентны $\phi$ .

$x = \frac{a\phi+b}{c\phi+d}, \quad \textrm{for all integers} \; \; a,b,c,d \; \textrm{such that } |ad-bc|=1$

Следовательно, причина того, что $\phi$ и $3-\phi$ так хорошо подходят друг другу, заключается в том, что

$\frac{1}{\phi} = \frac{\phi+1}{2\phi+1}, \quad \quad \frac{1}{3-\phi }= \frac{2\phi+1}{1\phi+1}$

Рисунок 3. Рассогласованность между объёмом выпуклой оболочки из точек и объёмом единичной сферы. Учтите, что чем она меньше, тем лучше. Рисунок показывает, что гибридная модель (оранжевая линия), основанная на $\phi$ и $3-\phi$ , обеспечивает более качественное распределение точек, чем каноническая сетка Фибоначчи (голубая линия).

Для оставшейся половины мы сначала определим вспомогательный ряд $inline$ , являющийся разновидностью ряда Фибоначчи

$A_1 =1, \; A_2 = 4; \; A_{n+2}= A_{n+1}+A_n \; \textrm{for } n = 1,2,3,…$

То есть

$display$

Все дроби этого ряда имеют изящные непрерывные дроби, а в пределе сходятся к $\phi$ . Например,

$t _5/t_4 = 1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{4}}}}$

Теперь мы можем полностью обобщить $inline$ следующим образом:

$g(N) = \begin{cases} 3-\phi, & \text{if $k$ is even} \\ A_{j+1}/A_j , & \text{if $k$ is odd, where $j= (k+7)/2$} \end{cases} \tag{6}$

В таблице ниже показаны значения $inline$ для различных $inline$ .

$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline N & 4-6 & 7-10 & 11-16& 17-26& 27-43& 44-70& 71-114 & 115-184 & 185-300\\ \hline g(n) &3-\phi & \frac{23}{14} & 3-\phi & \frac{37}{23} & 3-\phi & \frac{60}{37} & 3-\phi & \frac{97}{60} & 3-\phi \\ \hline \end{array}$

Из рисунка 4 видно, что относительно объёма выпуклой оболочки это новое распределение лучше, чем каноническая сетка для всех значений $inline$

Рисунок 4. Рассогласование между объёмом выпуклой оболочки и объёмом единичной сферы. Чем меньше значения, тем лучше. Это говорит нам, что предлагаемый новый метод (зелёная линия) постоянно обеспечивает лучшее по сравнению с канонической сеткой Фибоначчи (синяя линия) распределение.

Рисунок 5. Наглядное сравнение канонической сетки (слева) с новой модифицированной сеткой (справа) при n=35 и n=150. Визуально различия почти незаметны. Однако в условиях, требующих максимальной эффективности, модифицированная версия (справа) обеспечивает небольшое, но поддающееся количественному измерению улучшению и в объёме, и в площади поверхности выпуклой оболочки.

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

Рисунок 5. Нормализованное рассогласование площадей между площадью поверхности выпуклой оболочки (сетки Делоне) и площадью поверхности единичной сферы. Чем ниже значения, тем лучше. Это показывает, что предложенная новая модификация (зелёные точки) демонстрирует небольшое, но постоянное снижение разности площадей поверхностей по сравнению с канонической сеткой Фибоначчи (синие точки)

Вывод из раздела 2

Сетка, соответствующая уравнению 6, является модификацией канонической сетки Фибоначчи, создающей значительно лучшее распределение точек, исходя из объёма и площади поверхности выпуклой оболочки (сетки Делоне).

Источники

Теги:

Хабы:

Если эта публикация вас вдохновила и вы хотите поддержать автора — не стесняйтесь нажать на кнопку

Равномерное распределение точек на сфере

Введение

Раздел 1. Оптимизация расстояния упаковки

Раздел 2. Оптимизация выпуклой оболочки (сетки Делоне)

Публикации

Истории

Ближайшие события