Distribuindo uniformemente n pontos em uma esfera

121

Preciso de um algoritmo que me dê posições em torno de uma esfera para N pontos (menos de 20, provavelmente) que os espalhe vagamente. Não há necessidade de "perfeição", mas eu só preciso para que nenhum deles fique agrupado.

  • Essa pergunta forneceu um bom código, mas não consegui encontrar uma maneira de fazer esse uniforme, pois parecia 100% aleatório.
  • Esta postagem de blog recomendada tinha duas maneiras de permitir a entrada de número de pontos na esfera, mas o algoritmo de Saff e Kuijlaars está exatamente em psuedocódigo que eu poderia transcrever e o exemplo de código que encontrei continha "nó [k]", que não pude ver explicado e arruinado essa possibilidade. O segundo exemplo de blog foi o Golden Section Spiral, que me deu resultados estranhos e agrupados, sem uma forma clara de definir um raio constante.
  • Este algoritmo de esta questão parece que ele poderia funcionar, mas não posso juntar o que está nessa página em psuedocode ou qualquer coisa.

Alguns outros tópicos de perguntas que encontrei falam de distribuição uniforme aleatória, o que adiciona um nível de complexidade com o qual não estou preocupado. Peço desculpas por esta ser uma pergunta tão boba, mas eu queria mostrar que eu realmente procurei muito e ainda não consegui.

Então, o que estou procurando é um pseudocódigo simples para distribuir uniformemente N pontos em torno de uma esfera unitária, que retorna em coordenadas esféricas ou cartesianas. Melhor ainda se puder distribuir com um pouco de randomização (pense em planetas ao redor de uma estrela, decentemente espalhados, mas com espaço para liberdade).

Befall
fonte
O que quer dizer "com um pouco de randomização"? Você quer dizer perturbações em algum sentido?
ninjagecko
32
OP está confuso. O que ele está procurando é colocar n pontos em uma esfera, de modo que a distância mínima entre dois pontos seja a maior possível. Isso dará aos pontos a aparência de estarem "uniformemente distribuídos" por toda a esfera. Isso não tem nenhuma relação com a criação de uma distribuição aleatória uniforme em uma esfera, que é o assunto de muitos desses links e sobre o que muitas das respostas a seguir estão falando.
BlueRaja - Danny Pflughoeft
1
20 não são muitos pontos para colocar em uma esfera se você não quiser que pareçam apenas aleatórios.
John Alexiou
2
Esta é uma maneira de fazer isso (tem exemplos de código): pdfs.semanticscholar.org/97a6/… (parece que usa cálculos de força de repulsão)
trusktr
1
Claro que para valores em N em {4, 6, 8, 12, 20} existem soluções exatas nas quais a distância de cada ponto a (cada um dos) seus vizinhos mais próximos é uma constante para todos os pontos e todos os vizinhos mais próximos.
dmckee --- gatinho ex-moderador de

Respostas:

13

Em este exemplo de código node[k] é apenas o nó k. Você está gerando uma matriz de N pontos e node[k]é o k-ésimo (de 0 a N-1). Se isso é tudo o que está confundindo você, espero que você possa usá-lo agora.

(em outras palavras, ké uma matriz de tamanho N que é definida antes do início do fragmento de código e que contém uma lista dos pontos).

Como alternativa , com base na outra resposta aqui (e usando Python):

> cat ll.py
from math import asin
nx = 4; ny = 5
for x in range(nx):
    lon = 360 * ((x+0.5) / nx)
    for y in range(ny):                                                         
        midpt = (y+0.5) / ny                                                    
        lat = 180 * asin(2*((y+0.5)/ny-0.5))                                    
        print lon,lat                                                           
> python2.7 ll.py                                                      
45.0 -166.91313924                                                              
45.0 -74.0730322921                                                             
45.0 0.0                                                                        
45.0 74.0730322921                                                              
45.0 166.91313924                                                               
135.0 -166.91313924                                                             
135.0 -74.0730322921                                                            
135.0 0.0                                                                       
135.0 74.0730322921                                                             
135.0 166.91313924                                                              
225.0 -166.91313924                                                             
225.0 -74.0730322921                                                            
225.0 0.0                                                                       
225.0 74.0730322921                                                             
225.0 166.91313924
315.0 -166.91313924
315.0 -74.0730322921
315.0 0.0
315.0 74.0730322921
315.0 166.91313924

Se você plotar isso, verá que o espaçamento vertical é maior perto dos pólos, de modo que cada ponto está situado aproximadamente na mesma área total do espaço (perto dos pólos há menos espaço "horizontalmente", então dá mais "verticalmente" )

Isso não é o mesmo que todos os pontos tendo aproximadamente a mesma distância de seus vizinhos (que é o que eu acho que seus links estão falando), mas pode ser suficiente para o que você deseja e melhora simplesmente fazendo uma grade lat / lon uniforme .

