kd-tree

kd-tree - Algo - Programmation

Marsh Posté le 21-06-2005 à 13:03:33    

:hello: Salut tous le monde
j' ai un espace de données, je veux le subdiviser en utilisant la meme démarche que le kd-tree,mais sans passer par une structure arborescente.
 :bounce: est ce que quelqu'un à une idée?

Reply

Marsh Posté le 21-06-2005 à 13:03:33   

Reply

Marsh Posté le 21-06-2005 à 13:34:06    

Incrémente ta verbosité, merci :)


---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.
Reply

Marsh Posté le 21-06-2005 à 14:09:59    

ok, je vais eéclaircir un peu plus le problème, kd-tree est une structure de données baseée sur la subdivision récursive de l'espace de données en des régions hyper-rectangles disjoites,parmis les statéges de division, la division standard, elle subdivise l'espace de données suivant la médiane des coordonnés de S (S ensemble de donnée).
je cherche à implémenter cette structure sans passer par une structure arborescente, j'ai fait un premier essai et je veux l'améliorer, voici la fonction utiliser:

Code :
  1. RegionApprox* Region::SplitRegion(char *fich,float xmin,float xmax,float ymin,float ymax,int Dimbase, int comp, int niv,int *nbreg,float *X)
  2. {// la condition d'arret au min une donnée par region
  3. RegionApprox *reg;
  4. float xma=0,yma=0;
  6.  cout<<"niv= "<<niv<<endl;
  8. if (comp>=3)
  10. {  
  11.      cout<<"nbrereg= "<<*nbreg<<endl;
  12.   niv++;//le niveau
  13.   cout<<"niv= "<<niv<<endl;
  14.   if (niv%2!=0)// on traite les x
  15.   {
  16.     
  17.      reg=new RegionApprox[*nbreg];
  18.  cout<<"test00:0: "<<(*nbreg)<<endl;
  19.   reg[(*nbreg)].rect[0]=xmin;
  20.   //cout<<"vvvvvvvvvxxxxxxxxxxx"<<(*nbreg)<<endl;
  21.   xma=xmax;
  22.   xmax=Subdivisionx(fich,Dimbase,X,xmin,xmax,ymin,ymax,8);
  23.   cout<<"subx= "<<xmax<<endl;
  24.   reg[(*nbreg)].rect[1]=xmax;
  25.   if(yma==0)
  26.    {
  27.      reg[(*nbreg)].rect[2]=ymin;
  28.         reg[(*nbreg)].rect[3]=ymax;
  29.    }
  30.   (*nbreg)++;
  31.  cout<<"test01:1: "<<(*nbreg)<<endl;
  32.   reg[(*nbreg)].rect[0]=xmax;
  33.   reg[(*nbreg)].rect[1]=xma;
  34.   if(yma==0)
  35.    {
  36.      reg[(*nbreg)].rect[2]=ymin;
  37.         reg[(*nbreg)].rect[3]=ymax;
  38.    }
  40.   //(*nbreg)++;
  41.        comp=NumberDataperRegionx(Dimbase,xmin,xmax,ymin,ymax,8,fich,X);
  42.   cout<<"NumberDataperRegionxgauche= "<<comp<<endl;
  44.   cout<<"*************la region de gauche*********** "<<endl;
  45.   SplitRegion(fich,xmin,xmax,ymin,ymax,Dimbase,comp,niv,nbreg,X);
  47.   cout<<"**********la region de droite************** "<<endl;
  49.   comp=NumberDataperRegionx(Dimbase,xmax,xma,ymin,ymax,8,fich,X);
  50.   cout<<"NumberDataperRegionxdroite= "<<comp<<endl;
  52.   SplitRegion(fich,xmax,xma,ymin,ymax,Dimbase,comp,niv,nbreg,X);
  54.   }
  57. else
  58. {
  59.    cout<<"**********on traite les y************"<<endl;
  60.    (*nbreg)--;
  62.  cout<<"test10: "<<(*nbreg)<<endl;
  63.    reg=new RegionApprox[*nbreg];
  64.    yma=ymax;
  65.    ymax=Subdivisiony(fich,Dimbase,X,xmin,xmax,ymin,ymax,8);cout<<"suby= "<<ymax<<endl;
  66.    reg[(*nbreg)].rect[2]=ymin;
  67.       reg[(*nbreg)].rect[3]=ymax;
  69.    (*nbreg)++;
  70.       reg[(*nbreg)].rect[2]=yma;
  71.    reg[(*nbreg)].rect[3]=yma;
  73.    (*nbreg)++;
  75.         comp=NumberDataperRegiony(Dimbase,xmin,xmax,ymin,ymax,8,fich,X);
  76.    cout<<"comptg= "<<comp<<endl;
  77.    cout<<"*************la region de gauche*********** "<<endl;
  78.    SplitRegion(fich,xmin,xmax,ymin,ymax,Dimbase,comp,niv,nbreg,X);
  79.    cout<<"**********la region de droite************** "<<endl;
  80.    comp=NumberDataperRegiony(Dimbase,xmin,xmax,ymax,yma,8,fich,X);
  81.    cout<<"comptd= "<<comp<<endl;
  82.    SplitRegion(fich,xmin,xmax,ymax,yma,Dimbase,comp,niv,nbreg,X);
  83.    niv++;
  84.    *nbreg++;
  85.   
  86. }
  88. }
  90. return reg;
  91. }

 
remarque: je suppose que la subdivision aura lieu si le nombre de données est >=3(on aura des région de 3 données)
 

Reply

Marsh Posté le 21-06-2005 à 14:16:04    

(detail : ton indentation est foireuse :/)
 
Je vois ce qu'est un Kd-tree, mais je capte pas vraiment ce que tu veut faire :/


---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.
Reply

Marsh Posté le 21-06-2005 à 14:28:16    

je veux éaiser une fonction qui  
1.lit les données d'un fichier(les données sont référencées par leurs coordonnées)
2.subdiviser l'espace de données suivant la distribution des données dans l'espace)
donc en entree on a le fichier de données, l'espace de données.
en sortie on a des régions disjointes bien référencés.

Reply

Marsh Posté le 04-07-2005 à 21:56:33    

Tu peux me dire quel est l'intérêt de ne pas utiliser une structure arborescente ?  [:figti]


Message édité par Giz le 04-07-2005 à 21:56:47
Reply

Marsh Posté le 27-07-2005 à 21:55:22    

ca c'est une trés bonne question!!
dans mon implémentation j'utilise une structure d'index basée sur liste triées, si j'utilise les arbres je dois passer par une structure intermédiaire pour exlpoiter la stucture d'index en question voila c ca.
c convainquant ou non?????????

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed