Any references on how to implement quadtrees with periodic limits?

Question

Hi all,

I have spatial data - (x, y) points on a plane - which I'm partitioning using quadtrees. The idea is to find which points are neighbors to a given (a, b) point. The points are neighbors if there some (say L) distance between the two. The problem is that the space is periodic, that is if a point is very close to the edge (< L) this point should be neighbor of a point close to the opposite edge. (By periodic in this case I mean that the plane repeats itself)

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

That is points (a,b) and (c, d) and (h, i) should be neighbors. The neighbors of (a,b) are the points inside the circle with radius L with center (a,b).

Papers, how-to are all welcome.

Thanks,

---

Guys:

Thanks for your answers, I've not check stackoverflow for a while was busy on another project will check your answers right away! Thanks a lot.

Answer 1

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

where px is the x-period.

ydist and the rest is left as an exercise for the reader :-)

Answer 2

It seems simpler to keep the quadtree as it is, since only the root level is periodically replicated. To take periodicity into account, do several requests (x+i*dx,y+j*dy,L) for each request (x,y,L). Loop on i,j such that the query disc intersects the root node of the tree.