Andrew Cooke
fonte
bom, é bom ver uma solução matemática. Eu estava pensando em usar uma hélice e separação do comprimento do arco. Ainda não estou certo de como obter a solução ideal, o que é um problema interessante.
robert king
você viu que eu editei minha resposta para incluir uma explicação do nó [k] no topo? Acho que isso pode ser tudo de que você precisa ...
Andrew Cooke
Maravilhoso, obrigado pela explicação. Vou tentar mais tarde, pois não tenho tempo no momento, mas muito obrigado por me ajudar. Eu vou deixar você saber como isso acaba funcionando para meus propósitos. ^^
Befall,
Usar o método Spiral atende perfeitamente às minhas necessidades, muito obrigado pela ajuda e esclarecimento. :)
Befall,
13
O link parece morto.
Scheintod
140

O algoritmo da esfera de Fibonacci é ótimo para isso. É rápido e dá resultados que à primeira vista enganam facilmente o olho humano. Você pode ver um exemplo feito com processamento que mostrará o resultado ao longo do tempo conforme os pontos são adicionados. Aqui está outro ótimo exemplo interativo feito por @gman. E aqui está uma implementação simples em python.

import math


def fibonacci_sphere(samples=1):

    points = []
    phi = math.pi * (3. - math.sqrt(5.))  # golden angle in radians

    for i in range(samples):
        y = 1 - (i / float(samples - 1)) * 2  # y goes from 1 to -1
        radius = math.sqrt(1 - y * y)  # radius at y

        theta = phi * i  # golden angle increment

        x = math.cos(theta) * radius
        z = math.sin(theta) * radius

        points.append((x, y, z))

    return points

1000 amostras fornecem isso:

insira a descrição da imagem aqui

Fnord
fonte
uma variável n é chamada ao definir phi: phi = ((i + rnd)% n) * incremento. N = faz uma amostra?
Andrew Staroscik
@AndrewStaroscik sim! Quando escrevi o código pela primeira vez, usei "n" como variável e alterei o nome mais tarde, mas não fiz a devida diligência. Obrigado por pegar isso!
Fnord
4
@Xarbrough, o código fornece pontos ao redor de uma esfera unitária, portanto, basta multiplicar cada ponto por qualquer escalar que você deseja para o raio.
Fnord
2
@Fnord: Podemos fazer isso para dimensões superiores?
pikachuchameleon
108

O método da espiral dourada

Você disse que não conseguiria fazer o método da espiral dourada funcionar e isso é uma pena, porque é muito, muito bom. Eu gostaria de dar a você um entendimento completo disso, para que talvez você possa entender como evitar que isso seja "amontoado".

Portanto, aqui está uma maneira rápida e não aleatória de criar uma rede que seja aproximadamente correta; como discutido acima, nenhuma rede será perfeita, mas isso pode ser bom o suficiente. É comparado a outros métodos, por exemplo, em BendWavy.org, mas tem uma aparência bonita e bonita, bem como uma garantia de espaçamento uniforme no limite.

Primer: espirais de girassol no disco da unidade

Para entender esse algoritmo, primeiro convido você a examinar o algoritmo 2D da espiral do girassol. Isso se baseia no fato de que o número mais irracional é a proporção áurea (1 + sqrt(5))/2e se alguém emitir pontos pela abordagem "fique no centro, gire uma proporção áurea de voltas inteiras, em seguida, emita outro ponto nessa direção", naturalmente se constrói um espiral que, conforme você chega a um número cada vez maior de pontos, se recusa a ter 'barras' bem definidas sobre as quais os pontos se alinham. (Nota 1.)

O algoritmo para espaçamento uniforme em um disco é,

from numpy import pi, cos, sin, sqrt, arange
import matplotlib.pyplot as pp

num_pts = 100
indices = arange(0, num_pts, dtype=float) + 0.5

r = sqrt(indices/num_pts)
theta = pi * (1 + 5**0.5) * indices

pp.scatter(r*cos(theta), r*sin(theta))
pp.show()

e produz resultados semelhantes a (n = 100 e n = 1000):

insira a descrição da imagem aqui

Espaçando os pontos radialmente

O mais estranho é a fórmula r = sqrt(indices / num_pts); como eu cheguei a esse? (Nota 2.)

Bem, estou usando a raiz quadrada aqui porque quero que eles tenham um espaçamento de área uniforme ao redor do disco. Isso é o mesmo que dizer que no limite de N grande eu quero uma pequena região R ∈ ( r , r + d r ), Θ ∈ ( θ , θ + d θ ) para conter um número de pontos proporcionais à sua área, que é r d r d θ . Agora, se fingirmos que estamos falando sobre uma variável aleatória aqui, isso tem uma interpretação direta, dizendo que a densidade de probabilidade conjunta para ( R , Θ ) é apenas crpara alguma constante c . A normalização no disco unitário então forçaria c = 1 / π.

