ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/REPOS_ERICCA/magic/lib/template/src/tpl_quadtree.h
Revision: 945
Committed: Tue Jun 12 19:03:38 2018 UTC (6 years, 11 months ago) by francois
Content type: text/plain
File size: 25164 byte(s)
Log Message: 
optimisation de la recherche dans les grilles, quadtree et octree

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 francois 945 {
210     BOITE_2D boiteentite=cellule->lst_entite_A.get(i)->get_boite_2D(0.,0.);
211     if (boite*boiteentite)
212     liste_entite_trouve.ajouter(cellule->lst_entite_A.get(i));
213     }
214 5 }
215     else
216     {
217     rechercher(boite,liste_entite_trouve,cellule->fils[0]);
218     rechercher(boite,liste_entite_trouve,cellule->fils[1]);
219     rechercher(boite,liste_entite_trouve,cellule->fils[2]);
220     rechercher(boite,liste_entite_trouve,cellule->fils[3]);
221     }
222     };
223    
224     virtual void rechercher(double xcentre,double ycentre,double rayon_recherche,TPL_MAP_ENTITE<A>& liste_entite_trouve)
225     {
226     BOITE_2D boite(xcentre-rayon_recherche,ycentre-rayon_recherche,xcentre+rayon_recherche,ycentre+rayon_recherche);
227     TPL_CELLULE_QUADTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(0);
228    
229 francois 632 if ((!est_periodique_u)&&(!est_periodique_v))
230 5 {
231     rechercher(boite,liste_entite_trouve,cellule);
232     return;
233     }
234 francois 632 if ((est_periodique_u)&&(!est_periodique_v))
235 5 {
236     if ((boite.get_xmin()>=0.) && (boite.get_xmax()<periode_u))
237     {
238     rechercher(boite,liste_entite_trouve,cellule);
239     return;
240     }
241     if (boite.get_xmin()<0.)
242     {
243     BOITE_2D boite1(0.,boite.get_ymin(),boite.get_xmax(),boite.get_ymax());
244     BOITE_2D boite2(boite.get_xmin()+periode_u,boite.get_ymin(),periode_u,boite.get_ymax());
245     rechercher(boite1,liste_entite_trouve,cellule);
246     rechercher(boite2,liste_entite_trouve,cellule);
247 francois 632 return;
248 5 }
249     if (boite.get_xmax()>=periode_u)
250     {
251     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),periode_u,boite.get_ymax());
252     BOITE_2D boite2(0.,boite.get_ymin(),boite.get_xmax()-periode_u,boite.get_ymax());
253     rechercher(boite1,liste_entite_trouve,cellule);
254     rechercher(boite2,liste_entite_trouve,cellule);
255     return;
256     }
257     }
258 francois 632 if ((!est_periodique_u)&&(est_periodique_v))
259 5 {
260     if ((boite.get_ymin()>=0.) && (boite.get_ymax()<periode_v))
261     {
262     rechercher(boite,liste_entite_trouve,cellule);
263     return;
264     }
265     if (boite.get_ymin()<0.)
266     {
267     BOITE_2D boite1(boite.get_xmin(),0.,boite.get_xmax(),boite.get_ymax());
268     BOITE_2D boite2(boite.get_xmin(),boite.get_ymin()+periode_v,boite.get_xmax(),periode_v);
269     rechercher(boite1,liste_entite_trouve,cellule);
270     rechercher(boite2,liste_entite_trouve,cellule);
271     return;
272     }
273     if (boite.get_ymax()>=periode_v)
274     {
275     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),boite.get_xmax(),periode_v);
276     BOITE_2D boite2(boite.get_xmin(),0.,boite.get_xmax(),boite.get_ymax()-periode_v);
277     rechercher(boite1,liste_entite_trouve,cellule);
278     rechercher(boite2,liste_entite_trouve,cellule);
279     return;
280     }
281     }
282 francois 632 if ((est_periodique_u)&&(est_periodique_v))
283 5 {
284     if ((boite.get_xmin()>=0.) && (boite.get_xmax()<periode_u) && (boite.get_ymin()>=0.) && (boite.get_ymax()<periode_v))
285     {
286     rechercher(boite,liste_entite_trouve,cellule);
287     return;
288     }
289     if ((boite.get_xmin()<0.)&&(boite.get_ymin()<0.))
290     {
291     BOITE_2D boite1(0.,0.,boite.get_xmax(),boite.get_ymax());
292     BOITE_2D boite2(boite.get_xmin()+periode_u,0.,periode_u,boite.get_ymax());
293     BOITE_2D boite3(0.,boite.get_ymin()+periode_v,boite.get_xmax(),periode_v);
294     BOITE_2D boite4(boite.get_xmin()+periode_u,boite.get_ymin()+periode_v,periode_u,periode_v);
295     rechercher(boite1,liste_entite_trouve,cellule);
296     rechercher(boite2,liste_entite_trouve,cellule);
297     rechercher(boite3,liste_entite_trouve,cellule);
298     rechercher(boite4,liste_entite_trouve,cellule);
299     return;
300     }
301     if ((boite.get_xmin()<0.)&&(boite.get_ymax()>=periode_v))
302     {
303     BOITE_2D boite1(0.,boite.get_ymin(),boite.get_xmax(),periode_v );
304     BOITE_2D boite2(0.,0.,boite.get_xmax(),boite.get_ymax()-periode_v );
305     BOITE_2D boite3(boite.get_xmin()+periode_u,0.,periode_u,boite.get_ymax()-periode_v );
306     BOITE_2D boite4(boite.get_xmin()+periode_u,boite.get_ymin(),periode_u,periode_v );
307     rechercher(boite1,liste_entite_trouve,cellule);
308     rechercher(boite2,liste_entite_trouve,cellule);
309     rechercher(boite3,liste_entite_trouve,cellule);
310     rechercher(boite4,liste_entite_trouve,cellule);
311     return;
312     }
313     if ((boite.get_xmax()>=periode_u)&&(boite.get_ymax()>=periode_v))
314     {
315     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),periode_u,periode_v );
316     BOITE_2D boite2(0.,boite.get_ymin(),boite.get_xmax()-periode_u,periode_v );
317     BOITE_2D boite3(0.,0.,boite.get_xmax()-periode_u,boite.get_ymax()-periode_v );
318     BOITE_2D boite4(boite.get_xmin(),0.,periode_u,boite.get_ymax()-periode_v );
319     rechercher(boite1,liste_entite_trouve,cellule);
320     rechercher(boite2,liste_entite_trouve,cellule);
321     rechercher(boite3,liste_entite_trouve,cellule);
322     rechercher(boite4,liste_entite_trouve,cellule);
323     return;
324     }
325     if ((boite.get_xmax()>=periode_u)&&(boite.get_ymin()<0.))
326     {
327     BOITE_2D boite1(boite.get_xmin(),0.,periode_u,boite.get_ymax() );
328     BOITE_2D boite2(0.,0.,boite.get_xmax()-periode_u,boite.get_ymax() );
329     BOITE_2D boite3(0.,boite.get_ymin()+periode_v,boite.get_xmax()-periode_u,periode_v );
330     BOITE_2D boite4(boite.get_xmin(),boite.get_ymin()+periode_v,periode_u,periode_v );
331     rechercher(boite1,liste_entite_trouve,cellule);
332     rechercher(boite2,liste_entite_trouve,cellule);
333     rechercher(boite3,liste_entite_trouve,cellule);
334     rechercher(boite4,liste_entite_trouve,cellule);
335     return;
336     }
337     if (boite.get_xmin()<0.)
338     {
339     BOITE_2D boite1(0.,boite.get_ymin(),boite.get_xmax(),boite.get_ymax() );
340     BOITE_2D boite2(boite.get_xmin()+periode_u,boite.get_ymin(),periode_u,boite.get_ymax() );
341     rechercher(boite1,liste_entite_trouve,cellule);
342     rechercher(boite2,liste_entite_trouve,cellule);
343     return;
344     }
345     if (boite.get_ymin()<0.)
346     {
347     BOITE_2D boite1(boite.get_xmin(),0.,boite.get_xmax(),boite.get_ymax() );
348     BOITE_2D boite2(boite.get_xmin(),boite.get_ymin()+periode_v,boite.get_xmax(),periode_v );
349     rechercher(boite1,liste_entite_trouve,cellule);
350     rechercher(boite2,liste_entite_trouve,cellule);
351     return;
352     }
353     if (boite.get_xmax()>=periode_u)
354     {
355     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),periode_u,boite.get_ymax() );
356     BOITE_2D boite2(0.,boite.get_ymin(),boite.get_xmax()-periode_u,boite.get_ymax() );
357     rechercher(boite1,liste_entite_trouve,cellule);
358     rechercher(boite2,liste_entite_trouve,cellule);
359     return;
360     }
361     if (boite.get_ymax()>=periode_v)
362     {
363     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),boite.get_xmax(),periode_v );
364     BOITE_2D boite2(boite.get_xmin(),0.,boite.get_xmax(),boite.get_ymax()-periode_v );
365     rechercher(boite1,liste_entite_trouve,cellule);
366     rechercher(boite2,liste_entite_trouve,cellule);
367     return;
368     }
369    
370     }
371     };
372    
373    
374    
375     virtual void inserer(BOITE_2D& boite,A a,TPL_CELLULE_QUADTREE<A ,CONDITION>* cellule)
376     {
377     if (boite*cellule->boite)
378     if (cellule->feuille==1)
379     {
380     cellule->lst_entite_A.ajouter(a);
381     }
382     else
383     {
384     inserer(boite,a,cellule->fils[0]);
385     inserer(boite,a,cellule->fils[1]);
386     inserer(boite,a,cellule->fils[2]);
387     inserer(boite,a,cellule->fils[3]);
388     }
389     };
390    
391     virtual void supprimer(BOITE_2D& boite,A a,TPL_CELLULE_QUADTREE<A ,CONDITION>* cellule)
392     {
393     if (boite*cellule->boite)
394     if (cellule->feuille==1)
395     {
396     cellule->lst_entite_A.supprimer(a);
397     }
398     else
399     {
400     supprimer(boite,a,cellule->fils[0]);
401     supprimer(boite,a,cellule->fils[1]);
402     supprimer(boite,a,cellule->fils[2]);
403     supprimer(boite,a,cellule->fils[3]);
404     }
405     };
406    
407     virtual void inserer(A a)
408     {
409     parcourir(a,1);
410 francois 632 };
411 5
412     virtual void supprimer(A a)
413     {
414     parcourir(a,0);
415 francois 632 };
416 5
417     virtual void parcourir(A a,int num)
418     {
419     BOITE_2D boite=a->get_boite_2D(periode_u,periode_v);
420     TPL_CELLULE_QUADTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(0);
421    
422 francois 632 if ((!est_periodique_u)&&(!est_periodique_v))
423 5 {
424     if (num==1) inserer(boite,a,cellule); else supprimer(boite,a,cellule);
425     return;
426     }
427 francois 632 if ((est_periodique_u)&&(!est_periodique_v))
428 5 {
429     if ((boite.get_xmin()>=0.) && (boite.get_xmax()<periode_u))
430     {
431     if (num==1) inserer(boite,a,cellule); else supprimer(boite,a,cellule);
432     return;
433     }
434     if (boite.get_xmin()<0.)
435     {
436     BOITE_2D boite1(0.,boite.get_ymin(),boite.get_xmax(),boite.get_ymax());
437     BOITE_2D boite2(boite.get_xmin()+periode_u,boite.get_ymin(),periode_u,boite.get_ymax());
438     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
439     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
440 francois 632 return;
441 5 }
442     if (boite.get_xmax()>=periode_u)
443     {
444     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),periode_u,boite.get_ymax());
445     BOITE_2D boite2(0.,boite.get_ymin(),boite.get_xmax()-periode_u,boite.get_ymax());
446     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
447     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
448     return;
449     }
450     }
451 francois 632 if ((!est_periodique_u)&&(est_periodique_v))
452 5 {
453     if ((boite.get_ymin()>=0.) && (boite.get_ymax()<periode_v))
454     {
455     if (num==1) inserer(boite,a,cellule); else supprimer(boite,a,cellule);
456     return;
457     }
458     if (boite.get_ymin()<0.)
459     {
460     BOITE_2D boite1(boite.get_xmin(),0.,boite.get_xmax(),boite.get_ymax());
461     BOITE_2D boite2(boite.get_xmin(),boite.get_ymin()+periode_v,boite.get_xmax(),periode_v);
462     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
463     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
464     return;
465     }
466     if (boite.get_ymax()>=periode_v)
467     {
468     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),boite.get_xmax(),periode_v);
469     BOITE_2D boite2(boite.get_xmin(),0.,boite.get_xmax(),boite.get_ymax()-periode_v);
470     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
471     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
472     return;
473     }
474     }
475 francois 632 if ((est_periodique_u)&&(est_periodique_v))
476 5 {
477     if ((boite.get_xmin()>=0.) && (boite.get_xmax()<periode_u) && (boite.get_ymin()>=0.) && (boite.get_ymax()<periode_v))
478     {
479     if (num==1) inserer(boite,a,cellule); else supprimer(boite,a,cellule);
480     return;
481     }
482     if ((boite.get_xmin()<0.)&&(boite.get_ymin()<0.))
483     {
484     BOITE_2D boite1(0.,0.,boite.get_xmax(),boite.get_ymax());
485     BOITE_2D boite2(boite.get_xmin()+periode_u,0.,periode_u,boite.get_ymax());
486     BOITE_2D boite3(0.,boite.get_ymin()+periode_v,boite.get_xmax(),periode_v);
487     BOITE_2D boite4(boite.get_xmin()+periode_u,boite.get_ymin()+periode_v,periode_u,periode_v);
488     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
489     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
490     if (num==1) inserer(boite3,a,cellule); else supprimer(boite3,a,cellule);
491     if (num==1) inserer(boite4,a,cellule); else supprimer(boite4,a,cellule);
492     return;
493     }
494     if ((boite.get_xmin()<0.)&&(boite.get_ymax()>=periode_v))
495     {
496     BOITE_2D boite1(0.,boite.get_ymin(),boite.get_xmax(),periode_v );
497     BOITE_2D boite2(0.,0.,boite.get_xmax(),boite.get_ymax()-periode_v );
498     BOITE_2D boite3(boite.get_xmin()+periode_u,0.,periode_u,boite.get_ymax()-periode_v );
499     BOITE_2D boite4(boite.get_xmin()+periode_u,boite.get_ymin(),periode_u,periode_v );
500     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
501     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
502     if (num==1) inserer(boite3,a,cellule); else supprimer(boite3,a,cellule);
503     if (num==1) inserer(boite4,a,cellule); else supprimer(boite4,a,cellule);
504     return;
505     }
506     if ((boite.get_xmax()>=periode_u)&&(boite.get_ymax()>=periode_v))
507     {
508     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),periode_u,periode_v );
509     BOITE_2D boite2(0.,boite.get_ymin(),boite.get_xmax()-periode_u,periode_v );
510     BOITE_2D boite3(0.,0.,boite.get_xmax()-periode_u,boite.get_ymax()-periode_v );
511     BOITE_2D boite4(boite.get_xmin(),0.,periode_u,boite.get_ymax()-periode_v );
512     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
513     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
514     if (num==1) inserer(boite3,a,cellule); else supprimer(boite3,a,cellule);
515     if (num==1) inserer(boite4,a,cellule); else supprimer(boite4,a,cellule);
516     return;
517     }
518     if ((boite.get_xmax()>=periode_u)&&(boite.get_ymin()<0.))
519     {
520     BOITE_2D boite1(boite.get_xmin(),0.,periode_u,boite.get_ymax() );
521     BOITE_2D boite2(0.,0.,boite.get_xmax()-periode_u,boite.get_ymax() );
522     BOITE_2D boite3(0.,boite.get_ymin()+periode_v,boite.get_xmax()-periode_u,periode_v );
523     BOITE_2D boite4(boite.get_xmin(),boite.get_ymin()+periode_v,periode_u,periode_v );
524     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
525     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
526     if (num==1) inserer(boite3,a,cellule); else supprimer(boite3,a,cellule);
527     if (num==1) inserer(boite4,a,cellule); else supprimer(boite4,a,cellule);
528     return;
529     }
530     if (boite.get_xmin()<0.)
531     {
532     BOITE_2D boite1(0.,boite.get_ymin(),boite.get_xmax(),boite.get_ymax() );
533     BOITE_2D boite2(boite.get_xmin()+periode_u,boite.get_ymin(),periode_u,boite.get_ymax() );
534     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
535     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
536     return;
537     }
538     if (boite.get_ymin()<0.)
539     {
540     BOITE_2D boite1(boite.get_xmin(),0.,boite.get_xmax(),boite.get_ymax() );
541     BOITE_2D boite2(boite.get_xmin(),boite.get_ymin()+periode_v,boite.get_xmax(),periode_v );
542     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
543     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
544     return;
545     }
546     if (boite.get_xmax()>=periode_u)
547     {
548     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),periode_u,boite.get_ymax() );
549     BOITE_2D boite2(0.,boite.get_ymin(),boite.get_xmax(),boite.get_ymax() );
550     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
551     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
552     return;
553     }
554     if (boite.get_ymax()>=periode_v)
555     {
556     BOITE_2D boite1(boite.get_xmin(),boite.get_ymin(),boite.get_xmax(),periode_v );
557     BOITE_2D boite2(boite.get_xmin(),0.,boite.get_xmax(),boite.get_ymax()-periode_v );
558     if (num==1) inserer(boite1,a,cellule); else supprimer(boite1,a,cellule);
559     if (num==1) inserer(boite2,a,cellule); else supprimer(boite2,a,cellule);
560     return;
561     }
562    
563     }
564    
565     };
566    
567 francois 632 protected:
568 5 TPL_LISTE_ENTITE<TPL_CELLULE_QUADTREE<A ,CONDITION>* > lst_entite_cellule;
569    
570     };
571    
572    
573    
574    
575     #endif