Distribuir uniformemente n puntos en una esfera

121

Necesito un algoritmo que pueda darme posiciones alrededor de una esfera para N puntos (menos de 20, probablemente) que los distribuya vagamente. No hay necesidad de "perfección", pero solo la necesito para que ninguno de ellos esté agrupado.

  • Esta pregunta proporcionó un buen código, pero no pude encontrar una manera de hacer este uniforme, ya que parecía 100% aleatorio.
  • Esta publicación de blog recomendada tenía dos formas que permitían ingresar el número de puntos en la esfera, pero el algoritmo de Saff y Kuijlaars está exactamente en psuedocode que pude transcribir, y el ejemplo de código que encontré contenía "nodo [k]", que no pude Ver explicado y arruinado esa posibilidad. El segundo ejemplo de blog fue el Golden Section Spiral, que me dio resultados extraños y agrupados, sin una forma clara de definir un radio constante.
  • Este algoritmo de esta pregunta parece que podría funcionar, pero no puedo juntar lo que hay en esa página en psuedocode ni nada.

Algunos otros hilos de preguntas que encontré hablaban de distribución uniforme aleatoria, que agrega un nivel de complejidad que no me preocupa. Me disculpo porque esta es una pregunta tan tonta, pero quería mostrar que realmente he buscado mucho y aún me he quedado corto.

Entonces, lo que estoy buscando es un pseudocódigo simple para distribuir uniformemente N puntos alrededor de una esfera unitaria, que regresa en coordenadas esféricas o cartesianas. Aún mejor si se puede distribuir con un poco de aleatorización (piense en planetas alrededor de una estrella, esparcidos decentemente, pero con margen de maniobra).

Acontecer
fuente
¿Qué quieres decir con "con un poco de aleatorización"? ¿Te refieres a perturbaciones en algún sentido?
ninjagecko
32
OP está confundido. Lo que busca es poner n puntos en una esfera, de modo que la distancia mínima entre dos puntos sea lo más grande posible. Esto le dará a los puntos la apariencia de estar "distribuidos uniformemente" por toda la esfera. Esto no tiene nada que ver con la creación de una distribución aleatoria uniforme en una esfera, que es de lo que tratan muchos de esos enlaces y de lo que hablan muchas de las respuestas a continuación.
BlueRaja - Danny Pflughoeft
1
20 no son muchos puntos para colocar en una esfera si no quieres que se vean simplemente al azar.
John Alexiou
2
Aquí hay una forma de hacerlo (tiene ejemplos de código): pdfs.semanticscholar.org/97a6/… (parece que usa cálculos de fuerza de repulsión)
trusktr
1
Por supuesto, para los valores de N en {4, 6, 8, 12, 20} existen soluciones exactas en las que la distancia desde cada punto a (cada uno de) sus vecinos más cercanos es una constante para todos los puntos y todos los vecinos más cercanos.
dmckee --- ex-moderador gatito

Respuestas:

13

En este ejemplo, el código node[k] es solo el k-ésimo nodo. Está generando una matriz de N puntos y node[k]es el kth (de 0 a N-1). Si eso es todo lo que te confunde, es de esperar que puedas usarlo ahora.

(en otras palabras, kes una matriz de tamaño N que se define antes de que comience el fragmento de código y que contiene una lista de los puntos).

Alternativamente , construyendo sobre la otra respuesta aquí (y 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

Si traza eso, verá que el espaciado vertical es mayor cerca de los polos, de modo que cada punto está situado aproximadamente en la misma área total de espacio (cerca de los polos hay menos espacio "horizontalmente", por lo que da más "verticalmente" ).

Esto no es lo mismo que todos los puntos que tienen aproximadamente la misma distancia a sus vecinos (que es de lo que creo que están hablando sus enlaces), pero puede ser suficiente para lo que desea y mejora simplemente haciendo una cuadrícula uniforme de lat / lon .

Andrew Cooke
fuente
bueno, es bueno ver una solución matemática. Estaba pensando en usar una hélice y una separación de longitud de arco. Todavía no estoy seguro de cómo obtener la solución óptima, que es un problema interesante.
robert king
¿Viste que edité mi respuesta para incluir una explicación del nodo [k] en la parte superior? Creo que eso puede ser todo lo que necesitas ...
Andrew Cooke
Maravilloso, gracias por la explicación. Lo probaré más tarde, ya que no tengo tiempo actualmente, pero muchas gracias por ayudarme. Les haré saber cómo termina funcionando para mis propósitos. ^^
Suceso
Usar el método Espiral se adapta perfectamente a mis necesidades, muchas gracias por la ayuda y aclaración. :)
Befall
13
El vínculo parece muerto.
Scheintod
140

El algoritmo de la esfera de Fibonacci es excelente para esto. Es rápido y da resultados que de un vistazo engañarán fácilmente al ojo humano. Puede ver un ejemplo realizado con procesamiento que mostrará el resultado a lo largo del tiempo a medida que se agregan puntos. Aquí hay otro gran ejemplo interactivo creado por @gman. Y aquí hay una implementación simple en 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 muestras te dan esto:

ingrese la descripción de la imagen aquí

Fnord
fuente
se llama una variable n al definir phi: phi = ((i + rnd)% n) * incremento. ¿N = muestras?
Andrew Staroscik
@AndrewStaroscik ¡sí! Cuando escribí el código por primera vez, usé "n" como variable y cambié el nombre más tarde, pero no hice la debida diligencia. ¡Gracias por captar eso!
Fnord
4
@Xarbrough el código le da puntos alrededor de una esfera unitaria, así que solo multiplique cada punto por el escalar que desee para el radio.
Fnord
2
@Fnord: ¿Podemos hacer esto para dimensiones más altas?
pikachuchameleon
108

El método de la espiral dorada

Dijiste que no podías conseguir que el método de la espiral dorada funcionara y es una pena porque es realmente bueno. Me gustaría darte una comprensión completa de esto para que tal vez puedas entender cómo evitar que esto se "acumule".

Así que aquí hay una forma rápida y no aleatoria de crear una celosía que sea aproximadamente correcta; como se discutió anteriormente, ninguna celosía será perfecta, pero esto puede ser lo suficientemente bueno. Se compara con otros métodos, por ejemplo, en BendWavy.org, pero tiene un aspecto agradable y bonito, así como una garantía sobre el espaciado uniforme en el límite.

Imprimación: espirales de girasol en el disco unitario

Para comprender este algoritmo, primero lo invito a mirar el algoritmo de espiral de girasol 2D. Esto se basa en el hecho de que el número más irracional es la proporción áurea (1 + sqrt(5))/2y si uno emite puntos por el enfoque "párese en el centro, gire una proporción áurea de giros completos, luego emita otro punto en esa dirección", uno naturalmente construye un espiral que, a medida que se llega a un número cada vez mayor de puntos, se niega, sin embargo, a tener "barras" bien definidas en las que se alinean los puntos.(Nota 1.)

El algoritmo para el espaciado uniforme en un disco es,

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

y produce resultados que se parecen a (n = 100 yn = 1000):

ingrese la descripción de la imagen aquí

Espaciar los puntos radialmente

La clave extraña es la fórmula r = sqrt(indices / num_pts); ¿Cómo llegué a ese? (Nota 2.)

Bueno, estoy usando la raíz cuadrada aquí porque quiero que tengan un espacio uniforme alrededor del disco. Eso es lo mismo que decir que en el límite de N grande quiero que una pequeña región R ∈ ( r , r + d r ), Θ ∈ ( θ , θ + d θ ) contenga un número de puntos proporcional a su área, que es r d r d θ . Ahora, si pretendemos que estamos hablando de una variable aleatoria aquí, esto tiene una interpretación sencilla como decir que la densidad de probabilidad conjunta para ( R , Θ ) es simplemente crpara alguna constante = 1 / π.c . La normalización en el disco unitario forzaría entonces c

Ahora déjame presentarte un truco. Proviene de la teoría de la probabilidad, donde se conoce como muestreo de la CDF inversa : suponga que desea generar una variable aleatoria con una densidad de probabilidad f ( z ) y tiene una variable aleatoria U ~ Uniforme (0, 1), tal como sale de random()en la mayoría de los lenguajes de programación. ¿Cómo haces esto?

  1. Primero, convierta su densidad en una función de distribución acumulativa o CDF, que llamaremos F ( z ). Un CDF, recuerde, aumenta monótonamente de 0 a 1 con la derivada f ( z ).
  2. Luego calcule la función inversa F -1 ( z ) de la CDF .
  3. Encontrará que Z = F -1 ( U ) se distribuye de acuerdo con la densidad objetivo. (Nota 3).

Ahora, el truco de la espiral de la proporción áurea espacia los puntos en un patrón uniforme para θ, así que integremos eso; para el disco unitario nos queda F ( r ) = r 2 . Entonces la función inversa es F -1 ( u ) = u 1/2 , y por lo tanto generaríamos puntos aleatorios en el disco en coordenadas polares conr = sqrt(random()); theta = 2 * pi * random() .

Ahora, en lugar de muestrear aleatoriamente esta función inversa, la estamos muestreando uniformemente , y lo bueno del muestreo uniforme es que nuestros resultados sobre cómo se distribuyen los puntos en el límite de N grande se comportarán como si lo hubiéramos muestreado aleatoriamente. Esta combinación es el truco. En lugar de random()usamos (arange(0, num_pts, dtype=float) + 0.5)/num_pts, de modo que, digamos, si queremos muestrear 10 puntos, lo son r = 0.05, 0.15, 0.25, ... 0.95. Tomamos muestras de r uniformemente para obtener un espaciado de áreas iguales y usamos el incremento de girasol para evitar “barras” de puntos horribles en la salida.

Ahora haciendo el girasol en una esfera

Los cambios que debemos hacer para salpicar la esfera con puntos simplemente implican cambiar las coordenadas polares por coordenadas esféricas. La coordenada radial, por supuesto, no entra en esto porque estamos en una esfera unitaria. Para mantener las cosas un poco más consistentes aquí, aunque fui entrenado como físico, usaré las coordenadas de los matemáticos donde 0 ≤ φ ≤ π es la latitud que desciende del polo y 0 ≤ θ ≤ 2π es la longitud. Entonces, la diferencia con respecto a lo anterior es que básicamente estamos reemplazando la variable r con φ .

Nuestro elemento de área, que era r d r d θ , ahora se convierte en el pecado no mucho más complicado ( φ ) d φ d θ . Entonces, nuestra densidad conjunta para un espaciado uniforme es sin ( φ ) / 4π. Integrando θ , encontramos f ( φ ) = sin ( φ ) / 2, entonces F ( φ ) = (1 - cos ( φ )) / 2. Al invertir esto, podemos ver que una variable aleatoria uniforme se vería como acos (1 - 2 u ), pero tomamos muestras de manera uniforme en lugar de aleatoria, por lo que en su lugar usamos φ k = acos (1 - 2 ( k+ 0,5) /N ). Y el resto del algoritmo solo proyecta esto en las coordenadas x, y, 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()

Nuevamente, para n = 100 yn = 1000, los resultados se ven así: ingrese la descripción de la imagen aquí ingrese la descripción de la imagen aquí

Más investigación

Quería dar un saludo al blog de Martin Roberts. Tenga en cuenta que antes creé un desplazamiento de mis índices agregando 0.5 a cada índice. Esto fue visualmente atractivo para mí, pero resulta que la elección de la compensación es muy importante y no es constante durante el intervalo y puede significar obtener hasta un 8% más de precisión en el empaque si se elige correctamente. También debería haber una manera de hacer que su secuencia R 2 cubra una esfera y sería interesante ver si esto también producía una cobertura uniforme y agradable, tal vez tal como está, pero tal vez necesitando ser, digamos, tomado de solo la mitad de el cuadrado de la unidad cortó en diagonal más o menos y se estiró para formar un círculo.