Agora, deixe-me apresentar um truque. Vem da teoria da probabilidade, onde é conhecido como amostragem do CDF inverso : suponha que você queira gerar uma variável aleatória com uma densidade de probabilidade f ( z ) e você tem uma variável aleatória U ~ Uniforme (0, 1), assim como sai de random()na maioria das linguagens de programação. Como você faz isso?

  1. Primeiro, transforme sua densidade em uma função de distribuição cumulativa ou CDF, que chamaremos de F ( z ). Um CDF, lembre-se, aumenta monotonicamente de 0 a 1 com a derivada f ( z ).
  2. Em seguida, calcule a função inversa F -1 ( z ) do CDF .
  3. Você descobrirá que Z = F -1 ( U ) é distribuído de acordo com a densidade alvo. (Nota 3).

Agora, o truque da espiral de proporção áurea espaça os pontos em um padrão bem uniforme para θ, então vamos integrar isso; para o disco unitário, ficamos com F ( r ) = r 2 . Portanto, a função inversa é F -1 ( u ) = u 1/2 e, portanto, geraríamos pontos aleatórios no disco em coordenadas polares com r = sqrt(random()); theta = 2 * pi * random().

Agora, em vez de amostrar aleatoriamente essa função inversa, estamos amostrando-a uniformemente , e o bom da amostragem uniforme é que nossos resultados sobre como os pontos são espalhados no limite de N grande se comportarão como se tivéssemos amostrado aleatoriamente. Essa combinação é o truque. Em vez de random()usarmos (arange(0, num_pts, dtype=float) + 0.5)/num_pts, de modo que, digamos, se quisermos amostrar 10 pontos eles são r = 0.05, 0.15, 0.25, ... 0.95. Amostramos uniformemente r para obter espaçamento de área igual e usamos o incremento do girassol para evitar horríveis “barras” de pontos na saída.

Agora fazendo o girassol em uma esfera

As mudanças que precisamos fazer para pontilhar a esfera com pontos envolvem apenas trocar as coordenadas polares por coordenadas esféricas. A coordenada radial é claro não entra nisto porque estamos em uma esfera unitária. Para manter as coisas um pouco mais consistentes aqui, embora eu tenha sido treinado como um físico, usarei coordenadas matemáticas onde 0 ≤ φ ≤ π é a latitude descendo do pólo e 0 ≤ θ ≤ 2π é a longitude. Portanto, a diferença acima é que basicamente substituímos a variável r por φ .

Nosso elemento de área, que era r d r d θ , agora se torna o não muito mais complicado sen ( φ ) d φ d θ . Portanto, nossa densidade de junta para espaçamento uniforme é sin ( φ ) / 4π. Integrando fora de θ , encontramos f ( φ ) = sin ( φ ) / 2, assim F ( φ ) = (1 - cos ( φ )) / 2. Invertendo isso, podemos ver que uma variável aleatória uniforme se pareceria com acos (1 - 2 u ), mas nós amostramos uniformemente em vez de aleatoriamente, então usamos φ k = acos (1 - 2 ( k+ 0,5) / N ). E o resto do algoritmo está apenas projetando isso nas coordenadas x, y e z:

from numpy import pi, cos, sin, arccos, arange
import mpl_toolkits.mplot3d
import matplotlib.pyplot as pp

num_pts = 1000
indices = arange(0, num_pts, dtype=float) + 0.5

phi = arccos(1 - 2*indices/num_pts)
theta = pi * (1 + 5**0.5) * indices

x, y, z = cos(theta) * sin(phi), sin(theta) * sin(phi), cos(phi);

pp.figure().add_subplot(111, projection='3d').scatter(x, y, z);
pp.show()

Novamente, para n = 100 en = 1000, os resultados se parecem com: insira a descrição da imagem aqui insira a descrição da imagem aqui

Mais pesquisa

Eu queria dar uma mensagem para o blog de Martin Roberts. Observe que acima eu criei um deslocamento dos meus índices adicionando 0,5 a cada índice. Isso era apenas visualmente atraente para mim, mas descobri que a escolha do deslocamento é muito importante e não é constante ao longo do intervalo e pode significar obter até 8% a mais de precisão na embalagem, se escolhido corretamente. Também deve haver uma maneira de fazer com que sua sequência R 2 cubra uma esfera e seria interessante ver se isso também produziu uma boa cobertura uniforme, talvez como está, mas talvez precise ser, digamos, tirada de apenas metade de o quadrado da unidade é cortado na diagonal ou assim e esticado para obter um círculo.

