data-structurescompressionnearest-neighborquadtreeneighbours

QuadTree Neighbours defining


Hi i'd like to find all the neoghbours of node in a quadTree that has size up to 2^(10^9) per edge and up to 10^6 nodes in total.

I have seen this post Quadtree Nearest Neighbour Algorithm
I had an idea with putting into some ordered set the centers of each node during dfs and them during postorder in dfs defining whether the center of some node has overlap. The problem is that with comparing such huge numbers idk how to even store the bounds.

language is c++

How would you try to store such points and bounds?

enter image description here


Solution

  • Alright, to solution was to scale the quadtree. With the limit of 10^6 nodes totally its easy to do. As we can imagine it as 10^3 x 10^3 tile map.