tpl_octree.h

Aller à la documentation de ce fichier.

//####//------------------------------------------------------------
//####//------------------------------------------------------------
//####//  MAGiC
//####//  Jean Christophe Cuilliere et Vincent FRANCOIS
//####//  Departement de Genie Mecanique - UQTR
//####//------------------------------------------------------------
//####//  MAGIC est un projet de recherche de l equipe ERICCA
//####//  du departement de genie mecanique de l Universite du Quebec a Trois Rivieres
//####//  http://www.uqtr.ca/ericca
//####//  http://www.uqtr.ca/
//####//------------------------------------------------------------
//####//------------------------------------------------------------
//####//
//####//       tpl_octree.h
//####//
//####//------------------------------------------------------------
//####//------------------------------------------------------------
//####//    COPYRIGHT 2000-2024
//####//  jeu 13 jun 2024 11:54:00 EDT
//####//------------------------------------------------------------
//####//------------------------------------------------------------
#ifndef _TPLOCTREE_
#define _TPLOCTREE_
 
 
#include "ot_boite_3d.h"
#include "tpl_liste_entite.h"
#include "tpl_map_entite.h"
#include <math.h>
/*
*/
 
class OUTIL_OCTREE
{
public:
   OUTIL_OCTREE()
        {
        };
   ~OUTIL_OCTREE()
        {
        };
 
unsigned long determine_keycode(int nx,int ny,int nz)
{
std::vector<int> bits;
int ok=0,i=0;
do
        {
        int nnz=nz>>i;
        int nny=ny>>i;
        int nnx=nx>>i;
        int bit1= nnz & 1;
        int bit2= nny & 1;
        int bit3= nnx & 1;
        if ((nnz==0) && (nny==0) && (nnx==0)) ok=1;
        bits.insert(bits.end(),bit1);
        bits.insert(bits.end(),bit2);
        bits.insert(bits.end(),bit3);
        i++;
        }
while (ok==0);
unsigned long keycode=0;
for (int i=0;i<bits.size();i++)
        keycode=keycode+bits[i]*(1<<i);
return keycode;
}
 
 
bool adjacent(int direction,int octant)
{
bool tabadj[18][8]=
{
{true,  true,   true,   true,   false,  false,  false,  false},
{true,  true,   false,  false,  true,   true,   false,  false},
{false, true,   false,  true,   false,  true,   false,  true},
{false, false,  true,   true,   false,  false,  true,   true},
{true,  false,  true,   false,  true,   false,  true,   false},
{false, false,  false,  false,  true,   true,   true,   true},
{true,  true,   false,  false,  false,  false,  false,  false},
{true,  false,  true,   false,  false,  false,  false,  false},
{true,  false,  false,  false,  true,   false,  false,  false},
{false, true,   false,  true,   false,  false,  false,  false},
{false, true,   false,  false,  false,  true,   false,  false},
{false, false,  true,   true,   false,  false,  false,  false},
{false, false,  false,  true,   false,  false,  false,  true},
{false, false,  true,   false,  false,  false,  true,   false},
{false, false,  false,  false,  true,   true,   false,  false},
{false, false,  false,  false,  true,   false,  true,   false},
{false, false,  false,  false,  false,  true,   false,  true},
{false, false,  false,  false,  false,  false,  true,   true},
 
};
 
return tabadj[direction][octant];
}
 
 
int reflect(int direction,int octant)
{
int tabreflect[18][8]=
{
{4,     5,      6,      7,      0,      1,      2,      3},
{2,     3,      0,      1,      6,      7,      4,      5},
{1,     0,      3,      2,      5,      4,      7,      6},
{2,     3,      0,      1,      6,      7,      4,      5},
{1,     0,      3,      2,      5,      4,      7,      6},
{4,     5,      6,      7,      0,      1,      2,      3},
{6,     7,      4,      5,      2,      3,      0,      1},
{5,     4,      7,      6,      1,      0,      3,      2},
{3,     2,      1,      0,      7,      6,      5,      4},
{5,     4,      7,      6,      1,      0,      3,      2},
{3,     2,      1,      0,      7,      6,      5,      4},
{6,     7,      4,      5,      2,      3,      0,      1},
{3,     2,      1,      0,      7,      6,      5,      4},
{3,     2,      1,      0,      7,      6,      5,      4},
{6,     7,      4,      5,      2,      3,      0,      1},
{5,     4,      7,      6,      1,      0,      3,      2},
{5,     4,      7,      6,      1,      0,      3,      2},
{6,     7,      4,      5,      2,      3,      0,      1}
 
};
 
return tabreflect[direction][octant];
}
 
 
 
int commonface(int direction,int octant)
{
int tabcommonface[12][8]=
{
{-1,    -1,     0,      0,      1,      1,      -1,     -1},
{-1,    0,      -1,     0,      4,      -1,     4,      -1},
{-1,    1,      4,      -1,     -1,     1,      4,      -1},
{0,     -1,     0,      -1,     -1,     2,      -1,     2},
{1,     -1,     -1,     2,      1,      -1,     -1,     2},
{0,     0,      -1,     -1,     -1,     -1,     3,      3},
{-1,    2,      3,      -1,     -1,     2,      3,      -1},
{4,     -1,     -1,     3,      4,      -1,     -1,     3},
{1,     1,      -1,     -1,     -1,     -1,     5,      5},
{4,     -1,     4,      -1,     -1,     5,      -1,     5},
{-1,    2,      -1,     2,      5,      -1,     5,      -1},
{-1,    -1,     3,      3,      5,      5,      -1,     -1},
} ;
return tabcommonface[direction-6][octant];
 
}
 
int filsvoisin(int direction,int numvoisin)
{
int tab[6][4]=
{
{4,     5,      6,      7},
{2,     3,      6,      7},
{0,     2,      4,      6},
{0,     1,      4,      5},
{1,     3,      5,      7},
{0,     1,      2,      3}
};
return tab[direction][numvoisin];
}
 
int sommetface(int numface,int numsommet)
{
int tab[6][4]=
{
{0,1,2,3},
{0,1,5,4},
{1,2,6,5},
{3,2,6,7},
{0,3,7,4},
{4,5,6,7},
};
return tab[numface][numsommet];
}
 
int sommetarete(int numarete,int numsommet)
{
int tab[12][2]=
{
{0,1},
{0,3},
{0,4},
{1,2},
{1,5},
{3,2},
{2,6},
{3,7},
{4,5},
{4,7},
{5,6},
{7,6},
};
return tab[numarete-6][numsommet];
}
 
 
 
 
 
int areteface(int numface,int numarete)
{
int tab[6][4]=
{
{6,9,11,7},
{6,10,14,8},
{9,12,16,10},
{11,12,17,13},
{7,13,15,8},
{14,16,17,15},
};
return tab[numface][numarete];
}
 
int faceadjacente(int numface,int numarete)
{
int tab[6][4]=
{
{1,2,3,4},
{0,2,5,4},
{0,3,5,1},
{0,2,5,4},
{0,3,5,1},
{1,2,3,4},
};
return tab[numface][numarete];
}
 
 
 
};
 
 
class CELLULE_OCTREE_BASE
{
public:
   CELLULE_OCTREE_BASE()
        {
        static unsigned long idmax=0;
        id=idmax;
        idmax++;
        };
 
   virtual ~CELLULE_OCTREE_BASE() {};
   virtual BOITE_3D get_boite(void)=0;
   virtual CELLULE_OCTREE_BASE* get_fils(int num)=0;
   virtual int get_feuille(void)=0;
   virtual int get_niveau(void)=0;
   virtual int get_sontype(void)=0;
   virtual unsigned long get_id() {return id;};
   unsigned long id;
};
 
 
class OCTREE_BASE
{
   public:
   OCTREE_BASE() {};
   virtual ~OCTREE_BASE() {};
   virtual int get_nb_cellule(void)=0;
   virtual CELLULE_OCTREE_BASE* get_cellule(int num)=0;
   virtual int get_niveau_max(void)=0;
};
 
 
template <class A,class CONDITION>
class TPL_CELLULE_OCTREE:public CELLULE_OCTREE_BASE
{
public:
   TPL_CELLULE_OCTREE(TPL_CELLULE_OCTREE<A,CONDITION> *cell,double xmin,double ymin,double zmin,double xmax,double ymax,double zmax,int niv,int st):CELLULE_OCTREE_BASE(),boite(xmin,ymin,zmin,xmax,ymax,zmax),niveau(niv),pere(cell),sontype(st)
   {
   fils[0]=NULL;fils[1]=NULL;fils[2]=NULL;fils[3]=NULL;fils[4]=NULL;fils[5]=NULL;fils[6]=NULL;fils[7]=NULL;
  };
virtual ~TPL_CELLULE_OCTREE() {};
BOITE_3D get_boite(void) {return boite;};
int get_niveau(void) {return niveau;};
BOITE_3D boite;
int feuille;
TPL_LISTE_ENTITE<CONDITION> lst_entite_CONDITION;
TPL_LISTE_ENTITE<A> lst_entite_A;
virtual TPL_CELLULE_OCTREE<A,CONDITION>* get_fils(int num) {return fils[num];};
virtual TPL_CELLULE_OCTREE<A,CONDITION>* get_pere(void) {return pere;};
virtual int get_feuille(void) {return feuille;};
 
virtual void vide(void)
{
lst_entite_A.vide();
}
 
int get_sontype(void)
{
return sontype;
}
int get_nb_entite(void)
{
return lst_entite_A.get_nb();
};
A get_entite(int num)
{
return lst_entite_A.get(num);
};
TPL_CELLULE_OCTREE< A ,CONDITION> *fils[8];
TPL_CELLULE_OCTREE< A ,CONDITION> *pere;
 
 
int niveau;
int sontype;
};
 
