Cualquier referencia sobre cómo implementar quadtrees con límites periódica?

Question

Tengo datos espaciales - (x, y) puntos en un plano - que estoy creación de particiones con quadtrees. La idea es encontrar cuales son los puntos vecinos a un (a b), punto dado. Los puntos son vecinos si hay alguna (por ejemplo L) distancia entre los dos. El problema es que el espacio es periódica, es decir, si un punto es muy cerca del borde (

|=================== | ===================|
|(a, b)         (c,d)| (a, b)      (c,d)  |
|                    |                    |
|  (e,f)             |   (e, f)           |
|               (h,i)|               (h,i)|
|=================== | ===================|
|(a, b)         (c,d)| (a, b)      (c,d)  |
|                    |                    |
|  (e,f)             |   (e, f)           |
|               (h,i)|               (h,i)|
| ================== | ===================|

Es decir puntos (a, b) y (c, d) y (h, i) debe ser vecinos. Los vecinos de (a, b) son los puntos en el interior del círculo con un radio L con el centro (a, b).

Los documentos, cómo-a son todos bienvenidos.

Gracias,

---

Guys:

Gracias por sus respuestas, he no comprueba stackoverflow por un tiempo estaba ocupado en otro proyecto va a revisar sus respuestas de inmediato! Muchas gracias.

Answer 1

¿Por qué no dividir su "búsqueda círculo" en los gráficos circulares con pi ángulo / 2? Vamos a ver si puedo conseguir esto a través de a través de texto y una imagen simple.

texto alternativo http://img168.imageshack.us/img168/8426/circleinquarters .gif

La idea es ver la "búsqueda círculo" como cuatro "gráficos circulares", así que cuando se hace una búsqueda con C (a, b, L) Tienes que tener en cuenta que cuando se pasa hacia abajo en el árbol cuádruple, la círculo no sólo se cruzan esquina superior izquierda del árbol de cuatro ramas, por lo que en este caso tendría que ramifican en cuatro ramas (no sólo uno, si esta área no era periódica).

Answer 2

xdist = min( (x1-x2) % px, (x2-x1) % px )

donde px es el período de x.

ydist y el resto se deja como ejercicio para el lector: -)

Answer 3

Parece más simple para mantener el árbol cuaternario tal como es, ya que sólo el nivel de la raíz se replica periódicamente. Para tomar en cuenta la periodicidad, hacer varias peticiones (x+i*dx,y+j*dy,L) para cada solicitud (x,y,L). Loop en i, j de tal manera que el disco de consulta se cruza con el nodo raíz del árbol.