Estoy buscando un buen algoritmo para el siguiente problema: dada una cuadrícula 3D de vóxeles (que puede estar vacía o llena), si elijo dos vóxeles no adyacentes, quiero saber si están conectados entre sí por otros vóxeles
Por ejemplo (para ilustrar la situación en 2D), donde # es un cuadrado relleno:
1 2 3
a # # #
b # #
c # # #Si elijo a3 y c3, quiero determinar lo más rápido posible si están conectados; si hay una ruta entre a3 y c3 a través de píxeles rellenos. (La situación real está en una cuadrícula de vóxeles 3D, por supuesto).
He analizado los algoritmos de inundación y los algoritmos de búsqueda de rutas, pero no estoy seguro de cuál elegir. Ambos realizan un trabajo innecesario: el relleno de inundación intenta llenar todos los vóxeles, pero esto no es necesario. Los algoritmos de búsqueda de ruta generalmente se ocupan de encontrar la ruta más corta, que tampoco es necesaria. Sólo necesito saber si hay es un camino.
¿Qué algoritmo debería usar?
Editar: según los comentarios, creo que debería agregar lo siguiente: el contenido de los vóxeles no se conoce de antemano, y también, el algoritmo es necesario para detectar si la eliminación (vaciado) de un vóxel podría romper el grupo de vóxeles en dos o más grupos más pequeños.
fuente
c3->c2->b2->a2->a3?Respuestas:
A * funcionaría bien. Encontrar la ruta es lo que desea, encontrar la ruta más corta es tan rápido (o más rápido) que encontrar cualquier ruta. En esta situación, A * es probablemente el más adecuado dado que tiene un punto de inicio y finalización. Esto significa que tiene la heurística adicional para acelerar la búsqueda.
Con A *, generalmente, la primera ruta que encuentra es la más corta, por lo que no está haciendo un trabajo adicional después de que ya haya encontrado una ruta.
Para algunas optimizaciones, mira mi respuesta aquí .
fuente
Si está preparado para hacer un preprocesamiento y reducir el costo de almacenamiento, entonces la división de los vóxeles en grupos conectados en el momento de la compilación da una respuesta obvia a '¿hay algún camino?' Hay un camino entre dos vóxeles si están en el mismo grupo. El problema con eso obviamente es que tiene que almacenar información de grupo en algún lugar, y eso depende de su diseño de datos. Si está almacenando una lista simple, puede dividirla en varias listas, una para cada grupo espacialmente conectado. Si se está organizando en algún tipo de BVH, entonces probablemente podría obtener algunas eficiencias razonablemente buenas si puede decir "todos los vóxeles en este nodo y debajo pertenecen al grupo X".
Alternativamente, podría hacer un pre-partición espacial y almacenar un conjunto más pequeño de vóxeles 'hub' para cada grupo conectado. A continuación, puede buscar rutas desde los vóxeles de origen y destino al vóxel del centro más cercano, que debería ser una ruta mucho más corta / más barata de calcular. Si puede encontrar una ruta desde un voxel a un hub voxel, entonces el voxel es parte del grupo del hub voxel. Con la selección inteligente de esos vóxeles de concentrador, puede minimizar el número de recorridos de ruta. Por ejemplo, una esfera puede tener un solo voxel hub en su centro, pero un grupo largo y delgado puede tener un voxel hub cada X voxels a lo largo de su longitud. Si los vóxeles de origen y destino están en cualquiera de los extremos de la longitud, solo tienen que ir a la mayoría de los vóxeles X para encontrar un centro, y aunque puede haber una gran cantidad de vóxeles entre el inicio y el final de la longitud,
Todo depende de cuán patológicos sean sus grupos de voxel: si espera una gran cantidad de grupos desconectados pequeños, el aumento en el costo de almacenamiento va a superar enormemente el impacto en el rendimiento de solo encontrar rutas. Si espera relativamente pocos grupos conectados pero con topologías extrañas, entonces la búsqueda ingenua de rutas puede ser enormemente costosa y el costo de almacenamiento y la búsqueda mínima de rutas es una opción mucho más barata.
fuente
No estoy muy familiarizado con los vóxeles, pero me imagino que podría obtener un rendimiento bastante bueno utilizando el mejor algoritmo de búsqueda como A *. El problema con el uso de A * en este caso es que la heurística que usaría normalmente está diseñada para priorizar la búsqueda del camino más corto y no 'cualquier camino' lo más rápido posible.
Es posible que tenga suerte usando una heurística alternativa que expande menos nodos como
f (p) = g (p) + w (p) * h (p)
donde w> = 1. disminuye el valor de 'w' cuanto más se acerca a la meta, dando así una mayor prioridad al costo de la ruta 'g' cuanto más se acerca al vóxel que está buscando.
¡Espero que esto ayude!
fuente