Notas

  1. Esas "barras" están formadas por aproximaciones racionales a un número, y las mejores aproximaciones racionales a un número provienen de su expresión de fracción continua, z + 1/(n_1 + 1/(n_2 + 1/(n_3 + ...)))donde zes un número entero y n_1, n_2, n_3, ...es una secuencia finita o infinita de enteros positivos:

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

    Dado que la parte de la fracción 1/(...)siempre está entre cero y uno, un número entero grande en la fracción continua permite una aproximación racional particularmente buena: "uno dividido por algo entre 100 y 101" es mejor que "uno dividido por algo entre 1 y 2". El número más irracional es, por tanto, el que es 1 + 1/(1 + 1/(1 + ...))y no tiene aproximaciones racionales particularmente buenas; se puede resolver φ = 1 + 1 / φ multiplicando por φ para obtener la fórmula de la proporción áurea.

  2. Para las personas que no están tan familiarizadas con NumPy, todas las funciones están "vectorizadas", por lo que sqrt(array)es lo mismo que escribirían otros lenguajes map(sqrt, array). Así que esta es una aplicación componente por componente sqrt. Lo mismo también se aplica a la división por un escalar o la suma con escalares, que se aplican a todos los componentes en paralelo.

  3. La prueba es simple una vez que sabes que este es el resultado. Si pregunta cuál es la probabilidad de que z < Z < z + d z , esto es lo mismo que preguntar cuál es la probabilidad de que z < F -1 ( U ) < z + d z , aplique F a las tres expresiones y observe que es una función que aumenta monótonamente, por lo tanto F ( z ) < U < F ( z + d z ), expanda el lado derecho hacia afuera para encontrar F ( z ) + f( z ) d z , y dado que U es uniforme, esta probabilidad es solo f ( z ) d z como se prometió.

CR Drost
fuente
4
No estoy seguro de por qué esto está tan abajo, este es, con mucho, el mejor método rápido para hacer esto.
2017
2
@snb ¡gracias por tus amables palabras! está tan abajo en parte porque es mucho, mucho más joven que el resto de las respuestas aquí. Me sorprende que incluso le esté yendo tan bien como hasta ahora.
CR Drost
Una pregunta que me queda es: ¿Cuántos puntos n necesito distribuir para una distancia máxima dada entre dos puntos cualesquiera?
Felix D.
1
@FelixD. Eso suena como una pregunta que podría complicarse muy rápidamente, especialmente si comienza a usar, digamos, distancias de círculo máximo en lugar de distancias euclidianas. Pero tal vez pueda responder una pregunta simple, si uno convierte los puntos en la esfera a su diagrama de Voronoi, se puede describir cada celda de Voronoi como que tiene aproximadamente un área de 4π / N y se puede convertir esto a una distancia característica fingiendo que es un círculo en lugar de que un rombo, πr² = 4π / N. Entonces r = 2 / √ (N).
CR Drost
2
Usar el teorema de muestreo con entrada realmente uniforme en lugar de aleatoriamente uniforme es una de esas cosas que me hace decir "Bueno, ¿por qué el # $% & no pensé en eso?" . Agradable.
dmckee --- ex-moderador gatito
86

