Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members

bsp.h

Go to the documentation of this file.
00001 /***************************************************************************************************/ 00002 /***************************************************************************************************/ 00016 /***************************************************************************************************/ 00017 /***************************************************************************************************/ 00018 #ifndef BSP_TREE_H 00019 #define BSP_TREE_H 00020 00021 00022 /*------------------------------------- Globals -----------------------------------------------*/ 00023 typedef enum { DIVIDER_FRONT , DIVIDER_BACK , DIVIDER_CROSS , DIVIDER_ON} BSP_POSITION_DIVIDER; 00024 typedef enum { POINT_ON , POINT_FRONT , POINT_BACK }BSP_POSITION_POINT; 00025 00026 00027 /*------------------------------------ Prototypes ---------------------------------------------*/ 00028 template< class Divider_Type> class cBSP_Node; 00029 template<class cItem , class cBSP_Node , class cDivider_Type > class cBSP_Tree; 00030 00031 /*------------------------------------ Includes ---------------------------------------------*/ 00032 #include <iostream> 00033 00034 00035 #include "assert.h" 00036 00037 using namespace std; 00038 00039 /*------------------------------------- Classes ---------------------------------------------*/ 00040 00041 00042 /*************************************************************************************************/ 00044 00046 template< class Divider_Type> 00047 class cBSP_Node 00048 { 00049 public: 00051 cBSP_Node() { Front=NULL;Back=NULL;Id=-1;}; 00053 00057 cBSP_Node(Divider_Type & div , int id) 00058 { 00059 Divider=div; 00060 Front=NULL; 00061 Back=NULL; 00062 Id=id; 00063 }; 00064 00066 ~cBSP_Node() { delete Front; Front=NULL; delete Back; Back=NULL;}; 00068 inline int Get_Id() { return Id;}; 00070 inline Set_Id(int id) { Id=id;}; 00072 // TODO : devrait etre virtuelle, mais si c le cas, ca plante a la compile 00073 virtual void Print() 00074 { 00075 //cout << "[" << Id << "]:" << divider << " fils: ["; 00076 if( Front != NULL ) 00077 cout << Front->Get_Id(); 00078 else 00079 cout << "empty"; 00080 cout << "] <---> ["; 00081 if( Back != NULL ) 00082 cout << Back->Get_Id(); 00083 else 00084 cout << "empty"; 00085 cout << "] \n"; 00086 00087 if( Front != NULL) 00088 Front->Print(); 00089 if( Back != NULL) 00090 Back->Print(); 00091 } 00092 00093 cBSP_Node * Front; 00094 cBSP_Node * Back; 00095 Divider_Type Divider; 00096 00097 protected: 00098 int Id; 00099 }; 00100 00101 00102 00103 00104 /*************************************************************************************************/ 00106 00114 template<class cItem , class cBSP_Node , class cDivider_Type > 00115 class cBSP_Tree 00116 { 00117 public: 00119 cBSP_Tree() 00120 { 00121 Root = NULL; 00122 N_Nodes=0; 00123 } 00124 00126 ~cBSP_Tree() 00127 { 00128 if( Root != NULL) delete Root; 00129 Root=NULL; 00130 }; 00131 00133 cBSP_Node * Get_Root() { return Root; }; 00134 00136 void Add_Divider( cDivider_Type & divider) 00137 { 00138 if( Root == NULL) 00139 { 00140 Root = new cBSP_Node( divider,N_Nodes); 00141 N_Nodes++; 00142 } 00143 else 00144 Add_Divider( divider , Root ); 00145 } 00146 00148 void Print() 00149 { 00150 cout << "######### BSP TREE ######### \n"; 00151 cout << "N_Nodes = " << N_Nodes << "\n"; 00152 if(Root != NULL) 00153 Root->Print(); 00154 cout << "############################# \n"; 00155 } 00156 00158 00162 cBSP_Node * Where_Is( cItem & item ) 00163 { 00164 return Where_Is( item , Root ); 00165 }; 00166 00168 00171 cBSP_Node * In_Which_Leaf_Is( cItem & item ) 00172 { 00173 return In_Which_Leaf_Is( item , Root ); 00174 }; 00175 00177 void Apply_To_Each_Node( void (*Call_Back)(cBSP_Node * node) ) 00178 { 00179 Recursive_Apply_To_Each_Node(Call_Back , Root ); 00180 } 00181 00182 private: 00183 cBSP_Node * Root; 00184 int N_Nodes; 00185 00187 void Recursive_Apply_To_Each_Node(void (*Call_Back)(cBSP_Node * node), cBSP_Node * node ) 00188 { 00189 if( node == NULL) 00190 return; 00191 00192 //si ce n'est pas une feuille ! 00193 if( node->Front != NULL && node->Back != NULL) 00194 { 00195 Call_Back(node); 00196 Recursive_Apply_To_Each_Node(Call_Back , node->Front ); 00197 Recursive_Apply_To_Each_Node(Call_Back , node->Back ); 00198 } 00199 } 00200 00201 //--------------------------------------------------------------------------------------------------- 00204 cBSP_Node * Where_Is( cItem & item , cBSP_Node * node ) 00205 { 00206 assert( node != NULL); 00207 BSP_POSITION_POINT pos; 00208 00209 // si node == NULL, cela signifie qu'on est arrivé dans une feuille qui n'a pas ete défini 00210 // ce BSP laisse l'implémentation des feuilles a l'utilisateur ! 00211 if( node == NULL) return NULL; 00212 00213 //si on est sur une feuille, on retourne la feuille 00214 if( node->Front == NULL && node->Back==NULL) return node; 00215 00216 // sinon, on cherche la position de 'item' par rapport a ce divider, et on continue 00217 // la recherche dans le bon sous-espace 00218 pos = node->Divider.Get_Position_Point( item ); 00219 switch( pos) 00220 { 00221 case POINT_FRONT : 00222 return Where_Is(item , node->Front ); 00223 case POINT_BACK : 00224 return Where_Is(item , node->Back ); 00225 case POINT_ON : 00226 return node; 00227 default: 00228 cout << "ERROR 001 : cBSP_Node * Where_Is( cItem & item , cBSP_Node * node ) \n"; 00229 break; 00230 } 00231 00232 return NULL; // pour eviter le warning 'path without return !" 00233 } 00234 00235 //--------------------------------------------------------------------------------------------------- 00238 cBSP_Node * In_Which_Leaf_Is( cItem & item , cBSP_Node * node ) 00239 { 00240 BSP_POSITION_POINT pos; 00241 // si node == NULL, cela signifie qu'on est arrivé sur une feuille qui n'a pas ete défini 00242 // ce BSP laisse l'implémentation des feuilles a l'utilisateur ! 00243 if( node == NULL) 00244 return NULL; 00245 00246 //si on est sur une feuille, on retourne la feuille 00247 if( node->Front == NULL && node->Back==NULL) 00248 return node; 00249 00250 // sinon, on cherche la position de 'item' par rapport a ce divider, et on continue 00251 // la recherche dans le bon sous-espace 00252 pos = node->Divider.Get_Position_Point( item ); 00253 switch( pos) 00254 { 00255 case POINT_FRONT : 00256 case POINT_ON : 00257 return In_Which_Leaf_Is(item , node->Front ); 00258 case POINT_BACK : 00259 return In_Which_Leaf_Is(item , node->Back ); 00260 default: 00261 cout << "ERROR 001 : cBSP_Node * Where_Is( cItem & item , cBSP_Node * node ) \n"; 00262 break; 00263 } 00264 00265 return NULL; // pour eviter le warning 'path without return' 00266 } 00267 00268 //--------------------------------------------------------------------------------------------------- 00270 void Add_Divider( cDivider_Type & divider , cBSP_Node * node ) 00271 { 00272 BSP_POSITION_DIVIDER pos; 00273 cDivider_Type div_front; 00274 cDivider_Type div_back; 00275 assert( node != NULL); 00276 00277 pos = node->Divider.Get_Position_Divider_And_Split( divider , div_front , div_back); 00278 00279 switch( pos) 00280 { 00281 case DIVIDER_FRONT: 00282 if( node->Front != NULL) 00283 { 00284 Add_Divider( divider , node->Front ); 00285 } 00286 else 00287 { 00288 node->Front = new cBSP_Node( divider,N_Nodes); 00289 N_Nodes++; 00290 } 00291 break; 00292 case DIVIDER_BACK: 00293 if( node->Back != NULL) 00294 { 00295 Add_Divider( divider , node->Back ); 00296 } 00297 else 00298 { 00299 node->Back = new cBSP_Node( divider,N_Nodes); 00300 N_Nodes++; 00301 } 00302 break; 00303 case DIVIDER_CROSS: 00304 00305 if( node->Front != NULL) 00306 { 00307 Add_Divider( div_front , node->Front); 00308 00309 } 00310 else 00311 { 00312 node->Front = new cBSP_Node( div_front,N_Nodes); 00313 N_Nodes++; 00314 } 00315 00316 if(node->Back != NULL) 00317 { 00318 Add_Divider( div_back , node->Back); 00319 } 00320 else 00321 { 00322 node->Back = new cBSP_Node( div_back,N_Nodes); 00323 N_Nodes++; 00324 } 00325 break; 00326 case DIVIDER_ON: 00327 cout << "ERROR : class cBSP_Tree : DIVIDER_ON is not managed in this bsp !!! \n"; 00328 return; 00329 break; 00330 default: 00331 cout << "ERROR : class cBSP_Tree : unknown position of the divider \n"; 00332 return; 00333 break; 00334 } 00335 } 00336 00337 00338 00339 //--------------------------------------------------------------------------------------------------- 00341 static char * Get_String_BSP_Position_Divider(BSP_POSITION_DIVIDER pos) 00342 { 00343 switch(pos) 00344 { 00345 case DIVIDER_FRONT : 00346 return "DIVIDER_FRONT"; 00347 case DIVIDER_BACK : 00348 return "DIVIDER_BACK"; 00349 case DIVIDER_CROSS : 00350 return "DIVIDER_CROSS"; 00351 case DIVIDER_ON : 00352 return "DIVIDER_ON"; 00353 } 00354 return "DIVIDER_unknown"; 00355 } 00356 00357 //--------------------------------------------------------------------------------------------------- 00359 static char * Get_String_BSP_Position_Point(BSP_POSITION_POINT pos) 00360 { 00361 switch(pos) 00362 { 00363 case POINT_ON : 00364 return "POINT_ON"; 00365 case POINT_FRONT : 00366 return "POINT_FRONT"; 00367 case POINT_BACK : 00368 return "POINT_BACK"; 00369 } 00370 return "POSITION_unknown"; 00371 } 00372 }; 00373 00374 00375 00376 00377 #endif

Generated on Fri May 21 19:22:36 2004 for LIBELL by doxygen 1.3.7