template <class A,class CONDITION,class B>
class TPL_CELLULE_INFO:public CELLULE_OCTREE_BASE
{
public:
   TPL_CELLULE_INFO(double xmin,double ymin,double zmin,double xmax,double ymax,double zmax):CELLULE_OCTREE_BASE(),boite(xmin,ymin,zmin,xmax,ymax,zmax)
   {
   };
virtual ~TPL_CELLULE_INFO() {};
BOITE_3D get_boite(void) {return boite;};
BOITE_3D boite;
int feuille;
TPL_CELLULE_INFO< A ,CONDITION,B> *fils[8];
TPL_LISTE_ENTITE<CONDITION> lst_entite_CONDITION;
TPL_LISTE_ENTITE<A> lst_entite_A;
B tab[8];
virtual TPL_CELLULE_INFO<A,CONDITION,B>* get_fils(int num) {return fils[num];};
virtual int get_feuille(void) {return feuille;};
int get_nb_entite(void)
{
return lst_entite_A.get_nb();
};
A get_entite(int num)
{
return lst_entite_A.get(num);
};
 
B get_info(int num) {return tab[num];};
void change_info(int num,B val) {tab[num]=val;};
 
};
 
 
 
template <class A,class CONDITION>
class TPL_OCTREE:public OCTREE_BASE
{
public:
TPL_OCTREE():niveaumax(0),niveaumaxlim(10000) {};
virtual ~TPL_OCTREE()
{
   for (int i1=0;i1<lst_entite_cellule.get_nb();i1++)
   {
   TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(i1);
   delete cellule;
   }
};
 
virtual int get_nb_cellule(void) {return lst_entite_cellule.get_nb();};
virtual int get_nb_feuille(void) {return lst_entite_feuille.get_nb();};
 
virtual BOITE_3D get_boite_de_base(void) {return lst_entite_cellule.get(0)->get_boite();};
 
virtual TPL_CELLULE_OCTREE<A,CONDITION>* get_cellule(int num) {return lst_entite_cellule.get(num); };
virtual TPL_CELLULE_OCTREE<A,CONDITION>* get_feuille(int num) {return lst_entite_feuille.get(num); };
 
 
virtual void initialiser(TPL_LISTE_ENTITE<CONDITION>* lst_entite,int nombre,double xmin,double ymin,double zmin,double xmax,double ymax,double zmax)
   {
   TPL_CELLULE_OCTREE<A ,CONDITION>* root_cellule=new TPL_CELLULE_OCTREE<A ,CONDITION>(NULL,xmin,ymin,zmin,xmax,ymax,zmax,0,-1);
   lst_entite_cellule.ajouter(root_cellule);
   for (int i=0;i<lst_entite->get_nb();i++)
      {
      CONDITION cond=lst_entite->get(i);
      BOITE_3D boite_cond=cond->get_boite_3D();
      if (boite_cond*root_cellule->boite) root_cellule->lst_entite_CONDITION.ajouter(cond);
      }
   if (root_cellule->lst_entite_CONDITION.get_nb()>nombre)
      {
      root_cellule->feuille=0;
      double dx=xmax-xmin;
      double dy=ymax-ymin;
      double dz=zmax-zmin;
      root_cellule->fils[0]=cree_fils(root_cellule,xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,0);
      root_cellule->fils[1]=cree_fils(root_cellule,xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,1);
      root_cellule->fils[2]=cree_fils(root_cellule,xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,2);
      root_cellule->fils[3]=cree_fils(root_cellule,xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,3);
      root_cellule->fils[4]=cree_fils(root_cellule,xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,4);
      root_cellule->fils[5]=cree_fils(root_cellule,xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,5);
      root_cellule->fils[6]=cree_fils(root_cellule,xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,6);
      root_cellule->fils[7]=cree_fils(root_cellule,xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,7);
      }
   else root_cellule->feuille=1;
   for (int j=0;j<lst_entite_cellule.get_nb();j++)
      {
         TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(j);
         cellule->lst_entite_CONDITION.vide();
      }
   }
 
virtual void initialiser(TPL_MAP_ENTITE<CONDITION>* lst_entite,int nombre,double xmin,double ymin,double zmin,double xmax,double ymax,double zmax)
   {
   TPL_CELLULE_OCTREE<A ,CONDITION>* root_cellule=new TPL_CELLULE_OCTREE<A ,CONDITION>(NULL,xmin,ymin,zmin,xmax,ymax,zmax,0,-1);
   lst_entite_cellule.ajouter(root_cellule);
   typename TPL_MAP_ENTITE<CONDITION>::ITERATEUR it;
   for (CONDITION cond=lst_entite->get_premier(it);cond!=NULL;cond=lst_entite->get_suivant(it))
      {
      BOITE_3D boite_cond=cond->get_boite_3D();
      if (boite_cond*root_cellule->boite) root_cellule->lst_entite_CONDITION.ajouter(cond);
      }
   if (root_cellule->lst_entite_CONDITION.get_nb()>nombre)
      {
      root_cellule->feuille=0;
      double dx=xmax-xmin;
      double dy=ymax-ymin;
      double dz=zmax-zmin;
      root_cellule->fils[0]=cree_fils(root_cellule,xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,0);
      root_cellule->fils[1]=cree_fils(root_cellule,xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,1);
      root_cellule->fils[2]=cree_fils(root_cellule,xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,2);
      root_cellule->fils[3]=cree_fils(root_cellule,xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,3);
      root_cellule->fils[4]=cree_fils(root_cellule,xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,4);
      root_cellule->fils[5]=cree_fils(root_cellule,xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,5);
      root_cellule->fils[6]=cree_fils(root_cellule,xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,6);
      root_cellule->fils[7]=cree_fils(root_cellule,xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,7);
      }
   else root_cellule->feuille=1;
   for (int j=0;j<lst_entite_cellule.get_nb();j++)
      {
         TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(j);
         cellule->lst_entite_CONDITION.vide();
      }
   }
 
virtual void initialiser2D(int dimanepasdecouper,TPL_LISTE_ENTITE<CONDITION>* lst_entite,int nombre,double xmin,double ymin,double zmin,double xmax,double ymax,double zmax)
   {
   TPL_CELLULE_OCTREE<A ,CONDITION>* root_cellule=new TPL_CELLULE_OCTREE<A ,CONDITION>(NULL,xmin,ymin,zmin,xmax,ymax,zmax,0,-1);
   lst_entite_cellule.ajouter(root_cellule);
   for (int i=0;i<lst_entite->get_nb();i++)
      {
      CONDITION cond=lst_entite->get(i);
      BOITE_3D boite_cond=cond->get_boite_3D();
      if (boite_cond*root_cellule->boite) root_cellule->lst_entite_CONDITION.ajouter(cond);
      }
   if (root_cellule->lst_entite_CONDITION.get_nb()>nombre)
      {
      root_cellule->feuille=0;
      double dx=xmax-xmin;
      double dy=ymax-ymin;
      double dz=zmax-zmin;
      if (dimanepasdecouper==3)
        {
        root_cellule->fils[0]=cree_fils2D(dimanepasdecouper,root_cellule,xmin,ymin,zmin,dx/2.,dy/2.,dz,&(root_cellule->lst_entite_CONDITION),nombre,1,0);
        root_cellule->fils[1]=cree_fils2D(dimanepasdecouper,root_cellule,xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz,&(root_cellule->lst_entite_CONDITION),nombre,1,1);
        root_cellule->fils[2]=cree_fils2D(dimanepasdecouper,root_cellule,xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz,&(root_cellule->lst_entite_CONDITION),nombre,1,2);
        root_cellule->fils[3]=cree_fils2D(dimanepasdecouper,root_cellule,xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz,&(root_cellule->lst_entite_CONDITION),nombre,1,3);
        }
      if (dimanepasdecouper==2)
        {
        root_cellule->fils[0]=cree_fils2D(dimanepasdecouper,root_cellule,xmin,ymin,zmin,dx/2.,dy,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,0);
        root_cellule->fils[1]=cree_fils2D(dimanepasdecouper,root_cellule,xmin+dx/2.,ymin,zmin,dx/2.,dy,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,1);
        root_cellule->fils[4]=cree_fils2D(dimanepasdecouper,root_cellule,xmin,ymin,zmin+dz/2.,dx/2.,dy,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,4);
        root_cellule->fils[5]=cree_fils2D(dimanepasdecouper,root_cellule,xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,5);
        }
      if (dimanepasdecouper==1)
        {
        root_cellule->fils[0]=cree_fils2D(dimanepasdecouper,root_cellule,xmin,ymin,zmin,dx,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,0);
        root_cellule->fils[2]=cree_fils2D(dimanepasdecouper,root_cellule,xmin,ymin+dy/2.,zmin,dx,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,2);
        root_cellule->fils[4]=cree_fils2D(dimanepasdecouper,root_cellule,xmin,ymin,zmin+dz/2.,dx,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,4);
        root_cellule->fils[6]=cree_fils2D(dimanepasdecouper,root_cellule,xmin,ymin+dy/2.,zmin+dz/2.,dx,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre,1,6);
        }
      }
   else root_cellule->feuille=1;
   for (int j=0;j<lst_entite_cellule.get_nb();j++)
      {
         TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(j);
         cellule->lst_entite_CONDITION.vide();
      }
   }
 
virtual void initialiser(OCTREE_BASE* oc)
{
 BOITE_3D boite=oc->get_cellule(0)->get_boite();
 double xmin=boite.get_xmin();
 double xmax=boite.get_xmax();
 double ymin=boite.get_ymin();
 double ymax=boite.get_ymax();
 double zmin=boite.get_zmin();
 double zmax=boite.get_zmax();
 TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=new TPL_CELLULE_OCTREE<A ,CONDITION>(NULL,xmin,ymin,zmin,xmax,ymax,zmax,0,oc->get_cellule(0)->get_sontype());
 lst_entite_cellule.ajouter(cellule);
 niveaumax=oc->get_niveau_max();
 cellule->feuille=oc->get_cellule(0)->get_feuille();
 if (oc->get_cellule(0)->get_feuille()==0)
 {
 if (oc->get_cellule(0)->get_fils(0)!=NULL) cellule->fils[0]=cree_fils(cellule,oc->get_cellule(0)->get_fils(0),0);
 if (oc->get_cellule(0)->get_fils(1)!=NULL) cellule->fils[1]=cree_fils(cellule,oc->get_cellule(0)->get_fils(1),1);
 if (oc->get_cellule(0)->get_fils(2)!=NULL) cellule->fils[2]=cree_fils(cellule,oc->get_cellule(0)->get_fils(2),2);
 if (oc->get_cellule(0)->get_fils(3)!=NULL) cellule->fils[3]=cree_fils(cellule,oc->get_cellule(0)->get_fils(3),3);
 if (oc->get_cellule(0)->get_fils(4)!=NULL) cellule->fils[4]=cree_fils(cellule,oc->get_cellule(0)->get_fils(4),4);
 if (oc->get_cellule(0)->get_fils(5)!=NULL) cellule->fils[5]=cree_fils(cellule,oc->get_cellule(0)->get_fils(5),5);
 if (oc->get_cellule(0)->get_fils(6)!=NULL) cellule->fils[6]=cree_fils(cellule,oc->get_cellule(0)->get_fils(6),6);
 if (oc->get_cellule(0)->get_fils(7)!=NULL) cellule->fils[7]=cree_fils(cellule,oc->get_cellule(0)->get_fils(7),7);
 }
 else {cellule->feuille=1;lst_entite_feuille.ajouter(cellule);}
};
 
 
TPL_CELLULE_OCTREE<A,CONDITION>* cree_fils( TPL_CELLULE_OCTREE<A ,CONDITION>* cell,CELLULE_OCTREE_BASE *cellule_base,int st)
{
 BOITE_3D boite=cellule_base->get_boite();
 double xmin=boite.get_xmin();
 double xmax=boite.get_xmax();
 double ymin=boite.get_ymin();
 double ymax=boite.get_ymax();
 double zmin=boite.get_zmin();
 double zmax=boite.get_zmax();
 TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=new TPL_CELLULE_OCTREE<A ,CONDITION>(cell,xmin,ymin,zmin,xmax,ymax,zmax,cellule_base->get_niveau(),st);
 lst_entite_cellule.ajouter(cellule);
 if (niveaumax<cellule_base->get_niveau()) niveaumax=cellule_base->get_niveau();
 if (cellule_base->get_feuille()==1)
 {
 {cellule->feuille=1;lst_entite_feuille.ajouter(cellule);}
 }
 else
 {
 if (cellule_base->get_fils(0)!=NULL) cellule->fils[0]=cree_fils(cellule,cellule_base->get_fils(0),0);
 if (cellule_base->get_fils(1)!=NULL) cellule->fils[1]=cree_fils(cellule,cellule_base->get_fils(1),1);
 if (cellule_base->get_fils(2)!=NULL) cellule->fils[2]=cree_fils(cellule,cellule_base->get_fils(2),2);
 if (cellule_base->get_fils(3)!=NULL) cellule->fils[3]=cree_fils(cellule,cellule_base->get_fils(3),3);
 if (cellule_base->get_fils(4)!=NULL) cellule->fils[4]=cree_fils(cellule,cellule_base->get_fils(4),4);
 if (cellule_base->get_fils(5)!=NULL) cellule->fils[5]=cree_fils(cellule,cellule_base->get_fils(5),5);
 if (cellule_base->get_fils(6)!=NULL) cellule->fils[6]=cree_fils(cellule,cellule_base->get_fils(6),6);
 if (cellule_base->get_fils(7)!=NULL) cellule->fils[7]=cree_fils(cellule,cellule_base->get_fils(7),7);
 cellule->feuille=cellule_base->get_feuille();
 }
return cellule;
};
 
virtual TPL_CELLULE_OCTREE<A ,CONDITION>* cree_fils(TPL_CELLULE_OCTREE<A ,CONDITION>* cell,double xmin,double ymin,double zmin,double dx,double dy,double dz,TPL_LISTE_ENTITE<CONDITION>* lst_entite,int nombre,int niv,int st)
   {
   TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=new TPL_CELLULE_OCTREE<A ,CONDITION>(cell,xmin,ymin,zmin,xmin+dx,ymin+dy,zmin+dz,niv,st);
   lst_entite_cellule.ajouter(cellule);
    if (niveaumax<niv) niveaumax=niv;
    for (int i=0;i<lst_entite->get_nb();i++)
      {
      CONDITION cond=lst_entite->get(i);
      BOITE_3D boite_cond=cond->get_boite_3D();
      if (boite_cond*cellule->boite) cellule->lst_entite_CONDITION.ajouter(cond);
      }
    if ((cellule->lst_entite_CONDITION.get_nb()>nombre) && (niveaumax<niveaumaxlim))
      {
      cellule->feuille=0;
      cellule->fils[0]=cree_fils(cellule,xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,0);
      cellule->fils[1]=cree_fils(cellule,xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,1);
      cellule->fils[2]=cree_fils(cellule,xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,2);
      cellule->fils[3]=cree_fils(cellule,xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,3);
      cellule->fils[4]=cree_fils(cellule,xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,4);
      cellule->fils[5]=cree_fils(cellule,xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,5);
      cellule->fils[6]=cree_fils(cellule,xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,6);
      cellule->fils[7]=cree_fils(cellule,xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,7);
      }
   else {cellule->feuille=1;lst_entite_feuille.ajouter(cellule);}
   return cellule;
   }
 
virtual TPL_CELLULE_OCTREE<A ,CONDITION>* cree_fils2D(int dimanepasdecouper,TPL_CELLULE_OCTREE<A ,CONDITION>* cell,double xmin,double ymin,double zmin,double dx,double dy,double dz,TPL_LISTE_ENTITE<CONDITION>* lst_entite,int nombre,int niv,int st)
   {
   TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=new TPL_CELLULE_OCTREE<A ,CONDITION>(cell,xmin,ymin,zmin,xmin+dx,ymin+dy,zmin+dz,niv,st);
   lst_entite_cellule.ajouter(cellule);
    if (niveaumax<niv) niveaumax=niv;
    dz=dz*2;
    for (int i=0;i<lst_entite->get_nb();i++)
      {
      CONDITION cond=lst_entite->get(i);
      BOITE_3D boite_cond=cond->get_boite_3D();
      if (boite_cond*cellule->boite) cellule->lst_entite_CONDITION.ajouter(cond);
      }
    if (cellule->lst_entite_CONDITION.get_nb()>nombre)
      {
      cellule->feuille=0;
      if (dimanepasdecouper==3) 
        {
        cellule->fils[0]=cree_fils2D(dimanepasdecouper,cellule,xmin,ymin,zmin,dx/2.,dy/2.,dz,&(cellule->lst_entite_CONDITION),nombre,niv+1,0);
        cellule->fils[1]=cree_fils2D(dimanepasdecouper,cellule,xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz,&(cellule->lst_entite_CONDITION),nombre,niv+1,1);
        cellule->fils[2]=cree_fils2D(dimanepasdecouper,cellule,xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz,&(cellule->lst_entite_CONDITION),nombre,niv+1,2);
        cellule->fils[3]=cree_fils2D(dimanepasdecouper,cellule,xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz,&(cellule->lst_entite_CONDITION),nombre,niv+1,3);
        }
      if (dimanepasdecouper==2) 
        {
        cellule->fils[0]=cree_fils2D(dimanepasdecouper,cellule,xmin,ymin,zmin,dx/2.,dy,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,0);
        cellule->fils[1]=cree_fils2D(dimanepasdecouper,cellule,xmin+dx/2.,ymin,zmin,dx/2.,dy,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,1);
        cellule->fils[4]=cree_fils2D(dimanepasdecouper,cellule,xmin,ymin,zmin+dz/2.,dx/2.,dy,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,4);
        cellule->fils[5]=cree_fils2D(dimanepasdecouper,cellule,xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,5);
        }
      if (dimanepasdecouper==1) 
        {
        cellule->fils[0]=cree_fils2D(dimanepasdecouper,cellule,xmin,ymin,zmin,dx,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,0);
        cellule->fils[2]=cree_fils2D(dimanepasdecouper,cellule,xmin,ymin+dy/2.,zmin,dx,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,2);
        cellule->fils[4]=cree_fils2D(dimanepasdecouper,cellule,xmin,ymin,zmin+dz/2.,dx,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,4);
        cellule->fils[6]=cree_fils2D(dimanepasdecouper,cellule,xmin,ymin+dy/2.,zmin+dz/2.,dx,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre,niv+1,6);
        }
      }
   else {cellule->feuille=1;lst_entite_feuille.ajouter(cellule);}
   return cellule;
   }
 
 
virtual void rechercher(BOITE_3D& boite,TPL_MAP_ENTITE<A>& liste_entite_trouve,TPL_CELLULE_OCTREE<A ,CONDITION>* cellule)
{
if (cellule==NULL) return;
if (boite*cellule->boite)
 if (cellule->feuille==1)
 {
 for (int i=0;i<cellule->lst_entite_A.get_nb();i++)
   if (boite*cellule->lst_entite_A.get(i)->get_boite_3D())
     liste_entite_trouve.ajouter(cellule->lst_entite_A.get(i));
 }
else
 {
 rechercher(boite,liste_entite_trouve,cellule->fils[0]);
 rechercher(boite,liste_entite_trouve,cellule->fils[1]);
 rechercher(boite,liste_entite_trouve,cellule->fils[2]);
 rechercher(boite,liste_entite_trouve,cellule->fils[3]);
 rechercher(boite,liste_entite_trouve,cellule->fils[4]);
 rechercher(boite,liste_entite_trouve,cellule->fils[5]);
 rechercher(boite,liste_entite_trouve,cellule->fils[6]);
 rechercher(boite,liste_entite_trouve,cellule->fils[7]);
 }
};
 
 
virtual void get_cellule(BOITE_3D& boite,TPL_CELLULE_OCTREE<A ,CONDITION>* cellule,TPL_MAP_ENTITE<TPL_CELLULE_OCTREE<A ,CONDITION> * > &liste_entite)
{
if (boite*cellule->boite)
 if (cellule->feuille==1)
 {
      liste_entite.ajouter(cellule);
 }
else
 {
 get_cellule(boite,cellule->fils[0],liste_entite);
 get_cellule(boite,cellule->fils[1],liste_entite);
 get_cellule(boite,cellule->fils[2],liste_entite);
 get_cellule(boite,cellule->fils[3],liste_entite);
 get_cellule(boite,cellule->fils[4],liste_entite);
 get_cellule(boite,cellule->fils[5],liste_entite);
 get_cellule(boite,cellule->fils[6],liste_entite);
 get_cellule(boite,cellule->fils[7],liste_entite);
 }
};
 
virtual  TPL_CELLULE_OCTREE<A,CONDITION> *get_cellule_adjacent(TPL_CELLULE_OCTREE<A,CONDITION> * cellule,int direction)
{
TPL_CELLULE_OCTREE<A,CONDITION> *cellule2;
OUTIL_OCTREE outil;
if (cellule->pere==NULL) cellule2=NULL;
else if (outil.adjacent(direction,cellule->get_sontype())) cellule2=get_cellule_adjacent(cellule->pere,direction);
else if (outil.commonface(direction,cellule->get_sontype())!=-1) cellule2=get_cellule_voisin(cellule->pere,outil.commonface(direction,cellule->get_sontype()));
else cellule2=cellule->pere;
if (cellule2!=NULL)
        if (cellule2->get_feuille()==0)
                return cellule2->get_fils(outil.reflect(direction,cellule->get_sontype()));
return cellule2;
}
 
virtual  TPL_CELLULE_OCTREE<A,CONDITION> *get_cellule_voisin(TPL_CELLULE_OCTREE<A,CONDITION> * cellule,int direction)
{
TPL_CELLULE_OCTREE<A,CONDITION> *cellule2;
OUTIL_OCTREE outil;
if ((!(cellule->pere==NULL)) && (outil.adjacent(direction,cellule->get_sontype())))
        cellule2=get_cellule_voisin(cellule->pere,direction);
        else
        cellule2=cellule->pere;
if (cellule2!=NULL)
        if (cellule2->feuille==0)
                return cellule2->get_fils(outil.reflect(direction,cellule->get_sontype()));
return cellule2;
}
 
 
 
 
virtual  void get_feuille_voisins(TPL_CELLULE_OCTREE<A,CONDITION> * cellule,int direction,std::vector<TPL_CELLULE_OCTREE<A,CONDITION> *> *lst)
{
OUTIL_OCTREE outil;
lst->clear();
TPL_CELLULE_OCTREE<A,CONDITION> *cellule2=get_cellule_voisin(cellule,direction);
if (cellule2!=NULL) lst->insert(lst->end(),cellule2);
int i=0;
while (i<lst->size())
        {
        TPL_CELLULE_OCTREE<A,CONDITION> *cell=(*lst)[i];
        if (cell->feuille==0)
                {
                lst->insert(lst->end(),cell->get_fils(outil.filsvoisin(direction,0)));
                lst->insert(lst->end(),cell->get_fils(outil.filsvoisin(direction,1)));
                lst->insert(lst->end(),cell->get_fils(outil.filsvoisin(direction,2)));
                lst->insert(lst->end(),cell->get_fils(outil.filsvoisin(direction,3)));
                }
        i++;
        }
typename std::vector<TPL_CELLULE_OCTREE<A,CONDITION> * >::iterator j=lst->end();
while (j!=lst->begin())
{
j--;
TPL_CELLULE_OCTREE<A,CONDITION> *cell=*j;
if (cell->feuille==0)
        lst->erase(j);
 
}
}
 
virtual TPL_CELLULE_OCTREE<A,CONDITION> *get_cellule(double x,double y, double z)
{
BOITE_3D boite(x,y,z,x,y,z);
TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(0);
TPL_MAP_ENTITE<TPL_CELLULE_OCTREE<A ,CONDITION> * > liste_cellule;
get_cellule(boite,cellule,liste_cellule);
if (liste_cellule.get_nb()==1) return liste_cellule.get(0);
return NULL;
};
 
 
virtual unsigned long get_cellule_keycode(int numcellule,int numsommet)
{
TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(numcellule);
return get_keycode(cellule,numsommet);
}
 
virtual unsigned long get_feuille_keycode(int numcellule,int numsommet)
{
TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_feuille.get(numcellule);
return get_keycode(cellule,numsommet);
}
 
virtual unsigned long get_keycode(TPL_CELLULE_OCTREE<A ,CONDITION>* cellule,int numsommet)
{
TPL_CELLULE_OCTREE<A ,CONDITION>* root=lst_entite_cellule.get(0);
 
double x=cellule->boite.get_xmin();
double y=cellule->boite.get_ymin();
double z=cellule->boite.get_zmin();
double xx=cellule->boite.get_xmax();
double yy=cellule->boite.get_ymax();
double zz=cellule->boite.get_zmax();
double somx=x,somy=y,somz=z;
if (numsommet==1) somx=xx;
if (numsommet==2) {somx=xx;somy=yy;}
if (numsommet==3) somy=yy;
if (numsommet==4) somz=zz;
if (numsommet==5) {somx=xx;somz=zz;}
if (numsommet==6) {somx=xx;somy=yy;somz=zz;}
if (numsommet==7) {somy=yy;somz=zz;}
double nx=0.1+(somx-root->boite.get_xmin())/(root->boite.get_xmax()-root->boite.get_xmin())*(1<<get_niveau_max());
double ny=0.1+(somy-root->boite.get_ymin())/(root->boite.get_ymax()-root->boite.get_ymin())*(1<<get_niveau_max());
double nz=0.1+(somz-root->boite.get_zmin())/(root->boite.get_zmax()-root->boite.get_zmin())*(1<<get_niveau_max());
OUTIL_OCTREE outil;
return outil.determine_keycode(nx,ny,nz);
}
 
virtual unsigned long get_keycode(double x,double y,double z)
{
TPL_CELLULE_OCTREE<A ,CONDITION>* root=lst_entite_cellule.get(0);
double nx=0.1+(x-root->boite.get_xmin())/(root->boite.get_xmax()-root->boite.get_xmin())*(1<<get_niveau_max());
double ny=0.1+(y-root->boite.get_ymin())/(root->boite.get_ymax()-root->boite.get_ymin())*(1<<get_niveau_max());
double nz=0.1+(z-root->boite.get_zmin())/(root->boite.get_zmax()-root->boite.get_zmin())*(1<<get_niveau_max());
OUTIL_OCTREE outil;
return outil.determine_keycode(nx,ny,nz);
}
 
 
 
virtual void get_xyzsommet_cellule(int numcellule,int numsommet,double &x,double &y,double &z)
{
TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(numcellule);
x=cellule->boite.get_xmin();
y=cellule->boite.get_ymin();
z=cellule->boite.get_zmin();
double xx=cellule->boite.get_xmax();
double yy=cellule->boite.get_ymax();
double zz=cellule->boite.get_zmax();
if (numsommet==1) x=xx;
if (numsommet==2) {x=xx;y=yy;}
if (numsommet==3) y=yy;
if (numsommet==4) z=zz;
if (numsommet==5) {x=xx;z=zz;}
if (numsommet==6) {x=xx;y=yy;z=zz;}
if (numsommet==7) {y=yy;z=zz;}
}
 
virtual void get_xyzsommet_feuille(int numcellule,int numsommet,double &x,double &y,double &z)
{
TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_feuille.get(numcellule);
x=cellule->boite.get_xmin();
y=cellule->boite.get_ymin();
z=cellule->boite.get_zmin();
double xx=cellule->boite.get_xmax();
double yy=cellule->boite.get_ymax();
double zz=cellule->boite.get_zmax();
if (numsommet==1) x=xx;
if (numsommet==2) {x=xx;y=yy;}
if (numsommet==3) y=yy;
if (numsommet==4) z=zz;
if (numsommet==5) {x=xx;z=zz;}
if (numsommet==6) {x=xx;y=yy;z=zz;}
if (numsommet==7) {y=yy;z=zz;}
}
 
 
 
virtual void equilibre(int niveauequilibre=1)
{
int ok=0;
do
{
int nbfeuilleavant=get_nb_feuille();
std::vector< TPL_CELLULE_OCTREE<A,CONDITION> *> lstraf;
for (int i=0;i<lst_entite_feuille.get_nb();i++)
        {
        TPL_CELLULE_OCTREE<A,CONDITION> *feuille=lst_entite_feuille.get(i);
        int niveaumaxvoisin=0;
        for (int j=0;j<6;j++)
                {
                std::vector< TPL_CELLULE_OCTREE<A,CONDITION> *> lstvoi;
                get_feuille_voisins(feuille,j,&lstvoi);
                int nb_feuille=lstvoi.size();
                for (int k=0;k<nb_feuille;k++)
                        {
                        int niveau=lstvoi[k]->get_niveau();
                        if (niveau>niveaumaxvoisin) niveaumaxvoisin=niveau;
                        }
 
                }
        if (niveaumaxvoisin-feuille->get_niveau()>niveauequilibre) {lstraf.insert(lstraf.end(),feuille);feuille->feuille=niveaumaxvoisin-niveauequilibre;}
        }
int nbcelluleraffiner=lstraf.size();
for (int i=0;i<nbcelluleraffiner;i++)
        {
        TPL_CELLULE_OCTREE<A,CONDITION> *cell=lstraf[i];
        lst_entite_feuille.supprimer(cell);
        int niveauatteindre=cell->feuille;
        int niveau=cell->niveau;
        cell->feuille=0;
        double xmin=cell->boite.get_xmin();
        double ymin=cell->boite.get_ymin();
        double zmin=cell->boite.get_zmin();
        double dx=cell->boite.get_xmax()-cell->boite.get_xmin();
        double dy=cell->boite.get_ymax()-cell->boite.get_ymin();
        double dz=cell->boite.get_zmax()-cell->boite.get_zmin();
 
        cell->fils[0]=cree_fils(cell,xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,niveau+1,niveauatteindre,0);
        cell->fils[1]=cree_fils(cell,xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,niveau+1,niveauatteindre,1);
        cell->fils[2]=cree_fils(cell,xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,niveau+1,niveauatteindre,2);
        cell->fils[3]=cree_fils(cell,xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,niveau+1,niveauatteindre,3);
        cell->fils[4]=cree_fils(cell,xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,niveau+1,niveauatteindre,4);
        cell->fils[5]=cree_fils(cell,xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,niveau+1,niveauatteindre,5);
        cell->fils[6]=cree_fils(cell,xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,niveau+1,niveauatteindre,6);
        cell->fils[7]=cree_fils(cell,xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,niveau+1,niveauatteindre,7);
        }
int nbfeuilleapres=get_nb_feuille();
if (nbfeuilleapres==nbfeuilleavant) ok=1;
}
while (ok==0);
 
 
}
 
virtual TPL_CELLULE_OCTREE<A ,CONDITION>* cree_fils(TPL_CELLULE_OCTREE<A ,CONDITION>* cell,double xmin,double ymin,double zmin,double dx,double dy,double dz,int niv,int niveauatteindre,int st)
   {
   TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=new TPL_CELLULE_OCTREE<A ,CONDITION>(cell,xmin,ymin,zmin,xmin+dx,ymin+dy,zmin+dz,niv,st);
   lst_entite_cellule.ajouter(cellule);
    if (niveaumax<niv) niveaumax=niv;
    if (cellule->get_niveau()!=niveauatteindre)
      {
      cellule->feuille=0;
      cellule->fils[0]=cree_fils(cellule,xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,niv+1,niveauatteindre,0);
      cellule->fils[1]=cree_fils(cellule,xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,niv+1,niveauatteindre,1);
      cellule->fils[2]=cree_fils(cellule,xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,niv+1,niveauatteindre,2);
      cellule->fils[3]=cree_fils(cellule,xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,niv+1,niveauatteindre,3);
      cellule->fils[4]=cree_fils(cellule,xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,niv+1,niveauatteindre,4);
      cellule->fils[5]=cree_fils(cellule,xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,niv+1,niveauatteindre,5);
      cellule->fils[6]=cree_fils(cellule,xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,niv+1,niveauatteindre,6);
      cellule->fils[7]=cree_fils(cellule,xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,niv+1,niveauatteindre,7);
      }
   else {cellule->feuille=1;lst_entite_feuille.ajouter(cellule);}
   return cellule;
   }
 
 
virtual void rechercher(double xcentre,double ycentre,double zcentre,double rayon_recherche,TPL_MAP_ENTITE<A>& liste_entite_trouve)
{
BOITE_3D boite(xcentre-rayon_recherche,ycentre-rayon_recherche,zcentre-rayon_recherche,xcentre+rayon_recherche,ycentre+rayon_recherche,zcentre+rayon_recherche);
TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(0);
rechercher(boite,liste_entite_trouve,cellule);
};
 
 
 
virtual void inserer(BOITE_3D& boite,A a,TPL_CELLULE_OCTREE<A ,CONDITION>* cellule)
{
if (cellule==NULL) return;
if (boite*cellule->boite)
 if (cellule->feuille==1)
 {
 cellule->lst_entite_A.ajouter(a);
 }
else
 {
 inserer(boite,a,cellule->fils[0]);
 inserer(boite,a,cellule->fils[1]);
 inserer(boite,a,cellule->fils[2]);
 inserer(boite,a,cellule->fils[3]);
 inserer(boite,a,cellule->fils[4]);
 inserer(boite,a,cellule->fils[5]);
 inserer(boite,a,cellule->fils[6]);
 inserer(boite,a,cellule->fils[7]);
 }
};
 
virtual void supprimer(BOITE_3D& boite,A a,TPL_CELLULE_OCTREE<A ,CONDITION>* cellule)
{
if (cellule==NULL) return;
if (boite*cellule->boite)
 if (cellule->feuille==1)
 {
 cellule->lst_entite_A.supprimer(a);
 }
else
 {
 supprimer(boite,a,cellule->fils[0]);
 supprimer(boite,a,cellule->fils[1]);
 supprimer(boite,a,cellule->fils[2]);
 supprimer(boite,a,cellule->fils[3]);
 supprimer(boite,a,cellule->fils[4]);
 supprimer(boite,a,cellule->fils[5]);
 supprimer(boite,a,cellule->fils[6]);
 supprimer(boite,a,cellule->fils[7]);
 }
};
 
virtual void inserer(A a)
{
BOITE_3D boite=a->get_boite_3D();
TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(0);
inserer(boite,a,cellule);
}
 
virtual void supprimer(A a)
{
BOITE_3D boite=a->get_boite_3D();
TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(0);
supprimer(boite,a,cellule);
}
 
virtual int get_tout_entite(TPL_MAP_ENTITE<A> &lst)
{
for (int i=0;i<lst_entite_feuille.get_nb();i++)
    {
    TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_feuille.get(i); 
    for (int j=0;j<cellule->lst_entite_A.get_nb();j++)
        lst.ajouter(cellule->lst_entite_A.get(j));
    }
return lst.get_nb();    
}
 
 
 
virtual int get_niveau_max(void)
{
return niveaumax;
}
 
virtual int get_niveau_max_lim(void)
{
return niveaumaxlim;  
}
 
 
void change_niveau_max_lim(int num)
{
niveaumaxlim=num;  
}
 
virtual void vide(void)
{
for (int i=0;i<lst_entite_feuille.get_nb();i++)
      {
      TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_feuille.get(i);
      cellule->vide();
      }
}
 
 
virtual double get_dimension_caracteristique()
{
TPL_CELLULE_OCTREE<A ,CONDITION>* cellule=lst_entite_cellule.get(0);
double x=cellule->boite.get_xmin();
double y=cellule->boite.get_ymin();
double z=cellule->boite.get_zmin();
double xx=cellule->boite.get_xmax();
double yy=cellule->boite.get_ymax();
double zz=cellule->boite.get_zmax();
return sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y)+(zz-z)*(zz-z)) ;
}
 
 
 
protected:
TPL_LISTE_ENTITE<TPL_CELLULE_OCTREE<A ,CONDITION>* > lst_entite_cellule;
TPL_LISTE_ENTITE<TPL_CELLULE_OCTREE<A ,CONDITION>* > lst_entite_feuille;
int niveaumax;
int niveaumaxlim;
 
};
 
template <class A,class B>
class TPL_OCTREE_FCT:public TPL_OCTREE<A,A>
{
private:
double coef;
 
public:
TPL_OCTREE_FCT():TPL_OCTREE<A,A>(),coef(1.) {};
virtual ~TPL_OCTREE_FCT() {}
 
 
virtual void change_coefficent_multiplicateur(double val) {coef=val;};
 
virtual void initialiser(B &fonction,double xmin,double ymin,double zmin,double xmax,double ymax,double zmax)
   {
   TPL_CELLULE_OCTREE<A ,A>* root_cellule=new TPL_CELLULE_OCTREE<A ,A>(NULL,xmin,ymin,zmin,xmax,ymax,zmax,0,-1);
   TPL_OCTREE<A,A>::lst_entite_cellule.ajouter(root_cellule);
   double dx=root_cellule->boite.get_xmax()-root_cellule->boite.get_xmin();
   double dy=root_cellule->boite.get_ymax()-root_cellule->boite.get_ymin();
   double dz=root_cellule->boite.get_zmax()-root_cellule->boite.get_zmin();
   double d=dx;
   if (dy>d) d=dy;
   if (dz>d) d=dz;
   double xyz[3];
   root_cellule->boite.get_centre(xyz);
   double ecart[9];
   fonction.evaluer(xyz,ecart);
   double dcible=coef/sqrt(ecart[0]);
   if (dcible<d)
        {
        root_cellule->feuille=0;
        root_cellule->fils[0]=cree_fils(root_cellule,xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,fonction,1,0);
        root_cellule->fils[1]=cree_fils(root_cellule,xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,fonction,1,1);
        root_cellule->fils[2]=cree_fils(root_cellule,xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,fonction,1,2);
        root_cellule->fils[3]=cree_fils(root_cellule,xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,fonction,1,3);
        root_cellule->fils[4]=cree_fils(root_cellule,xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,fonction,1,4);
        root_cellule->fils[5]=cree_fils(root_cellule,xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,fonction,1,5);
        root_cellule->fils[6]=cree_fils(root_cellule,xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,fonction,1,6);
        root_cellule->fils[7]=cree_fils(root_cellule,xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,fonction,1,7);
        }
   else {root_cellule->feuille=1;TPL_OCTREE<A,A>::lst_entite_feuille.ajouter(root_cellule);}
   }
 
virtual TPL_CELLULE_OCTREE<A ,A>* cree_fils(TPL_CELLULE_OCTREE<A ,A>* cell,double xmin,double ymin,double zmin,double dx,double dy,double dz,B &fonction,int niv,int st)
   {
   TPL_CELLULE_OCTREE<A ,A>* cellule=new TPL_CELLULE_OCTREE<A ,A>(cell,xmin,ymin,zmin,xmin+dx,ymin+dy,zmin+dz,niv,st);
   TPL_OCTREE<A,A>::lst_entite_cellule.ajouter(cellule);
    if (TPL_OCTREE<A,A>::niveaumax<niv) TPL_OCTREE<A,A>::niveaumax=niv;
    double ddx=cellule->boite.get_xmax()-cellule->boite.get_xmin();
   double ddy=cellule->boite.get_ymax()-cellule->boite.get_ymin();
   double ddz=cellule->boite.get_zmax()-cellule->boite.get_zmin();
   double d=dx;
   if (ddy>d) d=ddy;
   if (ddz>d) d=ddz;
   double xyz[3];
   cellule->boite.get_centre(xyz);
   double ecart[9];
   fonction.evaluer(xyz,ecart);
   double dcible=coef/sqrt(ecart[0]);
   if (dcible<d)
        {
        cellule->feuille=0;
        cellule->fils[0]=cree_fils(cellule,xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,fonction,niv+1,0);
        cellule->fils[1]=cree_fils(cellule,xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,fonction,niv+1,1);
        cellule->fils[2]=cree_fils(cellule,xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,fonction,niv+1,2);
        cellule->fils[3]=cree_fils(cellule,xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,fonction,niv+1,3);
        cellule->fils[4]=cree_fils(cellule,xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,fonction,niv+1,4);
        cellule->fils[5]=cree_fils(cellule,xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,fonction,niv+1,5);
        cellule->fils[6]=cree_fils(cellule,xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,fonction,niv+1,6);
        cellule->fils[7]=cree_fils(cellule,xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,fonction,niv+1,7);
        }
   else {cellule->feuille=1;TPL_OCTREE<A,A>::lst_entite_feuille.ajouter(cellule);}
   return cellule;
   }
};
 
 
template <class A,class B>
class TPL_NTREE_FCT:public TPL_OCTREE<A,A>
{
private:
double coef;
 
public:
TPL_NTREE_FCT():TPL_OCTREE<A,A>(),coef(1.) {};
virtual ~TPL_NTREE_FCT() {}
 
 
virtual void change_coefficent_multiplicateur(double val) {coef=val;};
 
virtual void initialiser(B &fonction,double xmin,double ymin,double zmin,double xmax,double ymax,double zmax)
   {
   TPL_CELLULE_OCTREE<A ,A>* root_cellule=new TPL_CELLULE_OCTREE<A ,A>(NULL,xmin,ymin,zmin,xmax,ymax,zmax,0,-1);
   TPL_OCTREE<A,A>::lst_entite_cellule.ajouter(root_cellule);
   double dx=root_cellule->boite.get_xmax()-root_cellule->boite.get_xmin();
   double dy=root_cellule->boite.get_ymax()-root_cellule->boite.get_ymin();
   double dz=root_cellule->boite.get_zmax()-root_cellule->boite.get_zmin();
   double xyz[3];
   root_cellule->boite.get_centre(xyz);
   double ecart[9];
   fonction.evaluer(xyz,ecart);
   double dcible=coef/sqrt(ecart[0]);
   int ndivx=2,ndivy=2,ndivz=2;
   if (dcible>dx) ndivx=1;
   if (dcible>dy) ndivy=1;
   if (dcible>dz) ndivz=1;
   if (ndivx*ndivy*ndivz!=1)
        {
        root_cellule->feuille=0;
        for (int i=0;i<ndivx;i++)
            for (int j=0;j<ndivy;j++)
                  for (int k=0;k<ndivz;k++)
                      root_cellule->fils[((i*ndivx)+j)*ndivy+k]=cree_fils(root_cellule,xmin+i*1.0/ndivx*dx,ymin+j*1.0/ndivy*dy,zmin+k*1.0/ndivz*dz,dx*1./ndivx,dy*1./ndivy,dz*1./ndivz,fonction,1,0);
        }
   else {root_cellule->feuille=1;TPL_OCTREE<A,A>::lst_entite_feuille.ajouter(root_cellule);}
   }
 
virtual TPL_CELLULE_OCTREE<A ,A>* cree_fils(TPL_CELLULE_OCTREE<A ,A>* cell,double xmin,double ymin,double zmin,double dx,double dy,double dz,B &fonction,int niv,int st)
   {
   TPL_CELLULE_OCTREE<A ,A>* cellule=new TPL_CELLULE_OCTREE<A ,A>(cell,xmin,ymin,zmin,xmin+dx,ymin+dy,zmin+dz,niv,st);
   TPL_OCTREE<A,A>::lst_entite_cellule.ajouter(cellule);
    if (TPL_OCTREE<A,A>::niveaumax<niv) TPL_OCTREE<A,A>::niveaumax=niv;
    double ddx=cellule->boite.get_xmax()-cellule->boite.get_xmin();
   double ddy=cellule->boite.get_ymax()-cellule->boite.get_ymin();
   double ddz=cellule->boite.get_zmax()-cellule->boite.get_zmin();
   double xyz[3];
   cellule->boite.get_centre(xyz);
   double ecart[9];
   fonction.evaluer(xyz,ecart);
   double dcible=coef/sqrt(ecart[0]);
   int ndivx=2,ndivy=2,ndivz=2;
   if (dcible>dx) ndivx=1;
   if (dcible>dy) ndivy=1;
   if (dcible>dz) ndivz=1;
   if (ndivx*ndivy*ndivz!=1)
        {
        cellule->feuille=0;
        for (int i=0;i<ndivx;i++)
            for (int j=0;j<ndivy;j++)
                  for (int k=0;k<ndivz;k++)
                      cellule->fils[((i*ndivx)+j)*ndivy+k]=cree_fils(cellule,xmin+i*1.0/ndivx*dx,ymin+j*1.0/ndivy*dy,zmin+k*1.0/ndivz*dz,dx*1./ndivx,dy*1./ndivy,dz*1./ndivz,fonction,1,0);
        }
   else {cellule->feuille=1;TPL_OCTREE<A,A>::lst_entite_feuille.ajouter(cellule);}
   return cellule;
   }
};
 
 
 
 
 
 
 
 
 
 template <class A,class CONDITION,class B>
class TPL_OCTREE_INFO:public OCTREE_BASE
{
public:
TPL_OCTREE_INFO() {};
virtual ~TPL_OCTREE_INFO()
{
   for (int i1=0;i1<lst_entite_cellule.get_nb();i1++)
   {
   TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=lst_entite_cellule.get(i1);
   delete cellule;
   }
};
 
virtual int get_nb_cellule(void) {return lst_entite_cellule.get_nb();};
 
virtual BOITE_3D get_boite_de_base(void) {return lst_entite_cellule.get(0)->get_boite();};
 
virtual TPL_CELLULE_INFO<A,CONDITION,B>* get_cellule(int num) {return lst_entite_cellule.get(num); };
 
 
virtual void initialiser(TPL_LISTE_ENTITE<CONDITION>* lst_entite,int nombre,double xmin,double ymin,double zmin,double xmax,double ymax,double zmax)
   {
   TPL_CELLULE_INFO<A ,CONDITION,B>* root_cellule=new TPL_CELLULE_INFO<A ,CONDITION,B>(xmin,ymin,zmin,xmax,ymax,zmax);
   lst_entite_cellule.ajouter(root_cellule);
   for (int i=0;i<lst_entite->get_nb();i++)
      {
      CONDITION cond=lst_entite->get(i);
      BOITE_3D boite_cond=cond->get_boite_3D();
      if (boite_cond*root_cellule->boite) root_cellule->lst_entite_CONDITION.ajouter(cond);
      }
   if (root_cellule->lst_entite_CONDITION.get_nb()>nombre)
      {
      root_cellule->feuille=0;
      double dx=xmax-xmin;
      double dy=ymax-ymin;
      double dz=zmax-zmin;
      root_cellule->fils[0]=cree_fils(xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
      root_cellule->fils[1]=cree_fils(xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
      root_cellule->fils[2]=cree_fils(xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
      root_cellule->fils[3]=cree_fils(xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
      root_cellule->fils[4]=cree_fils(xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
      root_cellule->fils[5]=cree_fils(xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
      root_cellule->fils[6]=cree_fils(xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
      root_cellule->fils[7]=cree_fils(xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
      }
   else root_cellule->feuille=1;
   for (int j=0;j<lst_entite_cellule.get_nb();j++)
      {
         TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=lst_entite_cellule.get(j);
         cellule->lst_entite_CONDITION.vide();
      }
   }
 
virtual void initialiser(TPL_MAP_ENTITE<CONDITION>* lst_entite,int nombre,double xmin,double ymin,double zmin,double xmax,double ymax,double zmax)
   {
   TPL_CELLULE_INFO<A ,CONDITION,B>* root_cellule=new TPL_CELLULE_INFO<A ,CONDITION,B>(xmin,ymin,zmin,xmax,ymax,zmax);
   lst_entite_cellule.ajouter(root_cellule);
   for (int i=0;i<lst_entite->get_nb();i++)
      {
      CONDITION cond=lst_entite->get(i);
      BOITE_3D boite_cond=cond->get_boite_3D();
      if (boite_cond*root_cellule->boite) root_cellule->lst_entite_CONDITION.ajouter(cond);
      }
   if (root_cellule->lst_entite_CONDITION.get_nb()>nombre)
      {
      root_cellule->feuille=0;
      double dx=xmax-xmin;
      double dy=ymax-ymin;
      double dz=zmax-zmin;
      root_cellule->fils[0]=cree_fils(xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
      root_cellule->fils[1]=cree_fils(xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
      root_cellule->fils[2]=cree_fils(xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
      root_cellule->fils[3]=cree_fils(xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
      root_cellule->fils[4]=cree_fils(xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
      root_cellule->fils[5]=cree_fils(xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
      root_cellule->fils[6]=cree_fils(xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
      root_cellule->fils[7]=cree_fils(xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(root_cellule->lst_entite_CONDITION),nombre);
      }
   else root_cellule->feuille=1;
   for (int j=0;j<lst_entite_cellule.get_nb();j++)
      {
         TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=lst_entite_cellule.get(j);
         cellule->lst_entite_CONDITION.vide();
      }
   }
 
virtual void initialiser(OCTREE_BASE* oc)
{
 BOITE_3D boite=oc->get_cellule(0)->get_boite();
 double xmin=boite.get_xmin();
 double xmax=boite.get_xmax();
 double ymin=boite.get_ymin();
 double ymax=boite.get_ymax();
 double zmin=boite.get_zmin();
 double zmax=boite.get_zmax();
 TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=new TPL_CELLULE_INFO<A ,CONDITION,B>(xmin,ymin,zmin,xmax,ymax,zmax);
 lst_entite_cellule.ajouter(cellule);
 if (oc->get_cellule(0)->get_feuille()==0)
 {
 cellule->fils[0]=cree_fils(oc->get_cellule(0)->get_fils(0));
 cellule->fils[1]=cree_fils(oc->get_cellule(0)->get_fils(1));
 cellule->fils[2]=cree_fils(oc->get_cellule(0)->get_fils(2));
 cellule->fils[3]=cree_fils(oc->get_cellule(0)->get_fils(3));
 cellule->fils[4]=cree_fils(oc->get_cellule(0)->get_fils(4));
 cellule->fils[5]=cree_fils(oc->get_cellule(0)->get_fils(5));
 cellule->fils[6]=cree_fils(oc->get_cellule(0)->get_fils(6));
 cellule->fils[7]=cree_fils(oc->get_cellule(0)->get_fils(7));
 }
 cellule->feuille=oc->get_cellule(0)->get_feuille();
};
 
 
TPL_CELLULE_INFO<A,CONDITION,B>* cree_fils(CELLULE_OCTREE_BASE *cellule_base)
{
 BOITE_3D boite=cellule_base->get_boite();
 double xmin=boite.get_xmin();
 double xmax=boite.get_xmax();
 double ymin=boite.get_ymin();
 double ymax=boite.get_ymax();
 double zmin=boite.get_zmin();
 double zmax=boite.get_zmax();
 TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=new TPL_CELLULE_INFO<A ,CONDITION,B>(xmin,ymin,zmin,xmax,ymax,zmax);
 lst_entite_cellule.ajouter(cellule);
 if (cellule_base->get_feuille()==1)
 {
 cellule->feuille=1;
 }
 else
 {
 cellule->fils[0]=cree_fils(cellule_base->get_fils(0));
 cellule->fils[1]=cree_fils(cellule_base->get_fils(1));
 cellule->fils[2]=cree_fils(cellule_base->get_fils(2));
 cellule->fils[3]=cree_fils(cellule_base->get_fils(3));
 cellule->fils[4]=cree_fils(cellule_base->get_fils(4));
 cellule->fils[5]=cree_fils(cellule_base->get_fils(5));
 cellule->fils[6]=cree_fils(cellule_base->get_fils(6));
 cellule->fils[7]=cree_fils(cellule_base->get_fils(7));
 cellule->feuille=0;
 }
return cellule;
};
 
virtual TPL_CELLULE_INFO<A ,CONDITION,B>* cree_fils(double xmin,double ymin,double zmin,double dx,double dy,double dz,TPL_LISTE_ENTITE<CONDITION>* lst_entite,int nombre)
   {
   TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=new TPL_CELLULE_INFO<A ,CONDITION,B>(xmin,ymin,zmin,xmin+dx,ymin+dy,zmin+dz);
   lst_entite_cellule.ajouter(cellule);
   for (int i=0;i<lst_entite->get_nb();i++)
      {
      CONDITION cond=lst_entite->get(i);
      BOITE_3D boite_cond=cond->get_boite_3D();
      if (boite_cond*cellule->boite) cellule->lst_entite_CONDITION.ajouter(cond);
      }
    if (cellule->lst_entite_CONDITION.get_nb()>nombre)
      {
      cellule->feuille=0;
      cellule->fils[0]=cree_fils(xmin,ymin,zmin,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre);
      cellule->fils[1]=cree_fils(xmin+dx/2.,ymin,zmin,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre);
      cellule->fils[2]=cree_fils(xmin,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre);
      cellule->fils[3]=cree_fils(xmin+dx/2.,ymin+dy/2.,zmin,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre);
      cellule->fils[4]=cree_fils(xmin,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre);
      cellule->fils[5]=cree_fils(xmin+dx/2.,ymin,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre);
      cellule->fils[6]=cree_fils(xmin,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre);
      cellule->fils[7]=cree_fils(xmin+dx/2.,ymin+dy/2.,zmin+dz/2.,dx/2.,dy/2.,dz/2.,&(cellule->lst_entite_CONDITION),nombre);
      }
   else cellule->feuille=1;
   return cellule;
   }
 
 
virtual void rechercher(BOITE_3D& boite,TPL_MAP_ENTITE<A>& liste_entite_trouve,TPL_CELLULE_INFO<A ,CONDITION,B>* cellule)
{
if (boite*cellule->boite)
 if (cellule->feuille==1)
 {
 for (int i=0;i<cellule->lst_entite_A.get_nb();i++)
        if (boite*cellule->lst_entite_A.get(i)->get_boite_3D())
          liste_entite_trouve.ajouter(cellule->lst_entite_A.get(i));
 }
else
 {
 rechercher(boite,liste_entite_trouve,cellule->fils[0]);
 rechercher(boite,liste_entite_trouve,cellule->fils[1]);
 rechercher(boite,liste_entite_trouve,cellule->fils[2]);
 rechercher(boite,liste_entite_trouve,cellule->fils[3]);
 rechercher(boite,liste_entite_trouve,cellule->fils[4]);
 rechercher(boite,liste_entite_trouve,cellule->fils[5]);
 rechercher(boite,liste_entite_trouve,cellule->fils[6]);
 rechercher(boite,liste_entite_trouve,cellule->fils[7]);
 }
};
 
 
virtual void get_cellule(BOITE_3D& boite,TPL_CELLULE_INFO<A ,CONDITION,B>* cellule,TPL_MAP_ENTITE<TPL_CELLULE_INFO<A ,CONDITION,B> * > &liste_entite)
{
if (boite*cellule->boite)
 if (cellule->feuille==1)
 {
      liste_entite.ajouter(cellule);
 }
else
 {
 get_cellule(boite,cellule->fils[0],liste_entite);
 get_cellule(boite,cellule->fils[1],liste_entite);
 get_cellule(boite,cellule->fils[2],liste_entite);
 get_cellule(boite,cellule->fils[3],liste_entite);
 get_cellule(boite,cellule->fils[4],liste_entite);
 get_cellule(boite,cellule->fils[5],liste_entite);
 get_cellule(boite,cellule->fils[6],liste_entite);
 get_cellule(boite,cellule->fils[7],liste_entite);
 }
};
 
virtual TPL_CELLULE_INFO<A,CONDITION,B> *get_cellule(double x,double y, double z)
{
BOITE_3D boite(x,y,z,x,y,z);
TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=lst_entite_cellule.get(0);
TPL_MAP_ENTITE<TPL_CELLULE_INFO<A ,CONDITION,B> * > liste_cellule;
get_cellule(boite,cellule,liste_cellule);
if (liste_cellule.get_nb()==1) return liste_cellule.get(0);
return NULL;
};
 
 
virtual void rechercher(double xcentre,double ycentre,double zcentre,double rayon_recherche,TPL_MAP_ENTITE<A>& liste_entite_trouve)
{
BOITE_3D boite(xcentre-rayon_recherche,ycentre-rayon_recherche,zcentre-rayon_recherche,xcentre+rayon_recherche,ycentre+rayon_recherche,zcentre+rayon_recherche);
TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=lst_entite_cellule.get(0);
rechercher(boite,liste_entite_trouve,cellule);
};
 
 
 
virtual void inserer(BOITE_3D& boite,A a,TPL_CELLULE_INFO<A ,CONDITION,B>* cellule)
{
if (boite*cellule->boite)
 if (cellule->feuille==1)
 {
 cellule->lst_entite_A.ajouter(a);
 }
else
 {
 inserer(boite,a,cellule->fils[0]);
 inserer(boite,a,cellule->fils[1]);
 inserer(boite,a,cellule->fils[2]);
 inserer(boite,a,cellule->fils[3]);
 inserer(boite,a,cellule->fils[4]);
 inserer(boite,a,cellule->fils[5]);
 inserer(boite,a,cellule->fils[6]);
 inserer(boite,a,cellule->fils[7]);
 }
};
 
virtual void supprimer(BOITE_3D& boite,A a,TPL_CELLULE_INFO<A ,CONDITION,B>* cellule)
{
if (boite*cellule->boite)
 if (cellule->feuille==1)
 {
 cellule->lst_entite_A.supprimer(a);
 }
else
 {
 supprimer(boite,a,cellule->fils[0]);
 supprimer(boite,a,cellule->fils[1]);
 supprimer(boite,a,cellule->fils[2]);
 supprimer(boite,a,cellule->fils[3]);
 supprimer(boite,a,cellule->fils[4]);
 supprimer(boite,a,cellule->fils[5]);
 supprimer(boite,a,cellule->fils[6]);
 supprimer(boite,a,cellule->fils[7]);
 }
};
 
virtual void inserer(A a)
{
BOITE_3D boite=a->get_boite_3D();
TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=lst_entite_cellule.get(0);
inserer(boite,a,cellule);
}
 
virtual void supprimer(A a)
{
BOITE_3D boite=a->get_boite_3D();
TPL_CELLULE_INFO<A ,CONDITION,B>* cellule=lst_entite_cellule.get(0);
supprimer(boite,a,cellule);
}
 
 
private:
TPL_LISTE_ENTITE<TPL_CELLULE_INFO<A ,CONDITION,B>* > lst_entite_cellule;
 
};
 
 
 
 
#endif