Binary Space Partitioning Data Structure For Donut 2D Space

Question

I have a 2D map which wraps at the edges. So if you move off the right edge you will reappear at the left side of the map. Likewise with the three other edges.

This is inheritable a problem for the KDTree which I use to find elements in range of points. Normally you would check whether the hyper sphere collides with the hyper plane to see if you should continue searching the other side of the tree, but this check does not work with wrapping edges.

Is there any way to modify the KD Tree to work with donut 2D spaces?

Answer 1

The data structure doesn't have to change, but the search procedure does. Represent each point by coordinates (x, y) in [0, w) * [0, h), where w is the width of the map, h is the height, and * denotes a Cartesian product. Store these points in a normal KD tree.

The fundamental primitive for searching a KD tree is, given a point (x, y) and a rectangle [a, b] * [c, d], determine the distance (squared) from the point to the rectangle. Normally this is g(x, a, b)² + g(y, c, d)², where

g(z, e, f) = e - z if z < e
             0     if e <= z <= f
             z - f if f < z

is the one-dimensional distance of z to [e, f]. In a toroidal space, we modify g slightly to account for wraparound.

g(z, e, f, v) = min(e - z, (z + v) - f) if z < e
                0                       if e < z < f
                min(z - f, (e + v) - z) if f < z.

and the distance squared is g(x, a, b, w)² + g(y, c, d, h)². I expect that the running times will be comparable for this variant. (I'd redo the recurrences, but the worst-case for regular KD trees is much worse than practice most of the time - O(n^1/2) for identifying the nearest neighbor in 2D among n points.)

Answer 2

Jitamaro suggested but didn't explain a method based on a "2x size" quadtree. It's a reasonable suggestion, except the quadtree uses four times as many nodes rather than two, as I'll explain below before tentatively suggesting an alternative method.

Suppose each (x,y) coordinate has -.5 < x <= .5 and -.5 < y <= .5 and whenever j, k are integers, point (x+j,y+k) is identical with point (x,y). Let quadtree T cover points with coordinates in the range -1 < x,y <= 1. Each time you add an item at (x,y) to T, where -.5 < x,y <= .5, let x' = {x-1 if x>0 else x+1}, and y' = {y-1 if y>0 else y+1}. Also add the item at (x,y'), (x',y'), and (x',y). [When you delete points later, again calculate (x', y') et al and delete them too.] It's easy to see that nearest-point lookups will work properly, so long as any lookup coordinate outside interval (-.5,.5] is adjusted properly.

If the four-fold number of nodes is a deal-breaker, note that if coordinates as described above are used in subtrees above say level k=3, and relative coordinates are stored below level k, it should be possible to maintain single copies of subtrees below level k. That is, each subtree at level k would have four parents. (I haven't thought about this enough to know if this totally works; will edit answer if I find it doesn't.)