Esto se conoce como puntos de empaquetamiento en una esfera y no existe una solución general perfecta (conocida). Sin embargo, hay muchas soluciones imperfectas. Los tres más populares parecen ser:

  1. Crea una simulación . Trate cada punto como un electrón restringido a una esfera, luego ejecute una simulación para un cierto número de pasos. La repulsión de los electrones tenderá naturalmente al sistema a un estado más estable, donde los puntos están lo más lejos posible unos de otros.
  2. Rechazo del hipercubo . Este método que suena elegante es realmente simple: usted elige puntos uniformemente (mucho más que nellos) dentro del cubo que rodea la esfera, luego rechaza los puntos fuera de la esfera. Trate los puntos restantes como vectores y normalícelos. Estas son sus "muestras" - elíjalas nusando algún método (al azar, codicioso, etc.).
  3. Aproximaciones en espiral . Traza una espiral alrededor de una esfera y distribuye uniformemente los puntos alrededor de la espiral. Debido a las matemáticas involucradas, estos son más complicados de entender que la simulación, pero mucho más rápidos (y probablemente involucran menos código). El más popular parece ser el de Saff, et al .

Puede encontrar mucha más información sobre este problema aquí

BlueRaja - Danny Pflughoeft
fuente
Estaré investigando la táctica en espiral que Andrew Cooke publicó a continuación, sin embargo, ¿podrían aclarar la diferencia entre lo que quiero y lo que es una "distribución aleatoria uniforme"? ¿Es solo una ubicación 100% aleatoria de puntos en una esfera para que estén colocados de manera uniforme? Gracias por la ayuda. :)
Sucede el
4
@Befall: "distribución aleatoria uniforme" se refiere a que la distribución de probabilidad es uniforme; es decir, al elegir un punto aleatorio en la esfera, cada punto tiene la misma probabilidad de ser elegido. No tiene nada que ver con la distribución espacial final de los puntos y, por lo tanto, no tiene nada que ver con su pregunta.
BlueRaja - Danny Pflughoeft
Ahhh, está bien, muchas gracias. La búsqueda de mi pregunta me llevó a un montón de respuestas para ambos, y realmente no pude entender lo que no tenía sentido para mí.
Sucederá el
Para ser claros, cada punto tiene cero probabilidades de ser elegido. La razón de las probabilidades de que el punto pertenezca a dos áreas cualesquiera de la superficie de la esfera es igual a la razón de las superficies.
AturSams
2
El último enlace ya está muerto
Felix D.
10

Lo que busca se llama recubrimiento esférico . El problema de la cobertura esférica es muy difícil y se desconocen las soluciones, excepto por un pequeño número de puntos. Una cosa que se sabe con certeza es que dados n puntos en una esfera, siempre existen dos puntos de distancia d = (4-csc^2(\pi n/6(n-2)))^(1/2)o más cercanos.

Si desea un método probabilístico para generar puntos distribuidos uniformemente en una esfera, es fácil: genere puntos en el espacio uniformemente mediante distribución gaussiana (está integrado en Java, no es difícil encontrar el código para otros lenguajes). Entonces, en el espacio tridimensional, necesitas algo como

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

Luego proyecta el punto sobre la esfera normalizando su distancia desde el origen

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

La distribución gaussiana en n dimensiones es esféricamente simétrica, por lo que la proyección sobre la esfera es uniforme.

Por supuesto, no hay garantía de que la distancia entre dos puntos cualesquiera en una colección de puntos generados uniformemente esté delimitada a continuación, por lo que puede usar el rechazo para hacer cumplir las condiciones que pueda tener: probablemente sea mejor generar la colección completa y luego rechazar toda la colección si es necesario. (O utilice "rechazo temprano" para rechazar toda la colección que ha generado hasta ahora; simplemente no guarde algunos puntos y descarte otros). Puede usar la fórmula ddada anteriormente, menos cierta holgura, para determinar la distancia mínima entre puntos por debajo de los cuales rechazará un conjunto de puntos. Deberá calcular n elegir 2 distancias, y la probabilidad de rechazo dependerá de la holgura; Es difícil decir cómo, así que ejecute una simulación para familiarizarse con las estadísticas relevantes.

Edward Doolittle
fuente
Voto a favor de las expresiones de distancia mínima máxima. Útil para poner límites a la cantidad de puntos que desea utilizar. Sin embargo, sería bueno hacer una referencia a una fuente autorizada.
dmckee --- ex-moderador gatito
6

