cuya estructura de datos es adecuada para consultar "todos los puntos dentro de la distancia d desde el punto p"

Question

Tengo una nube de puntos 3D y me gustaría consultar eficientemente todos los puntos dentro de la distancia d desde un punto arbitrario p (que no es necesariamente parte de la nube de puntos almacenado)

la consulta sería algo como

Pointcloud getAllPoints(Point p, float d); 

lo accelerationstructure sería apropiado para esto? Un árbol de rango parece ser apropiado solo para consultar volúmenes rectangulares, no volúmenes esféricos (por supuesto, podría consultar el cuadro delimitador de la esfera y luego ordenar todos los vértices que tengan una distancia mayor que d, pero tal vez haya una mejor manera de hacerlo esto ??)

gracias!

acuerdo con Novelocrats sugerencia, trato de definir las funciones deseadas de la estructura:

SearchStructure Create(Set<Point> cloud) 
Set<Point> Query(SearchStructure S, Point p, float maxDistance) 
SearchStructure Remove(Point p) 
SearchStructure Insert(Point p) 
SearchStructure Displace(Set<Point> displacement) //where each value describes an offsetVector to the currently present points 

Por lo general, después de n consultas, los puntos quedan desplazados y unos pocos (no muchos!) Se hacen inserciones y deleciones . los vectores de desplazamiento son muy pequeños en comparación con el cuadro delimitador de todos los puntos

Answer 1

Un mapa con una clave igual a la distancia y el valor del Punto en sí mismo le permitiría consultar todos los puntos a menos de una distancia determinada o dentro de un rango determinado.

Answer 2

Bueno, depende de qué otros usos necesite para la estructura de datos.

Puede tener una lista de distancias del punto p a otros puntos, ordenadas por distancia, y asignar estas listas a los puntos con un hashmap.

map: 
p1 -> [{p2, d12}, {p4, d14}, {p3, d13}] 
p2 -> ... 
... 

Puede buscar el punto en el mapa e iterar la lista hasta que la distancia sea más alta que la requerida.

Answer 3

Lo que quiere es una estructura que descompone el espacio para que las regiones particulares se puedan encontrar de manera eficiente. Una descomposición octree o kD-tree debería permitirle hacerlo bien, ya que solo 'abrirá' la sección del árbol que contiene su punto p para buscar puntos cercanos. Esto debería permitirle poner un límite asintótico bastante bajo sobre la cantidad de puntos extra que necesita para comparar la distancia (sabiendo que debajo de cierto nivel de descomposición, todos los puntos están lo suficientemente cerca). Desafortunadamente, no conozco la literatura en esta área lo suficientemente bien como para dar indicaciones más detalladas. Mi encuentro con estas cosas proviene del algoritmo de simulación Barnes-Hut n-Body.

Aquí está another question estrechamente relacionado con este. y another. Y a third, mencionando una estructura de datos (Hilbert R-Trees) de la que no había oído hablar anteriormente.

Answer 4

No entiendo su API, puede redondear todos los puntos en un PointCloud que se encuentran dentro de una esfera arbitraria, pero también dice que las nubes de puntos están almacenadas? En ese caso, ¿no debería obtener una lista de PointClouds que se encuentra dentro de la esfera dada? De lo contrario, ¿cuál es el punto (excusa del juego de palabras) para almacenar PointClouds?

En lugar de tratar de definir la API de antemano, defínala cuando la necesites. No es necesario implementar algo que nunca se utilizará, y mucho menos optimizar una función que nunca se llamará (a menos que sea por diversión, por supuesto :)).

Creo que debería implementar el sacrificio de caja delimitadora, seguido de la búsqueda de esfera más detallada como primera implementación. Tal vez no sea un cuello de botella como piensas, y tal vez tengas cuellos de botella mucho más serios que considerar. Siempre es posible optimizarlo más tarde cuando realmente vea que tiene todo funcionando en conjunto como lo planeó.

Answer 5

VTK pueden ayudar:

void vtkAbstractPointLocator::FindPointsWithinRadius (
double R, double x, double y, double z, vtkIdList * result
)

Las subclases de vtkAbstractPointLocator contienen diferentes estructuras de datos para la aceleración de búsqueda: cubos regulares, KD-árboles, y octrees.

Answer 6

Eche un vistazo a A Template for the Nearest Neighbor Problem (Larry Andrews at DDJ). Es solo 2D, tiene una complejidad de recuperación de O (log n), pero también podría adoptarse para 3D.