Algo

kd-tree

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : kd-tree

d_imane

: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?

Publicité

0x90

→

Incrémente ta verbosité, merci

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

d_imane

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 :

RegionApprox* Region::SplitRegion(char *fich,float xmin,float xmax,float ymin,float ymax,int Dimbase, int comp, int niv,int *nbreg,float *X)
{// la condition d'arret au min une donnée par region
RegionApprox *reg;
float xma=0,yma=0;
cout<<"niv= "<<niv<<endl;
if (comp>=3)
{
cout<<"nbrereg= "<<*nbreg<<endl;
niv++;//le niveau
cout<<"niv= "<<niv<<endl;
if (niv%2!=0)// on traite les x
{
reg=new RegionApprox[*nbreg];
cout<<"test00:0: "<<(*nbreg)<<endl;
reg[(*nbreg)].rect[0]=xmin;
//cout<<"vvvvvvvvvxxxxxxxxxxx"<<(*nbreg)<<endl;
xma=xmax;
xmax=Subdivisionx(fich,Dimbase,X,xmin,xmax,ymin,ymax,8);
cout<<"subx= "<<xmax<<endl;
reg[(*nbreg)].rect[1]=xmax;
if(yma==0)
{
reg[(*nbreg)].rect[2]=ymin;
reg[(*nbreg)].rect[3]=ymax;
}
(*nbreg)++;
cout<<"test01:1: "<<(*nbreg)<<endl;
reg[(*nbreg)].rect[0]=xmax;
reg[(*nbreg)].rect[1]=xma;
if(yma==0)
{
reg[(*nbreg)].rect[2]=ymin;
reg[(*nbreg)].rect[3]=ymax;
}
//(*nbreg)++;
comp=NumberDataperRegionx(Dimbase,xmin,xmax,ymin,ymax,8,fich,X);
cout<<"NumberDataperRegionxgauche= "<<comp<<endl;
cout<<"*************la region de gauche*********** "<<endl;
SplitRegion(fich,xmin,xmax,ymin,ymax,Dimbase,comp,niv,nbreg,X);
cout<<"**********la region de droite************** "<<endl;
comp=NumberDataperRegionx(Dimbase,xmax,xma,ymin,ymax,8,fich,X);
cout<<"NumberDataperRegionxdroite= "<<comp<<endl;
SplitRegion(fich,xmax,xma,ymin,ymax,Dimbase,comp,niv,nbreg,X);
}
else
{
cout<<"**********on traite les y************"<<endl;
(*nbreg)--;
cout<<"test10: "<<(*nbreg)<<endl;
reg=new RegionApprox[*nbreg];
yma=ymax;
ymax=Subdivisiony(fich,Dimbase,X,xmin,xmax,ymin,ymax,8);cout<<"suby= "<<ymax<<endl;
reg[(*nbreg)].rect[2]=ymin;
reg[(*nbreg)].rect[3]=ymax;
(*nbreg)++;
reg[(*nbreg)].rect[2]=yma;
reg[(*nbreg)].rect[3]=yma;
(*nbreg)++;
comp=NumberDataperRegiony(Dimbase,xmin,xmax,ymin,ymax,8,fich,X);
cout<<"comptg= "<<comp<<endl;
cout<<"*************la region de gauche*********** "<<endl;
SplitRegion(fich,xmin,xmax,ymin,ymax,Dimbase,comp,niv,nbreg,X);
cout<<"**********la region de droite************** "<<endl;
comp=NumberDataperRegiony(Dimbase,xmin,xmax,ymax,yma,8,fich,X);
cout<<"comptd= "<<comp<<endl;
SplitRegion(fich,xmin,xmax,ymax,yma,Dimbase,comp,niv,nbreg,X);
niv++;
*nbreg++;
}
}
return reg;
}

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)

0x90

→

(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.

d_imane

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.

Giz

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

d_imane

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?????????

FORUM HardWare.fr

Programmation

Algo

kd-tree

Sujets relatifs
Perte de puissance avec Tk::Tree	algorithme de subdivision k-D-B tree
implémentation du VA_FILE et Pyramid-Tree	[VB6] Pbe sur Tree View
menu arborescence (tree)	Tree [JS + CSS]
b-arbre (b-tree)	Algorithme de B-Tree
red black tree song	[3D] BSP Tree
Plus de sujets relatifs à : kd-tree

Page générée en 0.062 secondes