Encontrar Todos los Objetos 3D dentro de una Cierta Distancia de un Punto a a

Question

Tengo un conjunto de objetos (vamos a llamar a points) que contienen los x - y - y z - componentes de sus posiciones dentro de un cierto espacio.Me gustaría modelo de las interacciones entre los objetos en points, sin embargo , no puedo hacerlo, a menos que pueda encontrar rápidamente los objetos en el conjunto que están a menos de una determinada distancia de uno de los objetos en este juego.

Esto, sin duda, suena un poco confuso, así que permítanme decirlo de otra manera:si el primer punto en points tiene coordenadas <x, y, z>, Me gustaría averiguar cuál de los objetos en points tiene una distancia de menos de [algún valor arbitrario] desde el primer punto.

Yo estaba considerando la posibilidad de una implementación de un R-Tree para hacer esto en Java, sin embargo, me siento como si esta es una común suficientemente problema que una solución más simple que existe.Si no hay uno, le agradecería una explicación sencilla del método por el cual una de las consultas de un R-Tree con el fin de encontrar los objetos que se encuentran a cierta distancia x a partir de un objeto en el árbol, donde x ya es conocido.

Editar:tenga en cuenta que los valores de posición de estos objetos va a cambiar

Answer 1

El R * -Tree es una estructura de datos bastante buena para esto, en particular cuando los puntos están cambiando.Está diseñado para cambios, en realidad.

El árbol K-D es más sencillo, pero no es compatible con los cambios muy bien.Está diseñado para una construcción a granel de una sola vez.

Sin embargo, a medida que sus datos solo son tridimensionales: si sus datos son lo suficientemente pequeños como para caber en la memoria, y se conocen los valores máximos y mínimos de X, Y, Z, un octree o unsimple cuadrícula puede ser la compensación de la simplicidad y el rendimiento que necesita.

En particular si correge su radio de consulta de antemano, un archivo de cuadrícula es difícil de superar.R * -Trees Obtenga atractivo cuando necesita soportar múltiples radios, consultas de ventanas, consultas de vecinos más cercanas y todo esto.

Answer 2

Editar: Square= Cube (sin embargo, imaginarlo en el espacio 2D sería mejor, entonces puede convertirlo en 3D fácilmente)

Estaba pensando y creo que lo resolví. Sin embargo, esta es solo "mi" solución, no tengo ninguna referencia para ello.

Create la clase "cuadrada", que tiene posición, ancho y lista de puntos en ese objeto.

Todos los cuadrados se almacenarán en matriz o hashmap en función de su posición, de modo que se les puede acceder rápidamente, si conoce la posición que busca.

Todos los cuadrados se distribuirán regularmente, por lo que, desde el punto de vista de la "instancia de punto", no tiene que conocer todos los cuadrados existentes para averiguar en un momento constante en el que perteneces. (Ejemplo: Sé que hay cuadrados con un ancho de 40 y se distribuyen por distancia de 20. Estoy en la posición 10001, así que sé que pertenezco a cuadrados en la posición 9980 y 10000)

Los cuadrados se cruzarán unos a otros, por lo tanto, un punto puede ser en más cuadrados.

Cuando haces algo, por cada punto, solo verificas puntos, que se almacenan en cuadrados de los que pertenece el punto. Por supuesto, los cuadrados tienen que ser lo suficientemente grandes y cruzados lo suficiente para lograr su objetivo.

Cuando se mueven los puntos, son responsables de registrarse y no registrarse en los cuadrados.

---

1D Ejemplo:

Clases: Line segment y Point

Attrributes:

Line segment: int position, List<Points> points

Point: int position, List<LineSegment> lineSegments

Quiero interactuar solo con puntos en la distancia de 20.

Entonces creo instancias de Line segments con ancho 40 y los puse uno por uno en la distancia de 20.

para que estén en las posiciones 0, 20, 40, 60 ...

El frist se cubrirá el área 0-40, segundo 20-60, etc.

Los puse en la matriz y con la posición conocida, puedo acceder a ellos rápidamente: arrayOfLineSegments[position/20]

Cuando creo punto, lo agrego al line segments que pertenece.

Cuando actualizo, cada punto solo interactúa con puntos en linesegments.

Cuando me muevo punto, se registra y registra el registro de Líneas que pertenece.

Answer 3

Usted puede utilizar un bucle for para comprobar a través de la matriz de objeto.

utilice la siguiente fórmula: d = sqrt[(x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2]

x1,y1,z1 ser el primer punto en Points y el x2,y2,z2 siendo los puntos del objeto que va a comprobar.Esto se compruebe si el punto conocido vs todos los demás puntos.Si la distancia (d) es menor que el de su distancia deseada x a continuación, hacer lo que usted desea que el programa para hacer.