Tutti i riferimenti su come implementare quadtree con limiti periodici?
-
06-09-2019 - |
Domanda
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 ( 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. |=================== | ===================|
|(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)|
| ================== | ===================|
Soluzione
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).
Altri suggerimenti
xdist = min( (x1-x2) % px, (x2-x1) % px )
dove px è l'x-periodo.
ydist e il resto è lasciato come esercizio per il lettore: -)
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.