Esta respuesta se basa en la misma 'teoría' que se describe bien en esta respuesta

Estoy agregando esta respuesta como:
- Ninguna de las otras opciones se ajusta a la necesidad de 'uniformidad' (o no obviamente). (Teniendo en cuenta que para obtener el comportamiento de apariencia de distribución similar a un planeta particularmente deseado en la solicitud original, simplemente rechaza de la lista finita de los k puntos creados uniformemente al azar (aleatorio con el recuento del índice en los k elementos)) .Además, Es muy difícil "asimilar" cómo diferenciar entre las otras opciones sin ninguna imagen, así que así es como se ve esta opción (a continuación) y la implementación lista para ejecutar que la acompaña.
--La más cercano otra implicación lo obligó a decidir la 'N' por el 'eje angular', frente a solo 'un valor de N' en ambos valores del eje angular (que en recuentos bajos de N es muy complicado saber qué puede o no importar ( por ejemplo, quieres '5' puntos - diviértete))

con N en 20:

ingrese la descripción de la imagen aquí
y luego N en 80: ingrese la descripción de la imagen aquí


aquí está el código python3 listo para ejecutar, donde la emulación es la misma fuente: " http://web.archive.org/web/20120421191837/http://www.cgafaq.info/wiki/Evenly_distributed_points_on_sphere " encontrado por otros . (El trazado que he incluido, que se activa cuando se ejecuta como 'principal', está tomado 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

probado en recuentos bajos (N en 2, 5, 7, 13, etc.) y parece funcionar 'bien'

Matt S.
fuente
5

Tratar:

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); 
};

La función anterior debe ejecutarse en bucle con N bucle total y k iteración actual de bucle.

Se basa en un patrón de semillas de girasol, excepto que las semillas de girasol se curvan en una media cúpula y nuevamente en una esfera.

Aquí hay una imagen, excepto que puse la cámara a medio camino dentro de la esfera para que se vea 2d en lugar de 3d porque la cámara está a la misma distancia de todos los puntos. http://3.bp.blogspot.com/-9lbPHLccQHA/USXf88_bvVI/AAAAAAAAADY/j7qhQsSZsA8/s640/sphere.jpg

aliential
fuente
2

Healpix resuelve un problema estrechamente relacionado (pixelar la esfera con píxeles de igual área):

http://healpix.sourceforge.net/

Probablemente sea exagerado, pero tal vez después de mirarlo se dé cuenta de que algunas de sus otras propiedades agradables son interesantes para usted. Es mucho más que una función que genera una nube de puntos.

Aterricé aquí tratando de encontrarlo nuevamente; el nombre "healpix" no evoca exactamente esferas ...

Andrew Wagner
fuente
1

con una pequeña cantidad de puntos, podría ejecutar una simulación:

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
fuente
para mejorar mi respuesta, debe cambiar most_index = i a más cercano_index = randchoice (i, j)
robert king
1

Tome los dos factores más grandes de su N, si N==20entonces los dos factores más grandes son {5,4}, o, más en general {a,b}. Calcular

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

Pon tu primer punto en {90-dlat/2,(dlong/2)-180}, tu segundo en {90-dlat/2,(3*dlong/2)-180}, tu tercero en {90-dlat/2,(5*dlong/2)-180}, hasta que hayas dado la vuelta al mundo una vez, momento en el que habrás llegado a aproximadamente {75,150}cuando vayas a continuación {90-3*dlat/2,(dlong/2)-180}.

Obviamente, estoy trabajando esto en grados en la superficie de la tierra esférica, con las convenciones habituales para traducir +/- a N / S o E / W. Y obviamente esto le brinda una distribución completamente no aleatoria, pero es uniforme y los puntos no están agrupados.

Para agregar algún grado de aleatoriedad, puede generar 2 distribuidos normalmente (con media 0 y std dev de {dlat / 3, dlong / 3} según corresponda) y agregarlos a sus puntos distribuidos uniformemente.

