box_list.c
Go to the documentation of this file.
1 #include "box_list.h"
2 
3 #include "interval.h"
4 
5 #include "boolean.h"
6 #include "defines.h"
7 
8 #include <stdio.h>
9 #include <stdlib.h>
10 #include <string.h>
11 
21 /*
22  * Starts a list of boxes
23  */
25 {
26  InitList(sizeof(Tbox),l);
27 }
28 
29 void CopyListOfBoxes(Tlist *l_dst,Tlist *l_src)
30 {
31  Titerator i;
32  Tbox b;
33 
34  InitListOfBoxes(l_dst);
35 
36  InitIterator(&i,l_src);
37  First(&i);
38  while(!EndOfList(&i))
39  {
40  CopyBox(&b,(Tbox *)GetCurrent(&i));
41  AddLastElement((void *)&b,l_dst);
42  Advance(&i);
43  }
44 }
45 
46 /*
47  * Returns the total volume of the box stored in the list
48  * (normalized using t_trans and t_rot)
49  */
50 double ListOfBoxesVolume(boolean *used,Tlist *l)
51 {
52  double v;
53  Titerator i;
54 
55  InitIterator(&i,l);
56  First(&i);
57  v=0.0;
58  while(!EndOfList(&i))
59  {
60  v+=GetBoxVolume(used,(Tbox *)GetCurrent(&i));
61  Advance(&i);
62  }
63 
64  return(v);
65 }
66 
67 /*
68  * Returns the maximum diagonal for all boxes in the list
69  */
70 double ListOfBoxesMaxDiagonal(boolean *used,Tlist *l)
71 {
72  double d,d_max;
73  Titerator i;
74 
75  InitIterator(&i,l);
76  First(&i);
77  d_max=0.0;
78  while(!EndOfList(&i))
79  {
80  d=GetBoxDiagonal(used,(Tbox *)GetCurrent(&i));
81  if (d>d_max) d_max=d;
82  Advance(&i);
83  }
84 
85  return(d_max);
86 }
87 
88 /*
89  * Returns the maximum size for all boxes in the list
90  */
91 double ListOfBoxesMaxSize(boolean *used,Tlist *l)
92 {
93  double s,s_max;
94  Titerator i;
95 
96  InitIterator(&i,l);
97  First(&i);
98  s_max=0.0;
99  while(!EndOfList(&i))
100  {
101  s=GetBoxSize(used,(Tbox *)GetCurrent(&i));
102  if (s>s_max) s_max=s;
103  Advance(&i);
104  }
105 
106  return(s_max);
107 }
108 
109 /*
110  * Returns a box that fully includes all boxes in the list.
111  * If the list is empty so is the box.
112  */
113 void ListOfBoxesBB(boolean *used,Tbox *b,Tlist *l)
114 {
115  if (ListSize(l)==0)
116  InitBox(0,NULL,b);
117  else
118  {
119  Titerator i;
120 
121  InitIterator(&i,l);
122  First(&i);
123  CopyBox(b,(Tbox *)GetCurrent(&i));
124  Advance(&i);
125  while(!EndOfList(&i))
126  {
127  BoxUnion(used,(Tbox *)GetCurrent(&i),b,b);
128  Advance(&i);
129  }
130  }
131 }
132 
133 
134 /*
135  * Returns a list with the bounding boxes for all clusters of boxes
136  * in l_in.
137  */
138 void ListOfBoxesCluster(boolean *used,Tlist *l_out,Tlist *l_in)
139 {
140  unsigned int k,n,l,t;
141  Titerator i;
142  Titerator j;
143  Titerator c;
144  Tbox *b2,*b3,b_out,*cb;
145  boolean modified;
146  unsigned int *cluster,nc;
147 
148  /*Number of boxes to be clustered*/
149  n=ListSize(l_in);
150 
151  /*Initially we have no cluster*/
152  NEW(cluster,n,unsigned int);
153  nc=0;
154  for(k=0;k<n;k++)
155  cluster[k]=(unsigned int)(-1);
156 
157  /*Initially the output is empty*/
158  InitListOfBoxes(l_out);
159 
160  /*Proceed for all boxes in the input list not yet clustered*/
161  InitIterator(&i,l_in);
162  First(&i);
163  k=0;
164  while(!EndOfList(&i))
165  {
166  if (cluster[k]==(unsigned int)(-1)) /*= not clustered*/
167  {
168  /*Start a new cluster*/
169  nc++;
170  cluster[k]=nc;
171  NEW(cb,1,Tbox);
172  CopyBox(cb,(Tbox *)GetCurrent(&i)); /*'cb' is the bounding box for all boxes in the cluster*/
173 
174  do {
175 
176  /*For all boxes still to be clustered*/
177  modified=FALSE; /*Initally we assume the cluster to remain as it is now*/
178 
179  /*and we check for the rest of boxes in the input list whether or not they
180  can be included in the current cluster*/
181  InitIterator(&j,l_in);
182  First(&j);
183  l=0;
184  while(!EndOfList(&j))
185  {
186  if (cluster[l]==(unsigned int)(-1)) /*the box in not yet assigned to any cluster*/
187  {
188  b2=(Tbox *)GetCurrent(&j); /*this is the box candidate to joint the current cluster*/
189 
190  /*Check if the non-clustered box has contact with one of the
191  boxes already in cluster 'nc'=cluster[k]*/
192  InitIterator(&c,l_in);
193  First(&c);
194  t=0;
195  while(!EndOfList(&c))
196  {
197  if (cluster[t]==cluster[k])
198  {
199  b3=(Tbox *)GetCurrent(&c); /*This is a box already in cluster 'nc'*/
200  CopyBox(&b_out,b3);
201  if (BoxesIntersection(used,b2,b3,&b_out))
202  {
203  cluster[l]=nc; /*box b2 (number 'l') is included in the current cluster*/
204  BoxUnion(NULL,cb,b2,cb); /*Enlarge the cluster bounding box*/
205 
206  modified=TRUE; /*Indicate the current cluster has been modified*/
207  }
208  DeleteBox(&b_out); /*bout is an auxiliary box that must be deleted*/
209  }
210  Advance(&c);
211  t++;
212  }
213  }
214  Advance(&j);
215  l++;
216  }
217  } while(modified); /* If we added one or more boxex to the cluster we have to check whether
218  or not the cluster can be still extended*/
219 
220 
221  AddLastElement((void *)cb,l_out); /*Add the bounding box of the current cluster to the output list*/
222  }
223  Advance(&i);
224  k++;
225  }
226  free(cluster);
227 }
228 
229 
231 {
232  Titerator i;
233  Tbox b;
234 
235  InitIterator(&i,l_new);
236  First(&i);
237  while(!EndOfList(&i))
238  {
239  CopyBox(&b,(Tbox *)GetCurrent(&i));
240  AddLastElement((void *)&b,l);
241  Advance(&i);
242  }
243 }
244 
246 {
247  Titerator i;
248  Tbox b;
249 
250  InitListOfBoxes(l);
251 
252  InitIterator(&i,l_orig);
253  First(&i);
254  while(!EndOfList(&i))
255  {
256  CopyBox(&b,(Tbox *)GetCurrent(&i));
257  AddFirstElement((void *)&b,l);
258  Advance(&i);
259  }
260 }
261 
262 /*
263  * Prints a given list of boxes
264  */
265 void PrintListOfBoxes(FILE *f,boolean *used,char *heading,Tlist *l)
266 {
267  Titerator i;
268  unsigned int k;
269 
270  InitIterator(&i,l);
271  First(&i);
272  k=1;
273  while(!EndOfList(&i))
274  {
275  if (heading!=NULL) fprintf(f,"%s ",heading);
276  fprintf(f,"%u : ",k++);
277  PrintBoxSubset(f,used,NULL,(Tbox *)GetCurrent(&i));
278  Advance(&i);
279  }
280  fflush(f);
281 }
282 
283 /*
284  * Read a list of boxes from a file (wrote by cuik).
285  */
286 boolean ReadListOfBoxes(char *filename,Tlist *l)
287 {
288  FILE *PSin;
289  int token=~EOF;
290  Tbox box;
291 
292  InitList(sizeof(Tbox),l);
293 
294  PSin=fopen(filename,"r");
295  if (PSin)
296  {
297  do {
298  //read a box from the file
299  token=ReadBox(PSin,&box);
300  //if we got a proper box (no end of file)...
301  if (token!=EOF)
302  {
303  //and add the box to the list (this re-uses the
304  //intervals in 'box' so there is no need to call
305  //DeleteBox(&box) afterwards
306  AddLastElement((void *)&box,l);
307  }
308  } while (token!=EOF);
309  return(TRUE);
310  }
311  else
312  return(FALSE);
313 }
314 
315 /* Now the binary alternatives to save/load boxes */
316 void SaveListOfBoxes(FILE *f,Tlist *list)
317 {
318  unsigned int n;
319  Titerator i;
320 
321  n=ListSize(list);
322  fwrite(&n,sizeof(unsigned int),1,f);
323 
324  InitIterator(&i,list);
325  First(&i);
326  n=0;
327  while(!EndOfList(&i))
328  {
329  SaveBox(f,(Tbox *)GetCurrent(&i));
330  Advance(&i);
331  }
332 }
333 
334 void LoadListOfBoxes(FILE *f,Tlist *list)
335 {
336  unsigned int i,n;
337  Tbox box;
338 
339  fread(&n,sizeof(unsigned int),1,f);
340 
341  InitListOfBoxes(list);
342 
343  for(i=0;i<n;i++)
344  {
345  LoadBox(f,&box);
346  AddLastElement((void *)&box,list);
347  }
348 }
349 
350 /*
351  * Deletes a given list of boxes
352  */
354 {
355  Titerator i;
356 
357  InitIterator(&i,l);
358  First(&i);
359  while(!EndOfList(&i))
360  {
361  DeleteBox((Tbox *)GetCurrent(&i));
362  DeleteCurrent(&i);
363  }
364 }
365 
Definition of the boolean type.
void First(Titerator *i)
Moves an iterator to the first position of its associated list.
Definition: list.c:356
double ListOfBoxesMaxSize(boolean *used, Tlist *l)
Computes the maximum size for all boxes in a list.
Definition: box_list.c:91
#define FALSE
FALSE.
Definition: boolean.h:30
void ReverseListOfBoxes(Tlist *l_orig, Tlist *l)
Reverses a list.
Definition: box_list.c:245
#define NEW(_var, _n, _type)
Allocates memory space.
Definition: defines.h:385
double GetBoxSize(boolean *used, Tbox *b)
Computes the size of the box.
Definition: box.c:631
double ListOfBoxesVolume(boolean *used, Tlist *l)
Computes the volume of a list.
Definition: box_list.c:50
void PrintListOfBoxes(FILE *f, boolean *used, char *heading, Tlist *l)
Prints a list of boxes.
Definition: box_list.c:265
void ListOfBoxesCluster(boolean *used, Tlist *l_out, Tlist *l_in)
Clusters a list of boxes.
Definition: box_list.c:138
#define TRUE
TRUE.
Definition: boolean.h:21
void InitBox(unsigned int dim, Tinterval *is, Tbox *b)
Initializes a box.
Definition: box.c:23
boolean ReadListOfBoxes(char *filename, Tlist *l)
Reads a list of boxes from a file.
Definition: box_list.c:286
void CopyListOfBoxes(Tlist *l_dst, Tlist *l_src)
Copy constructor.
Definition: box_list.c:29
Collection of methods to work on Tlist of boxes.
void ListOfBoxesBB(boolean *used, Tbox *b, Tlist *l)
Computes an axis-aligned bounding box for all boxes in a list.
Definition: box_list.c:113
int ReadBox(FILE *f, Tbox *b)
Reads a box from a file.
Definition: box.c:1196
void DeleteListOfBoxes(Tlist *l)
Destructor.
Definition: box_list.c:353
void AddLastElement(void *Info, Tlist *list)
Adds an element at the tail of the list.
Definition: list.c:206
boolean EndOfList(Titerator *i)
Checks if an iterator is pointing at the end of the list.
Definition: list.c:445
Definitions of constants and macros used in several parts of the cuik library.
A generic list.
Definition: list.h:46
void InitIterator(Titerator *i, Tlist *list)
Constructor.
Definition: list.c:284
void CopyBox(void *b_out, void *b_in)
Box copy operator.
Definition: box.c:160
double GetBoxDiagonal(boolean *used, Tbox *b)
Computes the diagonal of a (sub-)box.
Definition: box.c:678
A box.
Definition: box.h:83
void LoadListOfBoxes(FILE *f, Tlist *list)
Loads a list of boxes from a file.
Definition: box_list.c:334
void InitListOfBoxes(Tlist *l)
Constructor.
Definition: box_list.c:24
void SaveBox(FILE *f, Tbox *b)
Saves a box in binary format.
Definition: box.c:1258
void LoadBox(FILE *f, Tbox *b)
Reads a box in binary format.
Definition: box.c:1266
void * GetCurrent(Titerator *i)
Gets the element pointed by the iterator.
Definition: list.c:299
double ListOfBoxesMaxDiagonal(boolean *used, Tlist *l)
Computes the maximum diagonal for all boxes in a list.
Definition: box_list.c:70
void BoxUnion(boolean *used, Tbox *b1, Tbox *b2, Tbox *b_out)
Computes the box union of two given boxes.
Definition: box.c:314
void DeleteBox(void *b)
Destructor.
Definition: box.c:1283
void PrintBoxSubset(FILE *f, boolean *used, char **varNames, Tbox *b)
Prints a (sub-)box.
Definition: box.c:1162
List iterator.
Definition: list.h:61
void AddFirstElement(void *Info, Tlist *list)
Adds an element at the head of the list.
Definition: list.c:196
void DeleteCurrent(Titerator *i)
Destructor.
Definition: list.c:341
void InitList(unsigned int ele_size, Tlist *list)
Constructor.
Definition: list.c:135
unsigned int ListSize(Tlist *list)
Gets the number of elements in the list.
Definition: list.c:180
void ConcatListOfBoxes(Tlist *l_new, Tlist *l)
Concats two lists.
Definition: box_list.c:230
double GetBoxVolume(boolean *used, Tbox *b)
Computes the volume of the box.
Definition: box.c:980
boolean Advance(Titerator *i)
Moves an iterator to the next position of its associated list.
Definition: list.c:373
void SaveListOfBoxes(FILE *f, Tlist *list)
Saves a list of boxes.
Definition: box_list.c:316
boolean BoxesIntersection(boolean *used, Tbox *b1, Tbox *b2, Tbox *bout)
Computes the box intersection of two given boxes.
Definition: box.c:293
Definition of the Tinterval type and the associated functions.