Notas

  1. Essas "barras" são formadas por aproximações racionais de um número, e as melhores aproximações racionais de um número vêm de sua expressão de fração contínua, z + 1/(n_1 + 1/(n_2 + 1/(n_3 + ...)))onde zé um inteiro e n_1, n_2, n_3, ...é uma sequência finita ou infinita de inteiros positivos:

    def continued_fraction(r):
        while r != 0:
            n = floor(r)
            yield n
            r = 1/(r - n)

    Como a parte da fração 1/(...)está sempre entre zero e um, um grande número inteiro na fração contínua permite uma aproximação racional particularmente boa: "um dividido por algo entre 100 e 101" é melhor do que "um dividido por algo entre 1 e 2." O número mais irracional é, portanto, aquele que é 1 + 1/(1 + 1/(1 + ...))e não tem aproximações racionais particularmente boas; pode-se resolver φ = 1 + 1 / φ multiplicando por φ para obter a fórmula da razão áurea.

  2. Para pessoas que não estão tão familiarizadas com o NumPy - todas as funções são "vetorizadas", de modo que sqrt(array)é o mesmo que outras linguagens podem escrever map(sqrt, array). Portanto, este é um sqrtaplicativo componente por componente . O mesmo também se aplica à divisão por um escalar ou adição com escalares - esses se aplicam a todos os componentes em paralelo.

  3. A prova é simples quando você sabe que esse é o resultado. Se você perguntar qual é a probabilidade de z < Z < z + d z , isso é o mesmo que perguntar qual é a probabilidade de z < F -1 ( U ) < z + d z , aplicar F a todas as três expressões observando que é uma função monotonicamente crescente, portanto, F ( z ) < U < F ( z + d z ), expanda o lado direito para encontrar F ( z ) + f ( z ) d z , e como U é uniforme, essa probabilidade é apenas f ( z ) d z, conforme prometido.

CR Drost
fonte
4
Não sei por que isso está tão baixo, este é de longe o melhor método rápido para fazer isso.
whn
2
@snb, obrigado pelas amáveis ​​palavras! está tão baixo em parte porque é muito, muito mais jovem do que todas as outras respostas aqui. Estou surpreso por ele estar indo tão bem quanto antes.
CR Drost de
Uma pergunta que permanece para mim é: quantos pontos n preciso distribuir para uma determinada distância máxima entre dois pontos quaisquer?
Felix D.
1
@FelixD. Isso soa como uma pergunta que pode ficar muito complicada muito rapidamente, especialmente se você começar a usar, digamos, distâncias de grande círculo em vez de distâncias euclidianas. Mas talvez eu possa responder a uma pergunta simples, se alguém converter os pontos na esfera em seu diagrama de Voronoi, pode-se descrever cada célula de Voronoi como tendo aproximadamente área 4π / N e pode-se converter isso para uma distância característica fingindo que é um círculo em vez do que um losango, πr² = 4π / N. Então, r = 2 / √ (N).
CR Drost
2
Usar o teorema da amostragem com entrada realmente uniforme em vez de aleatoriamente uniforme é uma daquelas coisas que me faz dizer "Bem, por que o # $% & não pensei nisso?" . Agradável.
dmckee --- gatinho ex-moderador
86

Isso é conhecido como pontos de empacotamento em uma esfera, e não há uma solução geral perfeita (conhecida). No entanto, existem muitas soluções imperfeitas. Os três mais populares parecem ser:

  1. Crie uma simulação . Trate cada ponto como um elétron restrito a uma esfera e, em seguida, execute uma simulação por um determinado número de etapas. A repulsão dos elétrons naturalmente tenderá o sistema a um estado mais estável, onde os pontos estão tão distantes um do outro quanto eles podem chegar.
  2. Rejeição do hipercubo . Esse método que parece sofisticado é realmente muito simples: você escolhe uniformemente os pontos (muito mais do que neles) dentro do cubo ao redor da esfera e, em seguida, rejeita os pontos fora da esfera. Trate os pontos restantes como vetores e normalize-os. Estas são as suas "amostras" - escolha n-as usando algum método (aleatoriamente, ganancioso, etc.).
  3. Aproximações espirais . Você traça uma espiral ao redor de uma esfera e distribui uniformemente os pontos ao redor da espiral. Por causa da matemática envolvida, eles são mais complicados de entender do que a simulação, mas muito mais rápidos (e provavelmente envolvem menos código). O mais popular parece ser por Saff, et al .

Um monte mais informações sobre este problema pode ser encontrada aqui

BlueRaja - Danny Pflughoeft
fonte
Estarei examinando a tática espiral que andrew cooke postou abaixo, no entanto, você poderia esclarecer a diferença entre o que eu quero e o que é "distribuição aleatória uniforme"? Isso é apenas colocação 100% aleatória de pontos em uma esfera para que sejam colocados uniformemente? Obrigado pela ajuda. :)
Befall
4
@Befall: "distribuição aleatória uniforme" refere-se à distribuição de probabilidade ser uniforme - significa que, ao escolher um ponto aleatório na esfera, cada ponto tem uma probabilidade igual de ser escolhido. Não tem nada a ver com a distribuição espacial final dos pontos e, portanto, nada tem a ver com sua pergunta.
BlueRaja - Danny Pflughoeft
Ahhh, ok, muito obrigado. Procurar minha pergunta levou a uma tonelada de respostas para ambos, e eu não conseguia entender o que era inútil para mim.
Befall,
Para ser claro, todo ponto tem probabilidade zero de ser escolhido. A proporção das probabilidades de que o ponto pertencerá a quaisquer duas áreas na superfície da esfera é igual à proporção das superfícies.
AturSams
2
O último link está morto
Felix D.
10

