********************************************************************************
*                                                                              *
*                       Kd-tree implementation                                 *
*                    - By Ross Hemsley Sept. '09 -                             *
*                                                                              *
********************************************************************************
  About:
********************************************************************************

    The code provided here implements a kd-tree in any number of dimensions
    the number of dimensions can be modified at compile time by changing
    the definintion of the DIMENSION constant at the top of kdtree.h.

********************************************************************************
  Testing:
********************************************************************************
  
    All code has built in testing, simply setting the _TEST_ variable at the top
    of each file will make it possible to compile that file and run build in 
    tests.
    
    For example:
    
      > gcc -O3 kdtree.c utils.c -o kdtest
      > ./kdtest

    We note that the testing for the kdtree requires some test pointset to work.

********************************************************************************
  Use:
********************************************************************************  
  
    [Very similar to Natural Neighbour]

    See example.c for an example.

    To use the interpolator, we need to set up an array of verticies with 
    their associated vector values. We do this using the vertex structure.
    Each vertex contains two arrays of double, and a cached value of the 
    Voronoi Volume about that vertex, which is not elegent - but speeds up
    interpolation by a factor of two.
    
    To load points into the program, we can use the function:
    
      vertex *initPoints(double *x, double *y, double *z, 
                         double *u, double *v, double *w, int n)
                       
    Here is an example of building a simple point set:
    
      double x[] = {0,1,2};
      double y[] = {3,4,5};
      double z[] = {6,7,8};
      
      double u[] = {0,1,2};
      double v[] = {3,4,5};
      double w[] = {6,7,8};
      
      vertex* ps = initPoints(x,y,z,  u,v,w,  3);
                       
    which will take arrays containing the values of each point, and the 
    vector value at each point, along with the number of points to return 
    an array of verticies.
      
     
    -----------------------------------------------------------------------       
      Notes on using verticies directly.
    -----------------------------------------------------------------------       
    
          struct 
          {
            double v[3];
            double data[3];
            double voronoiVolume;
          } vertex;
        
        We initialise v to {x,y,z} and data to {u,v,w}. *We must also initialise
        voronoiVolume to be < 0.*
         
        *** Failing to do this will probably result in nonsense output.***   
         
    -----------------------------------------------------------------------        
    
    To do interpolation, we first need to create a kd-tree.
    We do this by using the following:
    
      treeNode* tree = addToTree(ps,0,n-1,0);  
     
    Where n is the number of points, and ps is the set of verticies.
    We can now perform interpolation by using the nearest neighbour function:

      vertex* nearestNeighbour(vertex *v, treeNode* tree)
   
    If we just want to search for an arbitrary point (x,y,z),
    we initialise the search vertex as follows:
    
      vertex find = {{x,y,z},{0,0,0}}
    
    we can then use 
    
      vertex *nn =  nearestNeighbour(&find, tree);
   
   and get the interpolated estimate at this point by extracing the
   values from nn->data.
        
********************************************************************************  

