Toute référence sur la façon de mettre en œuvre quadtrees avec des limites périodiques?

Question

I ai données spatiales - (x, y) des points sur un plan - que je suis le partitionnement en utilisant quadtrees. L'idée est de trouver des points qui sont voisins à un donné (a, b) le point. Les points sont voisins s'il y a certains (par exemple L) distance entre les deux. Le problème est que l'espace est périodique, qui est si un point est très proche du bord (

|=================== | ===================|
|(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) devraient être voisins. Les voisins de (a, b) sont les points à l'intérieur du cercle de rayon L avec le centre (a, b).

Papiers, comment faire sont les bienvenus.

Merci,

---

Les gars:

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? Permet de voir si je peux obtenir ce texte et par l'intermédiaire d'une simple image.

texte alt 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 l'arbre quaternaire, la cercle ne coupe pas seulement coin supérieur gauche de l'arbre quaternaire, donc dans ce cas, vous auriez à la branche en quatre branches (et pas seulement un, si ce domaine n'était pas périodique).

Answer 2

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

où px est le x-période.

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

Answer 3

Il semble plus simple de garder le quadtree tel qu'il est, puisque seul le niveau de la racine est périodiquement répliqué. Pour prendre en compte la périodicité, faire plusieurs demandes (x+i*dx,y+j*dy,L) pour chaque (x,y,L) de demande. Boucle sur i, j de telle sorte que le disque de requête coupe le noeud racine de l'arbre.