ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/REPOS_ERICCA/magic/lib/template/src/tpl_quadtree.h
Revision: 253
Committed: Tue Jul 13 19:40:46 2010 UTC (14 years, 10 months ago) by francois
Content type: text/plain
File size: 24756 byte(s)
Log Message: 
changement de hiearchie et utilisation de ccmake + mise a jour

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