O que você está procurando é chamado de cobertura esférica . O problema da cobertura esférica é muito difícil e as soluções são desconhecidas, exceto por um pequeno número de pontos. Uma coisa que se sabe com certeza é que dados n pontos em uma esfera, sempre existem dois pontos de distânciad = (4-csc^2(\pi n/6(n-2)))^(1/2) ou mais próximos.

Se você deseja um método probabilístico para gerar pontos uniformemente distribuídos em uma esfera, é fácil: gere pontos no espaço uniformemente pela distribuição Gaussiana (é construído em Java, não é difícil encontrar o código para outras linguagens). Então, no espaço tridimensional, você precisa de algo como

Random r = new Random();
double[] p = { r.nextGaussian(), r.nextGaussian(), r.nextGaussian() };

Em seguida, projete o ponto na esfera normalizando sua distância da origem

double norm = Math.sqrt( (p[0])^2 + (p[1])^2 + (p[2])^2 ); 
double[] sphereRandomPoint = { p[0]/norm, p[1]/norm, p[2]/norm };

A distribuição gaussiana em n dimensões é esfericamente simétrica, então a projeção na esfera é uniforme.

Claro, não há garantia de que a distância entre quaisquer dois pontos em uma coleção de pontos gerados uniformemente será limitada abaixo, então você pode usar a rejeição para impor quaisquer condições que você possa ter: provavelmente é melhor gerar toda a coleção e então rejeite a coleção inteira se necessário. (Ou use "rejeição antecipada" para rejeitar toda a coleção que você gerou até agora; apenas não mantenha alguns pontos e descartar outros.) Você pode usar a fórmula ddada acima, menos alguma folga, para determinar a distância mínima entre pontos abaixo dos quais você rejeitará um conjunto de pontos. Você terá que calcular n escolher 2 distâncias, e a probabilidade de rejeição dependerá da folga; é difícil dizer como, então execute uma simulação para ter uma ideia das estatísticas relevantes.

Edward Doolittle
fonte
Votos positivos para as expressões de distância máxima mínima. Útil para colocar limites no número de pontos que você deseja usar. Uma referência a uma fonte autorizada para isso seria bom, no entanto.
dmckee --- ex-moderador gatinho
6

Esta resposta é baseada na mesma 'teoria' que é bem delineada por esta resposta

