Estructuras de datos espaciales en C

Question

Trabajo en química teórica en un clúster de alto rendimiento, a menudo con simulaciones de dinámica molecular. Uno de los problemas que aborda mi trabajo involucra un campo estático de hiper-esferas N-dimensionales (típicamente N = 2-5) con las que una partícula de prueba puede colisionar. Estoy buscando optimizar (leer: revisar) la estructura de datos que utilizo para representar el campo de esferas para poder hacer una rápida detección de colisión. Actualmente utilizo una matriz muerta de punteros a una estructura de N-miembros (dobles para cada coordenada del centro) y una lista de vecinos más cercanos. He oído hablar de árboles de oct y cuádruples, pero no he encontrado una explicación clara de cómo funcionan, cómo implementarlo eficientemente, o cómo hacer la detección rápida de colisiones con uno. Dado el tamaño de mis simulaciones, la memoria es (casi) sin objeto, pero los ciclos sí lo son.

Answer 1

Un árbol cuádruple es un árbol bidimensional, en el que en cada nivel un nodo tiene 4 hijos, cada uno de los cuales cubre 1/4 del área del nodo padre.

Un árbol de octubre es un árbol tridimensional, en el que en cada nivel un nodo tiene 8 hijos, cada uno de los cuales contiene 1/8 del volumen del nodo padre. Aquí hay una imagen para ayudarlo a visualizarlo: http://en.wikipedia.org/wiki/Octree

Si realiza pruebas de intersección en N dimensiones, puede generalizar esto en un árbol N.

Los algoritmos de intersección funcionan comenzando en la parte superior del árbol y atravesando recursivamente en los nodos secundarios que se cruzan con el objeto que se está probando, en algún punto se llega a los nodos hoja, que contienen los objetos reales.

Answer 2

Parece que desea implementar un kd-tree, que le permita buscar más rápidamente el espacio N-dimensional. Hay más información y enlaces a implementaciones en the Stony Brook Algorithm Repository.

Answer 3

Dado que su campo es estático (supongo que quiere decir que las hiper esféricas no se mueven), entonces la solución más rápida que conozco es un Kdtree.
Usted puede hacer su propio, o utilizar de otra persona, como éste: http://libkdtree.alioth.debian.org/

Answer 4

mejor manera de abordar esto para su problema depende de varios factores que no se han descrito: - será la misma disposición hiperesfera utilizado para muchos cálculos de colisión de partículas? - ¿Las hiperesferas tienen un tamaño uniforme? - ¿Cuál es el movimiento de la partícula (por ejemplo, línea recta/curva) y es ese movimiento afectado por las esferas? - ¿Considera que la partícula tiene cero volumen?

Supongo que la partícula no tiene un movimiento simple en línea recta, ya que sería el cálculo relativamente rápido de encontrar el punto más cercano entre una línea y un punto, que probablemente tendrá la misma velocidad que encontrar cuál de los cuadros con los que se cruza la línea (para determinar dónde se debe examinar en el árbol n).

Si las posiciones de su hiperesfera se arreglan para una gran cantidad de colisiones de partículas, calcular voronoi decomposition/Dirichlet tessellation le proporcionará una forma rápida de encontrar exactamente qué esfera está más cerca de su partícula en cualquier punto dado del espacio.

Sin embargo, para responder a su pregunta original sobre octrees/quadtrees/2^n-trees, en n dimensiones comienza con un (hiper) -cubo que contiene el área de espacio que le interesa. Esta se subdivide en 2^n hipercubos si considera que el contenido es demasiado complicado. Esto continúa recursivamente hasta que solo tenga elementos simples (por ejemplo, un centroide de hiperesfera) en los nodos de hoja. Ahora que se construyó el n-tree, lo utilizas para la detección de colisiones tomando la ruta de tu partícula e interseciéndola con el hipercubo externo. La posición de intersección le indicará qué hipercubo se encuentra en el próximo nivel inferior del árbol que visitará a continuación, y usted determinará la posición de intersección con los 2^n hipercubos en ese nivel, siguiendo hacia abajo hasta llegar a un nodo hoja. Una vez que alcanzas la hoja, puedes examinar las interacciones entre tu trayectoria de partículas y la hiperesfera almacenada en esa hoja. Si has tenido una colisión has terminado, de lo contrario debes encontrar el punto de salida de la trayectoria de la partícula desde la hoja hipercubo actual y determinar a qué hipercubo se mueve. Continúa hasta que encuentres una colisión o abandones por completo el hipercubo delimitador general.

Encontrar eficientemente el hipercubo vecino al salir de un hipercubo es una de las partes más desafiantes de este enfoque. Para 2^n árboles, los enfoques de Samet {1, 2} se pueden adaptar. Para kd-trees (árboles binarios), se sugiere un enfoque en {3} sección 4.3.3.

La implementación eficiente puede ser tan simple como almacenar una lista de 8 punteros desde cada hipercubo a sus hipercubos hijos y marcar el hipercubo de forma especial si es una hoja (por ejemplo, hacer todos los punteros NULL).

Una descripción de dividir el espacio para crear un árbol de cuatro ramas (que se puede generalizar para n-árbol) se puede encontrar en Klinger & Dyer {4}

Como otros han mencionado KD-árboles pueden ser más adecuados que los 2^n-trees como extensión a un número arbitrario de dimensiones es más sencillo, sin embargo, dará como resultado un árbol más profundo. También es más fácil adaptar las posiciones divididas para que coincidan con la geometría de sus hiperesferas con un árbol kd. La descripción anterior de la detección de colisiones en un árbol 2^n es igualmente aplicable a un árbol kd.

{1} Connected Component Labeling, Hanan Samet, Using Quadtrees Journal of the ACM Volume 28 , Issue 3 (July 1981)

{2} Neighbor finding in images represented by octrees, Hanan Samet, Computer Vision, Graphics, and Image Processing Volume 46 , Issue 3 (June 1989)

{3} Convex hull generation, connected component labelling, and minimum distance calculation for set-theoretically defined models, Dan Pidcock, 2000

{4} Los experimentos en representación de imagen utilizando la descomposición regular, Klinger, A., y Dyer, CR E, Comptr. Graphics and Image Processing 5 (1976), 68-105.

Answer 5

Un octree funcionará siempre que pueda especificar las esferas por sus centros: jerarquiza los puntos en regiones cúbicas con ocho hijos. Trabajar con los vecinos en una estructura de datos de octárbol requerirá que haga cálculos de cubo de intersección de esfera (hasta cierto punto más fáciles de lo que parecen) para determinar qué regiones cúbicas en un octárbol están dentro de la esfera.

Encontrar los vecinos más cercanos significa caminar de nuevo por el árbol hasta obtener un nodo con más de un hijo poblado y todos los nodos incluidos (esto garantiza que la consulta obtenga todos los lados).

De memoria, este es el (algo ingenua) algoritmo básico para la intersección de la esfera-cubo:

i. Es el centro dentro del cubo (esto obtiene la situación del mismo nombre)

ii. Son cualquiera de las esquinas del cubo dentro del radio r del centro (esquinas dentro de la esfera)

iii. Para cada superficie del cubo (puede eliminar algunas superficies determinando en qué lado de la superficie se encuentra el centro) haga ejercicio (esto es aritmética vectorial de primer año):

a.Una normal de la superficie que va al centro de la esfera

b. La distancia desde el centro de la esfera a la intersección de la normal con el plano de la superficie (los cordones interconectan la superficie del cubo)

c. La intersección del plano se encuentra dentro del costado del cubo (una condición de intersección de cuerda con el cubo)

iv. Calcule el tamaño del acorde (Sin de Cos^-1 de proporción de longitud normal a radio de esfera)

v. Si el punto más cercano en la línea es menor que la distancia del acorde y el punto se encuentra entre al final de la línea, el acorde se cruza con uno de los bordes del cubo (el acorde corta la superficie del cubo en algún lugar a lo largo de uno de los bordes).

Un poco vagamente recordado, pero esto es algo que hice para una situación que involucraba regiones esféricas usando una estructura de datos de octetos (hace muchos años). También es posible que desee ver KD-trees como sugieren algunos de los otros carteles, pero su pregunta inicial suena muy similar a lo que hice.