A distribuição mais uniforme de pontos na esfera é uma tarefa incrivelmente importante em matemática, ciências e sistemas de computadores, e aplicar uma grade de Fibonacci à superfície de uma esfera usando a mesma projeção é um método de aproximação extremamente rápido e eficiente para resolvê-la. Vou mostrar como, com pequenas alterações, isso pode ser feito ainda melhor.

Algum tempo atrás, este post apareceu na página inicial do Hacker News. Sua discussão pode ser lida aqui .

1. Introdução

O problema da distribuição uniforme de pontos em uma esfera tem uma história muito longa. Este é um dos problemas mais estudados na literatura matemática sobre geometria esférica. É de importância crítica em muitas áreas da matemática, física, química, incluindo métodos computacionais, teoria das aproximações, teoria das codificações, cristalografia, eletrostática, computação gráfica, morfologia de vírus e muitas outras.

Infelizmente, com exceção de alguns casos especiais (sólidos platônicos), é impossível distribuir perfeitamente pontos em uma esfera. Além disso, a solução do problema depende fortemente do critério usado para avaliar a uniformidade. Na prática, muitos critérios são usados, incluindo:

Embalagem e revestimento
Cascos convexos, células de Voronoi e triângulos de Delaunay
Kernels $s$ Rice Energy
Cubature e qualificadores

É muito importante esclarecer esse aspecto: geralmente não existe uma solução ótima para esse problema, porque uma solução ótima com base em um critério geralmente não é uma distribuição ótima de pontos para outros. Por exemplo, também descobriremos que a otimização de embalagens não cria necessariamente um casco convexo ideal e vice-versa.

Por uma questão de brevidade, neste post, consideraremos apenas dois critérios: a distância mínima de empacotamento e a malha convexa do casco / malha Delaunay (volume e área).

Na seção 1, mostramos como você pode alterar a grade canônica de Fibonacci para criar uma distribuição aprimorada de embalagens . Na Seção 2, mostramos como você pode alterar a grade canônica de Fibonacci para criar parâmetros aprimorados para cascos convexos (volume e área de superfície).

Seção 1. Otimização da distância da embalagem

Muitas vezes, esse problema é chamado de tarefa de Tamm em homenagem ao botânico Tems, que buscou uma explicação da estrutura da superfície dos grãos de pólen. O critério de embalagem exige que maximizemos a menor distância entre vizinhos para

$N$ pontos. Isso é

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

Este valor diminui com a velocidade.

$~ 1 / \ sqrt {N}$ , portanto, será útil determinar a distância normalizada, bem como o limite assintótico da distância normalizada, como

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

Grade de Fibonacci

Uma solução muito elegante modela os nós encontrados na natureza, por exemplo, a distribuição de sementes em um cone de girassol ou pinheiro. Esse fenômeno é chamado filotaxia em espiral. Coxeter mostrou que essas estruturas têm uma conexão fundamental com a série Fibonacci,

$F_k = \ {1, 1, 2, 3, 5, 8, 13, ... \}$ e a proporção áurea

$\ phi = (1+ \ sqrt {5}) / 2$ .

Na literatura, duas definições semelhantes do conjunto de pontos de uma grade esférica de Fibonacci são encontradas. A fonte é definida estritamente para

$N$ igual a um dos membros da série Fibonacci,

$F_m$ , e bem estudado em teoria dos números.

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

A segunda definição generaliza a fórmula para um valor arbitrário

$N$ e é usado em cálculos com mais frequência:

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

onde

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

Abaixo está um exemplo das mesmas grades de Fibonacci. Por transformação, você pode transformar esses conjuntos de pontos em espirais de Fibonacci que são bem conhecidas por nós.

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

Da mesma forma, esses conjuntos de pontos podem ser transferidos do quadrado da unidade

$[0, 1] ^ 2$ em uma esfera usando uma projeção isométrica cilíndrica:

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

Muitas versões diferentes do código Python podem ser encontradas no stackoverflow: Distribuição uniforme de pontos em uma esfera .

