00001
00002
00016
00017
00018
#ifndef BSP_TREE_H
00019
#define BSP_TREE_H
00020
00021
00022
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
00028
template<
class Div
ider_Type>
class cBSP_Node;
00029
template<
class cItem ,
class cBSP_Node ,
class cDiv
ider_Type >
class cBSP_Tree;
00030
00031
00032
#include <iostream>
00033
00034
00035
#include "assert.h"
00036
00037
using namespace std;
00038
00039
00040
00041
00042
00044
00046
template<
class Div
ider_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
00073 virtual void Print()
00074 {
00075
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 cDiv
ider_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
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
00210
00211
if( node == NULL)
return NULL;
00212
00213
00214
if( node->
Front == NULL && node->
Back==NULL)
return node;
00215
00216
00217
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;
00233 }
00234
00235
00238 cBSP_Node * In_Which_Leaf_Is( cItem & item ,
cBSP_Node * node )
00239 {
00240
BSP_POSITION_POINT pos;
00241
00242
00243
if( node == NULL)
00244
return NULL;
00245
00246
00247
if( node->
Front == NULL && node->
Back==NULL)
00248
return node;
00249
00250
00251
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;
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