Estou adicionando esta resposta como: - Além disso, é muito difícil 'grocar' como diferenciar entre as outras opções sem qualquer imagem, então aqui está a aparência desta opção (abaixo), e a implementação pronta para execução que vai com isso.
- Nenhuma das outras opções se encaixa na necessidade de 'uniformidade' 'exata' (ou não obviamente). (Observando para obter a distribuição parecida com um planeta parecendo um comportamento particularmente desejado na pergunta original, você apenas rejeita da lista finita dos k pontos criados uniformemente aleatoriamente (aleatoriamente em relação à contagem do índice nos k itens de volta). -
- O mais próximo outra implicação forçou você a decidir o 'N' por 'eixo angular', vs. apenas 'um valor de N' em ambos os valores do eixo angular (que em contagens baixas de N é muito complicado saber o que pode ou não importar ( por exemplo, você quer '5' pontos - divirta-se))

com N em 20:

insira a descrição da imagem aqui
e então N em 80: insira a descrição da imagem aqui


aqui está o código python3 pronto para executar, em que a emulação é a mesma fonte: " http://web.archive.org/web/20120421191837/http://www.cgafaq.info/wiki/Evenly_distributed_points_on_sphere " encontrada por outros . (A plotagem que incluí, que dispara quando executada como 'principal', foi retirada de: http://www.scipy.org/Cookbook/Matplotlib/mplot3D )

from math import cos, sin, pi, sqrt

def GetPointsEquiAngularlyDistancedOnSphere(numberOfPoints=45):
    """ each point you get will be of form 'x, y, z'; in cartesian coordinates
        eg. the 'l2 distance' from the origion [0., 0., 0.] for each point will be 1.0 
        ------------
        converted from:  http://web.archive.org/web/20120421191837/http://www.cgafaq.info/wiki/Evenly_distributed_points_on_sphere ) 
    """
    dlong = pi*(3.0-sqrt(5.0))  # ~2.39996323 
    dz   =  2.0/numberOfPoints
    long =  0.0
    z    =  1.0 - dz/2.0
    ptsOnSphere =[]
    for k in range( 0, numberOfPoints): 
        r    = sqrt(1.0-z*z)
        ptNew = (cos(long)*r, sin(long)*r, z)
        ptsOnSphere.append( ptNew )
        z    = z - dz
        long = long + dlong
    return ptsOnSphere

if __name__ == '__main__':                
    ptsOnSphere = GetPointsEquiAngularlyDistancedOnSphere( 80)    

    #toggle True/False to print them
    if( True ):    
        for pt in ptsOnSphere:  print( pt)

    #toggle True/False to plot them
    if(True):
        from numpy import *
        import pylab as p
        import mpl_toolkits.mplot3d.axes3d as p3

        fig=p.figure()
        ax = p3.Axes3D(fig)

        x_s=[];y_s=[]; z_s=[]

        for pt in ptsOnSphere:
            x_s.append( pt[0]); y_s.append( pt[1]); z_s.append( pt[2])

        ax.scatter3D( array( x_s), array( y_s), array( z_s) )                
        ax.set_xlabel('X'); ax.set_ylabel('Y'); ax.set_zlabel('Z')
        p.show()
        #end

testado em contagens baixas (N em 2, 5, 7, 13, etc) e parece funcionar 'bem'

Matt S.
fonte
5

Experimentar:

function sphere ( N:float,k:int):Vector3 {
    var inc =  Mathf.PI  * (3 - Mathf.Sqrt(5));
    var off = 2 / N;
    var y = k * off - 1 + (off / 2);
    var r = Mathf.Sqrt(1 - y*y);
    var phi = k * inc;
    return Vector3((Mathf.Cos(phi)*r), y, Mathf.Sin(phi)*r); 
};

A função acima deve ser executada em loop com total de N loop e iteração de corrente de loop k.

É baseado em um padrão de sementes de girassol, exceto que as sementes de girassol são curvadas em uma meia cúpula e novamente em uma esfera.

Aqui está uma foto, exceto que coloquei a câmera no meio da esfera para que pareça 2d em vez de 3d porque a câmera está à mesma distância de todos os pontos. http://3.bp.blogspot.com/-9lbPHLccQHA/USXf88_bvVI/AAAAAAAAADY/j7qhQsSZsA8/s640/sphere.jpg

aliential
fonte
2

Healpix resolve um problema intimamente relacionado (pixelização da esfera com pixels de área igual):

http://healpix.sourceforge.net/

Provavelmente é um exagero, mas talvez depois de olhar você perceberá que algumas de suas outras propriedades interessantes são interessantes para você. É muito mais do que apenas uma função que gera uma nuvem de pontos.

Aterrissei aqui tentando encontrá-lo novamente; o nome "healpix" não evoca exatamente esferas ...

Andrew Wagner
fonte
1

com um pequeno número de pontos, você pode executar uma simulação:

from random import random,randint
r = 10
n = 20
best_closest_d = 0
best_points = []
points = [(r,0,0) for i in range(n)]
for simulation in range(10000):
    x = random()*r
    y = random()*r
    z = r-(x**2+y**2)**0.5
    if randint(0,1):
        x = -x
    if randint(0,1):
        y = -y
    if randint(0,1):
        z = -z
    closest_dist = (2*r)**2
    closest_index = None
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            p1,p2 = points[i],points[j]
            x1,y1,z1 = p1
            x2,y2,z2 = p2
            d = (x1-x2)**2+(y1-y2)**2+(z1-z2)**2
            if d < closest_dist:
                closest_dist = d
                closest_index = i
    if simulation % 100 == 0:
        print simulation,closest_dist
    if closest_dist > best_closest_d:
        best_closest_d = closest_dist
        best_points = points[:]
    points[closest_index]=(x,y,z)


print best_points
>>> best_points
[(9.921692138442777, -9.930808529773849, 4.037839326088124),
 (5.141893371460546, 1.7274947332807744, -4.575674650522637),
 (-4.917695758662436, -1.090127967097737, -4.9629263893193745),
 (3.6164803265540666, 7.004158551438312, -2.1172868271109184),
 (-9.550655088997003, -9.580386054762917, 3.5277052594769422),
 (-0.062238110294250415, 6.803105171979587, 3.1966101417463655),
 (-9.600996012203195, 9.488067284474834, -3.498242301168819),
 (-8.601522086624803, 4.519484132245867, -0.2834204048792728),
 (-1.1198210500791472, -2.2916581379035694, 7.44937337008726),
 (7.981831370440529, 8.539378431788634, 1.6889099589074377),
 (0.513546008372332, -2.974333486904779, -6.981657873262494),
 (-4.13615438946178, -6.707488383678717, 2.1197605651446807),
 (2.2859494919024326, -8.14336582650039, 1.5418694699275672),
 (-7.241410895247996, 9.907335206038226, 2.271647103735541),
 (-9.433349952523232, -7.999106443463781, -2.3682575660694347),
 (3.704772125650199, 1.0526567864085812, 6.148581714099761),
 (-3.5710511242327048, 5.512552040316693, -3.4318468250897647),
 (-7.483466337225052, -1.506434920354559, 2.36641535124918),
 (7.73363824231576, -8.460241422163824, -1.4623228616326003),
 (10, 0, 0)]
robert king
fonte
para melhorar a minha resposta, você deve alterar close_index = i para mais próximo_index = randchoice (i, j)
robert king
1

Pegue os dois maiores fatores do seu N, se N==20então os dois maiores fatores são {5,4}, ou, mais geralmente {a,b}. Calcular

dlat  = 180/(a+1)
dlong = 360/(b+1})

Ponha seu primeiro ponto em {90-dlat/2,(dlong/2)-180}, seu segundo em {90-dlat/2,(3*dlong/2)-180}, seu terceiro em {90-dlat/2,(5*dlong/2)-180}, até que você tenha dado a volta ao mundo uma vez, quando então você tem que fazer {75,150}quando for ao lado {90-3*dlat/2,(dlong/2)-180}.

Obviamente estou trabalhando isso em graus na superfície da Terra esférica, com as convenções usuais para traduzir +/- para N / S ou E / W. E, obviamente, isso dá a você uma distribuição completamente não aleatória, mas é uniforme e os pontos não estão agrupados.

Para adicionar algum grau de aleatoriedade, você pode gerar 2 normalmente distribuídos (com média 0 e dev padrão de {dlat / 3, dlong / 3} conforme apropriado) e adicioná-los aos seus pontos uniformemente distribuídos.

Marca de alto desempenho
fonte
5
isso ficaria muito melhor se você trabalhasse em sin (lat) ao invés de lat. do jeito que está, você terá muitos amontoados perto dos pólos.
Andrew Cooke
1

editar: Isso não responde à pergunta que o OP pretendia fazer, deixando-o aqui para o caso de as pessoas acharem que é útil de alguma forma.

Usamos a regra de multiplicação da probabilidade, combinada com infinitosimais. Isso resulta em 2 linhas de código para alcançar o resultado desejado:

longitude: φ = uniform([0,2pi))
azimuth:   θ = -arcsin(1 - 2*uniform([0,1]))

(definido no seguinte sistema de coordenadas :)

insira a descrição da imagem aqui

Sua linguagem normalmente tem um primitivo de número aleatório uniforme. Por exemplo, em python, você pode usar random.random()para retornar um número no intervalo [0,1). Você pode multiplicar esse número por k para obter um número aleatório no intervalo [0,k). Assim, em python, uniform([0,2pi))significaria random.random()*2*math.pi.


Prova

Agora não podemos atribuir θ uniformemente, caso contrário, ficaríamos aglomerados nos pólos. Queremos atribuir probabilidades proporcionais à área de superfície da cunha esférica (o θ neste diagrama é na verdade φ):

insira a descrição da imagem aqui

Um deslocamento angular dφ no equador resultará em um deslocamento de dφ * r. Qual será esse deslocamento em um azimute arbitrário θ? Bem, o raio do eixo z é r*sin(θ), então o comprimento de arco dessa "latitude" que cruza a cunha é dφ * r*sin(θ). Assim, calculamos a distribuição cumulativa da área a ser amostrada, integrando a área da fatia do polo sul ao polo norte.

insira a descrição da imagem aqui(onde coisas = dφ*r)

Agora tentaremos obter o inverso do CDF para obter uma amostra dele: http://en.wikipedia.org/wiki/Inverse_transform_sampling

Primeiro, normalizamos dividindo nosso quase-CDF por seu valor máximo. Isso tem o efeito colateral de cancelar dφ e r.

azimuthalCDF: cumProb = (sin(θ)+1)/2 from -pi/2 to pi/2

inverseCDF: θ = -sin^(-1)(1 - 2*cumProb)

Portanto:

let x by a random float in range [0,1]
θ = -arcsin(1-2*x)
ninjagecko
fonte
isso não é equivalente à opção que ele descartou como sendo "100% randomizado"? meu entendimento é que ele deseja que eles tenham um espaçamento mais uniforme do que uma distribuição aleatória uniforme.
Andrew Cooke
@ BlueRaja-DannyPflughoeft: Hmm, é justo. Acho que não li a pergunta tão cuidadosamente como deveria. Deixo isso aqui de qualquer maneira, caso outros considerem útil. Obrigado por apontar isso.
ninjagecko
1

OU ... para colocar 20 pontos, calcule os centros das faces icosaedronais. Por 12 pontos, encontre os vértices do icosaedro. Para 30 pontos, o ponto médio das bordas do icosaedro. você pode fazer a mesma coisa com o tetraedro, cubo, dodecaedro e octaedro: um conjunto de pontos está nos vértices, outro no centro da face e outro no centro das arestas. Eles não podem ser misturados, no entanto.

user19371
fonte
Uma boa ideia, mas só funciona para 4, 6, 8, 12, 20, 24 ou 30 pontos.
O cara com o chapéu
Se você quiser trapacear, pode usar o centro das faces e vértices. Eles não terão espaçamento igual, mas uma aproximação decente. Isso é bom porque é determinístico.
chessofnerd
0
# create uniform spiral grid
numOfPoints = varargin[0]
vxyz = zeros((numOfPoints,3),dtype=float)
sq0 = 0.00033333333**2
sq2 = 0.9999998**2
sumsq = 2*sq0 + sq2
vxyz[numOfPoints -1] = array([(sqrt(sq0/sumsq)), 
                              (sqrt(sq0/sumsq)), 
                              (-sqrt(sq2/sumsq))])
vxyz[0] = -vxyz[numOfPoints -1] 
phi2 = sqrt(5)*0.5 + 2.5
rootCnt = sqrt(numOfPoints)
prevLongitude = 0
for index in arange(1, (numOfPoints -1), 1, dtype=float):
  zInc = (2*index)/(numOfPoints) -1
  radius = sqrt(1-zInc**2)

  longitude = phi2/(rootCnt*radius)
  longitude = longitude + prevLongitude
  while (longitude > 2*pi): 
    longitude = longitude - 2*pi

  prevLongitude = longitude
  if (longitude > pi):
    longitude = longitude - 2*pi

  latitude = arccos(zInc) - pi/2
  vxyz[index] = array([ (cos(latitude) * cos(longitude)) ,
                        (cos(latitude) * sin(longitude)), 
                        sin(latitude)])
ksmith
fonte
4
Seria útil se você escrevesse algum texto explicando o que isso significa, para que o OP não tenha que acreditar que funcionará.
hcarver
0

@robert king É uma solução muito boa, mas tem alguns bugs desleixados. Eu sei que me ajudou muito, então não importa o desleixo. :) Aqui está uma versão limpa ....

