Una manera rápida y sucia utiliza un recursiva esférica de la subdivisión. Comienzo con una triangulación de la superficie de la tierra, de forma recursiva dividir cada triángulo a partir de un vértice a través de a la mitad de su lado más largo. (Lo ideal sería que divide el triángulo en dos de igual diámetro de las partes o de igual área partes, sino porque los que implican más incómoda de cálculo, acabo de dividir los lados exactamente en la mitad: esto hace que los diferentes triángulos, finalmente, para variar un poco en tamaño, pero que no parece ser crítico para esta aplicación.)
Por supuesto que va a mantener esta subdivisión en una estructura de datos que permite identificar rápidamente el triángulo en el que cualquier punto arbitrario que se encuentra. Un árbol binario (basado en las llamadas recursivas) funciona bien: cada vez que un triángulo se divide, el árbol se divide en ese triángulo del nodo. Los datos relativos a la división de plano son retenidas, por lo que rápidamente puede determinar en cual de los lados del plano cualquier punto arbitrario mentiras: que va a determinar si para viajar a la izquierda o a la derecha abajo en el árbol.
(¿He dicho división "plano"? Sí, si el modelo de la superficie de la tierra como una esfera y uso geocéntrica (x,y,z) las coordenadas, entonces la mayoría de nuestros cálculos se realizan en tres dimensiones, en donde los lados de los triángulos son piezas de intersección de la esfera con los aviones a través de su origen. Esto hace que los cálculos de forma rápida y sencilla.)
Voy a ilustrar mostrando el procedimiento en un octante de una esfera; los otros siete octantes se procesan de la misma manera. Un octante es un 90-90-90 triángulo. En mi gráficos voy a dibujar Euclidiana triángulos que abarca el mismo esquinas: no se ven muy bien hasta obtener pequeños, pero pueden ser fácilmente y rápidamente atraído. Aquí es la distancia Euclídea del triángulo correspondiente a la octante: es el inicio del procedimiento.
![Figure 1]()
Como todos los lados tienen igual longitud, uno es elegido al azar, como la "más larga" y se subdividen:
![Figure 2]()
Repita esto para cada uno de los nuevos triángulos:
![Figure 3]()
Después de n pasos vamos a tener 2^n triángulos. Aquí es la situación después de 10 pasos, mostrando 1024 triángulos en el octante (y 8192 en el ámbito general):
![Figure 4]()
Como una ilustración, además, generó un punto al azar dentro de este octante y viajó a la subdivisión de árbol, hasta que el triángulo del lado más largo alcanzado menos de 0.05 radianes. El (cartesiano) los triángulos se muestra con la sonda de punto rojo.
![Figure 5]()
Por cierto, a un estrecho punto de que la ubicación de un grado de latitud (aproximadamente), se nota que esto es acerca de 1/60 radian y por lo cubre todo (1/60)^2 / (Pi/2) = 1/6000 de la superficie total. Ya que cada subdivisión aproximadamente la mitad del tamaño del triángulo, de 13 a 14 subdivisiones de la octante hará el truco. Que no se mucho de computación--como veremos a continuación-lo que es eficiente, no para almacenar el árbol, sino para llevar a cabo la subdivisión sobre la marcha. Al principio se nota que octante el punto se encuentra en--que está determinado por los signos de sus tres coordenadas, que puede ser registrada como una de tres dígitos del número binario, y a cada paso que desea recordar si el punto se encuentra en la izquierda (0) o a la derecha (1) del triángulo. Que da a otra de 14 dígitos del número binario. El código completo para el ilustrado punto pasa a ser 111.10111110111100. Usted puede usar estos códigos de grupo de puntos arbitrarios.
(Generalmente, cuando dos códigos de cerca como de los números binarios, los correspondientes puntos de cierre; sin embargo, los puntos puede estar cerca y tienen muy diferentes códigos. Considere dos puntos de un metro de distancia separan el Ecuador, por ejemplo: sus códigos deben ser diferentes, incluso antes de que el binario de punto, porque están en diferentes octantes. Este tipo de cosas es inevitable con cualquier fijo de particionamiento del espacio.)
He utilizado Mathematica 8 para implementar esta: usted puede tomar tal cual o como pseudocódigo para una implementación favoritos en tu entorno de programación.
Determinar qué lado del plano 0-a-b en el punto p se encuentra en:
side[p_, {a_, b_}] := If[Det[{p, a, b}] >= 0, left, right];
Refinar el triángulo a-b-c con base en el punto p.
refine[p_, {a_, b_, c_}] := Block[{sides, x, y, z, m},
sides = Norm /@ {b - c, c - a, a - b} // N;
{x, y, z} = RotateLeft[{a, b, c}, First[Position[sides, Max[sides]]] - 1];
m = Normalize[Mean[{y, z}]];
If[side[p, {x, m}] === right, {y, m, x}, {x, m, z}]
]
La última figura que fue dibujada por mostrar el octante y, en la parte superior de que, mediante el procesamiento de la siguiente lista como un conjunto de polígonos:
p = Normalize@RandomReal[NormalDistribution[0, 1], 3] (* Random point *)
{a, b, c} = IdentityMatrix[3] . DiagonalMatrix[Sign[p]] // N (* First octant *)
NestWhileList[refine[p, #] &, {a, b, c}, Norm[#[[1]] - #[[2]]] >= 0.05 &, 1, 16]
NestWhileList repetidamente se aplica una operación (refine), mientras que una condición se refiere (el triángulo es grande) o hasta un máximo de recuento de operación de que se ha llegado (16).
Para mostrar la triangulación de la octante, yo empecé con el primer octante y reiteró el refinamiento de diez veces. Esto comienza con una ligera modificación de refine:
split[{a_, b_, c_}] := Module[{sides, x, y, z, m},
sides = Norm /@ {b - c, c - a, a - b} // N;
{x, y, z} = RotateLeft[{a, b, c}, First[Position[sides, Max[sides]]] - 1];
m = Normalize[Mean[{y, z}]];
{{y, m, x}, {x, m, z}}
]
La diferencia es que split devuelve ambas mitades de su entrada triángulo en lugar de uno en el que un determinado punto se encuentra. La triangulación se obtiene por recorrer en esto:
triangles = NestList[Flatten[split /@ #, 1] &, {IdentityMatrix[3] // N}, 10];
A ver, yo calcula una medida de cada triángulo del tamaño y miró a la gama. (Este tamaño es proporcional a la pirámide en forma de figura subtendido por cada triángulo y en el centro de la esfera; por triángulos pequeños como estos, este tamaño es esencialmente proporcional a su área esférica.)
Through[{Min, Max}[Map[Round[Det[#], 0.00001] &, triangles[[10]] // N, {1}]]]
{0.00523, 0.00739}
Así, los tamaños varían hacia arriba o hacia abajo por aproximadamente el 25% de su promedio: que parece razonable para el logro de aproximadamente un modo uniforme de grupo de puntos.
En la exploración a través de este código, se dará cuenta de que no trigonometría: el único lugar en el que será necesario, en todo caso, será en la conversión de ida y vuelta entre el esférico y coordenadas cartesianas. El código tampoco el proyecto de la superficie de la tierra en cualquier mapa, evitando de este modo el operador de distorsiones. De lo contrario, sólo se utiliza un promedio de (Mean), el Teorema de Pitágoras (Norm) y un 3 por 3 determinante (Det) para hacer todo el trabajo. (Hay algunos simple lista de manipulación de comandos como, por ejemplo RotateLeft y Flatten, también, junto con una búsqueda por el lado más largo de cada triángulo.)
