search2007.01.23 18:19

from : http://filebox.vt.edu/users/jegrant/stuff/kdtrees.html

Spatial Data Structures

K-D Trees, PR Quadtrees

K-Dimensional Trees work with "k" dimensions not just 1 dimension as BSTs do
Point Regional (PR) Quadtrees have 2k branches at each node given data in a k-dimensional space
Multi-dimensional queries

Range queries

Applications

Geographic Information Systems (GIS)
Computer Graphics
Robotics

--------------------------------------------------------------------------------


K-D Trees: a Generalization of BSTs

Binary Search Trees search using 1 key

Some data naturally contain multiple dimensions

Given k-dimensional data, a K-D tree indexes dimension 0 of the data at level 0, dimension 1 at level 1, etc.


Figure 13.8 (b) from book

 

Definition: the discriminator is the search key at each level i

calculation of discriminator : i mod k

Given 3-dimensional data indexed by (x,y,z),

y is the discriminator if the level number of the k-d tree is 10 since 10 mod 3 = 1


--------------------------------------------------------------------------------


K-D Trees ….

At ith level of the tree, discriminator indexes the tree exactly as for a BST: select i mod kth coordinate of data item and compare it with i mod kth coordinate of value stored at node of K-D tree.

If (data value < node value)

    take-left-branch

else

    take-right-branch // >= case

For 2-D space, K-D tree subdivides space into rectangles. The direction of subdivision alternates among the dimensions:


 


Figure 13.8 (a) from book


--------------------------------------------------------------------------------

K-D Tree Find Operation

Simple modification of BST search.

Must determine correct discriminator at each level (= level number mod k) to find out what coordinate of key to use for comparison at that level


KDNode* KD::Kdfindhelp(KDNode* rt, ELEM val, int lev, int K) const

{

   //lev: current level (mod K); K: number of dimensions

   //dkey(val, i) returns the key value of val for dimension i

   if (rt == NULL)

      return NULL; // Empty tree

   else if (val == rt->value)

      return rt; // Found it

   else if (dkey(val, lev) < dkey(rt->value, lev))

      return Kdfindhelp(rt->left, val, (lev+1) % K, K);

   else

      return Kdfindhelp(rt->right, val, (lev+1) % K, K);

}

Example: find (55, 80) in


Figure 13.8 (b) from book


--------------------------------------------------------------------------------

Deleting Nodes in a K-D Tree

Deletion similar to BST but slightly harder.

Step 1: find node to be deleted

Step 2: two cases must be handled

No children - replace ptr to node by NULL

Has children - replace node by minimum node in right subtree using KDfindmin (harder to find than in a BST!)

If no right subtree exists, then first move left subtree to become right subtree and proceed with usual delete procedure using KDfindmin

Special note: node found by KDfindmin may occur in middle of tree. Recursive call to the delete routine must be used to replace it (careful!)


--------------------------------------------------------------------------------


KDfindmin

Must search both left and right subtrees to find minimum value for a given discriminator


KDNode* KD::KDfindmin(KDNode* rt, int discrim, int level, int K)

{

    // discrim: discriminator key used for minimum search

    // level: current level(mod K); K: # of levels in key

    KDNode *temp1, *temp2;

    if (rt == NULL)

      return NULL;

    temp1 = KDfindmin(rt->left, discrim, (level+1)%K, K)

    if (discrim != level)

   {

       //Min val could be on l/r side

       temp2=KDfindmin(rt->right, discrim, (level+1)%K,K);

       if((temp1 == NULL) || ((temp2 != NULL) && (dkey(temp2->value,discrim) <

               dkey(temp1->value,discrim))))

           temp1 = temp2;   //in line above, rt subtree has smaller key value

    }

    // temp1 has the smallest value in children (if any)

    if ((temp1 == NULL) || (dkey(rt->value,discrim) <

               dkey(temp1->value,discrim)))

          return rt;

    else

         return temp1;

}

Now delete C(70, 10) from


Figure 13.8 (b) from book


--------------------------------------------------------------------------------

K-D Tree Range Query

Problem: find all k-dimensional points within distance 'D' of point P

Must search through K-D tree using Euclidean distance formula

If any coordinate in the K-D tree is more than distance 'D' away from point P's corresponding coordinate, then no need to search one of the subtrees below that node.

Example: if D=10, y-coordinate of node is being examined and is 13 less than the y-coordinate of P, then no search needed of left subtree below that node


void KDRegionSearch(KDNode* rt, ELEM val, int D, int level, int K)

{

    // val: search key; D: search radius;

    // level: current level (mod K); K: # of dimensions

    // Check if record at rt is in circle

    if(InCircle(key(val), D, key(rt->value)))

       printout(rt->value);//Do appropriate action with node

    if(dkey(rt->value,level)>(dkey(val,level)-D)      //Go left

       KDRegionSearch(rt->left, val, D, (level+1)%K,K);

    if(dkey(rt->value,level)<(dkey(val,level)+D))     //Go right

       KDRegionSearch(rt->right, val, D, (level+1) % K, K);

 }

Function 'InCircle' uses Euclidean distance to test if point is within distance D of query point

신고
Creative Commons License
Creative Commons License
Posted by myditto

티스토리 툴바