btree.c
Go to the documentation of this file.
1 #include "btree.h"
2 
3 #include "algebra.h"
4 
5 #include <string.h>
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;i<nd;i++)
48  {
49  range=GetBoxInterval(i,ambient);
50  SetRectangleLimits(i,LowerLimit(range),UpperLimit(range),&rec);
51  }
52 
53  p=GetChartCenter(mp);
54 
55  t->kdtree=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 
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 boolean PointInBTree(double eps,double *p,TBTree *t)
114 {
115  boolean found;
116  unsigned int nn,*n;
117 
118  #if (_KDTREE==1)
119  NeighboursInBall(p,eps,&nn,&n,t->kdtree);
120 
121  found=(nn>0);
122  if (found)
123  free(n);
124  #endif
125 
126  #if (_KDTREE==2)
127  double *d;
128 
129  QueryKDTreeR(p,eps,(int *)(&nn),(int **)(&n),&d,t->kdtree);
130 
131  found=(nn>0);
132  if (found)
133  {
134  free(n);
135  free(d);
136  }
137  #endif
138 
139  return(found);
140 }
141 
142 void SearchInBtree(Tchart *mp,unsigned int *nn,unsigned int **n,TBTree *t)
143 {
144  #if (_KDTREE==1)
145  NeighboursInBall(GetChartCenter(mp),t->r,nn,n,t->kdtree);
146  #endif
147 
148  #if (_KDTREE==2)
149  double *d;
150  unsigned int i;
151 
152  if (t->tp==NULL)
153  QueryKDTreeR(GetChartCenter(mp),t->r,(int *)nn,(int **)n,&d,t->kdtree);
154  else
155  {
156  /* The NN library can only deal with angles in [-pi,pi] but
157  we might have larger angles (specially in helix). Thus,
158  we map all angular variables in the query point to [-pi,pi].
159  This will return a larger list of potential neighbours
160  when using angular ranges larger than [-pi,pi]
161  */
162  double *p;
163 
164  NEW(p,t->m,double);
165  memcpy(p,GetChartCenter(mp),sizeof(double)*t->m);
166  ArrayPi2Pi(t->m,t->tp,p);
167 
168  QueryKDTreeR(p,t->r,(int *)nn,(int **)n,&d,t->kdtree);
169 
170  free(p);
171  }
172 
173  if (*nn>0)
174  {
175  free(d); /* distance to each point not used */
176 
177  /* Translate from cardinals to identifiers. */
178  for(i=0;i<*nn;i++)
179  (*n)[i]=t->n2id[(*n)[i]];
180  }
181  #endif
182 }
183 
185 {
186  if (t->tp!=NULL)
187  free(t->tp);
188 
189  #if (_KDTREE==1)
190  DeleteKDtree(t->kdtree);
191  #endif
192 
193  #if (_KDTREE==2)
194  free(t->n2id);
195  DeleteKDTree(t->kdtree);
196  #endif
197 }
198 
void AddChart2Btree(unsigned int id, Tchart *mp, TBTree *t)
Adds a chart to the tree.
Definition: btree.c:75
Tinterval * GetBoxInterval(unsigned int n, Tbox *b)
Returns a pointer to one of the intervals defining the box.
Definition: box.c:270
unsigned int * tp
Definition: btree.h:45
unsigned int m
Definition: btree.h:43
#define NEW(_var, _n, _type)
Allocates memory space.
Definition: defines.h:385
void SearchInBtree(Tchart *mp, unsigned int *nn, unsigned int **n, TBTree *t)
Search for neighbouring charts.
Definition: btree.c:142
void ArrayPi2Pi(unsigned int n, unsigned int *t, double *a)
Applies PI2PI to an array.
Definition binary tree of charts.
#define INIT_NUM_POINTS_IN_BTREE
Initial number of points in the tree.
Definition: btree.h:29
void DeleteBTree(TBTree *t)
Chart tree destructor.
Definition: btree.c:184
boolean PointInBTree(double eps, double *p, TBTree *t)
Point in a tree.
Definition: btree.c:113
void Error(const char *s)
General error function.
Definition: error.c:80
double r
Definition: btree.h:44
A chart on a manifold.
Definition: chart.h:70
unsigned int GetBoxNIntervals(Tbox *b)
Box dimensionality.
Definition: box.c:1016
double GetChartRadius(Tchart *c)
Returns de range of the chart.
Definition: chart.c:941
double LowerLimit(Tinterval *i)
Gets the lower limit.
Definition: interval.c:79
void InitBTree(unsigned int id, Tchart *mp, Tbox *ambient, unsigned int *topology, TBTree *t)
Initializes a binary tree of charts.
Definition: btree.c:19
unsigned int GetChartAmbientDim(Tchart *c)
Dimensionality of the ambient space.
Definition: chart.c:963
double UpperLimit(Tinterval *i)
Gets the uppser limit.
Definition: interval.c:87
A box.
Definition: box.h:83
#define MEM_DUP(_var, _n, _type)
Duplicates a previously allocated memory space.
Definition: defines.h:414
double * GetChartCenter(Tchart *c)
Returns the center of the chart.
Definition: chart.c:936
Binary tree of charts.
Definition: btree.h:42
Defines a interval.
Definition: interval.h:33