btree.c Go to the documentation of this file. 1 #include "btree.h" 2  3 #include "algebra.h" 4  5 #include 6  19 void InitBTree(unsigned int id,Tchart *mp,Tbox *ambient,unsigned int *topology,TBTree *t) 20 { 21  t->m=GetChartAmbientDim(mp); 22  23  /* Threshold larger than 'r' since charts center are not in the same 24  tangent space. The distance between the centers of the charts will 25  be larger than 'r' (probably r/CE, CE the user defined parameter. 26  We somehow assuem that CE is always below 0.5 (i.e. that the angle 27  between tangent spaces is always below 60 deg, which is very large)*/ 28  t->r=2*GetChartRadius(mp); 29  30  if (topology==NULL) 31  t->tp=NULL; 32  else 33  { 34  NEW(t->tp,t->m,unsigned int); 35  memcpy(t->tp,topology,sizeof(unsigned int)*t->m); 36  } 37  38  #if (_KDTREE==1) 39  { 40  unsigned int nd,i; 41  double *p; 42  Trectangle rec; 43  Tinterval *range; 44  45  nd=GetBoxNIntervals(ambient); 46  InitRectangle(nd,NULL,NULL,&rec); 47  for(i=0;ikdtree=InitKDTree(&rec,topology,25,0,1,&p,&id); 56  57  DeleteRectangle(&rec); 58  } 59  #endif 60  61  #if (_KDTREE==2) 62  if (t->tp==NULL) 63  t->kdtree=CreateKDTree(t->m); 64  else 65  t->kdtree=CreateKDTreeT(t->m,(int *)t->tp); 66  67  t->mp=INIT_NUM_POINTS_IN_BTREE; 68  t->np=0; 69  NEW(t->n2id,t->mp,unsigned int); 70  71  AddChart2Btree(id,mp,t); 72  #endif 73 } 74  75 void AddChart2Btree(unsigned int id,Tchart *mp,TBTree *t) 76 { 77  #if (_KDTREE==1) 78  AddPoint2KDtree(GetChartCenter(mp),id,&(t->kdtree)); 79  #endif 80  81  #if (_KDTREE==2) 82  if (t->np==1000000) 83  Error("The kd-tree in the NN library can only hold one million points"); 84  85  if (t->np==t->mp) 86  MEM_DUP(t->n2id,t->mp,unsigned int); 87  t->n2id[t->np]=id; 88  t->np++; 89  90  if (t->tp==NULL) 91  AddPoint2KDTree(GetChartCenter(mp),t->kdtree); 92  else 93  { 94  /* The NN library can only deal with angles in [-pi,pi] but 95  we might have larger angles (specially in helix). Thus, 96  we map all angular variables in the stored points to [-pi,pi]. 97  This will return a larger list of potential neighbours 98  when using angular ranges larger than [-pi,pi] 99  */ 100  double *p; 101  102  NEW(p,t->m,double); 103  memcpy(p,GetChartCenter(mp),sizeof(double)*t->m); 104  ArrayPi2Pi(t->m,t->tp,p); 105  106  AddPoint2KDTree(p,t->kdtree); 107  108  free(p); 109  } 110  #endif 111 } 112  113 void SearchInBtree(Tchart *mp,unsigned int *nn,unsigned int **n,TBTree *t) 114 { 115  #if (_KDTREE==1) 116  NeighboursInBall(GetChartCenter(mp),t->r,nn,n,t->kdtree); 117  #endif 118  119  #if (_KDTREE==2) 120  double *d; 121  unsigned int i; 122  123  if (t->tp==NULL) 124  QueryKDTreeR(GetChartCenter(mp),t->r,(int *)nn,(int **)n,&d,t->kdtree); 125  else 126  { 127  /* The NN library can only deal with angles in [-pi,pi] but 128  we might have larger angles (specially in helix). Thus, 129  we map all angular variables in the query point to [-pi,pi]. 130  This will return a larger list of potential neighbours 131  when using angular ranges larger than [-pi,pi] 132  */ 133  double *p; 134  135  NEW(p,t->m,double); 136  memcpy(p,GetChartCenter(mp),sizeof(double)*t->m); 137  ArrayPi2Pi(t->m,t->tp,p); 138  139  QueryKDTreeR(p,t->r,(int *)nn,(int **)n,&d,t->kdtree); 140  141  free(p); 142  } 143  144  if (*nn>0) 145  { 146  free(d); /* distance to each point not used */ 147  148  /* Translate from cardinals to identifiers. */ 149  for(i=0;i<*nn;i++) 150  (*n)[i]=t->n2id[(*n)[i]]; 151  } 152  #endif 153 } 154  155 void DeleteBTree(TBTree *t) 156 { 157  if (t->tp!=NULL) 158  free(t->tp); 159  160  #if (_KDTREE==1) 161  DeleteKDtree(t->kdtree); 162  #endif 163  164  #if (_KDTREE==2) 165  free(t->n2id); 166  DeleteKDTree(t->kdtree); 167  #endif 168 } 169  AddChart2Btreevoid AddChart2Btree(unsigned int id, Tchart *mp, TBTree *t)Adds a chart to the tree. Definition: btree.c:75 GetBoxIntervalTinterval * GetBoxInterval(unsigned int n, Tbox *b)Returns a pointer to one of the intervals defining the box. Definition: box.c:270 TBTree::tpunsigned int * tpDefinition: btree.h:45 TBTree::munsigned int mDefinition: btree.h:43 NEW#define NEW(_var, _n, _type)Allocates memory space. Definition: defines.h:385 SearchInBtreevoid SearchInBtree(Tchart *mp, unsigned int *nn, unsigned int **n, TBTree *t)Search for neighbouring charts. Definition: btree.c:113 ArrayPi2Pivoid ArrayPi2Pi(unsigned int n, unsigned int *t, double *a)Applies PI2PI to an array. Definition: basic_algebra.c:496 btree.hDefinition binary tree of charts. INIT_NUM_POINTS_IN_BTREE#define INIT_NUM_POINTS_IN_BTREEInitial number of points in the tree. Definition: btree.h:29 DeleteBTreevoid DeleteBTree(TBTree *t)Chart tree destructor. Definition: btree.c:155 Errorvoid Error(const char *s)General error function. Definition: error.c:80 algebra.h TBTree::rdouble rDefinition: btree.h:44 TchartA chart on a manifold. Definition: chart.h:70 GetBoxNIntervalsunsigned int GetBoxNIntervals(Tbox *b)Box dimensionality. Definition: box.c:992 GetChartRadiusdouble GetChartRadius(Tchart *c)Returns de range of the chart. Definition: chart.c:938 LowerLimitdouble LowerLimit(Tinterval *i)Gets the lower limit. Definition: interval.c:79 InitBTreevoid InitBTree(unsigned int id, Tchart *mp, Tbox *ambient, unsigned int *topology, TBTree *t)Initializes a binary tree of charts. Definition: btree.c:19 GetChartAmbientDimunsigned int GetChartAmbientDim(Tchart *c)Dimensionality of the ambient space. Definition: chart.c:960 UpperLimitdouble UpperLimit(Tinterval *i)Gets the uppser limit. Definition: interval.c:87 TboxA box. Definition: box.h:83 MEM_DUP#define MEM_DUP(_var, _n, _type)Duplicates a previously allocated memory space. Definition: defines.h:414 GetChartCenterdouble * GetChartCenter(Tchart *c)Returns the center of the chart. Definition: chart.c:933 TBTreeBinary tree of charts. Definition: btree.h:42 TintervalDefines a interval. Definition: interval.h:33