from math import pi, asin, sin, degrees
halfpi, twopi = .5 * pi, 2 * pi
sphere_area = lambda R=1.0: 4 * pi * R ** 2

lat_dist = lambda lat, R=1.0: R*(1-sin(lat))

#A = 2*pi*R^2(1-sin(lat))
def sphere_latarea(lat, R=1.0):
    if -halfpi > lat or lat > halfpi:
        raise ValueError("lat must be between -halfpi and halfpi")
    return 2 * pi * R ** 2 * (1-sin(lat))

sphere_lonarea = lambda lon, R=1.0: \
        4 * pi * R ** 2 * lon / twopi

#A = 2*pi*R^2 |sin(lat1)-sin(lat2)| |lon1-lon2|/360
#    = (pi/180)R^2 |sin(lat1)-sin(lat2)| |lon1-lon2|
sphere_rectarea = lambda lat0, lat1, lon0, lon1, R=1.0: \
        (sphere_latarea(lat0, R)-sphere_latarea(lat1, R)) * (lon1-lon0) / twopi


def test_sphere(n_lats=10, n_lons=19, radius=540.0):
    total_area = 0.0
    for i_lons in range(n_lons):
        lon0 = twopi * float(i_lons) / n_lons
        lon1 = twopi * float(i_lons+1) / n_lons
        for i_lats in range(n_lats):
            lat0 = asin(2 * float(i_lats) / n_lats - 1)
            lat1 = asin(2 * float(i_lats+1)/n_lats - 1)
            area = sphere_rectarea(lat0, lat1, lon0, lon1, radius)
            print("{:} {:}: {:9.4f} to  {:9.4f}, {:9.4f} to  {:9.4f} => area {:10.4f}"
                    .format(i_lats, i_lons
                    , degrees(lat0), degrees(lat1)
                    , degrees(lon0), degrees(lon1)
                    , area))
            total_area += area
    print("total_area = {:10.4f} (difference of {:10.4f})"
            .format(total_area, abs(total_area) - sphere_area(radius)))

