The Cuik KD-Tree Library


cuik-kdtree.h

Go to the documentation of this file.
00001 #ifndef CUIKKDTREEH
00002 #define CUIKKDTREEH
00003 
00004 #include "definitions.h"
00005 #include "rectangle.h"
00006 
00022 #define KDTPTR(a) ((TKDtree *)(a))
00023 
00036 typedef struct {
00037   boolean isLeaf;           
00039   /* for all sub-trees */
00040   unsigned int nd;          
00041   unsigned int n;           
00042   unsigned int m;           
00043   double r;                 
00044   Trectangle ambient;       
00045   unsigned int height;      
00046   double volume;            
00048   /* for internal nodes */
00049   unsigned int splitDim;    
00050   double splitValue;        
00051   void *left;               
00052   void *right;              
00053   void *leftLeaf;           
00054   void *rightLeaf;          
00056   /* for leaves */
00057   void *nextLeaf;           
00058   double **p;               
00059   unsigned int *id;         
00060   Trectangle boundingBox;   
00061   Trectangle samplingArea;  
00063 } TKDtree;
00064 
00079 TKDtree *InitKDTree(Trectangle *ambient,unsigned int m,double r,unsigned int n,
00080                     double **points,unsigned int *ids);
00081 
00093 void AddPoint2KDtree(unsigned int *topology,double *point,unsigned int id,TKDtree **kdt);
00094 
00106 unsigned int NearestNeighbour(unsigned int *topology,double *point,TKDtree *kdt);
00107 
00120 void NeighboursInBall(unsigned int *topology,double *point,double r,
00121                       unsigned int *n,unsigned int **ids,TKDtree *kdt);
00122 
00134 void SampleInKDtree(double *point,TKDtree *kdt);
00135 
00141 void DeleteKDtree(TKDtree *kdt);
00142 
00143 #endif