ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/REPOS_ERICCA/magic/lib/template/src/tpl_quadtree.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: 25048 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     // Jean Christophe Cuillière et Vincent FRANCOIS
5     // Département de Génie Mécanique - UQTR
6     //------------------------------------------------------------
7     // 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     // des auteurs (contact : francois@uqtr.ca)
12     //------------------------------------------------------------
13     //------------------------------------------------------------
14     //
15     // tpl_quadtree.h
16     //
17     //------------------------------------------------------------
18     //------------------------------------------------------------
19     // COPYRIGHT 2000
20     // Version du 02/03/2006 à 11H24
21     //------------------------------------------------------------
22     //------------------------------------------------------------
23     #ifndef _TPLQUADTREE_
24     #define _TPLQUADTREE_
25    
26    
27 francois 481 #include "ot_boite_2d.h"
28 5 #include "tpl_liste_entite.h"
29     #include "tpl_map_entite.h"
30    
31    
32     class CELLULE_QUADTREE_BASE
33     {
34     public:
35     CELLULE_QUADTREE_BASE() {};
36     virtual ~CELLULE_QUADTREE_BASE() {};
37     virtual BOITE_2D get_boite(void)=0;
38     virtual CELLULE_QUADTREE_BASE* get_fils(int num)=0;
39     virtual int get_feuille(void)=0;
40     };
41    
42    
43     class QUADTREE_BASE
44     {
45     public:
46     QUADTREE_BASE() {};
47     virtual ~QUADTREE_BASE() {};
48     virtual int get_nb_cellule(void)=0;
49     virtual CELLULE_QUADTREE_BASE* get_cellule(int num)=0;
50     double periode_u;
51 francois 632 double periode_v;
52     bool est_periodique_u;
53     bool est_periodique_v;
54 5 };
55    
56    
57     template <class A,class CONDITION>
58     class TPL_CELLULE_QUADTREE:public CELLULE_QUADTREE_BASE
59     {
60     public:
61     TPL_CELLULE_QUADTREE(double xmin,double ymin,double xmax,double ymax):boite(xmin,ymin,xmax,ymax)
62     {
63     };
64     virtual ~TPL_CELLULE_QUADTREE() {};
65     BOITE_2D get_boite(void) {return boite;};
66     BOITE_2D boite;
67     int feuille;
68     TPL_CELLULE_QUADTREE< A ,CONDITION> *fils[4];
69     TPL_LISTE_ENTITE<CONDITION> lst_entite_CONDITION;
70     TPL_LISTE_ENTITE<A> lst_entite_A;
71     virtual TPL_CELLULE_QUADTREE<A,CONDITION>* get_fils(int num) {return fils[num];};
72     virtual int get_feuille(void) {return feuille;};
73     };
74    
75    
76    
77     template <class A,class CONDITION>
78     class TPL_QUADTREE:public QUADTREE_BASE
79     {
80     public:
81     TPL_QUADTREE() {};
82     ~TPL_QUADTREE()
83     {
84     for (int i1=0;i1<lst_entite_cellule.get_nb();i1++)
85     {
86     TPL_CELLULE_QUADTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(i1);
87     delete cellule;
88     }
89     };
90    
91     virtual int get_nb_cellule(void) {return lst_entite_cellule.get_nb();};
92    
93    
94    
95     virtual TPL_CELLULE_QUADTREE<A,CONDITION>* get_cellule(int num) {return lst_entite_cellule.get(num); };
96    
97    
98 francois 632 virtual void initialiser(TPL_LISTE_ENTITE<CONDITION>* lst_entite,int nombre,double xmin,double ymin,double xmax,double ymax,bool estu,bool estv,double periodeu,double periodev)
99 5 {
100     periode_u=periodeu;
101     periode_v=periodev;
102 francois 632 est_periodique_u=estu;
103     est_periodique_v=estv;
104     if (est_periodique_u) {xmin=0.;xmax=periode_u;}
105     if (est_periodique_v) {ymin=0.;ymax=periode_v;}
106 5 TPL_CELLULE_QUADTREE<A ,CONDITION>* root_cellule=new TPL_CELLULE_QUADTREE<A ,CONDITION>(xmin,ymin,xmax,ymax);
107     lst_entite_cellule.ajouter(root_cellule);
108     for (int i=0;i<lst_entite->get_nb();i++)
109     {
110     CONDITION cond=lst_entite->get(i);
111     BOITE_2D boite_cond=cond->get_boite_2D(periode_u,periode_v);
112     if (boite_cond*root_cellule->boite) root_cellule->lst_entite_CONDITION.ajouter(cond);
113     }
114     if (root_cellule->lst_entite_CONDITION.get_nb()>nombre)
115     {
116     root_cellule->feuille=0;
117     double dx=xmax-xmin;
118     double dy=ymax-ymin;
119     root_cellule->fils[0]=cree_fils(xmin,ymin,dx/2.,dy/2.,&(root_cellule->lst_entite_CONDITION),nombre);
120     root_cellule->fils[1]=cree_fils(xmin+dx/2.,ymin,dx/2.,dy/2.,&(root_cellule->lst_entite_CONDITION),nombre);
121     root_cellule->fils[2]=cree_fils(xmin,ymin+dy/2.,dx/2.,dy/2.,&(root_cellule->lst_entite_CONDITION),nombre);
122     root_cellule->fils[3]=cree_fils(xmin+dx/2.,ymin+dy/2.,dx/2.,dy/2.,&(root_cellule->lst_entite_CONDITION),nombre);
123     }
124     else root_cellule->feuille=1;
125     for (int j=0;j<lst_entite_cellule.get_nb();j++)
126     {
127     TPL_CELLULE_QUADTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(j);
128     cellule->lst_entite_CONDITION.vide();
129     }
130 francois 632 };
131 5
132     virtual void initialiser(QUADTREE_BASE* quad)
133     {
134     BOITE_2D boite=quad->get_cellule(0)->get_boite();
135     double xmin=boite.get_xmin();
136     double xmax=boite.get_xmax();
137     double ymin=boite.get_ymin();
138     double ymax=boite.get_ymax();
139     TPL_CELLULE_QUADTREE<A ,CONDITION>* cellule=new TPL_CELLULE_QUADTREE<A ,CONDITION>(xmin,ymin,xmax,ymax);
140     lst_entite_cellule.ajouter(cellule);
141     if (quad->get_cellule(0)->get_feuille()==0)
142     {
143     cellule->fils[0]=cree_fils(quad->get_cellule(0)->get_fils(0));
144     cellule->fils[1]=cree_fils(quad->get_cellule(0)->get_fils(1));
145     cellule->fils[2]=cree_fils(quad->get_cellule(0)->get_fils(2));
146     cellule->fils[3]=cree_fils(quad->get_cellule(0)->get_fils(3));
147     }
148     cellule->feuille=quad->get_cellule(0)->get_feuille();
149     periode_u=quad->periode_u;
150     periode_v=quad->periode_v;
151 francois 632 est_periodique_u=quad->est_periodique_u;
152     est_periodique_v=quad->est_periodique_v;
153 5 };
154    
155    
156     TPL_CELLULE_QUADTREE<A,CONDITION>* cree_fils(CELLULE_QUADTREE_BASE *cellule_base)
157     {
158     BOITE_2D boite=cellule_base->get_boite();
159     double xmin=boite.get_xmin();
160     double xmax=boite.get_xmax();
161     double ymin=boite.get_ymin();
162     double ymax=boite.get_ymax();
163     TPL_CELLULE_QUADTREE<A ,CONDITION>* cellule=new TPL_CELLULE_QUADTREE<A ,CONDITION>(xmin,ymin,xmax,ymax);
164     lst_entite_cellule.ajouter(cellule);
165     if (cellule_base->get_feuille()==1)
166     {
167     cellule->feuille=1;
168     }
169     else
170     {
171     cellule->fils[0]=cree_fils(cellule_base->get_fils(0));
172     cellule->fils[1]=cree_fils(cellule_base->get_fils(1));
173     cellule->fils[2]=cree_fils(cellule_base->get_fils(2));
174     cellule->fils[3]=cree_fils(cellule_base->get_fils(3));
175     cellule->feuille=0;
176     }
177     return cellule;
178     };
179    
180     virtual TPL_CELLULE_QUADTREE<A ,CONDITION>* cree_fils(double xmin,double ymin,double dx,double dy,TPL_LISTE_ENTITE<CONDITION>* lst_entite,int nombre)
181     {
182     TPL_CELLULE_QUADTREE<A ,CONDITION>* cellule=new TPL_CELLULE_QUADTREE<A ,CONDITION>(xmin,ymin,xmin+dx,ymin+dy);
183     lst_entite_cellule.ajouter(cellule);
184     for (int i=0;i<lst_entite->get_nb();i++)
185     {
186     CONDITION cond=lst_entite->get(i);
187     BOITE_2D boite_cond=cond->get_boite_2D(periode_u,periode_v);
188     if (boite_cond*cellule->boite) cellule->lst_entite_CONDITION.ajouter(cond);
189     }
190     if (cellule->lst_entite_CONDITION.get_nb()>nombre)
191     {
192     cellule->feuille=0;
193     cellule->fils[0]=cree_fils(xmin,ymin,dx/2.,dy/2.,&(cellule->lst_entite_CONDITION),nombre);
194     cellule->fils[1]=cree_fils(xmin+dx/2.,ymin,dx/2.,dy/2.,&(cellule->lst_entite_CONDITION),nombre);
195     cellule->fils[2]=cree_fils(xmin,ymin+dy/2.,dx/2.,dy/2.,&(cellule->lst_entite_CONDITION),nombre);
196     cellule->fils[3]=cree_fils(xmin+dx/2.,ymin+dy/2.,dx/2.,dy/2.,&(cellule->lst_entite_CONDITION),nombre);
197     }
198     else cellule->feuille=1;
199     return cellule;
200 francois 632 };
201 5
202    
203     virtual void rechercher(BOITE_2D& boite,TPL_MAP_ENTITE<A>& liste_entite_trouve,TPL_CELLULE_QUADTREE<A ,CONDITION>* cellule)
204     {
205     if (boite*cellule->boite)
206     if (cellule->feuille==1)
207     {
208     for (int i=0;i<cellule->lst_entite_A.get_nb();i++)
209     liste_entite_trouve.ajouter(cellule->lst_entite_A.get(i));
210     }
211     else
212     {
213     rechercher(boite,liste_entite_trouve,cellule->fils[0]);
214     rechercher(boite,liste_entite_trouve,cellule->fils[1]);
215     rechercher(boite,liste_entite_trouve,cellule->fils[2]);
216     rechercher(boite,liste_entite_trouve,cellule->fils[3]);
217     }
218     };
219    
220     virtual void rechercher(double xcentre,double ycentre,double rayon_recherche,TPL_MAP_ENTITE<A>& liste_entite_trouve)
221     {
222     BOITE_2D boite(xcentre-rayon_recherche,ycentre-rayon_recherche,xcentre+rayon_recherche,ycentre+rayon_recherche);
223     TPL_CELLULE_QUADTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(0);
224    
225 francois 632 if ((!est_periodique_u)&&(!est_periodique_v))
226 5 {
227     rechercher(boite,liste_entite_trouve,cellule);
228     return;
229     }
230 francois 632 if ((est_periodique_u)&&(!est_periodique_v))
231 5 {
232     if ((boite.get_xmin()>=0.) && (boite.get_xmax()<periode_u))
233     {
234     rechercher(boite,liste_entite_trouve,cellule);
235     return;
236     }
237     if (boite.get_xmin()<0.)
238     {
239     BOITE_2D boite1(0.,boite.get_ymin(),boite.get_xmax(),boite.get_ymax());
240     BOITE_2D boite2(boite.get_xmin()+periode_u,boite.get_ymin(),periode_u,boite.get_ymax());
241     rechercher(boite1,liste_entite_trouve,cellule);
242     rechercher(boite2,liste_entite_trouve,cellule);
243 francois 632 return;
244 5 }
245     if (boite.get_xmax()>=periode_u)
246     {
247     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),periode_u,boite.get_ymax());
248     BOITE_2D boite2(0.,boite.get_ymin(),boite.get_xmax()-periode_u,boite.get_ymax());
249     rechercher(boite1,liste_entite_trouve,cellule);
250     rechercher(boite2,liste_entite_trouve,cellule);
251     return;
252     }
253     }
254 francois 632 if ((!est_periodique_u)&&(est_periodique_v))
255 5 {
256     if ((boite.get_ymin()>=0.) && (boite.get_ymax()<periode_v))
257     {
258     rechercher(boite,liste_entite_trouve,cellule);
259     return;
260     }
261     if (boite.get_ymin()<0.)
262     {
263     BOITE_2D boite1(boite.get_xmin(),0.,boite.get_xmax(),boite.get_ymax());
264     BOITE_2D boite2(boite.get_xmin(),boite.get_ymin()+periode_v,boite.get_xmax(),periode_v);
265     rechercher(boite1,liste_entite_trouve,cellule);
266     rechercher(boite2,liste_entite_trouve,cellule);
267     return;
268     }
269     if (boite.get_ymax()>=periode_v)
270     {
271     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),boite.get_xmax(),periode_v);
272     BOITE_2D boite2(boite.get_xmin(),0.,boite.get_xmax(),boite.get_ymax()-periode_v);
273     rechercher(boite1,liste_entite_trouve,cellule);
274     rechercher(boite2,liste_entite_trouve,cellule);
275     return;
276     }
277     }
278 francois 632 if ((est_periodique_u)&&(est_periodique_v))
279 5 {
280     if ((boite.get_xmin()>=0.) && (boite.get_xmax()<periode_u) && (boite.get_ymin()>=0.) && (boite.get_ymax()<periode_v))
281     {
282     rechercher(boite,liste_entite_trouve,cellule);
283     return;
284     }
285     if ((boite.get_xmin()<0.)&&(boite.get_ymin()<0.))
286     {
287     BOITE_2D boite1(0.,0.,boite.get_xmax(),boite.get_ymax());
288     BOITE_2D boite2(boite.get_xmin()+periode_u,0.,periode_u,boite.get_ymax());
289     BOITE_2D boite3(0.,boite.get_ymin()+periode_v,boite.get_xmax(),periode_v);
290     BOITE_2D boite4(boite.get_xmin()+periode_u,boite.get_ymin()+periode_v,periode_u,periode_v);
291     rechercher(boite1,liste_entite_trouve,cellule);
292     rechercher(boite2,liste_entite_trouve,cellule);
293     rechercher(boite3,liste_entite_trouve,cellule);
294     rechercher(boite4,liste_entite_trouve,cellule);
295     return;
296     }
297     if ((boite.get_xmin()<0.)&&(boite.get_ymax()>=periode_v))
298     {
299     BOITE_2D boite1(0.,boite.get_ymin(),boite.get_xmax(),periode_v );
300     BOITE_2D boite2(0.,0.,boite.get_xmax(),boite.get_ymax()-periode_v );
301     BOITE_2D boite3(boite.get_xmin()+periode_u,0.,periode_u,boite.get_ymax()-periode_v );
302     BOITE_2D boite4(boite.get_xmin()+periode_u,boite.get_ymin(),periode_u,periode_v );
303     rechercher(boite1,liste_entite_trouve,cellule);
304     rechercher(boite2,liste_entite_trouve,cellule);
305     rechercher(boite3,liste_entite_trouve,cellule);
306     rechercher(boite4,liste_entite_trouve,cellule);
307     return;
308     }
309     if ((boite.get_xmax()>=periode_u)&&(boite.get_ymax()>=periode_v))
310     {
311     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),periode_u,periode_v );
312     BOITE_2D boite2(0.,boite.get_ymin(),boite.get_xmax()-periode_u,periode_v );
313     BOITE_2D boite3(0.,0.,boite.get_xmax()-periode_u,boite.get_ymax()-periode_v );
314     BOITE_2D boite4(boite.get_xmin(),0.,periode_u,boite.get_ymax()-periode_v );
315     rechercher(boite1,liste_entite_trouve,cellule);
316     rechercher(boite2,liste_entite_trouve,cellule);
317     rechercher(boite3,liste_entite_trouve,cellule);
318     rechercher(boite4,liste_entite_trouve,cellule);
319     return;
320     }
321     if ((boite.get_xmax()>=periode_u)&&(boite.get_ymin()<0.))
322     {
323     BOITE_2D boite1(boite.get_xmin(),0.,periode_u,boite.get_ymax() );
324     BOITE_2D boite2(0.,0.,boite.get_xmax()-periode_u,boite.get_ymax() );
325     BOITE_2D boite3(0.,boite.get_ymin()+periode_v,boite.get_xmax()-periode_u,periode_v );
326     BOITE_2D boite4(boite.get_xmin(),boite.get_ymin()+periode_v,periode_u,periode_v );
327     rechercher(boite1,liste_entite_trouve,cellule);
328     rechercher(boite2,liste_entite_trouve,cellule);
329     rechercher(boite3,liste_entite_trouve,cellule);
330     rechercher(boite4,liste_entite_trouve,cellule);
331     return;
332     }
333     if (boite.get_xmin()<0.)
334     {
335     BOITE_2D boite1(0.,boite.get_ymin(),boite.get_xmax(),boite.get_ymax() );
336     BOITE_2D boite2(boite.get_xmin()+periode_u,boite.get_ymin(),periode_u,boite.get_ymax() );
337     rechercher(boite1,liste_entite_trouve,cellule);
338     rechercher(boite2,liste_entite_trouve,cellule);
339     return;
340     }
341     if (boite.get_ymin()<0.)
342     {
343     BOITE_2D boite1(boite.get_xmin(),0.,boite.get_xmax(),boite.get_ymax() );
344     BOITE_2D boite2(boite.get_xmin(),boite.get_ymin()+periode_v,boite.get_xmax(),periode_v );
345     rechercher(boite1,liste_entite_trouve,cellule);
346     rechercher(boite2,liste_entite_trouve,cellule);
347     return;
348     }
349     if (boite.get_xmax()>=periode_u)
350     {
351     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),periode_u,boite.get_ymax() );
352     BOITE_2D boite2(0.,boite.get_ymin(),boite.get_xmax()-periode_u,boite.get_ymax() );
353     rechercher(boite1,liste_entite_trouve,cellule);
354     rechercher(boite2,liste_entite_trouve,cellule);
355     return;
356     }
357     if (boite.get_ymax()>=periode_v)
358     {
359     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),boite.get_xmax(),periode_v );
360     BOITE_2D boite2(boite.get_xmin(),0.,boite.get_xmax(),boite.get_ymax()-periode_v );
361     rechercher(boite1,liste_entite_trouve,cellule);
362     rechercher(boite2,liste_entite_trouve,cellule);
363     return;
364     }
365    
366     }
367     };
368    
369    
370    
371     virtual void inserer(BOITE_2D& boite,A a,TPL_CELLULE_QUADTREE<A ,CONDITION>* cellule)
372     {
373     if (boite*cellule->boite)
374     if (cellule->feuille==1)
375     {
376     cellule->lst_entite_A.ajouter(a);
377     }
378     else
379     {
380     inserer(boite,a,cellule->fils[0]);
381     inserer(boite,a,cellule->fils[1]);
382     inserer(boite,a,cellule->fils[2]);
383     inserer(boite,a,cellule->fils[3]);
384     }
385     };
386    
387     virtual void supprimer(BOITE_2D& boite,A a,TPL_CELLULE_QUADTREE<A ,CONDITION>* cellule)
388     {
389     if (boite*cellule->boite)
390     if (cellule->feuille==1)
391     {
392     cellule->lst_entite_A.supprimer(a);
393     }
394     else
395     {
396     supprimer(boite,a,cellule->fils[0]);
397     supprimer(boite,a,cellule->fils[1]);
398     supprimer(boite,a,cellule->fils[2]);
399     supprimer(boite,a,cellule->fils[3]);
400     }
401     };
402    
403     virtual void inserer(A a)
404     {
405     parcourir(a,1);
406 francois 632 };
407 5
408     virtual void supprimer(A a)
409     {
410     parcourir(a,0);
411 francois 632 };
412 5
413     virtual void parcourir(A a,int num)
414     {
415     BOITE_2D boite=a->get_boite_2D(periode_u,periode_v);
416     TPL_CELLULE_QUADTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(0);
417    
418 francois 632 if ((!est_periodique_u)&&(!est_periodique_v))
419 5 {
420     if (num==1) inserer(boite,a,cellule); else supprimer(boite,a,cellule);
421     return;
422     }
423 francois 632 if ((est_periodique_u)&&(!est_periodique_v))
424 5 {
425     if ((boite.get_xmin()>=0.) && (boite.get_xmax()<periode_u))
426     {
427     if (num==1) inserer(boite,a,cellule); else supprimer(boite,a,cellule);
428     return;
429     }
430     if (boite.get_xmin()<0.)
431     {
432     BOITE_2D boite1(0.,boite.get_ymin(),boite.get_xmax(),boite.get_ymax());
433     BOITE_2D boite2(boite.get_xmin()+periode_u,boite.get_ymin(),periode_u,boite.get_ymax());
434     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
435     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
436 francois 632 return;
437 5 }
438     if (boite.get_xmax()>=periode_u)
439     {
440     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),periode_u,boite.get_ymax());
441     BOITE_2D boite2(0.,boite.get_ymin(),boite.get_xmax()-periode_u,boite.get_ymax());
442     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
443     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
444     return;
445     }
446     }
447 francois 632 if ((!est_periodique_u)&&(est_periodique_v))
448 5 {
449     if ((boite.get_ymin()>=0.) && (boite.get_ymax()<periode_v))
450     {
451     if (num==1) inserer(boite,a,cellule); else supprimer(boite,a,cellule);
452     return;
453     }
454     if (boite.get_ymin()<0.)
455     {
456     BOITE_2D boite1(boite.get_xmin(),0.,boite.get_xmax(),boite.get_ymax());
457     BOITE_2D boite2(boite.get_xmin(),boite.get_ymin()+periode_v,boite.get_xmax(),periode_v);
458     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
459     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
460     return;
461     }
462     if (boite.get_ymax()>=periode_v)
463     {
464     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),boite.get_xmax(),periode_v);
465     BOITE_2D boite2(boite.get_xmin(),0.,boite.get_xmax(),boite.get_ymax()-periode_v);
466     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
467     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
468     return;
469     }
470     }
471 francois 632 if ((est_periodique_u)&&(est_periodique_v))
472 5 {
473     if ((boite.get_xmin()>=0.) && (boite.get_xmax()<periode_u) && (boite.get_ymin()>=0.) && (boite.get_ymax()<periode_v))
474     {
475     if (num==1) inserer(boite,a,cellule); else supprimer(boite,a,cellule);
476     return;
477     }
478     if ((boite.get_xmin()<0.)&&(boite.get_ymin()<0.))
479     {
480     BOITE_2D boite1(0.,0.,boite.get_xmax(),boite.get_ymax());
481     BOITE_2D boite2(boite.get_xmin()+periode_u,0.,periode_u,boite.get_ymax());
482     BOITE_2D boite3(0.,boite.get_ymin()+periode_v,boite.get_xmax(),periode_v);
483     BOITE_2D boite4(boite.get_xmin()+periode_u,boite.get_ymin()+periode_v,periode_u,periode_v);
484     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
485     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
486     if (num==1) inserer(boite3,a,cellule); else supprimer(boite3,a,cellule);
487     if (num==1) inserer(boite4,a,cellule); else supprimer(boite4,a,cellule);
488     return;
489     }
490     if ((boite.get_xmin()<0.)&&(boite.get_ymax()>=periode_v))
491     {
492     BOITE_2D boite1(0.,boite.get_ymin(),boite.get_xmax(),periode_v );
493     BOITE_2D boite2(0.,0.,boite.get_xmax(),boite.get_ymax()-periode_v );
494     BOITE_2D boite3(boite.get_xmin()+periode_u,0.,periode_u,boite.get_ymax()-periode_v );
495     BOITE_2D boite4(boite.get_xmin()+periode_u,boite.get_ymin(),periode_u,periode_v );
496     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
497     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
498     if (num==1) inserer(boite3,a,cellule); else supprimer(boite3,a,cellule);
499     if (num==1) inserer(boite4,a,cellule); else supprimer(boite4,a,cellule);
500     return;
501     }
502     if ((boite.get_xmax()>=periode_u)&&(boite.get_ymax()>=periode_v))
503     {
504     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),periode_u,periode_v );
505     BOITE_2D boite2(0.,boite.get_ymin(),boite.get_xmax()-periode_u,periode_v );
506     BOITE_2D boite3(0.,0.,boite.get_xmax()-periode_u,boite.get_ymax()-periode_v );
507     BOITE_2D boite4(boite.get_xmin(),0.,periode_u,boite.get_ymax()-periode_v );
508     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
509     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
510     if (num==1) inserer(boite3,a,cellule); else supprimer(boite3,a,cellule);
511     if (num==1) inserer(boite4,a,cellule); else supprimer(boite4,a,cellule);
512     return;
513     }
514     if ((boite.get_xmax()>=periode_u)&&(boite.get_ymin()<0.))
515     {
516     BOITE_2D boite1(boite.get_xmin(),0.,periode_u,boite.get_ymax() );
517     BOITE_2D boite2(0.,0.,boite.get_xmax()-periode_u,boite.get_ymax() );
518     BOITE_2D boite3(0.,boite.get_ymin()+periode_v,boite.get_xmax()-periode_u,periode_v );
519     BOITE_2D boite4(boite.get_xmin(),boite.get_ymin()+periode_v,periode_u,periode_v );
520     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
521     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
522     if (num==1) inserer(boite3,a,cellule); else supprimer(boite3,a,cellule);
523     if (num==1) inserer(boite4,a,cellule); else supprimer(boite4,a,cellule);
524     return;
525     }
526     if (boite.get_xmin()<0.)
527     {
528     BOITE_2D boite1(0.,boite.get_ymin(),boite.get_xmax(),boite.get_ymax() );
529     BOITE_2D boite2(boite.get_xmin()+periode_u,boite.get_ymin(),periode_u,boite.get_ymax() );
530     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
531     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
532     return;
533     }
534     if (boite.get_ymin()<0.)
535     {
536     BOITE_2D boite1(boite.get_xmin(),0.,boite.get_xmax(),boite.get_ymax() );
537     BOITE_2D boite2(boite.get_xmin(),boite.get_ymin()+periode_v,boite.get_xmax(),periode_v );
538     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
539     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
540     return;
541     }
542     if (boite.get_xmax()>=periode_u)
543     {
544     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),periode_u,boite.get_ymax() );
545     BOITE_2D boite2(0.,boite.get_ymin(),boite.get_xmax(),boite.get_ymax() );
546     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
547     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
548     return;
549     }
550     if (boite.get_ymax()>=periode_v)
551     {
552     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),boite.get_xmax(),periode_v );
553     BOITE_2D boite2(boite.get_xmin(),0.,boite.get_xmax(),boite.get_ymax()-periode_v );
554     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
555     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
556     return;
557     }
558    
559     }
560    
561     };
562    
563 francois 632 protected:
564 5 TPL_LISTE_ENTITE<TPL_CELLULE_QUADTREE<A ,CONDITION>* > lst_entite_cellule;
565    
566     };
567    
568    
569    
570    
571     #endif