ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/REPOS_ERICCA/magic/lib/template/src/tpl_octree.h
Revision: 632
Committed: Thu Jan 15 18:40:00 2015 UTC (10 years, 4 months ago) by francois
Content type: text/plain
File size: 51942 byte(s)
Log Message: 
Changement de l'espace de voisinage dans le mailleur 2D et 3D. On utilise un ntree (octree "anisotrope" qui ne se divise pas necessairement en 8). En 2D l'espace de voisinage est maintenant sur l'espace reelle au lieu d'être sur l'espace parametrique.
+Mise sous forme de parametres de certains choix stratégiques du mailleur

File Contents

# User Rev Content
1 5 //------------------------------------------------------------
2     //------------------------------------------------------------
3     // MAGiC
4 francois 276 // Jean Christophe Cuilli�re et Vincent FRANCOIS
5     // D�partement de G�nie M�canique - UQTR
6 5 //------------------------------------------------------------
7 francois 276 // Le projet MAGIC est un projet de recherche du d�partement
8     // de g�nie m�canique de l'Universit� du Qu�bec �
9     // Trois Rivi�res
10     // Les librairies ne peuvent �tre utilis�es sans l'accord
11 5 // des auteurs (contact : francois@uqtr.ca)
12     //------------------------------------------------------------
13     //------------------------------------------------------------
14     //
15     // tpl_octree.h
16     //
17     //------------------------------------------------------------
18     //------------------------------------------------------------
19     // COPYRIGHT 2000
20 francois 276 // Version du 02/03/2006 � 11H24
21 5 //------------------------------------------------------------
22     //------------------------------------------------------------
23     #ifndef _TPLOCTREE_
24     #define _TPLOCTREE_
25    
26    
27 francois 481 #include "ot_boite_3d.h"
28 5 #include "tpl_liste_entite.h"
29     #include "tpl_map_entite.h"
30 francois 65 #include <math.h>
31 5
32 francois 65 #define ID 0
33     #define IF 1
34     #define IR 2
35     #define IB 3
36     #define IL 4
37     #define IU 5
38     #define IDF 6
39     #define ILD 7
40     #define ILF 8
41     #define IRD 9
42     #define IRF 10
43     #define IDB 11
44     #define IRB 12
45     #define ILB 13
46     #define IUF 14
47     #define ILU 15
48     #define IRU 16
49     #define IUB 17
50    
51 francois 102 using namespace std;
52 francois 65
53     class OUTIL_OCTREE
54     {
55     public:
56     OUTIL_OCTREE()
57     {
58     };
59     ~OUTIL_OCTREE()
60     {
61     };
62    
63     unsigned long determine_keycode(int nx,int ny,int nz)
64     {
65     vector<int> bits;
66     int ok=0,i=0;
67     do
68     {
69     int nnz=nz>>i;
70     int nny=ny>>i;
71     int nnx=nx>>i;
72     int bit1= nnz & 1;
73     int bit2= nny & 1;
74     int bit3= nnx & 1;
75     if ((nnz==0) && (nny==0) && (nnx==0)) ok=1;
76     bits.insert(bits.end(),bit1);
77     bits.insert(bits.end(),bit2);
78     bits.insert(bits.end(),bit3);
79     i++;
80     }
81     while (ok==0);
82     unsigned long keycode=0;
83     for (int i=0;i<bits.size();i++)
84     keycode=keycode+bits[i]*(1<<i);
85     return keycode;
86     }
87    
88    
89     bool adjacent(int direction,int octant)
90     {
91     bool tabadj[18][8]=
92     {
93     {true, true, true, true, false, false, false, false},
94     {true, true, false, false, true, true, false, false},
95     {false, true, false, true, false, true, false, true},
96     {false, false, true, true, false, false, true, true},
97     {true, false, true, false, true, false, true, false},
98     {false, false, false, false, true, true, true, true},
99     {true, true, false, false, false, false, false, false},
100     {true, false, true, false, false, false, false, false},
101     {true, false, false, false, true, false, false, false},
102     {false, true, false, true, false, false, false, false},
103     {false, true, false, false, false, true, false, false},
104     {false, false, true, true, false, false, false, false},
105     {false, false, false, true, false, false, false, true},
106     {false, false, true, false, false, false, true, false},
107     {false, false, false, false, true, true, false, false},
108     {false, false, false, false, true, false, true, false},
109     {false, false, false, false, false, true, false, true},
110     {false, false, false, false, false, false, true, true},
111    
112     };
113    
114     return tabadj[direction][octant];
115     }
116    
117    
118     int reflect(int direction,int octant)
119     {
120     int tabreflect[18][8]=
121     {
122     {4, 5, 6, 7, 0, 1, 2, 3},
123     {2, 3, 0, 1, 6, 7, 4, 5},
124     {1, 0, 3, 2, 5, 4, 7, 6},
125     {2, 3, 0, 1, 6, 7, 4, 5},
126     {1, 0, 3, 2, 5, 4, 7, 6},
127     {4, 5, 6, 7, 0, 1, 2, 3},
128     {6, 7, 4, 5, 2, 3, 0, 1},
129     {5, 4, 7, 6, 1, 0, 3, 2},
130     {3, 2, 1, 0, 7, 6, 5, 4},
131     {5, 4, 7, 6, 1, 0, 3, 2},
132     {3, 2, 1, 0, 7, 6, 5, 4},
133     {6, 7, 4, 5, 2, 3, 0, 1},
134     {3, 2, 1, 0, 7, 6, 5, 4},
135     {3, 2, 1, 0, 7, 6, 5, 4},
136     {6, 7, 4, 5, 2, 3, 0, 1},
137     {5, 4, 7, 6, 1, 0, 3, 2},
138     {5, 4, 7, 6, 1, 0, 3, 2},
139     {6, 7, 4, 5, 2, 3, 0, 1}
140    
141     };
142    
143     return tabreflect[direction][octant];
144     }
145    
146    
147    
148     int commonface(int direction,int octant)
149     {
150     int tabcommonface[12][8]=
151     {
152     {-1, -1, 0, 0, 1, 1, -1, -1},
153     {-1, 0, -1, 0, 4, -1, 4, -1},
154     {-1, 1, 4, -1, -1, 1, 4, -1},
155     {0, -1, 0, -1, -1, 2, -1, 2},
156     {1, -1, -1, 2, 1, -1, -1, 2},
157     {0, 0, -1, -1, -1, -1, 3, 3},
158     {-1, 2, 3, -1, -1, 2, 3, -1},
159     {4, -1, -1, 3, 4, -1, -1, 3},
160     {1, 1, -1, -1, -1, -1, 5, 5},
161     {4, -1, 4, -1, -1, 5, -1, 5},
162     {-1, 2, -1, 2, 5, -1, 5, -1},
163     {-1, -1, 3, 3, 5, 5, -1, -1},
164     } ;
165     return tabcommonface[direction-6][octant];
166    
167     }
168    
169     int filsvoisin(int direction,int numvoisin)
170     {
171     int tab[6][4]=
172     {
173     {4, 5, 6, 7},
174     {2, 3, 6, 7},
175     {0, 2, 4, 6},
176     {0, 1, 4, 5},
177     {1, 3, 5, 7},
178     {0, 1, 2, 3}
179     };
180     return tab[direction][numvoisin];
181     }
182    
183     int sommetface(int numface,int numsommet)
184     {
185     int tab[6][4]=
186     {
187     {0,1,2,3},
188     {0,1,5,4},
189     {1,2,6,5},
190     {3,2,6,7},
191     {0,3,7,4},
192     {4,5,6,7},
193     };
194     return tab[numface][numsommet];
195     }
196    
197     int sommetarete(int numarete,int numsommet)
198     {
199     int tab[12][2]=
200     {
201     {0,1},
202     {0,3},
203     {0,4},
204     {1,2},
205     {1,5},
206     {3,2},
207     {2,6},
208     {3,7},
209     {4,5},
210     {4,7},
211     {5,6},
212     {7,6},
213     };
214     return tab[numarete-6][numsommet];
215     }
216    
217    
218    
219    
220    
221     int areteface(int numface,int numarete)
222     {
223     int tab[6][4]=
224     {
225     {6,9,11,7},
226     {6,10,14,8},
227     {9,12,16,10},
228     {11,12,17,13},
229     {7,13,15,8},
230     {14,16,17,15},
231     };
232     return tab[numface][numarete];
233     }
234    
235     int faceadjacente(int numface,int numarete)
236     {
237     int tab[6][4]=
238     {
239     {1,2,3,4},
240     {0,2,5,4},
241     {0,3,5,1},
242     {0,2,5,4},
243     {0,3,5,1},
244     {1,2,3,4},
245     };
246     return tab[numface][numarete];
247     }
248    
249    
250    
251     };
252    
253    
254 5 class CELLULE_OCTREE_BASE
255     {
256     public:
257     CELLULE_OCTREE_BASE()
258     {
259     static unsigned long idmax=0;
260     id=idmax;
261     idmax++;
262     };
263    
264     virtual ~CELLULE_OCTREE_BASE() {};
265     virtual BOITE_3D get_boite(void)=0;
266     virtual CELLULE_OCTREE_BASE* get_fils(int num)=0;
267     virtual int get_feuille(void)=0;
268 francois 65 virtual int get_niveau(void)=0;
269     virtual int get_sontype(void)=0;
270 5 virtual unsigned long get_id() {return id;};
271     unsigned long id;
272     };
273    
274    
275     class OCTREE_BASE
276     {
277     public:
278     OCTREE_BASE() {};
279     virtual ~OCTREE_BASE() {};
280     virtual int get_nb_cellule(void)=0;
281     virtual CELLULE_OCTREE_BASE* get_cellule(int num)=0;
282 francois 65 virtual int get_niveau_max(void)=0;
283 5 };
284    
285    
286     template <class A,class CONDITION>
287     class TPL_CELLULE_OCTREE:public CELLULE_OCTREE_BASE
288     {
289     public:
290 francois 65 TPL_CELLULE_OCTREE(TPL_CELLULE_OCTREE<A,CONDITION> *cell,double xmin,double ymin,double zmin,double xmax,double ymax,double zmax,int niv,int st):CELLULE_OCTREE_BASE(),boite(xmin,ymin,zmin,xmax,ymax,zmax),niveau(niv),pere(cell),sontype(st)
291 5 {
292 francois 632 fils[0]=NULL;fils[1]=NULL;fils[2]=NULL;fils[3]=NULL;fils[4]=NULL;fils[5]=NULL;fils[6]=NULL;fils[7]=NULL;
293     };
294 5 virtual ~TPL_CELLULE_OCTREE() {};
295     BOITE_3D get_boite(void) {return boite;};
296 francois 65 int get_niveau(void) {return niveau;};
297 5 BOITE_3D boite;
298     int feuille;
299     TPL_LISTE_ENTITE<CONDITION> lst_entite_CONDITION;
300     TPL_LISTE_ENTITE<A> lst_entite_A;
301     virtual TPL_CELLULE_OCTREE<A,CONDITION>* get_fils(int num) {return fils[num];};
302 francois 65 virtual TPL_CELLULE_OCTREE<A,CONDITION>* get_pere(void) {return pere;};
303 5 virtual int get_feuille(void) {return feuille;};
304 francois 276
305     virtual void vide(void)
306     {
307     lst_entite_A.vide();
308     }
309    
310 francois 65 int get_sontype(void)
311     {
312     return sontype;
313     }
314 5 int get_nb_entite(void)
315     {
316     return lst_entite_A.get_nb();
317     };
318     A get_entite(int num)
319     {
320     return lst_entite_A.get(num);
321     };
322 francois 65 TPL_CELLULE_OCTREE< A ,CONDITION> *fils[8];
323     TPL_CELLULE_OCTREE< A ,CONDITION> *pere;
324 5
325 francois 65
326     int niveau;
327     int sontype;
328 5 };
329    
330     template <class A,class CONDITION,class B>
331     class TPL_CELLULE_INFO:public CELLULE_OCTREE_BASE
332     {
333     public:
334     TPL_CELLULE_INFO(double xmin,double ymin,double zmin,double xmax,double ymax,double zmax):CELLULE_OCTREE_BASE(),boite(xmin,ymin,zmin,xmax,ymax,zmax)
335     {
336     };
337     virtual ~TPL_CELLULE_INFO() {};
338     BOITE_3D get_boite(void) {return boite;};
339     BOITE_3D boite;
340     int feuille;
341     TPL_CELLULE_INFO< A ,CONDITION,B> *fils[8];
342     TPL_LISTE_ENTITE<CONDITION> lst_entite_CONDITION;
343     TPL_LISTE_ENTITE<A> lst_entite_A;
344     B tab[8];
345     virtual TPL_CELLULE_INFO<A,CONDITION,B>* get_fils(int num) {return fils[num];};
346     virtual int get_feuille(void) {return feuille;};
347     int get_nb_entite(void)
348     {
349     return lst_entite_A.get_nb();
350     };
351     A get_entite(int num)
352     {
353     return lst_entite_A.get(num);
354     };
355    
356     B get_info(int num) {return tab[num];};
357     void change_info(int num,B val) {tab[num]=val;};
358    
359     };
360    
361    
362    
363     template <class A,class CONDITION>
364     class TPL_OCTREE:public OCTREE_BASE
365     {
366     public:
367 francois 65 TPL_OCTREE():niveaumax(0) {};
368 5 ~TPL_OCTREE()
369     {
370     for (int i1=0;i1<lst_entite_cellule.get_nb();i1++)
371     {
372     TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(i1);
373     delete cellule;
374     }
375     };
376    
377     virtual int get_nb_cellule(void) {return lst_entite_cellule.get_nb();};
378 francois 65 virtual int get_nb_feuille(void) {return lst_entite_feuille.get_nb();};
379 5
380     virtual BOITE_3D get_boite_de_base(void) {return lst_entite_cellule.get(0)->get_boite();};
381    
382     virtual TPL_CELLULE_OCTREE<A,CONDITION>* get_cellule(int num) {return lst_entite_cellule.get(num); };
383 francois 65 virtual TPL_CELLULE_OCTREE<A,CONDITION>* get_feuille(int num) {return lst_entite_feuille.get(num); };
384 5
385    
386     virtual void initialiser(TPL_LISTE_ENTITE<CONDITION>* lst_entite,int nombre,double xmin,double ymin,double zmin,double xmax,double ymax,double zmax)
387     {
388 francois 65 TPL_CELLULE_OCTREE<A ,CONDITION>* root_cellule=new TPL_CELLULE_OCTREE<A ,CONDITION>(NULL,xmin,ymin,zmin,xmax,ymax,zmax,0,-1);
389 5 lst_entite_cellule.ajouter(root_cellule);
390     for (int i=0;i<lst_entite->get_nb();i++)
391     {
392     CONDITION cond=lst_entite->get(i);
393     BOITE_3D boite_cond=cond->get_boite_3D();
394     if (boite_cond*root_cellule->boite) root_cellule->lst_entite_CONDITION.ajouter(cond);
395     }
396     if (root_cellule->lst_entite_CONDITION.get_nb()>nombre)
397     {
398     root_cellule->feuille=0;
399     double dx=xmax-xmin;
400     double dy=ymax-ymin;
401     double dz=zmax-zmin;
402 francois 65 root_cellule->fils[0]=cree_fils(root_cellule,xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,0);
403     root_cellule->fils[1]=cree_fils(root_cellule,xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,1);
404     root_cellule->fils[2]=cree_fils(root_cellule,xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,2);
405     root_cellule->fils[3]=cree_fils(root_cellule,xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,3);
406     root_cellule->fils[4]=cree_fils(root_cellule,xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,4);
407     root_cellule->fils[5]=cree_fils(root_cellule,xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,5);
408     root_cellule->fils[6]=cree_fils(root_cellule,xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,6);
409     root_cellule->fils[7]=cree_fils(root_cellule,xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,7);
410 5 }
411     else root_cellule->feuille=1;
412     for (int j=0;j<lst_entite_cellule.get_nb();j++)
413     {
414     TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(j);
415     cellule->lst_entite_CONDITION.vide();
416     }
417     }
418    
419     virtual void initialiser(TPL_MAP_ENTITE<CONDITION>* lst_entite,int nombre,double xmin,double ymin,double zmin,double xmax,double ymax,double zmax)
420     {
421 francois 65 TPL_CELLULE_OCTREE<A ,CONDITION>* root_cellule=new TPL_CELLULE_OCTREE<A ,CONDITION>(NULL,xmin,ymin,zmin,xmax,ymax,zmax,0,-1);
422 5 lst_entite_cellule.ajouter(root_cellule);
423 francois 276 typename TPL_MAP_ENTITE<CONDITION>::ITERATEUR it;
424     for (CONDITION cond=lst_entite->get_premier(it);cond!=NULL;cond=lst_entite->get_suivant(it))
425 5 {
426     BOITE_3D boite_cond=cond->get_boite_3D();
427     if (boite_cond*root_cellule->boite) root_cellule->lst_entite_CONDITION.ajouter(cond);
428     }
429     if (root_cellule->lst_entite_CONDITION.get_nb()>nombre)
430     {
431     root_cellule->feuille=0;
432     double dx=xmax-xmin;
433     double dy=ymax-ymin;
434     double dz=zmax-zmin;
435 francois 65 root_cellule->fils[0]=cree_fils(root_cellule,xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,0);
436     root_cellule->fils[1]=cree_fils(root_cellule,xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,1);
437     root_cellule->fils[2]=cree_fils(root_cellule,xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,2);
438     root_cellule->fils[3]=cree_fils(root_cellule,xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,3);
439     root_cellule->fils[4]=cree_fils(root_cellule,xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,4);
440     root_cellule->fils[5]=cree_fils(root_cellule,xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,5);
441     root_cellule->fils[6]=cree_fils(root_cellule,xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,6);
442     root_cellule->fils[7]=cree_fils(root_cellule,xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,7);
443 5 }
444     else root_cellule->feuille=1;
445     for (int j=0;j<lst_entite_cellule.get_nb();j++)
446     {
447     TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(j);
448     cellule->lst_entite_CONDITION.vide();
449     }
450     }
451    
452     virtual void initialiser(OCTREE_BASE* oc)
453     {
454     BOITE_3D boite=oc->get_cellule(0)->get_boite();
455     double xmin=boite.get_xmin();
456     double xmax=boite.get_xmax();
457     double ymin=boite.get_ymin();
458     double ymax=boite.get_ymax();
459     double zmin=boite.get_zmin();
460     double zmax=boite.get_zmax();
461 francois 65 TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=new TPL_CELLULE_OCTREE<A ,CONDITION>(NULL,xmin,ymin,zmin,xmax,ymax,zmax,0,oc->get_cellule(0)->get_sontype());
462 5 lst_entite_cellule.ajouter(cellule);
463 francois 65 niveaumax=oc->get_niveau_max();
464     cellule->feuille=oc->get_cellule(0)->get_feuille();
465 5 if (oc->get_cellule(0)->get_feuille()==0)
466     {
467 francois 632 if (oc->get_cellule(0)->get_fils(0)!=NULL) cellule->fils[0]=cree_fils(cellule,oc->get_cellule(0)->get_fils(0),0);
468     if (oc->get_cellule(0)->get_fils(1)!=NULL) cellule->fils[1]=cree_fils(cellule,oc->get_cellule(0)->get_fils(1),1);
469     if (oc->get_cellule(0)->get_fils(2)!=NULL) cellule->fils[2]=cree_fils(cellule,oc->get_cellule(0)->get_fils(2),2);
470     if (oc->get_cellule(0)->get_fils(3)!=NULL) cellule->fils[3]=cree_fils(cellule,oc->get_cellule(0)->get_fils(3),3);
471     if (oc->get_cellule(0)->get_fils(4)!=NULL) cellule->fils[4]=cree_fils(cellule,oc->get_cellule(0)->get_fils(4),4);
472     if (oc->get_cellule(0)->get_fils(5)!=NULL) cellule->fils[5]=cree_fils(cellule,oc->get_cellule(0)->get_fils(5),5);
473     if (oc->get_cellule(0)->get_fils(6)!=NULL) cellule->fils[6]=cree_fils(cellule,oc->get_cellule(0)->get_fils(6),6);
474     if (oc->get_cellule(0)->get_fils(7)!=NULL) cellule->fils[7]=cree_fils(cellule,oc->get_cellule(0)->get_fils(7),7);
475 5 }
476 francois 65 else {cellule->feuille=1;lst_entite_feuille.ajouter(cellule);}
477 5 };
478    
479    
480 francois 65 TPL_CELLULE_OCTREE<A,CONDITION>* cree_fils( TPL_CELLULE_OCTREE<A ,CONDITION>* cell,CELLULE_OCTREE_BASE *cellule_base,int st)
481 5 {
482     BOITE_3D boite=cellule_base->get_boite();
483     double xmin=boite.get_xmin();
484     double xmax=boite.get_xmax();
485     double ymin=boite.get_ymin();
486     double ymax=boite.get_ymax();
487     double zmin=boite.get_zmin();
488     double zmax=boite.get_zmax();
489 francois 65 TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=new TPL_CELLULE_OCTREE<A ,CONDITION>(cell,xmin,ymin,zmin,xmax,ymax,zmax,cellule_base->get_niveau(),st);
490 5 lst_entite_cellule.ajouter(cellule);
491 francois 65 if (niveaumax<cellule_base->get_niveau()) niveaumax=cellule_base->get_niveau();
492 5 if (cellule_base->get_feuille()==1)
493     {
494 francois 65 {cellule->feuille=1;lst_entite_feuille.ajouter(cellule);}
495 5 }
496     else
497     {
498 francois 632 if (cellule_base->get_fils(0)!=NULL) cellule->fils[0]=cree_fils(cellule,cellule_base->get_fils(0),0);
499     if (cellule_base->get_fils(1)!=NULL) cellule->fils[1]=cree_fils(cellule,cellule_base->get_fils(1),1);
500     if (cellule_base->get_fils(2)!=NULL) cellule->fils[2]=cree_fils(cellule,cellule_base->get_fils(2),2);
501     if (cellule_base->get_fils(3)!=NULL) cellule->fils[3]=cree_fils(cellule,cellule_base->get_fils(3),3);
502     if (cellule_base->get_fils(4)!=NULL) cellule->fils[4]=cree_fils(cellule,cellule_base->get_fils(4),4);
503     if (cellule_base->get_fils(5)!=NULL) cellule->fils[5]=cree_fils(cellule,cellule_base->get_fils(5),5);
504     if (cellule_base->get_fils(6)!=NULL) cellule->fils[6]=cree_fils(cellule,cellule_base->get_fils(6),6);
505     if (cellule_base->get_fils(7)!=NULL) cellule->fils[7]=cree_fils(cellule,cellule_base->get_fils(7),7);
506     cellule->feuille=cellule_base->get_feuille();
507 5 }
508     return cellule;
509     };
510    
511 francois 65 virtual TPL_CELLULE_OCTREE<A ,CONDITION>* cree_fils(TPL_CELLULE_OCTREE<A ,CONDITION>* cell,double xmin,double ymin,double zmin,double dx,double dy,double dz,TPL_LISTE_ENTITE<CONDITION>* lst_entite,int nombre,int niv,int st)
512 5 {
513 francois 65 TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=new TPL_CELLULE_OCTREE<A ,CONDITION>(cell,xmin,ymin,zmin,xmin+dx,ymin+dy,zmin+dz,niv,st);
514 5 lst_entite_cellule.ajouter(cellule);
515 francois 65 if (niveaumax<niv) niveaumax=niv;
516     for (int i=0;i<lst_entite->get_nb();i++)
517 5 {
518     CONDITION cond=lst_entite->get(i);
519     BOITE_3D boite_cond=cond->get_boite_3D();
520     if (boite_cond*cellule->boite) cellule->lst_entite_CONDITION.ajouter(cond);
521     }
522     if (cellule->lst_entite_CONDITION.get_nb()>nombre)
523     {
524     cellule->feuille=0;
525 francois 65 cellule->fils[0]=cree_fils(cellule,xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,0);
526     cellule->fils[1]=cree_fils(cellule,xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,1);
527     cellule->fils[2]=cree_fils(cellule,xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,2);
528     cellule->fils[3]=cree_fils(cellule,xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,3);
529     cellule->fils[4]=cree_fils(cellule,xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,4);
530     cellule->fils[5]=cree_fils(cellule,xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,5);
531     cellule->fils[6]=cree_fils(cellule,xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,6);
532     cellule->fils[7]=cree_fils(cellule,xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,7);
533 5 }
534 francois 65 else {cellule->feuille=1;lst_entite_feuille.ajouter(cellule);}
535 5 return cellule;
536     }
537    
538    
539     virtual void rechercher(BOITE_3D& boite,TPL_MAP_ENTITE<A>& liste_entite_trouve,TPL_CELLULE_OCTREE<A ,CONDITION>* cellule)
540     {
541 francois 632 if (cellule==NULL) return;
542 5 if (boite*cellule->boite)
543     if (cellule->feuille==1)
544     {
545     for (int i=0;i<cellule->lst_entite_A.get_nb();i++)
546     liste_entite_trouve.ajouter(cellule->lst_entite_A.get(i));
547     }
548     else
549     {
550     rechercher(boite,liste_entite_trouve,cellule->fils[0]);
551     rechercher(boite,liste_entite_trouve,cellule->fils[1]);
552     rechercher(boite,liste_entite_trouve,cellule->fils[2]);
553     rechercher(boite,liste_entite_trouve,cellule->fils[3]);
554     rechercher(boite,liste_entite_trouve,cellule->fils[4]);
555     rechercher(boite,liste_entite_trouve,cellule->fils[5]);
556     rechercher(boite,liste_entite_trouve,cellule->fils[6]);
557     rechercher(boite,liste_entite_trouve,cellule->fils[7]);
558     }
559     };
560    
561    
562     virtual void get_cellule(BOITE_3D& boite,TPL_CELLULE_OCTREE<A ,CONDITION>* cellule,TPL_MAP_ENTITE<TPL_CELLULE_OCTREE<A ,CONDITION> * > &liste_entite)
563     {
564     if (boite*cellule->boite)
565     if (cellule->feuille==1)
566     {
567     liste_entite.ajouter(cellule);
568     }
569     else
570     {
571     get_cellule(boite,cellule->fils[0],liste_entite);
572     get_cellule(boite,cellule->fils[1],liste_entite);
573     get_cellule(boite,cellule->fils[2],liste_entite);
574     get_cellule(boite,cellule->fils[3],liste_entite);
575     get_cellule(boite,cellule->fils[4],liste_entite);
576     get_cellule(boite,cellule->fils[5],liste_entite);
577     get_cellule(boite,cellule->fils[6],liste_entite);
578     get_cellule(boite,cellule->fils[7],liste_entite);
579     }
580     };
581    
582 francois 65 virtual TPL_CELLULE_OCTREE<A,CONDITION> *get_cellule_adjacent(TPL_CELLULE_OCTREE<A,CONDITION> * cellule,int direction)
583     {
584     TPL_CELLULE_OCTREE<A,CONDITION> *cellule2;
585     OUTIL_OCTREE outil;
586     if (cellule->pere==NULL) cellule2=NULL;
587     else if (outil.adjacent(direction,cellule->get_sontype())) cellule2=get_cellule_adjacent(cellule->pere,direction);
588     else if (outil.commonface(direction,cellule->get_sontype())!=-1) cellule2=get_cellule_voisin(cellule->pere,outil.commonface(direction,cellule->get_sontype()));
589     else cellule2=cellule->pere;
590     if (cellule2!=NULL)
591     if (cellule2->get_feuille()==0)
592     return cellule2->get_fils(outil.reflect(direction,cellule->get_sontype()));
593     return cellule2;
594     }
595    
596     virtual TPL_CELLULE_OCTREE<A,CONDITION> *get_cellule_voisin(TPL_CELLULE_OCTREE<A,CONDITION> * cellule,int direction)
597     {
598     TPL_CELLULE_OCTREE<A,CONDITION> *cellule2;
599     OUTIL_OCTREE outil;
600     if ((!(cellule->pere==NULL)) && (outil.adjacent(direction,cellule->get_sontype())))
601     cellule2=get_cellule_voisin(cellule->pere,direction);
602     else
603     cellule2=cellule->pere;
604     if (cellule2!=NULL)
605     if (cellule2->feuille==0)
606     return cellule2->get_fils(outil.reflect(direction,cellule->get_sontype()));
607     return cellule2;
608     }
609    
610    
611    
612    
613     virtual void get_feuille_voisins(TPL_CELLULE_OCTREE<A,CONDITION> * cellule,int direction,vector<TPL_CELLULE_OCTREE<A,CONDITION> *> *lst)
614     {
615     OUTIL_OCTREE outil;
616     lst->clear();
617     TPL_CELLULE_OCTREE<A,CONDITION> *cellule2=get_cellule_voisin(cellule,direction);
618     if (cellule2!=NULL) lst->insert(lst->end(),cellule2);
619     int i=0;
620     while (i<lst->size())
621     {
622     TPL_CELLULE_OCTREE<A,CONDITION> *cell=(*lst)[i];
623     if (cell->feuille==0)
624     {
625     lst->insert(lst->end(),cell->get_fils(outil.filsvoisin(direction,0)));
626     lst->insert(lst->end(),cell->get_fils(outil.filsvoisin(direction,1)));
627     lst->insert(lst->end(),cell->get_fils(outil.filsvoisin(direction,2)));
628     lst->insert(lst->end(),cell->get_fils(outil.filsvoisin(direction,3)));
629     }
630     i++;
631     }
632 francois 102 typename vector<TPL_CELLULE_OCTREE<A,CONDITION> * >::iterator j=lst->end();
633 francois 65 while (j!=lst->begin())
634     {
635     j--;
636     TPL_CELLULE_OCTREE<A,CONDITION> *cell=*j;
637     if (cell->feuille==0)
638     lst->erase(j);
639    
640     }
641     }
642    
643 5 virtual TPL_CELLULE_OCTREE<A,CONDITION> *get_cellule(double x,double y, double z)
644     {
645     BOITE_3D boite(x,y,z,x,y,z);
646     TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(0);
647     TPL_MAP_ENTITE<TPL_CELLULE_OCTREE<A ,CONDITION> * > liste_cellule;
648     get_cellule(boite,cellule,liste_cellule);
649     if (liste_cellule.get_nb()==1) return liste_cellule.get(0);
650     return NULL;
651     };
652    
653    
654 francois 65 virtual unsigned long get_cellule_keycode(int numcellule,int numsommet)
655     {
656     TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(numcellule);
657     return get_keycode(cellule,numsommet);
658     }
659    
660     virtual unsigned long get_feuille_keycode(int numcellule,int numsommet)
661     {
662     TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_feuille.get(numcellule);
663     return get_keycode(cellule,numsommet);
664     }
665    
666     virtual unsigned long get_keycode(TPL_CELLULE_OCTREE<A ,CONDITION>* cellule,int numsommet)
667     {
668     TPL_CELLULE_OCTREE<A ,CONDITION>* root=lst_entite_cellule.get(0);
669    
670     double x=cellule->boite.get_xmin();
671     double y=cellule->boite.get_ymin();
672     double z=cellule->boite.get_zmin();
673     double xx=cellule->boite.get_xmax();
674     double yy=cellule->boite.get_ymax();
675     double zz=cellule->boite.get_zmax();
676     double somx=x,somy=y,somz=z;
677     if (numsommet==1) somx=xx;
678     if (numsommet==2) {somx=xx;somy=yy;}
679     if (numsommet==3) somy=yy;
680     if (numsommet==4) somz=zz;
681     if (numsommet==5) {somx=xx;somz=zz;}
682     if (numsommet==6) {somx=xx;somy=yy;somz=zz;}
683     if (numsommet==7) {somy=yy;somz=zz;}
684     double nx=0.1+(somx-root->boite.get_xmin())/(root->boite.get_xmax()-root->boite.get_xmin())*(1<<get_niveau_max());
685     double ny=0.1+(somy-root->boite.get_ymin())/(root->boite.get_ymax()-root->boite.get_ymin())*(1<<get_niveau_max());
686     double nz=0.1+(somz-root->boite.get_zmin())/(root->boite.get_zmax()-root->boite.get_zmin())*(1<<get_niveau_max());
687     OUTIL_OCTREE outil;
688     return outil.determine_keycode(nx,ny,nz);
689     }
690    
691     virtual unsigned long get_keycode(double x,double y,double z)
692     {
693     TPL_CELLULE_OCTREE<A ,CONDITION>* root=lst_entite_cellule.get(0);
694     double nx=0.1+(x-root->boite.get_xmin())/(root->boite.get_xmax()-root->boite.get_xmin())*(1<<get_niveau_max());
695     double ny=0.1+(y-root->boite.get_ymin())/(root->boite.get_ymax()-root->boite.get_ymin())*(1<<get_niveau_max());
696     double nz=0.1+(z-root->boite.get_zmin())/(root->boite.get_zmax()-root->boite.get_zmin())*(1<<get_niveau_max());
697     OUTIL_OCTREE outil;
698     return outil.determine_keycode(nx,ny,nz);
699     }
700    
701    
702    
703     virtual void get_xyzsommet_cellule(int numcellule,int numsommet,double &x,double &y,double &z)
704     {
705     TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(numcellule);
706     x=cellule->boite.get_xmin();
707     y=cellule->boite.get_ymin();
708     z=cellule->boite.get_zmin();
709     double xx=cellule->boite.get_xmax();
710     double yy=cellule->boite.get_ymax();
711     double zz=cellule->boite.get_zmax();
712     if (numsommet==1) x=xx;
713     if (numsommet==2) {x=xx;y=yy;}
714     if (numsommet==3) y=yy;
715     if (numsommet==4) z=zz;
716     if (numsommet==5) {x=xx;z=zz;}
717     if (numsommet==6) {x=xx;y=yy;z=zz;}
718     if (numsommet==7) {y=yy;z=zz;}
719     }
720    
721     virtual void get_xyzsommet_feuille(int numcellule,int numsommet,double &x,double &y,double &z)
722     {
723     TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_feuille.get(numcellule);
724     x=cellule->boite.get_xmin();
725     y=cellule->boite.get_ymin();
726     z=cellule->boite.get_zmin();
727     double xx=cellule->boite.get_xmax();
728     double yy=cellule->boite.get_ymax();
729     double zz=cellule->boite.get_zmax();
730     if (numsommet==1) x=xx;
731     if (numsommet==2) {x=xx;y=yy;}
732     if (numsommet==3) y=yy;
733     if (numsommet==4) z=zz;
734     if (numsommet==5) {x=xx;z=zz;}
735     if (numsommet==6) {x=xx;y=yy;z=zz;}
736     if (numsommet==7) {y=yy;z=zz;}
737     }
738    
739    
740    
741     virtual void equilibre(int niveauequilibre=1)
742     {
743     int ok=0;
744     do
745     {
746     int nbfeuilleavant=get_nb_feuille();
747     vector< TPL_CELLULE_OCTREE<A,CONDITION> *> lstraf;
748     for (int i=0;i<lst_entite_feuille.get_nb();i++)
749     {
750     TPL_CELLULE_OCTREE<A,CONDITION> *feuille=lst_entite_feuille.get(i);
751     int niveaumaxvoisin=0;
752     for (int j=0;j<6;j++)
753     {
754     vector< TPL_CELLULE_OCTREE<A,CONDITION> *> lstvoi;
755     get_feuille_voisins(feuille,j,&lstvoi);
756     int nb_feuille=lstvoi.size();
757     for (int k=0;k<nb_feuille;k++)
758     {
759     int niveau=lstvoi[k]->get_niveau();
760     if (niveau>niveaumaxvoisin) niveaumaxvoisin=niveau;
761     }
762    
763     }
764     if (niveaumaxvoisin-feuille->get_niveau()>niveauequilibre) {lstraf.insert(lstraf.end(),feuille);feuille->feuille=niveaumaxvoisin-niveauequilibre;}
765     }
766     int nbcelluleraffiner=lstraf.size();
767     for (int i=0;i<nbcelluleraffiner;i++)
768     {
769     TPL_CELLULE_OCTREE<A,CONDITION> *cell=lstraf[i];
770     lst_entite_feuille.supprimer(cell);
771     int niveauatteindre=cell->feuille;
772     int niveau=cell->niveau;
773     cell->feuille=0;
774     double xmin=cell->boite.get_xmin();
775     double ymin=cell->boite.get_ymin();
776     double zmin=cell->boite.get_zmin();
777     double dx=cell->boite.get_xmax()-cell->boite.get_xmin();
778     double dy=cell->boite.get_ymax()-cell->boite.get_ymin();
779     double dz=cell->boite.get_zmax()-cell->boite.get_zmin();
780    
781     cell->fils[0]=cree_fils(cell,xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,niveau+1,niveauatteindre,0);
782     cell->fils[1]=cree_fils(cell,xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,niveau+1,niveauatteindre,1);
783     cell->fils[2]=cree_fils(cell,xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,niveau+1,niveauatteindre,2);
784     cell->fils[3]=cree_fils(cell,xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,niveau+1,niveauatteindre,3);
785     cell->fils[4]=cree_fils(cell,xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,niveau+1,niveauatteindre,4);
786     cell->fils[5]=cree_fils(cell,xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,niveau+1,niveauatteindre,5);
787     cell->fils[6]=cree_fils(cell,xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,niveau+1,niveauatteindre,6);
788     cell->fils[7]=cree_fils(cell,xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,niveau+1,niveauatteindre,7);
789     }
790     int nbfeuilleapres=get_nb_feuille();
791     if (nbfeuilleapres==nbfeuilleavant) ok=1;
792     }
793     while (ok==0);
794    
795    
796     }
797    
798     virtual TPL_CELLULE_OCTREE<A ,CONDITION>* cree_fils(TPL_CELLULE_OCTREE<A ,CONDITION>* cell,double xmin,double ymin,double zmin,double dx,double dy,double dz,int niv,int niveauatteindre,int st)
799     {
800     TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=new TPL_CELLULE_OCTREE<A ,CONDITION>(cell,xmin,ymin,zmin,xmin+dx,ymin+dy,zmin+dz,niv,st);
801     lst_entite_cellule.ajouter(cellule);
802     if (niveaumax<niv) niveaumax=niv;
803     if (cellule->get_niveau()!=niveauatteindre)
804     {
805     cellule->feuille=0;
806     cellule->fils[0]=cree_fils(cellule,xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,niv+1,niveauatteindre,0);
807     cellule->fils[1]=cree_fils(cellule,xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,niv+1,niveauatteindre,1);
808     cellule->fils[2]=cree_fils(cellule,xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,niv+1,niveauatteindre,2);
809     cellule->fils[3]=cree_fils(cellule,xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,niv+1,niveauatteindre,3);
810     cellule->fils[4]=cree_fils(cellule,xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,niv+1,niveauatteindre,4);
811     cellule->fils[5]=cree_fils(cellule,xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,niv+1,niveauatteindre,5);
812     cellule->fils[6]=cree_fils(cellule,xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,niv+1,niveauatteindre,6);
813     cellule->fils[7]=cree_fils(cellule,xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,niv+1,niveauatteindre,7);
814     }
815     else {cellule->feuille=1;lst_entite_feuille.ajouter(cellule);}
816     return cellule;
817     }
818    
819    
820 5 virtual void rechercher(double xcentre,double ycentre,double zcentre,double rayon_recherche,TPL_MAP_ENTITE<A>& liste_entite_trouve)
821     {
822     BOITE_3D boite(xcentre-rayon_recherche,ycentre-rayon_recherche,zcentre-rayon_recherche,xcentre+rayon_recherche,ycentre+rayon_recherche,zcentre+rayon_recherche);
823     TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(0);
824     rechercher(boite,liste_entite_trouve,cellule);
825     };
826    
827    
828    
829     virtual void inserer(BOITE_3D& boite,A a,TPL_CELLULE_OCTREE<A ,CONDITION>* cellule)
830     {
831 francois 632 if (cellule==NULL) return;
832 5 if (boite*cellule->boite)
833     if (cellule->feuille==1)
834     {
835     cellule->lst_entite_A.ajouter(a);
836     }
837     else
838     {
839     inserer(boite,a,cellule->fils[0]);
840     inserer(boite,a,cellule->fils[1]);
841     inserer(boite,a,cellule->fils[2]);
842     inserer(boite,a,cellule->fils[3]);
843     inserer(boite,a,cellule->fils[4]);
844     inserer(boite,a,cellule->fils[5]);
845     inserer(boite,a,cellule->fils[6]);
846     inserer(boite,a,cellule->fils[7]);
847     }
848     };
849    
850     virtual void supprimer(BOITE_3D& boite,A a,TPL_CELLULE_OCTREE<A ,CONDITION>* cellule)
851     {
852 francois 632 if (cellule==NULL) return;
853 5 if (boite*cellule->boite)
854     if (cellule->feuille==1)
855     {
856     cellule->lst_entite_A.supprimer(a);
857     }
858     else
859     {
860     supprimer(boite,a,cellule->fils[0]);
861     supprimer(boite,a,cellule->fils[1]);
862     supprimer(boite,a,cellule->fils[2]);
863     supprimer(boite,a,cellule->fils[3]);
864     supprimer(boite,a,cellule->fils[4]);
865     supprimer(boite,a,cellule->fils[5]);
866     supprimer(boite,a,cellule->fils[6]);
867     supprimer(boite,a,cellule->fils[7]);
868     }
869     };
870    
871     virtual void inserer(A a)
872     {
873     BOITE_3D boite=a->get_boite_3D();
874     TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(0);
875     inserer(boite,a,cellule);
876     }
877    
878     virtual void supprimer(A a)
879     {
880     BOITE_3D boite=a->get_boite_3D();
881     TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(0);
882     supprimer(boite,a,cellule);
883     }
884    
885 francois 65 virtual int get_niveau_max(void)
886     {
887     return niveaumax;
888     }
889 5
890 francois 65
891    
892 francois 276 virtual void vide(void)
893     {
894     for (int i=0;i<lst_entite_feuille.get_nb();i++)
895     {
896     TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_feuille.get(i);
897     cellule->vide();
898     }
899     }
900 francois 65
901 francois 507
902     virtual double get_dimension_caracteristique()
903     {
904     TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(0);
905     double x=cellule->boite.get_xmin();
906     double y=cellule->boite.get_ymin();
907     double z=cellule->boite.get_zmin();
908     double xx=cellule->boite.get_xmax();
909     double yy=cellule->boite.get_ymax();
910     double zz=cellule->boite.get_zmax();
911     return sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y)+(zz-z)*(zz-z)) ;
912     }
913    
914    
915    
916 francois 65 protected:
917 5 TPL_LISTE_ENTITE<TPL_CELLULE_OCTREE<A ,CONDITION>* > lst_entite_cellule;
918 francois 65 TPL_LISTE_ENTITE<TPL_CELLULE_OCTREE<A ,CONDITION>* > lst_entite_feuille;
919     int niveaumax;
920 5
921     };
922    
923 francois 65 template <class A,class B>
924     class TPL_OCTREE_FCT:public TPL_OCTREE<A,A>
925     {
926     private:
927     double coef;
928 5
929 francois 65 public:
930     TPL_OCTREE_FCT():TPL_OCTREE<A,A>(),coef(1.) {};
931     ~TPL_OCTREE_FCT() {}
932 5
933 francois 65
934 francois 102 virtual void change_coefficent_multiplicateur(double val) {coef=val;};
935 francois 65
936     virtual void initialiser(B &fonction,double xmin,double ymin,double zmin,double xmax,double ymax,double zmax)
937     {
938     TPL_CELLULE_OCTREE<A ,A>* root_cellule=new TPL_CELLULE_OCTREE<A ,A>(NULL,xmin,ymin,zmin,xmax,ymax,zmax,0,-1);
939 francois 102 TPL_OCTREE<A,A>::lst_entite_cellule.ajouter(root_cellule);
940 francois 65 double dx=root_cellule->boite.get_xmax()-root_cellule->boite.get_xmin();
941     double dy=root_cellule->boite.get_ymax()-root_cellule->boite.get_ymin();
942     double dz=root_cellule->boite.get_zmax()-root_cellule->boite.get_zmin();
943     double d=dx;
944 francois 584 if (dy>d) d=dy;
945     if (dz>d) d=dz;
946 francois 65 double xyz[3];
947     root_cellule->boite.get_centre(xyz);
948     double ecart[9];
949     fonction.evaluer(xyz,ecart);
950     double dcible=coef/sqrt(ecart[0]);
951     if (dcible<d)
952     {
953     root_cellule->feuille=0;
954     root_cellule->fils[0]=cree_fils(root_cellule,xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,fonction,1,0);
955     root_cellule->fils[1]=cree_fils(root_cellule,xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,fonction,1,1);
956     root_cellule->fils[2]=cree_fils(root_cellule,xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,fonction,1,2);
957     root_cellule->fils[3]=cree_fils(root_cellule,xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,fonction,1,3);
958     root_cellule->fils[4]=cree_fils(root_cellule,xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,fonction,1,4);
959     root_cellule->fils[5]=cree_fils(root_cellule,xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,fonction,1,5);
960     root_cellule->fils[6]=cree_fils(root_cellule,xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,fonction,1,6);
961     root_cellule->fils[7]=cree_fils(root_cellule,xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,fonction,1,7);
962     }
963 francois 102 else {root_cellule->feuille=1;TPL_OCTREE<A,A>::lst_entite_feuille.ajouter(root_cellule);}
964 francois 65 }
965    
966     virtual TPL_CELLULE_OCTREE<A ,A>* cree_fils(TPL_CELLULE_OCTREE<A ,A>* cell,double xmin,double ymin,double zmin,double dx,double dy,double dz,B &fonction,int niv,int st)
967     {
968     TPL_CELLULE_OCTREE<A ,A>* cellule=new TPL_CELLULE_OCTREE<A ,A>(cell,xmin,ymin,zmin,xmin+dx,ymin+dy,zmin+dz,niv,st);
969 francois 102 TPL_OCTREE<A,A>::lst_entite_cellule.ajouter(cellule);
970     if (TPL_OCTREE<A,A>::niveaumax<niv) TPL_OCTREE<A,A>::niveaumax=niv;
971 francois 65 double ddx=cellule->boite.get_xmax()-cellule->boite.get_xmin();
972     double ddy=cellule->boite.get_ymax()-cellule->boite.get_ymin();
973     double ddz=cellule->boite.get_zmax()-cellule->boite.get_zmin();
974     double d=dx;
975 francois 584 if (ddy>d) d=ddy;
976     if (ddz>d) d=ddz;
977 francois 65 double xyz[3];
978     cellule->boite.get_centre(xyz);
979     double ecart[9];
980     fonction.evaluer(xyz,ecart);
981     double dcible=coef/sqrt(ecart[0]);
982     if (dcible<d)
983     {
984     cellule->feuille=0;
985     cellule->fils[0]=cree_fils(cellule,xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,fonction,niv+1,0);
986     cellule->fils[1]=cree_fils(cellule,xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,fonction,niv+1,1);
987     cellule->fils[2]=cree_fils(cellule,xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,fonction,niv+1,2);
988     cellule->fils[3]=cree_fils(cellule,xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,fonction,niv+1,3);
989     cellule->fils[4]=cree_fils(cellule,xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,fonction,niv+1,4);
990     cellule->fils[5]=cree_fils(cellule,xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,fonction,niv+1,5);
991     cellule->fils[6]=cree_fils(cellule,xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,fonction,niv+1,6);
992     cellule->fils[7]=cree_fils(cellule,xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,fonction,niv+1,7);
993     }
994 francois 102 else {cellule->feuille=1;TPL_OCTREE<A,A>::lst_entite_feuille.ajouter(cellule);}
995 francois 65 return cellule;
996     }
997     };
998    
999    
1000 francois 632 template <class A,class B>
1001     class TPL_NTREE_FCT:public TPL_OCTREE<A,A>
1002     {
1003     private:
1004     double coef;
1005 francois 65
1006 francois 632 public:
1007     TPL_NTREE_FCT():TPL_OCTREE<A,A>(),coef(1.) {};
1008     ~TPL_NTREE_FCT() {}
1009    
1010    
1011     virtual void change_coefficent_multiplicateur(double val) {coef=val;};
1012    
1013     virtual void initialiser(B &fonction,double xmin,double ymin,double zmin,double xmax,double ymax,double zmax)
1014     {
1015     TPL_CELLULE_OCTREE<A ,A>* root_cellule=new TPL_CELLULE_OCTREE<A ,A>(NULL,xmin,ymin,zmin,xmax,ymax,zmax,0,-1);
1016     TPL_OCTREE<A,A>::lst_entite_cellule.ajouter(root_cellule);
1017     double dx=root_cellule->boite.get_xmax()-root_cellule->boite.get_xmin();
1018     double dy=root_cellule->boite.get_ymax()-root_cellule->boite.get_ymin();
1019     double dz=root_cellule->boite.get_zmax()-root_cellule->boite.get_zmin();
1020     double xyz[3];
1021     root_cellule->boite.get_centre(xyz);
1022     double ecart[9];
1023     fonction.evaluer(xyz,ecart);
1024     double dcible=coef/sqrt(ecart[0]);
1025     int ndivx=2,ndivy=2,ndivz=2;
1026     if (dcible>dx) ndivx=1;
1027     if (dcible>dy) ndivy=1;
1028     if (dcible>dz) ndivz=1;
1029     if (ndivx*ndivy*ndivz!=1)
1030     {
1031     root_cellule->feuille=0;
1032     for (int i=0;i<ndivx;i++)
1033     for (int j=0;j<ndivy;j++)
1034     for (int k=0;k<ndivz;k++)
1035     root_cellule->fils[((i*ndivx)+j)*ndivy+k]=cree_fils(root_cellule,xmin+i*1.0/ndivx*dx,ymin+j*1.0/ndivy*dy,zmin+k*1.0/ndivz*dz,dx*1./ndivx,dy*1./ndivy,dz*1./ndivz,fonction,1,0);
1036     }
1037     else {root_cellule->feuille=1;TPL_OCTREE<A,A>::lst_entite_feuille.ajouter(root_cellule);}
1038     }
1039    
1040     virtual TPL_CELLULE_OCTREE<A ,A>* cree_fils(TPL_CELLULE_OCTREE<A ,A>* cell,double xmin,double ymin,double zmin,double dx,double dy,double dz,B &fonction,int niv,int st)
1041     {
1042     TPL_CELLULE_OCTREE<A ,A>* cellule=new TPL_CELLULE_OCTREE<A ,A>(cell,xmin,ymin,zmin,xmin+dx,ymin+dy,zmin+dz,niv,st);
1043     TPL_OCTREE<A,A>::lst_entite_cellule.ajouter(cellule);
1044     if (TPL_OCTREE<A,A>::niveaumax<niv) TPL_OCTREE<A,A>::niveaumax=niv;
1045     double ddx=cellule->boite.get_xmax()-cellule->boite.get_xmin();
1046     double ddy=cellule->boite.get_ymax()-cellule->boite.get_ymin();
1047     double ddz=cellule->boite.get_zmax()-cellule->boite.get_zmin();
1048     double xyz[3];
1049     cellule->boite.get_centre(xyz);
1050     double ecart[9];
1051     fonction.evaluer(xyz,ecart);
1052     double dcible=coef/sqrt(ecart[0]);
1053     int ndivx=2,ndivy=2,ndivz=2;
1054     if (dcible>dx) ndivx=1;
1055     if (dcible>dy) ndivy=1;
1056     if (dcible>dz) ndivz=1;
1057     if (ndivx*ndivy*ndivz!=1)
1058     {
1059     cellule->feuille=0;
1060     for (int i=0;i<ndivx;i++)
1061     for (int j=0;j<ndivy;j++)
1062     for (int k=0;k<ndivz;k++)
1063     cellule->fils[((i*ndivx)+j)*ndivy+k]=cree_fils(cellule,xmin+i*1.0/ndivx*dx,ymin+j*1.0/ndivy*dy,zmin+k*1.0/ndivz*dz,dx*1./ndivx,dy*1./ndivy,dz*1./ndivz,fonction,1,0);
1064     }
1065     else {cellule->feuille=1;TPL_OCTREE<A,A>::lst_entite_feuille.ajouter(cellule);}
1066     return cellule;
1067     }
1068     };
1069    
1070    
1071    
1072    
1073    
1074    
1075    
1076    
1077    
1078 5 template <class A,class CONDITION,class B>
1079     class TPL_OCTREE_INFO:public OCTREE_BASE
1080     {
1081     public:
1082     TPL_OCTREE_INFO() {};
1083     ~TPL_OCTREE_INFO()
1084     {
1085     for (int i1=0;i1<lst_entite_cellule.get_nb();i1++)
1086     {
1087     TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=lst_entite_cellule.get(i1);
1088     delete cellule;
1089     }
1090     };
1091    
1092     virtual int get_nb_cellule(void) {return lst_entite_cellule.get_nb();};
1093    
1094     virtual BOITE_3D get_boite_de_base(void) {return lst_entite_cellule.get(0)->get_boite();};
1095    
1096     virtual TPL_CELLULE_INFO<A,CONDITION,B>* get_cellule(int num) {return lst_entite_cellule.get(num); };
1097    
1098    
1099     virtual void initialiser(TPL_LISTE_ENTITE<CONDITION>* lst_entite,int nombre,double xmin,double ymin,double zmin,double xmax,double ymax,double zmax)
1100     {
1101     TPL_CELLULE_INFO<A ,CONDITION,B>* root_cellule=new TPL_CELLULE_INFO<A ,CONDITION,B>(xmin,ymin,zmin,xmax,ymax,zmax);
1102     lst_entite_cellule.ajouter(root_cellule);
1103     for (int i=0;i<lst_entite->get_nb();i++)
1104     {
1105     CONDITION cond=lst_entite->get(i);
1106     BOITE_3D boite_cond=cond->get_boite_3D();
1107     if (boite_cond*root_cellule->boite) root_cellule->lst_entite_CONDITION.ajouter(cond);
1108     }
1109     if (root_cellule->lst_entite_CONDITION.get_nb()>nombre)
1110     {
1111     root_cellule->feuille=0;
1112     double dx=xmax-xmin;
1113     double dy=ymax-ymin;
1114     double dz=zmax-zmin;
1115     root_cellule->fils[0]=cree_fils(xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
1116     root_cellule->fils[1]=cree_fils(xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
1117     root_cellule->fils[2]=cree_fils(xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
1118     root_cellule->fils[3]=cree_fils(xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
1119     root_cellule->fils[4]=cree_fils(xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
1120     root_cellule->fils[5]=cree_fils(xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
1121     root_cellule->fils[6]=cree_fils(xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
1122     root_cellule->fils[7]=cree_fils(xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
1123     }
1124     else root_cellule->feuille=1;
1125     for (int j=0;j<lst_entite_cellule.get_nb();j++)
1126     {
1127     TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=lst_entite_cellule.get(j);
1128     cellule->lst_entite_CONDITION.vide();
1129     }
1130     }
1131    
1132     virtual void initialiser(TPL_MAP_ENTITE<CONDITION>* lst_entite,int nombre,double xmin,double ymin,double zmin,double xmax,double ymax,double zmax)
1133     {
1134     TPL_CELLULE_INFO<A ,CONDITION,B>* root_cellule=new TPL_CELLULE_INFO<A ,CONDITION,B>(xmin,ymin,zmin,xmax,ymax,zmax);
1135     lst_entite_cellule.ajouter(root_cellule);
1136     for (int i=0;i<lst_entite->get_nb();i++)
1137     {
1138     CONDITION cond=lst_entite->get(i);
1139     BOITE_3D boite_cond=cond->get_boite_3D();
1140     if (boite_cond*root_cellule->boite) root_cellule->lst_entite_CONDITION.ajouter(cond);
1141     }
1142     if (root_cellule->lst_entite_CONDITION.get_nb()>nombre)
1143     {
1144     root_cellule->feuille=0;
1145     double dx=xmax-xmin;
1146     double dy=ymax-ymin;
1147     double dz=zmax-zmin;
1148     root_cellule->fils[0]=cree_fils(xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
1149     root_cellule->fils[1]=cree_fils(xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
1150     root_cellule->fils[2]=cree_fils(xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
1151     root_cellule->fils[3]=cree_fils(xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
1152     root_cellule->fils[4]=cree_fils(xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
1153     root_cellule->fils[5]=cree_fils(xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
1154     root_cellule->fils[6]=cree_fils(xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
1155     root_cellule->fils[7]=cree_fils(xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
1156     }
1157     else root_cellule->feuille=1;
1158     for (int j=0;j<lst_entite_cellule.get_nb();j++)
1159     {
1160     TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=lst_entite_cellule.get(j);
1161     cellule->lst_entite_CONDITION.vide();
1162     }
1163     }
1164    
1165     virtual void initialiser(OCTREE_BASE* oc)
1166     {
1167     BOITE_3D boite=oc->get_cellule(0)->get_boite();
1168     double xmin=boite.get_xmin();
1169     double xmax=boite.get_xmax();
1170     double ymin=boite.get_ymin();
1171     double ymax=boite.get_ymax();
1172     double zmin=boite.get_zmin();
1173     double zmax=boite.get_zmax();
1174     TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=new TPL_CELLULE_INFO<A ,CONDITION,B>(xmin,ymin,zmin,xmax,ymax,zmax);
1175     lst_entite_cellule.ajouter(cellule);
1176     if (oc->get_cellule(0)->get_feuille()==0)
1177     {
1178     cellule->fils[0]=cree_fils(oc->get_cellule(0)->get_fils(0));
1179     cellule->fils[1]=cree_fils(oc->get_cellule(0)->get_fils(1));
1180     cellule->fils[2]=cree_fils(oc->get_cellule(0)->get_fils(2));
1181     cellule->fils[3]=cree_fils(oc->get_cellule(0)->get_fils(3));
1182     cellule->fils[4]=cree_fils(oc->get_cellule(0)->get_fils(4));
1183     cellule->fils[5]=cree_fils(oc->get_cellule(0)->get_fils(5));
1184     cellule->fils[6]=cree_fils(oc->get_cellule(0)->get_fils(6));
1185     cellule->fils[7]=cree_fils(oc->get_cellule(0)->get_fils(7));
1186     }
1187     cellule->feuille=oc->get_cellule(0)->get_feuille();
1188     };
1189    
1190    
1191     TPL_CELLULE_INFO<A,CONDITION,B>* cree_fils(CELLULE_OCTREE_BASE *cellule_base)
1192     {
1193     BOITE_3D boite=cellule_base->get_boite();
1194     double xmin=boite.get_xmin();
1195     double xmax=boite.get_xmax();
1196     double ymin=boite.get_ymin();
1197     double ymax=boite.get_ymax();
1198     double zmin=boite.get_zmin();
1199     double zmax=boite.get_zmax();
1200     TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=new TPL_CELLULE_INFO<A ,CONDITION,B>(xmin,ymin,zmin,xmax,ymax,zmax);
1201     lst_entite_cellule.ajouter(cellule);
1202     if (cellule_base->get_feuille()==1)
1203     {
1204     cellule->feuille=1;
1205     }
1206     else
1207     {
1208     cellule->fils[0]=cree_fils(cellule_base->get_fils(0));
1209     cellule->fils[1]=cree_fils(cellule_base->get_fils(1));
1210     cellule->fils[2]=cree_fils(cellule_base->get_fils(2));
1211     cellule->fils[3]=cree_fils(cellule_base->get_fils(3));
1212     cellule->fils[4]=cree_fils(cellule_base->get_fils(4));
1213     cellule->fils[5]=cree_fils(cellule_base->get_fils(5));
1214     cellule->fils[6]=cree_fils(cellule_base->get_fils(6));
1215     cellule->fils[7]=cree_fils(cellule_base->get_fils(7));
1216     cellule->feuille=0;
1217     }
1218     return cellule;
1219     };
1220    
1221     virtual TPL_CELLULE_INFO<A ,CONDITION,B>* cree_fils(double xmin,double ymin,double zmin,double dx,double dy,double dz,TPL_LISTE_ENTITE<CONDITION>* lst_entite,int nombre)
1222     {
1223     TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=new TPL_CELLULE_INFO<A ,CONDITION,B>(xmin,ymin,zmin,xmin+dx,ymin+dy,zmin+dz);
1224     lst_entite_cellule.ajouter(cellule);
1225     for (int i=0;i<lst_entite->get_nb();i++)
1226     {
1227     CONDITION cond=lst_entite->get(i);
1228     BOITE_3D boite_cond=cond->get_boite_3D();
1229     if (boite_cond*cellule->boite) cellule->lst_entite_CONDITION.ajouter(cond);
1230     }
1231     if (cellule->lst_entite_CONDITION.get_nb()>nombre)
1232     {
1233     cellule->feuille=0;
1234     cellule->fils[0]=cree_fils(xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre);
1235     cellule->fils[1]=cree_fils(xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre);
1236     cellule->fils[2]=cree_fils(xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre);
1237     cellule->fils[3]=cree_fils(xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre);
1238     cellule->fils[4]=cree_fils(xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre);
1239     cellule->fils[5]=cree_fils(xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre);
1240     cellule->fils[6]=cree_fils(xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre);
1241     cellule->fils[7]=cree_fils(xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre);
1242     }
1243     else cellule->feuille=1;
1244     return cellule;
1245     }
1246    
1247    
1248     virtual void rechercher(BOITE_3D& boite,TPL_MAP_ENTITE<A>& liste_entite_trouve,TPL_CELLULE_INFO<A ,CONDITION,B>* cellule)
1249     {
1250     if (boite*cellule->boite)
1251     if (cellule->feuille==1)
1252     {
1253     for (int i=0;i<cellule->lst_entite_A.get_nb();i++)
1254     liste_entite_trouve.ajouter(cellule->lst_entite_A.get(i));
1255     }
1256     else
1257     {
1258     rechercher(boite,liste_entite_trouve,cellule->fils[0]);
1259     rechercher(boite,liste_entite_trouve,cellule->fils[1]);
1260     rechercher(boite,liste_entite_trouve,cellule->fils[2]);
1261     rechercher(boite,liste_entite_trouve,cellule->fils[3]);
1262     rechercher(boite,liste_entite_trouve,cellule->fils[4]);
1263     rechercher(boite,liste_entite_trouve,cellule->fils[5]);
1264     rechercher(boite,liste_entite_trouve,cellule->fils[6]);
1265     rechercher(boite,liste_entite_trouve,cellule->fils[7]);
1266     }
1267     };
1268    
1269    
1270     virtual void get_cellule(BOITE_3D& boite,TPL_CELLULE_INFO<A ,CONDITION,B>* cellule,TPL_MAP_ENTITE<TPL_CELLULE_INFO<A ,CONDITION,B> * > &liste_entite)
1271     {
1272     if (boite*cellule->boite)
1273     if (cellule->feuille==1)
1274     {
1275     liste_entite.ajouter(cellule);
1276     }
1277     else
1278     {
1279     get_cellule(boite,cellule->fils[0],liste_entite);
1280     get_cellule(boite,cellule->fils[1],liste_entite);
1281     get_cellule(boite,cellule->fils[2],liste_entite);
1282     get_cellule(boite,cellule->fils[3],liste_entite);
1283     get_cellule(boite,cellule->fils[4],liste_entite);
1284     get_cellule(boite,cellule->fils[5],liste_entite);
1285     get_cellule(boite,cellule->fils[6],liste_entite);
1286     get_cellule(boite,cellule->fils[7],liste_entite);
1287     }
1288     };
1289    
1290     virtual TPL_CELLULE_INFO<A,CONDITION,B> *get_cellule(double x,double y, double z)
1291     {
1292     BOITE_3D boite(x,y,z,x,y,z);
1293     TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=lst_entite_cellule.get(0);
1294     TPL_MAP_ENTITE<TPL_CELLULE_INFO<A ,CONDITION,B> * > liste_cellule;
1295     get_cellule(boite,cellule,liste_cellule);
1296     if (liste_cellule.get_nb()==1) return liste_cellule.get(0);
1297     return NULL;
1298     };
1299    
1300    
1301     virtual void rechercher(double xcentre,double ycentre,double zcentre,double rayon_recherche,TPL_MAP_ENTITE<A>& liste_entite_trouve)
1302     {
1303     BOITE_3D boite(xcentre-rayon_recherche,ycentre-rayon_recherche,zcentre-rayon_recherche,xcentre+rayon_recherche,ycentre+rayon_recherche,zcentre+rayon_recherche);
1304     TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=lst_entite_cellule.get(0);
1305     rechercher(boite,liste_entite_trouve,cellule);
1306     };
1307    
1308    
1309    
1310     virtual void inserer(BOITE_3D& boite,A a,TPL_CELLULE_INFO<A ,CONDITION,B>* cellule)
1311     {
1312     if (boite*cellule->boite)
1313     if (cellule->feuille==1)
1314     {
1315     cellule->lst_entite_A.ajouter(a);
1316     }
1317     else
1318     {
1319     inserer(boite,a,cellule->fils[0]);
1320     inserer(boite,a,cellule->fils[1]);
1321     inserer(boite,a,cellule->fils[2]);
1322     inserer(boite,a,cellule->fils[3]);
1323     inserer(boite,a,cellule->fils[4]);
1324     inserer(boite,a,cellule->fils[5]);
1325     inserer(boite,a,cellule->fils[6]);
1326     inserer(boite,a,cellule->fils[7]);
1327     }
1328     };
1329    
1330     virtual void supprimer(BOITE_3D& boite,A a,TPL_CELLULE_INFO<A ,CONDITION,B>* cellule)
1331     {
1332     if (boite*cellule->boite)
1333     if (cellule->feuille==1)
1334     {
1335     cellule->lst_entite_A.supprimer(a);
1336     }
1337     else
1338     {
1339     supprimer(boite,a,cellule->fils[0]);
1340     supprimer(boite,a,cellule->fils[1]);
1341     supprimer(boite,a,cellule->fils[2]);
1342     supprimer(boite,a,cellule->fils[3]);
1343     supprimer(boite,a,cellule->fils[4]);
1344     supprimer(boite,a,cellule->fils[5]);
1345     supprimer(boite,a,cellule->fils[6]);
1346     supprimer(boite,a,cellule->fils[7]);
1347     }
1348     };
1349    
1350     virtual void inserer(A a)
1351     {
1352     BOITE_3D boite=a->get_boite_3D();
1353     TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=lst_entite_cellule.get(0);
1354     inserer(boite,a,cellule);
1355     }
1356    
1357     virtual void supprimer(A a)
1358     {
1359     BOITE_3D boite=a->get_boite_3D();
1360     TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=lst_entite_cellule.get(0);
1361     supprimer(boite,a,cellule);
1362     }
1363    
1364    
1365     private:
1366     TPL_LISTE_ENTITE<TPL_CELLULE_INFO<A ,CONDITION,B>* > lst_entite_cellule;
1367    
1368     };
1369    
1370    
1371    
1372    
1373     #endif