Mesmo que os conjuntos esféricos de Fibonacci não sejam globalmente a melhor distribuição de amostras em uma esfera (porque suas soluções não coincidem com as soluções para sólidos platônicos para

$n = $ 4,6,8,12,2$ ), eles têm excelentes propriedades de amostragem e são muito fáceis de construir em comparação com outros esquemas de amostragem esféricos mais complexos.

Como a transferência do quadrado da unidade para a superfície da esfera é realizada por uma projeção com preservação da área, pode-se esperar que, se os pontos de partida forem distribuídos uniformemente, eles também estejam razoavelmente bem distribuídos na superfície da esfera. No entanto, isso não significa que a distribuição será comprovadamente ótima.

Essa transferência sofre de dois problemas diferentes, mas inter-relacionados.

Em primeiro lugar, essa sobreposição é realizada mantendo a área, não a distância. Dado que, no nosso caso, a condição é maximizar a distância mínima entre pares entre pontos, tais condições e relacionamentos não serão necessariamente satisfeitos após a projeção.

O segundo problema é mais difícil de resolver do ponto de vista prático: a superposição tem dois pontos degenerados em cada pólo. Considere dois pontos que estão muito próximos do poste, mas diferem 180 graus em longitude. Em um único quadrado (e em uma projeção cilíndrica), eles correspondem a dois pontos muito distantes um do outro, no entanto, quando sobrepostos na superfície de uma esfera, podem ser conectados por um arco muito pequeno que passa pelo pólo norte. Devido a esse problema específico, muitas sobreposições em espiral não são ideais o suficiente.

A hélice esférica de Fibonacci obtida da equação 1 fornece o valor

$d_N ^ *$ para todos

$N$ isso é

$d ^ * = 2$ .

Malha 1

Uma versão mais comum (especialmente em sistemas de computador) que cria um valor melhor

$d ^ * = 3,09$ tem a forma:

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

Coloca os pontos nos pontos médios dos intervalos (de acordo com a regra do ponto médio na fórmula quadrática de Gauss), portanto, para

$n = 100$ , os valores da primeira coordenada serão os seguintes:

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

Grade 2.

A chave para melhorar ainda mais a Equação 2 é a constatação de que

$d ^ * _ N$ sempre corresponde à distância entre pontos

$t_0$ e

$t_3$ que estão nos polos. Ou seja, para melhorar

$d_N$ os pontos próximos aos pólos devem ser espaçados ainda mais.

Se definirmos a seguinte distribuição:

$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$ - curvas para vários valores.

$\ varepsilon = 0$ (azul);

$\ varepsilon = \ frac {1} {2}$ (laranja);

$\ varepsilon = \ frac {3} {2}$ (verde); e

$\ varepsilon = \ frac {5} {2}$ (vermelho) Você pode ver isso

$\ varepsilon = \ frac {5} {2}$ fornece resultados mais próximos dos resultados assintóticos. Ou seja, com

$N> $ 2$ A seguinte expressão simples gera resultados significativamente melhores.

$d ^ * = 3,29$ em comparação com a grade esférica canônica de Fibonacci:

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

Ou seja, com

$N = 100$ os valores da primeira coordenada serão iguais a:

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

Figura 1. Valores diferentes

$d_N ^ *$ em valores diferentes

$\ epsilon$ . Quanto maior o valor, mais otimizada a configuração. Nós vemos isso

$\ epsilon \ simeq 2.5$ fornece uma solução próxima do ideal.

Malha 3.

Como mencionado acima, um dos problemas mais sérios da distribuição uniforme de pontos em uma esfera é que a otimização da distribuição depende criticamente da função objetivo usada. Acontece. que quantidades locais como

$d_N ^ *$ às vezes quase “não perdoam erros” - um único ponto em uma posição insuficientemente ideal pode reduzir catastroficamente a avaliação de toda a distribuição de pontos.

No nosso caso, independentemente da magnitude

$N$ valor

$D_N ^ *$ geralmente definido pelos quatro pontos mais próximos de cada um dos polos, especialmente

$t_0$ e

$t_3$ . No entanto, também é conhecido sobre essa grade que o maior polígono de Voronoi está no polo. Então, tentando maximizar

$d_N$ dividindo os pontos polares originais em uma fileira, aumentamos ainda mais o vazio no polo! Portanto, apresentamos uma alternativa à grade 2, que geralmente é preferível porque não mostra um vazio tão grande perto dos polos.

É quase idêntico à grade 2, mas tem duas diferenças. Primeiro, ela usa

$\ varepsilon = 11/2$ às

$1 \ leq i \ leq N-2$ . Em segundo lugar, além desses

$N-2$ O primeiro e o último ponto estão localizados em cada um dos pólos.

Isto é:

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

Uma propriedade incrível desse método de construção é que, apesar de sua criação ter sido motivada pelo desejo de minimizar os vazios nos polos, ele realmente tem o melhor valor entre todos os métodos

$d_N$ e

$d ^ *$ com

$d ^ * = 3,31$ !

Ou seja, com

$N = 100$ os valores da primeira coordenada serão os seguintes:

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

Figura 2. Várias configurações de grade. A grade canônica de Fibonacci à esquerda. Observe que, embora a grade do meio

$d_N ^ *$ melhorado, no poste ela tem um vazio perceptível. A grade 3 não tem espaço no poste e tem o melhor valor

$d_N ^ *$ .

Comparação

Para valores grandes

$N$ esse valor

$d ^ *$ extremamente bem comparável com outros métodos, por exemplo, cúpulas geodésicas, que são baseadas em projeções trianguladas das faces dos sólidos platônicos na superfície de uma esfera. Não é de surpreender que as cúpulas geodésicas da mais alta qualidade sejam construídas com base no icosaedro ou dodecaedro.

Cúpulas geodésicas baseadas em icosaedro em vários valores

$N$ .

$\ 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 e 3,09 e 3,06 e 3,03 e 3,00 e 2,99 \\ \ hline \ end {array}$

Domos geodésicos baseados em dodecaedro para vários valores

$N$ .

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

Além disso, um icosaedro truncado correspondente à forma de fulereno

$C_ {60}$ tem apenas

$d ^ * = 3,125$ .

Ou seja, com

$N> 100$ a malha baseada na equação 3 é melhor que qualquer poliedro geodésico.

De acordo com os dados da primeira fonte na lista de referências abaixo, alguns dos métodos modernos, que geralmente são complexos e requerem programação recursiva e / ou dinâmica, possuem os seguintes indicadores.

$\ begin {array} {| lr |} \ hline \ text {Lattice 1} e 3,09 \\ \ hline \ text {Max Determinant} e 3,19 \\ \ hline \ text {Lattice 2} e 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}$

Conclusão da Seção 1

A grade 3, criada pela Equação 3, é uma modificação da grade canônica de Fibonacci, que fornece uma embalagem muito melhor para a distribuição dos pontos. Isso é

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

Seção 2. Otimização do casco convexo (malha Delaunay)

Na seção anterior, otimizamos a distribuição por

$d ^ * _ N$ No entanto, essas modificações pioram outros indicadores, por exemplo, o volume de um casco convexo (malha Delaunay). Esta seção descreve como distribuir pontos uniformemente em uma esfera de maneira a otimizar (maximizar) um indicador mais global, como o volume de um casco convexo.

Nós denotamos

$C_N$ como um casco convexo

$N$ pontos

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

fator de normalização incluído

$N$ , porque a discrepância absoluta diminui com a velocidade

$~ 1 / N$ .

Comportamento

$\ epsilon_N$ em vários

$N$ pode ser visto na Figura 3 (linha azul).

Para reduzir a incompatibilidade de volumes, deve-se notar que, apesar do uso de

$\ phi$ , a partir da lógica da seção dourada em

$N \ rightarrow \ infty$ isso não significa necessariamente que seja o melhor valor para a final

$N$ . Falando cientificamente, podemos dizer que precisamos levar em consideração a influência da correção do membro.

Vamos resumir a equação 1 da seguinte maneira:

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

onde definimos

$g (n)$ como

