¿Cómo puedo determinar qué cuboids un punto está en sin iterar sobre todos ellos?

Question

I tienen una serie de cuboides cuyas posiciones y tamaños se dan con mínimo y máximo x, y y z coordenadas (por lo que son paralelos a los ejes principales).

por ejemplo. Yo podría tener los siguientes 3 cuboides:

10.5 <= x <= 39.4,  90.73 <= y <= 110.2, 90.23 <= z <= 95.87
20.1 <= x <= 30.05,  9.4  <= y <=  37.6,  0.1  <= z <= 91.2
10.2 <= x <= 10.3,   0.1  <= y <=  99.8, 23.7  <= z <= 24.9

Si a continuación, dar un punto (por ejemplo (25.3,10.2,90.65)), hay una manera para determinar rápidamente qué cuboide (s) que estoy?

• Es evidente que sólo podía iterar sobre todos los paralelepípedos, pero hay potencialmente millones de ellos, y necesito esto para ir más rápido que la iteración sencilla (algo O (log n) o mejor sería grande).

• Esto me suena como un problema de tipo "coincidencia aproximada", y noto que soporta Apache Lucene consultas de rango , pero esto parece para trabajar de la manera opuesta y vuelta (la búsqueda de un punto en un cuboide en lugar de un cuboide que contiene un punto).

• Para complicar un poco más las cosas, el número de dimensiones podría ser mayor que 3 (que podría ser de hasta 20); es decir, que podría estar buscando "hypercuboids" en lugar de paralelepípedos.)

Answer 1

Una forma sencilla de acelerar esta consulta es mediante la construcción de la siguiente malla uniforme estructura de datos (a menudo llamados contenedores) como un paso de preprocesamiento: Poner n x n x n (en 3d) rejilla sobre la escena y para cada celda de la cuadrícula almacenar un puntero a todos los paralelepípedos se cruzan esa célula. Ahora, para un punto de consulta se puede calcular directamente en qué célula se halla en la cuadrícula uniforme, y luego hay que comprobar sólo los paralelepípedos asociados a esa celda, y no todos los paralelepípedos.

En función de lo grande es el espacio y cómo varían los tamaños cuboides son este método podría no ser muy eficiente, ya que puede ser que sea difícil elegir una buena resolución n para acelerar lo suficiente y no necesita una enorme cantidad de células. Para superar esto es posible que desee para tratar de buscar formas más adaptativas para dividir el espacio, como kd-trees (kD-árboles en Wikipedia) , que son básicamente los árboles binarios dividir el espacio con planos eje alineado: Véase, por ejemplo, aquí en el que el plano rojo divide la caja en dos partes y entonces el verde en partes más pequeñas, entonces el azul ...

Una consulta utilizando kd-árbol que atravesar primero a la hoja de la kd-árbol donde se encuentra el punto de la consulta y después con los paralelepípedos locales en esa celda. estructura de datos Otro espacio de partición opciones se pueden encontrar aquí .

Otra opción sería utilizar volumen que delimita jerarquías , que agrupar objetos juntos en volúmenes de delimitación, y luego volúmenes grupo de delimitación en volúmenes más grandes de delimitación y así sucesivamente ... para obtener una jerarquía de volúmenes que delimitan . Estos se adaptan mejor a una escena y pueden manejar más fácil escenas en las que los objetos se mueven, pero yo creo que para su partición de espacio de configuración podría funcionar bien ... De todas formas, para más detalles ver este capítulo del libro .

Answer 2

rayando en el territorio de "Partición binaria del espacio" y "Detección de Colisiones"; esencialmente las ideas son, básicamente, el almacenamiento de los paralelepípedos en una estructura tipo árbol, que divide el espacio que ocupan en pequeñas cajas. La decisión sobre qué "parte del espacio" cada paralelepípedo ocupa se hace durante la inserción en el strucutre árbol.

Haga una búsqueda en Google sobre octrees.

dividir eficientemente el espacio 3D, y los objetos contenidos dentro de ese espacio es bastante una gran parte de la informática; utilizado principalmente en el desarrollo de juegos de ordenador. Algunos de los algoritmos de tomar en consideración un factor de tiempo, es decir, que los objetos se mueven entre los espacios de partición.