QuadTree ... help !!!!!

QuadTree ... help !!!!! - C - Programmation

Marsh Posté le 06-12-2005 à 18:03:56    

salut,
 
j'ai besoin de faire une implémentation quadtree mais je sais pas comment m'y prendre. Quelqu'un peut-il faire le travail a ma place et me donner le code tout fait, gratuitement ? Quelques explications seraient un plus ...ainsi qu'un code bien commenté et indenté. Merci ... Pour ceux qui souhaiteraient me donner un peu d'argent en guise de gratitude je ferait tout mon possible pour qu'il puissent le faire :D  
 
 
plus serieusement, je comprend pas la méthode.  J'ai déja programmé des arbres binaires, tas, graphes, mais pour les quadtree je suis un peu bloqué pour le parcours,etc. Chaque feuille de mon quadtree a sois  
 
- pas de fils
- 4 fils
 
Quelqu'un saurait-il ou je peux trouver l'explication de l'algo ? j'ai déja fait mes structures, je les mets :
 

Code :
  1. typedef struct data {
  3.   int m_cx; // centre de la feuille en x
  4.   int m_cy; // centre de la feuille en y
  6.   int m_sx; //moitié en largeur
  7.   int m_sy; //moitié en hauteur
  9. }data;
  12. typedef struct leaf {
  14.   data *coords;
  16.   struct leaf * LP; //feuille parente
  17.   struct leaf * L1; //feuille 1,2,3,4 = fils
  18.   struct leaf * L2;
  19.   struct leaf * L3;
  20.   struct leaf * L4;
  22. }leaf;
  24. typedef struct quadtree {
  26.   leaf * root; // la racine du quadtree
  28. }quadtree;


 
 
 :love:  :love:  :love: Merci par avance  :love:  :love:  :love:  :love:
 
 
ps : heu ... si vous etes ok pour la premiere option ca marche toujours  :lol:


Message édité par in_your_phion le 06-12-2005 à 18:10:02
Reply

Marsh Posté le 06-12-2005 à 18:03:56   

Reply

Marsh Posté le 06-12-2005 à 18:09:54    

dans le quadtree, y'a pas une historie de parcourt en Z récursive?

Reply

Marsh Posté le 06-12-2005 à 19:04:22    

Citation :

Quelqu'un peut-il faire le travail a ma place et me donner le code tout fait, gratuitement ?

Non.

Citation :

Quelqu'un saurait-il ou je peux trouver l'explication de l'algo ?

Lequel? celui de parcours? C'est un bete parcours recursif d'arbre a la base.
A+,

Message cité 1 fois
Message édité par gilou le 06-12-2005 à 19:07:37

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 06-12-2005 à 19:20:52    

gilou a écrit :

Citation :

Quelqu'un peut-il faire le travail a ma place et me donner le code tout fait, gratuitement ?

Non.


Ca, je pense que c'était de l'humour...


---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/
Reply

Marsh Posté le 06-12-2005 à 20:00:42    


il te faut deux précidats :  

  • 1 qui te dit si une leaf a des leaf ou pas, appellons

le bool hasChildren(leaf*)

  • 1 qui te dit si un noeud (leaf*) recouvre un point p ou pas,  

appellons le bool isLeafOver(leaf*,int,int)
 
si le prédicat 2 est bien implémenté tu n'as pas besoin du 1
 
ensuite le parcours est tout simple, par exemple :
 
leaf *find(leaf*src,int x,int y)
{
 if(hasChildren(src))
 {
  if(isLeafOver(src->L1,x,y))
  {
   retun find(src->L1,x,y);
  } // x4...
 }
 else
 {
  return isLeafOver(src,x,y)?src:NULL;
 }
}
 
tu peux aussi gagner à représenter tes feuilles dans un tableau, un joli desing devrait te permettre de passer en 3D en un clin d'oeil

Message cité 1 fois
Reply

Marsh Posté le 07-12-2005 à 11:06:34    

fra0 a écrit :

il te faut deux précidats :  

  • 1 qui te dit si une leaf a des leaf ou pas, appellons

le bool hasChildren(leaf*)

  • 1 qui te dit si un noeud (leaf*) recouvre un point p ou pas,  

appellons le bool isLeafOver(leaf*,int,int)
 
si le prédicat 2 est bien implémenté tu n'as pas besoin du 1
 
ensuite le parcours est tout simple, par exemple :
 
leaf *find(leaf*src,int x,int y)
{
 if(hasChildren(src))
 {
  if(isLeafOver(src->L1,x,y))
  {
   retun find(src->L1,x,y);
  } // x4...
 }
 else
 {
  return isLeafOver(src,x,y)?src:NULL;
 }
}
 
tu peux aussi gagner à représenter tes feuilles dans un tableau, un joli desing devrait te permettre de passer en 3D en un clin d'oeil


 
 
ok merci pour ton aide :) .... en fait le problème que j'ai c'est pour créer la fonction d'insertion d'une nouvelle feuille ... je vois pas comment faire etant donné que j'ai quatre fils a chaque fois !!!  a mon avis je dois faire des opérations pour savoir dans quelle zone je me trouve mais ca m'a l'air super complique !!!! saurais-tu m'aider ?  
 
 
merci bcp par avance  :p  :love:  :whistle:  :)  :hello:  
 

Reply

Marsh Posté le 07-12-2005 à 18:55:14    


tu veux faire quoi avec ton quadtree exactement ?
 
si tu sais pas trop, reprends un de tes arbres binaires
 
transforme tes clés comme ça:
 
x:76543210 y:76543210
 
k:7766554433221100
 
et laisse la magie opérer
 
 
 

Reply

Marsh Posté le 09-12-2005 à 13:04:13    

salut  :)  
 
Merci, en fait j'ai trouvé comment faire .... mais maintenant j'ai un ENOoOoOOooooOOooOooooooOOOOOoooOOOOOOoOOorme problème relatif à la programmation  :cry:  :cry:  :cry:  :cry:  :cry:  :cry:  :cry:  :cry:  :cry:  :cry: c'est in-dé-bu-ga-bl-euh, je comprend pas, je comprend pas, je comprend pas ....je comprend pas. Je met ce que j'ai si une bonne âme veut bien aider c'est vraiment génial  :love:  :love:  :love:  
 
mes structures :
 

Code :
  1. typedef struct data {
  3.   //on a besoin de stocke le centre, et les coins
  4.  
  5.   int * m; // centre de la feuille en m = [x,y]
  6.   //repère image dans le sens trigo
  7.   int *m_c00;
  8.   int *m_c10;
  9.   int *m_c11;
  10.   int *m_c01;
  12. }data;
  15. typedef struct leaf {
  17.   enum {BLACK, WHITE} color; //si c'est blanc on a des fils, si c'est noir on en a pas
  18.  
  19.   data *coords;
  21.   struct leaf * LP; //feuille parente
  22.   struct leaf * L00; //feuille 00,10,11,01 = fils
  23.   struct leaf * L10;
  24.   struct leaf * L11;
  25.   struct leaf * L01;
  27. }leaf;
  29. typedef struct quadtree {
  31.   leaf * root; // la racine du quadtree
  33. }quadtree;


 
 
bon j'usqu'ici ca va ....alors ensuite j'ai crée une fonction qui me pond un alloc pour chaque feuille du quadtree (et son homologue free, etc, je les mets pas ici)  
 

Code :
  1. //je passe le centre et les coins (qui sont enfait des tableau de 2 pour chaque coordonée) et la fonction crée la feuillle
  2. leaf * leaf_alloc(int *m, int *m_c00, int *m_c10, int *m_c11, int *m_c01) {
  3.   leaf * new_leaf;
  5.   if ( (new_leaf = (leaf*)malloc(sizeof(leaf)) ) == NULL ) {
  6.     fprintf(stderr,"ca chie dans la colle" );
  7.   }
  9.   if ( (new_leaf->coords = (data*)malloc(sizeof(data)) ) == NULL ) {
  10.     fprintf(stderr,"ca chie dans la colle" );
  11.   }
  13.   new_leaf->coords->m = m ;
  14.   new_leaf->coords->m_c00 = m_c00 ;
  15.   new_leaf->coords->m_c10 = m_c10 ;
  16.   new_leaf->coords->m_c11 = m_c11 ;
  17.   new_leaf->coords->m_c01 = m_c01 ;
  19.   new_leaf->color = BLACK;
  21.   new_leaf->LP  = NULL;
  22.   new_leaf->L00 = NULL;
  23.   new_leaf->L10 = NULL;
  24.   new_leaf->L11 = NULL;
  25.   new_leaf->L01 = NULL;
  27.   return new_leaf;
  29. }


 
bon alors jusqu'ici tout va bien, jusqu'ici tout va bien ...alors ensuite j'ai crée une fonction que me subdivise une feuille en quatre, cad qui alloue quatre fils avec les nouvelles coordonnées et centre :
 

Code :
  1. void leaf_subdivise(leaf * leaf) {
  2.   //subdivision
  4.   if (!leaf) { // la feuille pointe vers NULL
  6.     fprintf(stderr,"[e] The leaf points to NULL and cannot be subdivided.\n" );
  7.     exit(EXIT_FAILURE);
  9.   } else {
  11.     int * m     = leaf->coords->m    ;
  12.     int * m_c00 = leaf->coords->m_c00;
  13.     int * m_c10 = leaf->coords->m_c10;
  14.     int * m_c11 = leaf->coords->m_c11;
  15.     int * m_c01 = leaf->coords->m_c01;
  17.     leaf->color = WHITE;
  19.     //on travaille dans un repère image, et on tourne dans le sens trigo
  21.     //centre et dimensions
  23.     //les nouveaux coins et centre de L00
  24.     int L00_corner00[2] = {m_c00[0] ,m_c00[1]};
  25.     int L00_corner10[2] = {m_c00[0] ,m[1]    };
  26.     int L00_corner11[2] = {m[0]     ,m[1]    };
  27.     int L00_corner01[2] = {m[0]     ,m_c00[1]};
  29.     int L00_center[2]   = { (L00_corner00[0] + L00_corner01[0])/2, (L00_corner00[1] + L00_corner10[1])/2};
  31.     leaf->L00 = leaf_alloc(
  32. L00_center,
  33. L00_corner00,
  34. L00_corner10,
  35. L00_corner11,
  36. L00_corner01
  37. );
  39.     leaf->L00->LP = leaf;
  41.        
  42. //bon apres je fais pareil pour les 3 autres fils je détaille pas c'est pareil.
  44. // ....la la la promenons nous dans les champs, donc ...
  45. }
  46. }


 
bon alors la ca va encore !!!!!!! Mais le big problème, c'est que dans le main,
 
je fais :
 

