Colisiones de Partículas mediante Tablas Hash

Utilizar un vector para almacenar las partículas requiere un coste lineal con el número de elementos O(N) para buscar una de ellas, al desconocer el punto exacto donde se encuentra es necesario realizar una búsqueda.

Para poder reducir ese factor y conocer mejor donde buscar o almacenar una partícula utilizamos las tablas hash.

Una tabla hash es una estructura de datos con las funciones de inserción, búsqueda y borrado de elementos en tiempo constante, para ello necesitaremos una función de dispersión que asignará un valor a una partícula determinada, que deberá calcularse en tiempo constante y distribuir de forma uniforme los objetos a lo largo de la tabla, y ese valor será utilizado para indexar el vector donde están almacenadas.

Una tabla hash debe tener un número mucho mayor que el número de elementos que espera almacenar para evitar incoherencias y colisiones, una colisión se produce cuando dos o más partículas diferentes dan lugar a un mismo índice hash. Si el factor de carga o grado de ocupación de la tabla es alto (superior al 75%) el número de colisiones aumenta significativamente.

En nuestro caso de estudio del cubo de partículas, donde computaremos las colisiones entre ellas, vamos a pasar del calculo O(n·n) a dividir el cubo en una malla de sub-cubos más pequeños donde solo comprobaremos y computaremos las colisiones entre partículas que se encuentren en el mismo sub-cubo ayudándonos de una tabla hash. Insertando y eliminando las partículas de la escena en cada tabla hash representada por los sub-cubos en función de la posición y el desplazamiento de cada partícula para cada instante de tiempo.

Anuncios

Publicado el 3 junio, 2013 en Colisiones, Dinámica de Partículas, Simulación. Añade a favoritos el enlace permanente. Deja un comentario.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s

A %d blogueros les gusta esto: