Any references on how to implement quadtrees with periodic limits?

Question

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

Why not split up your "search circle" into pie charts with pi/2 angle? Lets see if I can get this through via text and a simple image.

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

The idea is to see the "circle search" as four "pie charts", so when you do a search with C(a, b, L) you need to take into account that when passing down in the quadtree, the circle doesn't only intersect upper left corner of the quadtree, so in this case you would have to branch down into four branches (not just one, if this area wasn't periodic).

Answer 2

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 3

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.