Des références sur la façon d'implémenter des quadtrees avec des limites périodiques?

Question

J'ai des données spatiales - (x, y) points sur un plan - que je partitionne à l'aide de quadtrees. L'idée est de trouver quels points sont voisins d'un point donné (a, b). Les points sont voisins s'il y a une distance (disons L) entre les deux. Le problème est que l'espace est périodique, c'est-à-dire si un point est très proche du bord (< L) ce point devrait être voisin d'un point proche du bord opposé. (Par périodique dans ce cas, je veux dire que l'avion se répète)

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

C'est des points (a, b) et (c, d) et (h, i) devrait être voisins. Les voisins de (a, b) sont les points à l'intérieur du cercle de rayon L avec le centre (a, b).

Les papiers, comment-tous sont les bienvenus.

Merci,

---

Guys:

Merci pour vos réponses, je ne l'ai pas vérifier stackoverflow pendant un certain temps était occupé sur un autre projet vérifiera vos réponses tout de suite! Merci beaucoup.

Answer 1

Pourquoi ne pas diviser votre « recherche cercle » dans des diagrammes circulaires avec angle pi/2? Voyons voir si je peux obtenir ceci par l'intermédiaire du texte et d'une image simple.

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

L'idée est de voir la « recherche de cercle » comme quatre « camemberts », donc quand vous effectuez une recherche avec C (a, b, L), vous devez prendre en compte que lors du passage dans le quadtree, le cercle ne croise pas seulement le coin supérieur gauche du quadtree, donc dans ce cas vous devez vous diviser en quatre branches (pas seulement une, si cette zone n'était pas périodique).

Answer 2

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

où px est la période x.

ydist et le reste est laissé comme un exercice pour le lecteur :-)

Answer 3

Il semble plus simple de conserver le quadtree tel quel, puisque seul le niveau racine est répliqué périodiquement. Pour prendre en compte la périodicité, faites plusieurs demandes (x+i*dx,y+j*dy,L) pour chaque demande (x,y,L). Boucle sur i, j de sorte que le disque de requête croise le nœud racine de l'arbre.