Хабрахабр

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

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

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

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

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

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

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

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

$d_N = \min_ | 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$.

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

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

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

$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)$

Аналогичным образом эти множества точек можно перенести из единичного квадрата $[0, 1]^2$ на сферу при помощи цилиндрической равновеликой проекции:

$(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.

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

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

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

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

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

Сферическая спираль Фибоначчи, полученная из уравнения 1, даёт значение $d_N^*$ для всех $N$, то есть $d^* = 2$.

Сетка 1

09$" data-tex="inline"/>, имеет вид: Более распространённая версия (особенно в компьютерных системах), создающая более хорошее значение <img src="https://habrastorage.org/getpro/habr/formulas/e55/567/01b/e5556701bcf90b19dfe24f27532ef7eb.svg" alt="$d^*=3.

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

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

5}{100},\frac{1. $\{ \frac{0. 5}{100},\ldots, \frac{97. 5}{100},\frac{2. 5}{100},\frac{99. 5}{100},\frac{98. 5}{100} \}$

Сетка 2.

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

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

$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$

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

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

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

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

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

Сетка 3.

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

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

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

То есть:

$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}$

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

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

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

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

Сравнение

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

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

64 & 3. $\begin{array}{|c|cccccccccc|} \hline N & 12 & 42 & 92 & 162 & 252& 362 & 492 & 642 & 812 & 1002 \\ \hline d^* & 3. 34 & 3. 54 & 3. 15 & 3. 22 & 3. 06 & 3. 09 & 3. 00 & 2. 03 & 3. 99 \\ \hline \end{array}$

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

19 & 3. $\begin{array}{|c|ccccccc|} \hline N & 20 & 32 & 122 & 272 & 482 & 752 & 1082\\ \hline d^* & 3. 16 & 2. 63 & 3. 90 & 2. 99 & 2. 81 \\ \hline \end{array}$ 84 & 2.

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

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

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

09\\ \hline \text{Max Determinant} & 3. $\begin{array}{|lr|} \hline \text{Lattice 1} & 3. 28 \\ \hline \text{Lattice 3} & 3. 19 \\ \hline \text{Lattice 2} & 3. 32 \\ \hline \text{Coulomb} & 3. 31 \\ \hline \text{Zonal Equal Area} & 3. 37\\ \hline \end{array}$ 37 \\ \hline \text{Log Energy} & 3.

Вывод из раздела 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$

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

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

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

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

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

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

Давайте обобщим уравнение 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}$

где определим $g(n)$ как

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

где

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

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

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

Причина этого заключается в малоизвестном факте: все числа $x$, удовлетворяющие особому преобразованию Мёбиуса, исходя из иррациональности эквивалентны $\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$, обеспечивает более качественное распределение точек, чем каноническая сетка Фибоначчи (голубая линия).

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

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

То есть

$A_N = 1,4,5,9,14,23,37,60,97,157,254,411,…$

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

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

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

$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}$

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

$\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 видно, что относительно объёма выпуклой оболочки это новое распределение лучше, чем каноническая сетка для всех значений $n$

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

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

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

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

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

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

Источники

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть