Almacene puntos 2D para recuperarlos rápidamente dentro de un rectángulo

Question

Tengo una gran cantidad de puntos 2D y quiero obtener rápidamente los que se encuentran en un cierto rectángulo. Digamos un '.' es cualquier punto y 'X' es un punto que quiero encontrar dentro de un rectángulo que tenga 'T' como TopLeft y 'B' como puntos BottomRight:

. . . . . .
. T-----+ .
. | X X | .
. +-----B .
. . . . . .

He probado un std :: set con un functor de clasificación que ordena el punto TopLeft al principio y el BottomRight al final del conjunto. Al ordenar primero por valor X, esto daría como resultado que se encuentren los siguientes puntos.

. . . . . .
. T-----+ .
X | X X | X
. +-----B .
. . . . . .

Esto significa que tendría que verificar cada punto encontrado, si realmente está dentro del rectángulo. No muy bueno.

¿Cuál sería una mejor manera de hacer esto?

Mi lenguaje es C ++ (Windows) y tengo el STL y el refuerzo disponibles.

Actualizar

Después de leer las respuestas hasta ahora, me di cuenta de que no he tenido en cuenta todos los parámetros de mi problema: no hay un rectángulo fijo. El usuario puede establecer rectángulos en tiempo de ejecución. Esto significa que ordenar el conjunto de puntos promete ser más eficiente que una búsqueda lineal a través de todos los puntos como lo sugiere Artelius antes de esta actualización. ¡Sin embargo, aún lo intentaré! No espero que el usuario establezca un rectángulo muy frecuente. Entonces, con respecto al esfuerzo de implementación, podría parecer una buena solución para mí.

Answer 1

Puede almacenar los puntos en un índice espacial usando quad o r-trees. Luego, dado el rectángulo, podría encontrar todos los nodos del árbol que se superponen, luego tendría que comparar cada punto en este subconjunto para ver si cae en el rectángulo.

En esencia, el árbol espacial lo ayuda a podar el espacio de búsqueda.

Es posible que pueda usar una solución más simple, como dividir los puntos en rangos. Digamos donde x es de 0,10 como un rango, 11,20 como otro. Cualquier solución que le permita podar el espacio de búsqueda será útil.

Answer 2

Consulte esta pregunta . El repositorio de algoritmos Stony Brook tiene algunas implementaciones de KDTrees en C ++, aunque no son parte de STL ni Boost.

Answer 3

La ordenación de una matriz lleva O ( n log n ) tiempo. Simplemente verificar cada punto individualmente (sin ordenar) toma O ( n ) tiempo.

Ergo, solo pasar y verificar cada punto es más rápido que ordenar. Y es más rápido que construir un quadtree también.

EDITAR: si tiene muchos rectángulos para verificar, es una historia diferente. Pero si solo necesita verificar un número pequeño y fijo de rectángulos, hágalo de la forma "obvia". camino!

Answer 4

usa un quadtree y tiene 3 tipos de nodos qtree:

1. el nodo está fuera del rectángulo de destino: ignorar
2. el nodo está dentro del rectángulo objetivo: incluye todos los puntos dentro del nodo
3. el nodo está parcialmente fuera del rectángulo: verifique los límites en los puntos dentro del nodo

Answer 5

Siguiendo el enlace de Yuval F, encontré Búsqueda de rango , que parece ser el tipo exacto de cosas que estás buscando. Seguí algunos enlaces desde allí y encontré CGAL , una biblioteca de C ++ de código abierto, que implementa una búsqueda de rango, con ejemplos aquí .

Answer 6

Su función de clasificación podría verificar puntos a medida que se agregan dentro del rectángulo y ordenar todos los puntos dentro del rectángulo antes de todos los puntos fuera del rectángulo. Tendría que realizar un seguimiento de cuántos de cada uno existe, o utilizar una búsqueda binaria en todo el conjunto para encontrar el punto de corte en el momento de la búsqueda.