QuadTree find neighbor

algorithm quadtree
sebbn picture sebbn · Sep 5, 2015 · Viewed 8.6k times · Source

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

Answer

torvin picture torvin · Sep 5, 2015

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

Related questions

Quadtree explanation and C implementation

Please explain quadtrees and provide simple code (preferably in C) for insertion and searching.

Read More
Quadtree Nearest Neighbour Algorithm

I have implemented a quadtree structure for n points as well as a method for returning an array of points within a given rectangle. I can't seem to find an algorithm to efficiently find the point that is closest to …

Read More
How do I check if an array includes a value in JavaScript?

What is the most concise and efficient way to find out if a JavaScript array contains a value? This is the only way I know to do it: function contains(a, obj) { for (var i = 0; i < a.length; i++) { …

Read More