algorithmquadtree

QuadTree find neighbor


I'm searching for a algorithm to find neighbors of a quadtree, in the example image, I got the red node, how to find the blue nodes. Any ideas?

example


Solution

  • There are some known algorithms. Check them out.

    1. Kunio Aizawa et al. - Constant Time Neighbor Finding in Quadtrees: An Experimental Result
    2. Kasturi Varadarajan - All Nearest Neighbours via Quadtrees
    3. Robert Yoder, Peter Bloniarz - A Practical Algorithm for Computing Neighbors in Quadtrees, Octrees, and Hyperoctrees