Tutti i riferimenti su come implementare quadtree con limiti periodici?

Question

Ho dati spaziali - (x, y) punti su un piano - che sto partizionamento utilizzando quadtree. L'idea è di trovare quale i punti sono vicini a un determinato (a b,) punto. I punti sono vicini se c'è qualche (diciamo L) distanza tra i due. Il problema è che lo spazio è periodica, cioè se un punto è molto vicino al bordo (

|=================== | ===================|
|(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)|
| ================== | ===================|

Questa è punti (a, b) e (c, d), e (h, i), devono essere vicini. I vicini di (a, b) sono i punti interni al cerchio di raggio L con centro (a, b).

Papers, how-to sono tutti benvenuti.

Grazie,

---

Ragazzi:

Grazie per le vostre risposte, ho non controlla StackOverflow per un po 'è stato impegnato su un altro progetto controllerà le vostre risposte subito! Grazie mille.

Answer 1

Perché non dividere il "search cerchio" in grafici a torta con angolo di pi / 2? Vediamo se riesco a ottenere questo per via testo e un'immagine semplice.

alt text http://img168.imageshack.us/img168/8426/circleinquarters .gif

L'idea è quella di vedere la "ricerca di cerchio", come quattro "grafici a torta", in modo che quando si esegue una ricerca con C (a, b, L) è necessario tener conto che quando passa giù in quadtree, il cerchio non solo si intersecano in alto a sinistra del quadtree, quindi in questo caso si avrebbe dovuto espandersi in quattro rami (e non uno solo, se questa zona non era periodico).

Answer 2

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

dove px è l'x-periodo.

ydist e il resto è lasciato come esercizio per il lettore: -)

Answer 3

Sembra semplice per mantenere il Quadtree così com'è, poiché solo il livello principale viene periodicamente replicata. Per prendere in considerazione la periodicità, fare diverse richieste (x+i*dx,y+j*dy,L) per ogni richiesta (x,y,L). Anello sulla i, j tale che il disco interrogazione interseca il nodo radice dell'albero.