home *** CD-ROM | disk | FTP | other *** search
/ Los Alamos National Laboratory / LANL_CD.ISO / software / compres / src / search.c < prev    next >
C/C++ Source or Header  |  1992-02-11  |  5KB  |  203 lines
  1. /****************************************************************
  2.  
  3. COPYRIGHT (C) 1992 UNIVERSITY OF CALIFORNIA
  4.  
  5. ***************************************************************/
  6.  
  7. #include <math.h>
  8. #include "kdnode.h"
  9. #define NULL 0
  10.  
  11. int ClosestIndex;
  12. float *LoBound, *HiBound, ClosestDist, ClosestDistSq;
  13.  
  14. /****************************************************************/
  15.  
  16. int FindClosestVector(OKDTree, k, ncv, cbook, Z, CVDist)
  17. int k, ncv;
  18. float *cbook, *Z, *CVDist;
  19. struct KDTreeNode *OKDTree;
  20. {
  21.     int i;
  22.  
  23.     ClosestDist = ClosestDistSq = 1.e30;
  24.  
  25.     LoBound = (float*)malloc(k*sizeof(float));
  26.     HiBound = (float*)malloc(k*sizeof(float));
  27.     if(!LoBound || !HiBound ) {
  28.         printf("ERROR: Not enough room for malloc\n");
  29.         exit(-1);
  30.     }
  31.     for(i = 0; i < k; i++) {
  32.         LoBound[i] = -1.e30;
  33.         HiBound[i] = 1.e30;
  34.     }
  35.  
  36.     SearchOKDTree(OKDTree, k, ncv, cbook, Z);
  37.  
  38.     *CVDist = ClosestDist;
  39.     return ClosestIndex;
  40.  
  41. }
  42.  
  43. /****************************************************************/
  44.  
  45. int SearchOKDTree(Node, k, ncv, cbook, Z)
  46. struct KDTreeNode *Node;
  47. int k, ncv;
  48. float *cbook, *Z;
  49. {
  50.     int Index, i, Axis;
  51.     float Part, Store;
  52.     register float xx, delta, *cbptr, *max, *zptr;
  53.  
  54. /*________________________________________________________________*/
  55.  
  56.     if(Node->Left == NULL)  {  /*  Terminal node  */
  57.         for(i = 0; i < Node->ListSize; i++)  {
  58.             zptr = Z;
  59.             cbptr = cbook + (Index = Node->List[i])*k;
  60.             max = cbptr + k;
  61.             xx = 0.;
  62.             while(cbptr < max) {
  63.                 delta = *zptr++ - *cbptr++;
  64.                 xx += delta*delta;
  65.                 if(xx > ClosestDistSq)
  66.                     break;
  67.         }
  68.             if(xx < ClosestDistSq) {
  69.                 ClosestIndex = Index;
  70.                 ClosestDistSq = xx;
  71.         }
  72.     }
  73.  
  74.     ClosestDist = sqrt(ClosestDistSq);
  75.  
  76.     if(BallWithinBounds(Z, k))
  77.         return -1;
  78.     return 0;
  79.  
  80.     }
  81.  
  82. /*________________________________________________________________*/
  83.  
  84.     else  {  /*  Nonterminal node  */
  85.  
  86.         if(Z[Axis = Node->KeyIndex] <= (Part = Node->PartitionValue)) {
  87.             Store = HiBound[Axis];
  88.             HiBound[Axis] = Part;
  89.             i = SearchOKDTree(Node->Left, k, ncv, cbook, Z);
  90.             HiBound[Axis] = Store;
  91.             if(i == -1)
  92.                 return -1;
  93.     }
  94.  
  95.         else {  /* Search the right node */
  96.             Store = LoBound[Axis];
  97.             LoBound[Axis] = Part;
  98.             i = SearchOKDTree(Node->Right, k, ncv, cbook, Z);
  99.             LoBound[Axis] = Store;
  100.             if(i == -1)
  101.                 return -1;
  102.     }
  103.  
  104.         if(Z[Axis] <= Part) {  /* Search the right node */
  105.             Store = LoBound[Axis];
  106.             LoBound[Axis] = Part;
  107.             if(BoundsOverlapBall(Z, k)) {
  108.                 i = SearchOKDTree(Node->Right, k, ncv, cbook, Z);
  109.                 LoBound[Axis] = Store;
  110.                 if(i == -1)
  111.                     return -1;
  112.         }
  113.  
  114.             else LoBound[Axis] = Store;
  115.  
  116.     }
  117.  
  118.         else {  /* Search the left node */
  119.             Store = HiBound[Axis];
  120.             HiBound[Axis] = Part;
  121.  
  122.             if(BoundsOverlapBall(Z, k)) {
  123.                 i = SearchOKDTree(Node->Left, k, ncv, cbook, Z);
  124.                 HiBound[Axis] = Store;
  125.                 if(i == -1)
  126.                     return -1;
  127.         }
  128.  
  129.             else HiBound[Axis] = Store;
  130.  
  131.     }
  132.  
  133.         if(BallWithinBounds(Z, k))
  134.             return -1;
  135.         return 0;
  136.  
  137.     }
  138.  
  139. }
  140.  
  141. /****************************************************************/
  142.  
  143. int BallWithinBounds(z, k)
  144. register float *z;
  145. int k;
  146. {
  147.     register float delta, *lptr, *hptr, *max;
  148.  
  149.     lptr = LoBound;
  150.     hptr = HiBound;
  151.  
  152.     max = z + k;
  153.     while(z < max) {
  154.         delta = *z - *lptr++;
  155.         if(delta <= 0.)
  156.             delta = -delta;
  157.         if(delta <= ClosestDist)
  158.             return 0;
  159.         delta = *z++ - *hptr++;
  160.         if(delta <= 0.)
  161.             delta = -delta;
  162.         if(delta <= ClosestDist)
  163.             return 0;
  164.     }
  165.  
  166.     return 1;
  167.  
  168. }
  169.  
  170. /****************************************************************/
  171.  
  172. int BoundsOverlapBall(z, k)
  173. register float *z;
  174. int k;
  175. {
  176.     register float sum = 0., delta, *lptr, *hptr, *max;
  177.  
  178.     lptr = LoBound;
  179.     hptr = HiBound;
  180.  
  181.     max = z + k;
  182.     while(z < max) {
  183.  
  184.         if(*z < *lptr)
  185.             delta = *z - *lptr;
  186.         else if(*z > *hptr)
  187.             delta = *z - *hptr;
  188.         else
  189.             delta = 0;
  190.  
  191.         sum += delta*delta;
  192.         if(sum > ClosestDistSq)
  193.             return 0;
  194.  
  195.         z++;
  196.         lptr++;
  197.         hptr++;
  198.  
  199.     }
  200.  
  201.     return 1;
  202. }
  203.