Marca de alto rendimiento
fuente
5
eso se vería mucho mejor si trabajara en sin (lat) en lugar de lat. tal como están las cosas, obtendrás mucho agrupamiento cerca de los polos.
Andrew Cooke
1

editar: Esto no responde a la pregunta que el OP quería hacer, dejándolo aquí en caso de que la gente lo encuentre útil de alguna manera.

Usamos la regla de multiplicación de la probabilidad, combinada con infinitesimales. Esto da como resultado 2 líneas de código para lograr el resultado deseado:

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

(definido en el siguiente sistema de coordenadas :)

ingrese la descripción de la imagen aquí

Su idioma normalmente tiene una primitiva de número aleatorio uniforme. Por ejemplo, en Python puede usar random.random()para devolver un número en el rango [0,1). Puede multiplicar este número por k para obtener un número aleatorio en el rango [0,k). Por lo tanto, en python, uniform([0,2pi))significaría random.random()*2*math.pi.


Prueba

Ahora no podemos asignar θ uniformemente, de lo contrario nos aglutinaríamos en los polos. Deseamos asignar probabilidades proporcionales al área de la superficie de la cuña esférica (la θ en este diagrama es en realidad φ):

ingrese la descripción de la imagen aquí

Un desplazamiento angular dφ en el ecuador resultará en un desplazamiento de dφ * r. ¿Cuál será ese desplazamiento en un acimut arbitrario θ? Bueno, el radio del eje z es r*sin(θ), por lo que la longitud de arco de esa "latitud" que cruza la cuña es dφ * r*sin(θ). Así calculamos la distribución acumulada del área a muestrear de ella, integrando el área del corte del polo sur al polo norte.

ingrese la descripción de la imagen aquí(donde cosas = dφ*r)

Ahora intentaremos obtener el inverso del CDF para muestrearlo: http://en.wikipedia.org/wiki/Inverse_transform_sampling

Primero normalizamos dividiendo nuestro casi-CDF por su valor máximo. Esto tiene el efecto secundario de cancelar dφ y r.

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

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

Así:

let x by a random float in range [0,1]
θ = -arcsin(1-2*x)
ninjagecko
fuente
¿No es esto equivalente a la opción que descartó por ser "100% aleatoria"? tengo entendido que quiere que estén espaciados más uniformemente que una distribución aleatoria uniforme.
Andrew Cooke
@ BlueRaja-DannyPflughoeft: Hmm, bastante justo. Supongo que no leí la pregunta con tanta atención como debería. Dejo esto aquí de todos modos en caso de que otros lo encuentren útil. Gracias por señalar esto.
ninjagecko
1

O ... para colocar 20 puntos, calcule los centros de las caras del icosaedro. Para 12 puntos, encuentra los vértices del icosaedro. Para 30 puntos, el punto medio de los bordes del icosaedro. puedes hacer lo mismo con el tetraedro, el cubo, el dodecaedro y los octaedros: un conjunto de puntos está en los vértices, otro en el centro de la cara y otro en el centro de las aristas. Sin embargo, no se pueden mezclar.

user19371
fuente
Una buena idea, pero solo funciona para 4, 6, 8, 12, 20, 24 o 30 puntos.
The Guy with The Hat
Si quieres hacer trampa, puedes usar el centro de caras y vértices. Ellos no ser equidistantes sino una aproximación decente. Esto es bueno porque es determinista.
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
fuente
4
Sería útil si escribiera un texto que explique lo que se supone que debe hacer, para que el OP no tenga que confiar en que simplemente funcionará.
hcarver
0

@robert king Es una solución realmente agradable, pero tiene algunos errores descuidados. Sin embargo, sé que me ayudó mucho, así que no importa el descuido. :) Aquí hay una versión limpia ...

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
fuente
-1

Esto funciona y es mortalmente simple. Tantos puntos como quieras:

    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 Flor
fuente