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