test_sphere()
Ismael Harun
fonte
-1

Isso funciona e é extremamente simples. Quantos pontos você quiser:

    private function moveTweets():void {


        var newScale:Number=Scale(meshes.length,50,500,6,2);
        trace("new scale:"+newScale);


        var l:Number=this.meshes.length;
        var tweetMeshInstance:TweetMesh;
        var destx:Number;
        var desty:Number;
        var destz:Number;
        for (var i:Number=0;i<this.meshes.length;i++){

            tweetMeshInstance=meshes[i];

            var phi:Number = Math.acos( -1 + ( 2 * i ) / l );
            var theta:Number = Math.sqrt( l * Math.PI ) * phi;

            tweetMeshInstance.origX = (sphereRadius+5) * Math.cos( theta ) * Math.sin( phi );
            tweetMeshInstance.origY= (sphereRadius+5) * Math.sin( theta ) * Math.sin( phi );
            tweetMeshInstance.origZ = (sphereRadius+5) * Math.cos( phi );

            destx=sphereRadius * Math.cos( theta ) * Math.sin( phi );
            desty=sphereRadius * Math.sin( theta ) * Math.sin( phi );
            destz=sphereRadius * Math.cos( phi );

            tweetMeshInstance.lookAt(new Vector3D());


            TweenMax.to(tweetMeshInstance, 1, {scaleX:newScale,scaleY:newScale,x:destx,y:desty,z:destz,onUpdate:onLookAtTween, onUpdateParams:[tweetMeshInstance]});

        }

    }
    private function onLookAtTween(theMesh:TweetMesh):void {
        theMesh.lookAt(new Vector3D());
    }
Arthur Flower
fonte