Code :
  1. int main(int argc,char *argv[])
  2. {
  5. quadtree * TREE = (quadtree*)malloc(sizeof(quadtree));
  7.   int center[2] =  {imageX/2,imageY/2}; //bon ca c'est les coordonées de la feuille de départ, i.e mon image
  8.   int c00   [2] =  {0,0};
  9.   int c10   [2] =  {0,imageY};
  10.   int c11   [2] =  {imageX,imageY};
  11.   int c01   [2] =  {imageX,0};
  12.  
  13.   TREE->root = leaf_alloc(center,c00,c10,c11,c01);
  14.  
  15. //la j'appelle leaf subdivise pour tester sur une itération ... ca marche !!
  16.   leaf_subdivise(TREE->root);
  18. ...


 
donc jusque la ca marche, je récupère bien ma feuille qui est subdivisée avec les nouvelles coordonées pour chacun des fils, mais ensuite j'appelle une fonction  
 

Code :
  1. dessine_moi_un_quadtree (quadtree * qt, char * lenome);


 
 
Et là .... je récupère bien mon quadtre avec ces noeuds, sauf que les coordonées sont completements pas bonnes du tous, il me sort ds valeurs du genre {-1073747544,1074402066}  ...pourquoi ca marche pas alors que juste avant j'ai bien récupéré ma feuille subdivisée ????
est ce que ca vient de mes structures ? je dois mettre des tableaux ou des int * ???? je comprends plus rien .... si qqu'un peut m'aider please please please
 
 :love:  :love:  :love:  :love:  :love: merci par avance  :love:  :love:  :love:  :love:  :love:

Reply

Marsh Posté le 09-12-2005 à 15:12:44    

Peut être pasque l'erreur est dans dessine_moi_un_quadtree? T'as le code?

Message cité 1 fois

---------------
« Le hasard, c’est différent de la chance. Parce que la chance, je n'en ai jamais. »
Reply

Marsh Posté le 09-12-2005 à 15:16:22    

kaloskagatos a écrit :

Peut être pasque l'erreur est dans dessine_moi_un_quadtree? T'as le code?


 
 
salut, ben je crois pas parce que j'ai tout commenté, je fais juste un printf des valeurs des coins, sachant que j'ai fait une subdivision dans le main :
 

Code :
  1. void dessine_moi_un_quadtree (quadtree * qt, char * nom) {
  3.     int * m     = qt->root->L00->coords->m ;
  4.     int * m_c00 = qt->root->L00->coords->m_c00;
  5.     int * m_c10 = qt->root->L00->coords->m_c10;
  6.     int * m_c11 = qt->root->L00->coords->m_c11;
  7.     int * m_c01 = qt->root->L00->coords->m_c01;
  9.      printf("L00 : c00={%d,%d}\tc10={%d,%d}\tc11={%d,%d}\tc01={%d,%d}\tcenter={%d,%d}\tcolor=%d\n",
  10. m_c00[0],m_c00 [1],
  11. m_c10 [0],m_c10 [1],
  12. m_c11 [0], m_c11 [1],
  13. m_c01 [0], m_c01 [1],
  14. m[0],  m[1],qt->root->L00->color
  15. );
  17. }


 
c'est paranormal  :??:  :(


Message édité par in_your_phion le 09-12-2005 à 15:17:17
Reply

Marsh Posté le 09-12-2005 à 15:16:22   

Reply

Marsh Posté le 09-12-2005 à 15:36:24    

Dans ton leaf_subdivise il faut que tu alloues des tableaux  dans le tas au lieu de la pile
 
Parce que dans ton leaf_alloc tu copies les adresses de ces tableaux et pas leurs valeurs. Hors ces tableaux sont détruits à la sortie de  
leaf_subdivise
 
 
Donc fais des malloc pour tes tableaux L00_cornerXX je pense que ça passera
 
edit: ortho

Message cité 1 fois
Message édité par kaloskagatos le 09-12-2005 à 15:55:18

---------------
« Le hasard, c’est différent de la chance. Parce que la chance, je n'en ai jamais. »
Reply

Marsh Posté le 09-12-2005 à 17:09:05    

kaloskagatos a écrit :

Dans ton leaf_subdivise il faut que tu alloues des tableaux  dans le tas au lieu de la pile
 
Parce que dans ton leaf_alloc tu copies les adresses de ces tableaux et pas leurs valeurs. Hors ces tableaux sont détruits à la sortie de  
leaf_subdivise
 
 
Donc fais des malloc pour tes tableaux L00_cornerXX je pense que ça passera
 
edit: ortho


 
 
Ca marche, youpi [:arg]!!!! [:alizean] Merci   :)


Message édité par in_your_phion le 09-12-2005 à 17:10:59
Reply

Marsh Posté le 09-12-2005 à 17:11:34    

:jap:


---------------
« Le hasard, c’est différent de la chance. Parce que la chance, je n'en ai jamais. »
Reply

Sujets relatifs:

Leave a Replay

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