$g (n) = \ begin {cases} 3- \ phi, & \ text {se $ k $ for par} \\ \ phi, & \ text {se $ k $ for ímpar} \ end {cases} \ tag {5}$

onde

$k = \ esquerda \ piso \ textrm {log} _ {\ phi} (\ frac {n} {1.5}) \ direita \ rfloor = \ esquerda \ piso \ frac {\ ln (n / 1.5)} {\ ln \ phi} \ right \ r $ pis$

onde

$\ piso x x piso$ - a função de arredondar para o número inteiro mais próximo abaixo.

A Figura 3 mostra a diferença de volume otimizada para metade dos valores.

$N$ .

A razão para isso é um fato pouco conhecido: todos os números

$x$ satisfazendo a transformação especial de Mobius, a partir da irracionalidade, são equivalentes

$\ phi$ .

$x = \ frac {a \ phi + b} {c \ phi + d}, \ quad \ textrm {para todos os números inteiros} \; \; a, b, c, d \; \ textrm {tal que} | ad-bc | = 1$

Portanto, a razão pela qual

$\ phi$ e

$3- \ phi$ se encaixam tão bem, é que

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

Figura 3. A incompatibilidade entre o volume do casco convexo dos pontos e o volume da esfera unitária. Lembre-se de que quanto menor, melhor. A figura mostra que o modelo híbrido (linha laranja) baseado em

$\ phi$ e

$3- \ phi$ , fornece uma melhor distribuição de pontos do que a grade canônica de Fibonacci (linha azul).

Para a metade restante, primeiro definimos uma série auxiliar

$A_N$ sendo uma variação da série Fibonacci

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

Isso é

$A_N = 1,4,5,9,14,23,37,60,97.157.254.411, ...$

Todas as frações desta série possuem frações contínuas elegantes e, no limite, convergem para

$\ phi$ . Por exemplo

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

Agora podemos generalizar completamente

$g (n)$ da seguinte maneira:

$g (N) = \ begin {cases} 3- \ phi, & \ text {se $ k $ for par} \\ A_ {j + 1} / A_j, & \ text {se $ k $ for ímpar, onde $ j = (k + 7) / 2 $} \ end {cases} \ tag {6}$

A tabela abaixo mostra os valores

$g (N)$ para vários

$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} e 3- \ phi & \ frac {97} {60} e 3- \ phi \\ \ hline \ end {array}$

A Figura 4 mostra que, com relação ao volume do casco convexo, essa nova distribuição é melhor que a grade canônica para todos os valores

$n$

Figura 4. A incompatibilidade entre o volume do casco convexo e o volume da esfera unitária. Quanto menor o valor, melhor. Isso nos diz que o novo método proposto (linha verde) fornece constantemente uma melhor distribuição do que a grade canônica de Fibonacci (linha azul).

Figura 5. Comparação visual da malha canônica (esquerda) com a nova malha modificada (direita) com n = 35 en = 150. Visualmente, as diferenças são quase imperceptíveis. No entanto, em condições que exigem eficiência máxima, a versão modificada (à direita) fornece uma pequena, porém quantificável, melhora no volume e na área de superfície do casco convexo.

Curiosamente, essa distribuição também é insignificante, mas reduz constantemente a incompatibilidade entre a área de superfície do casco convexo e a área de uma única esfera. Isso é mostrado na Figura 6.

Figura 5. Incompatibilidade normalizada de áreas entre a área de superfície de um casco convexo (malha de Delaunay) e a área de superfície de uma única esfera. Quanto menor o valor, melhor. Isso mostra que a nova modificação proposta (pontos verdes) demonstra uma pequena mas constante diminuição da diferença nas áreas de superfície em comparação com a grade canônica de Fibonacci (pontos azuis)

Conclusão da Seção 2

A grade correspondente à Equação 6 é uma modificação da grade canônica de Fibonacci, criando uma distribuição significativamente melhor de pontos com base no volume e na área superficial do casco convexo (grade Delaunay).

Fontes

Distribuição uniforme de pontos em uma esfera

1. Introdução

Seção 1. Otimização da distância da embalagem

Seção 2. Otimização do casco convexo (malha Delaunay)

More articles: