educative.io

Building and Searching Location Id in QuadTree

Courses
,
#1

@Design_Gurus I have many doubts that I am trying to find:

  • From root node how will you decide which children node to traverse. For example if you have long/lat of user how can you compare with current node in quadTree and move forward towards children node.
  • While finding the neighbors of the current grid how will you know till how far do you need to go in forward and backward in case of Double linkedList in the leaf?
#2

Hi AmSh,

We can Insert in QuadTree using following steps
Insertion: This is a recursive function used to store a point in the quadtree.

  1. Start with the root node as the current node.
  2. If the given point is not in the boundary represented by the current node, stop insertion
    with error.
  3. Determine the appropriate child node to store the point.
  4. If the child node is the empty node, replace it with a point node representing the
    point. Stop insertion.
  5. If the child node is a point node, replace it with a region node. Call insert for
    the point that just got replaced. Set the current node as the newly formed region
    node.
  6. If the selected child node is a region node, set the child node as the current node.
    Goto step 2.

In order to determine neighbors of a given cell, we first note that the bit patterns of the locational codes of two neighboring cells differ by the binary distance between the two cells. Once the locational codes of the desired neighbor have been determined, the desired neighbor can be found by traversing the tree downward from the root cell. However, as described in [Samet 90b], it can be more efficient to first traverse the tree upward from the given cell to the smallest common ancestor of the cell and its neighbor and then traverse the tree downward to the neighbor. Fortunately, locational codes also provide an efficient means for determining this smallest common ancestor. Assuming a bi-tree, the neighbor’s locational code is determined, as described above, from the given cell’s locational code and the specified direction to the neighbor. The given cell’s locational code is then XOR’ed with the neighbor’s locational code to generate a difference code. The bi-tree is then traversed upward from the given cell to the first level where the corresponding bit in the difference code is a 0 bit. This 0 bit indicates the smallest level in the bi-tree where the two locational codes are the same. The cell reached by traversing upward to this level is the smallest common ancestor.

I hope you will understand now,