Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 12 sur 12
  1. #1
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 962
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 962
    Points : 16 880
    Points
    16 880

    Par défaut [java] Structure QuadTree

    Une implémentation de la structure QuadTree en Java. Cette structure permet de partitionner un espace 2D sous la forme d'un arbre. Chaque noeud possède 0 ou 4 enfants, suivant la granularité souhaitée pour une région.


    Exemple de partitionnement 2D et le QuadTree correspondant

    Code java :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
     
    import java.util.ArrayList;
    import java.util.List;
     
    /**
     * Cette classe implémente la structure QuadTree
     * 
     * @author Xavier Philippeau
     *
     */
    public class QuadTreeNode {
     
    	// organisation des noeuds enfant:
    	//  _________ 
    	// |    |    |
    	// | NW | NE |           
    	// |____|____|
    	// |    |    |
    	// | SW | SE | 
    	// |____|____| 
     
    	// types de noeuds
    	static final int TYPE_ROOT=-1, TYPE_NW=0, TYPE_NE=1, TYPE_SW=2, TYPE_SE=3;
     
    	// informations utilisées pour la navigation dans le QuadTree
     
    	// types des ancetres communs
    	private static final int[] rightAncestors = new int[] {TYPE_NW,TYPE_SW};
    	private static final int[] leftAncestors  = new int[] {TYPE_NE,TYPE_SE};
    	private static final int[] bottomAncestors= new int[] {TYPE_NW,TYPE_NE};
    	private static final int[] topAncestors   = new int[] {TYPE_SW,TYPE_SE};
     
    	// tableau de symetrie pour l'inversion des chemins
    	private static final int[] horizontalReverter = new int[] {TYPE_NE,TYPE_NW,TYPE_SE,TYPE_SW};
    	private static final int[] verticalReverter   = new int[] {TYPE_SW,TYPE_SE,TYPE_NW,TYPE_NE};
     
    	// types des enfants
    	private static final int[] leftNodes   = new int[] {TYPE_NW,TYPE_SW};
    	private static final int[] rightNodes  = new int[] {TYPE_NE,TYPE_SE};
    	private static final int[] topNodes    = new int[] {TYPE_NW,TYPE_NE};
    	private static final int[] bottomNodes = new int[] {TYPE_SW,TYPE_SE};
    	private static final int[] AllNodes    = new int[] {TYPE_NW,TYPE_NE,TYPE_SW,TYPE_SE};
     
    	// profondeur maximum de l'arbre
    	public static int MAXDEPTH=0;
     
    	// composants du noeud
    	public int type;
    	public int depth;
    	public QuadTreeNode parent;
    	public QuadTreeNode[] children = null;
     
    	public Object object; // champ libre (donnée utilisateur) 
     
    	/** constructeur public (racine de l'arbre) */
    	public QuadTreeNode(Object o) {
    		this.parent = null;
    		this.type = TYPE_ROOT;
    		this.depth = 0;
    		this.object = o;
    	}
     
    	// constructeur privé (utilisé lors du split)
    	private QuadTreeNode(QuadTreeNode parent, int type, Object o) {
    		this.parent = parent;
    		this.type = type;
    		this.depth = parent.depth+1;
    		this.object = o;
    		if (depth>MAXDEPTH) MAXDEPTH=depth;
    	}
     
    	// retourne le noeud voisin d'un noeud (algorithme générique)
    	private static QuadTreeNode sibling(QuadTreeNode node, int[] ancestortype, int[] reverter) {
    		int[] path = new int[MAXDEPTH+1];
    		int pathlength=0;
     
    		// recherche du plus proche ancetre commun
    		QuadTreeNode ancestor=node;
    		while(true) {
    			if (ancestor.type==-1) return null; // no common ancestor -> exit
    			path[pathlength] = ancestor.type; pathlength++;
    			if (ancestor.type==ancestortype[0]) {ancestor = ancestor.parent; break;}
    			if (ancestor.type==ancestortype[1]) {ancestor = ancestor.parent; break;}
    			ancestor = ancestor.parent;
    		}
     
    		// parcours de l'arbre en utilsant le chemin symetrique
    		QuadTreeNode cursor=ancestor,next=null;
    		for(int i=pathlength-1;i>=0;i--) {
    			if (cursor.children==null) break;
    			next = cursor.children[ reverter[ path[i] ] ];
    			if (next==null) break;
    			cursor=next;
    		}
    		return cursor;
    	}
     
    	// parcours reccursif des enfants. Helper pour la methode childrens()
    	private void childrens_atom(List<QuadTreeNode> results, QuadTreeNode node, int[] finaltypes) {
    		if (node==null) return;
    		if (node.children==null) {
    			results.add(node); 
    			return;
    		}
    		for(int type:finaltypes){
    			childrens_atom(results,node.children[type],finaltypes);
    		}
    	}
     
    	// retourne la liste des feuilles accessibles à partir d'un noeud
    	private List<QuadTreeNode> childrens(QuadTreeNode node, int[] finaltypes) {
    		List<QuadTreeNode> results = new ArrayList<QuadTreeNode>();
    		childrens_atom(results,node,finaltypes);
    		return results;
    	}
     
    	// ----------------------------------------------------------------------------------
     
    	/** split un noeud, i.e. création des 4 enfants (ordre=NW,NE,SW,SE)*/
    	public void split(Object... objects) {
    		if (children!=null) return;
    		children = new QuadTreeNode[4];
    		children[TYPE_NW] = new QuadTreeNode(this,TYPE_NW,null);
    		children[TYPE_NE] = new QuadTreeNode(this,TYPE_NE,null);
    		children[TYPE_SW] = new QuadTreeNode(this,TYPE_SW,null);
    		children[TYPE_SE] = new QuadTreeNode(this,TYPE_SE,null);
     
    		if(objects.length>=1) children[TYPE_NW].object = objects[0];
    		if(objects.length>=2) children[TYPE_NE].object = objects[1];
    		if(objects.length>=3) children[TYPE_SW].object = objects[2];
    		if(objects.length>=4) children[TYPE_SE].object = objects[3];
    	}
     
    	// ----------------------------------------------------------------------------------
     
    	/** retourne le noeud représentant la case de droite */
    	public QuadTreeNode getRightSibling() {
    		return 	sibling(this,QuadTreeNode.rightAncestors,QuadTreeNode.horizontalReverter);
    	}
     
    	/** retourne le noeud représentant la case de gauche */
    	public QuadTreeNode getLeftSibling() {
    		return 	sibling(this,QuadTreeNode.leftAncestors,QuadTreeNode.horizontalReverter);
    	}
     
    	/** retourne le noeud représentant la case du dessus */
    	public QuadTreeNode getTopSibling() {
    		return 	sibling(this,QuadTreeNode.topAncestors,QuadTreeNode.verticalReverter);
    	}
     
    	/** retourne le noeud représentant la case du dessous */
    	public QuadTreeNode getBottomSibling() {
    		return 	sibling(this,QuadTreeNode.bottomAncestors,QuadTreeNode.verticalReverter);
    	}
     
    	// ----------------------------------------------------------------------------------
     
    	/** retourne toutes les feuilles de type: gauche */
    	public List<QuadTreeNode> getLeftChildren() {
    		return 	childrens(this,QuadTreeNode.leftNodes);
    	}
     
    	/** retourne toutes les feuilles de type: droite */
    	public List<QuadTreeNode> getRightChildren() {
    		return childrens(this,QuadTreeNode.rightNodes);
    	}
     
    	/** retourne toutes les feuilles de type: haut */
    	public List<QuadTreeNode> getTopChildren() {
    		return childrens(this,QuadTreeNode.topNodes);
    	}
     
    	/** retourne toutes les feuilles de type: bas */
    	public List<QuadTreeNode> getBottomChildren() {
    		return childrens(this,QuadTreeNode.bottomNodes);
    	}
     
    	/** retourne toutes les feuilles */
    	public List<QuadTreeNode> getLeaves() {
    		return childrens(this,QuadTreeNode.AllNodes);
    	}
     
    	// ----------------------------------------------------------------------------------
     
    	/** retourne les noeuds représentant les cases voisines à gauche */
    	public List<QuadTreeNode> getRightNeighbors() {
    		QuadTreeNode sibling = this.getRightSibling();
    		if (sibling==null) return new ArrayList<QuadTreeNode>();
    		return 	sibling.getLeftChildren();
    	}
     
    	/** retourne les noeuds représentant les cases voisines à droite */
    	public List<QuadTreeNode> getLeftNeighbors() {
    		QuadTreeNode sibling = this.getLeftSibling();
    		if (sibling==null) return new ArrayList<QuadTreeNode>();
    		return 	sibling.getRightChildren();
    	}
     
    	/** retourne les noeuds représentant les cases voisines au dessus */
    	public List<QuadTreeNode> getTopNeighbors() {
    		QuadTreeNode sibling = this.getTopSibling();
    		if (sibling==null) return new ArrayList<QuadTreeNode>();
    		return 	sibling.getBottomChildren();
    	}	
     
    	/** retourne les noeuds représentant les cases voisines en dessous */
    	public List<QuadTreeNode> getBottomNeighbors() {
    		QuadTreeNode sibling = this.getBottomSibling();
    		if (sibling==null) return new ArrayList<QuadTreeNode>();
    		return 	sibling.getTopChildren();
    	}
    }

    Voici un exemple d'utilisation de cette classe qui permet de réaliser le partitionnement montré dans l'image d'exemple:
    Code java :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
    // Creation du noeud "racine"
    QuadTreeNode root = new QuadTreeNode("ROOT");
     
    // split du noeud "racine" en 4 
    root.split("1","2","3","4");
     
    // Reference du noeud "1"
    QuadTreeNode n1 = root.children[TYPE_NW];
     
    // split du noeud "1" en 4
    n1.split("1.1","1.2","1.3","1.4");

    Pour afficher les voisins de gauche du noeud "2":
    Code java :
    1
    2
    3
    4
    5
    6
    7
     
    // Reference du noeud "2"
    QuadTreeNode n2 = root.children[TYPE_NE];
     
    // Affiche les voisins de gauche du noeud "2" --> affiche: 1.2 1.4
    for( QuadTreeNode voisin : n2.getLeftNeighbors() )
    	System.out.println(voisin.object);

    PRomu@ld : sources
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  2. #2
    Membre du Club Avatar de highlight
    Homme Profil pro cv fun
    Développeur multimédia
    Inscrit en
    novembre 2008
    Messages
    139
    Détails du profil
    Informations personnelles :
    Nom : Homme cv fun

    Informations professionnelles :
    Activité : Développeur multimédia

    Informations forums :
    Inscription : novembre 2008
    Messages : 139
    Points : 68
    Points
    68

    Par défaut

    Très très bonne initiative Xavier de ta part. Je dois transcrire le code en C++ et voir comment l’intégrer pour Split and Merge, pour décomposer les images en bloque homogène. Il y a du boulot à faire . j'ai jamais fait du java dans ma vie lol

  3. #3
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 962
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 962
    Points : 16 880
    Points
    16 880

    Par défaut

    Citation Envoyé par highlight Voir le message
    Très très bonne initiative Xavier de ta part. Je dois transcrire le code en C++ et voir comment l’intégrer pour Split and Merge, pour décomposer les images en bloque homogène. Il y a du boulot à faire . j'ai jamais fait du java dans ma vie lol
    Il existe surement des implémentations déjà faites de Quadtree en C++. A moins que tu ne doives/préfères coder ta propre implémentation.

    L'implémentation que je propose ici est assez compliquée car elle inclut tout un système de navigation (sibling, neighbors, children, ...). Tout ce système n'est pas nécessaire si tu veux segmenter une image. Un bon graphe d'adjacence est tout aussi efficace et plus simple.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  4. #4
    Membre du Club Avatar de highlight
    Homme Profil pro cv fun
    Développeur multimédia
    Inscrit en
    novembre 2008
    Messages
    139
    Détails du profil
    Informations personnelles :
    Nom : Homme cv fun

    Informations professionnelles :
    Activité : Développeur multimédia

    Informations forums :
    Inscription : novembre 2008
    Messages : 139
    Points : 68
    Points
    68

    Par défaut

    Oui effectivement j'en ai trouvé pas mal mais c'est pour detecter la collision des objets hors de mon application donc . Franchement j'ai perdu un temps fou à chercher cela. Mon but en fin de compte est de retrouvé une decomposition en régions homogene d'une carte de profondeur (depth map). l'idée c'est de bien determiner des région connexes homogènes.
    Je n'ai pas trouvé d implémentation!

  5. #5
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 962
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 962
    Points : 16 880
    Points
    16 880

    Par défaut

    Citation Envoyé par highlight Voir le message
    Oui effectivement j'en ai trouvé pas mal mais c'est pour detecter la collision des objets hors de mon application donc . Franchement j'ai perdu un temps fou à chercher cela. Mon but en fin de compte est de retrouvé une decomposition en régions homogene d'une carte de profondeur (depth map). l'idée c'est de bien determiner des région connexes homogènes.
    Je n'ai pas trouvé d implémentation!
    Dans ce cas là, le plus simple c'est d'utiliser le QuadTree uniquement pour la phase de "split". Au final, on construit une nouvelle image où chaque pixel à la valeur moyenne de la région. On fait alors le "merge" avec un algo classique de composantes connexes (cf. les implémentation dans ce forum).

    Pas besoin de système de navigation, ni de graphe d'adjacence.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  6. #6
    Membre du Club Avatar de highlight
    Homme Profil pro cv fun
    Développeur multimédia
    Inscrit en
    novembre 2008
    Messages
    139
    Détails du profil
    Informations personnelles :
    Nom : Homme cv fun

    Informations professionnelles :
    Activité : Développeur multimédia

    Informations forums :
    Inscription : novembre 2008
    Messages : 139
    Points : 68
    Points
    68

    Par défaut

    Ok, je viens de définir qlqs structures essentielles pour la décomposition en Quadtree. C'est representation tres simple. Mettez en tete, qu'une image est decomposée en 4 régions a la forme suivante: L00, L01,L10 et L11, (comme les coefficients d'une matrices de 2x2).

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    typedef struct data{
    
    	float * c; // le centre de la feuille (leaf) c=[x,y]
    
    	float *corner_leaf00;
    	float *corner_leaf10;
    	float *corner_leaf11;
    	float *corner_leaf01;
    
    }data;
    Maintenant structure de la feuille

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    typedef struct leaf {
    
    	data *coords;
    	struct leaf *LP; // le noeud 
    	struct leaf *L00;  // Les feuilles 
    	struct leaf *L10;
    	struct leaf *L11;
    	struct leaf *L01;
    
    }leaf;
    et une structure quadtree
    Code :
    1
    2
    3
    4
    typedef struct quadtree{
    	leaf *root;
    }quadtree;
    Maintenant l'allcoation de la memoire :

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    leaf * leaf_alloc(float *center, float *corner00, float *corner10, float *corner11, float *corner01) 
    {
    	leaf * new_leaf;
    	if ( (new_leaf = (leaf*)malloc(sizeof(leaf)) ) == NULL ) 
    	{
    		fprintf(stderr,"Error : A problem of allocation of the leaf" );
    	}
    
    	if ( (new_leaf->coords = (data*)malloc(sizeof(data)) ) == NULL ) 
    	{
    		fprintf(stderr," Error: A problem of allocation of the leaf" );
    	}
    
    	new_leaf->coords->c = center ;
    	new_leaf->coords->corner_leaf00 = corner00 ;
    	new_leaf->coords->corner_leaf01 = corner01 ;
    	new_leaf->coords->corner_leaf11 = corner11 ;
    	new_leaf->coords->corner_leaf10 = corner10 ;
    
    	new_leaf->LP  = NULL;
    	new_leaf->L00 = NULL;
    	new_leaf->L10 = NULL;
    	new_leaf->L11 = NULL;
    	new_leaf->L01 = NULL;
    	return new_leaf;
    }
    Et bien evidemment une fonction de la subidivision de la feuille:

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    void leaf_subdivise(leaf * leaf) {
    
    	if (!leaf) 
    	{ // If the leaf is NULL (the null pointer)
    		fprintf(stderr,"[e] The leaf points to NULL and cannot be subdivided.\n" );
    		exit(EXIT_FAILURE);
    
    	} 
    	else 
    	{
    
    		float * center     = leaf->coords->c    ;
    		float * corner_leaf00 = leaf->coords->corner_leaf00;
    		float * corner_leaf10 = leaf->coords->corner_leaf10;
    		float * corner_leaf11 = leaf->coords->corner_leaf11;
    		float * corner_leaf01 = leaf->coords->corner_leaf01;
    
    		// the first child: L00 child ( the upper-left)
    
    		float L00_corner00[2] = {corner_leaf00[0] ,corner_leaf00[1]};
    		float L00_corner10[2] = {corner_leaf00[0] ,center[1]    };
    		float L00_corner11[2] = {center[0]     ,center[1]    };
    		float L00_corner01[2] = {center[0]     ,corner_leaf00[2]};
    
    		float L00_center[2]   = { (L00_corner00[0] + L00_corner01[0])/2.0f, (L00_corner00[1] + L00_corner10[1])/2.0f};
    
    		leaf->L00 = leaf_alloc(L00_center,L00_corner00,L00_corner10,L00_corner11,L00_corner01);
    		leaf->L00->LP = leaf;
    
    // Et on fait pareil pour les 3 restants, je vais pas les ecrire ici :)
    Je sais pas si cela est correct... C'est vraiment tres simple comme approche d'implémentation des quadtree!!
    A vous

  7. #7
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 962
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 962
    Points : 16 880
    Points
    16 880

    Par défaut

    Citation Envoyé par highlight Voir le message
    Je sais pas si cela est correct... C'est vraiment tres simple comme approche d'implémentation des quadtree!!
    A vous
    Ca m'a l'air correct.

    Faut bien faire attention au moment de la subdivision à créer 4 zones jointives, mais non couvrantes. A force de subdiviser, la zone de départ n'est pas toujours un carré parfait, ni une dimension multiple de 2. Avec ton approche de "centre" de la feuille, ca devrait marcher.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  8. #8
    Membre du Club Avatar de highlight
    Homme Profil pro cv fun
    Développeur multimédia
    Inscrit en
    novembre 2008
    Messages
    139
    Détails du profil
    Informations personnelles :
    Nom : Homme cv fun

    Informations professionnelles :
    Activité : Développeur multimédia

    Informations forums :
    Inscription : novembre 2008
    Messages : 139
    Points : 68
    Points
    68

    Par défaut

    Merci Pseudocode pour ta réponse. Je veux juste avoir quelques precisions pour determiner un critere d'homogeneité, on peut par exemple qui est d'ailleurs le plus simple:

    Calculer l'intesité moyenne d'un bloque intensity_average, et tester si l'intensité maximale et minimale de ce bloque appartient à l'intervalle:
    [intensity_average-seuil,intensity_average+seuil]

    Qu'est ce que tu en pense?
    Je te remercie infiniment

  9. #9
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 962
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 962
    Points : 16 880
    Points
    16 880

    Par défaut

    Citation Envoyé par highlight Voir le message
    Calculer l'intesité moyenne d'un bloque intensity_average, et tester si l'intensité maximale et minimale de ce bloque appartient à l'intervalle:
    [intensity_average-seuil,intensity_average+seuil]

    Qu'est ce que tu en pense?
    J'en pense que c'est extrêmement sensible au bruit. Un seul pixel trop clair dans un gros bloc va entrainer une cascade de division jusqu'à isoler ce pixel.

    Si ton image est synthétique (synthèse 2D ou 3D), ce critère peut être acceptable à condition de bien choisir le seuil. Si c'est une image réelle ou bruitée, il vaut mieux utiliser la variance.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  10. #10
    Invité de passage
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2012
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : avril 2012
    Messages : 1
    Points : 1
    Points
    1

    Par défaut Voisins des blocs

    Bonjour ,

    Merci beaucoup Philippeau pour le code moi je travaille sur le split and merge.
    J'ai terminé le split sauf mnt au merge je dois connaitre les voisins de chaque Bloc.
    J'ai lu la méthode utilisé dans votre code mais j'ai pas compris comment t'as fais pour connaitre les voisins.
    STP peux tu m'expliquer l'algorithme avec un petit algo ou les étapes que t'as fais pour que je puisse mettre le code dans mon propre projet.

    Merci d'avance

  11. #11
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 962
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 962
    Points : 16 880
    Points
    16 880

    Par défaut

    Citation Envoyé par ballou129 Voir le message
    J'ai terminé le split sauf mnt au merge je dois connaitre les voisins de chaque Bloc.
    J'ai lu la méthode utilisé dans votre code mais j'ai pas compris comment t'as fais pour connaitre les voisins.
    Il faut chercher indépendamment chacun des 4 voisins.

    Prenons l'exemple du "voisin de droite" d'un noeud X. Il y a deux cas:

    Le cas simple: Si X est du type NW ou SW, alors son voisin de droite Y est le noeud NE ou SE dans le même carré.

    Le cas compliqué: Si X est du type NE ou SE, alors son voisin de droite Y est dans un autre carré. Cet autre carré est forcément à droite de X. Il nous faut donc un moyen de nous ramener au cas simple...

    Et pour cela, on va remonter d'un cran dans la hiérarchie et inspecter le parent de X : si le parent de X est du type NW ou SW, alors le parent de Y est le NE ou SE dans le même carré. Si ce n'est pas le cas on inspecte le parent du parent de X, et ainsi de suite.

    Lorsqu'on fini par trouver un parent de X de type NW/SW, on a donc trouvé le parent de Y correspondant. Il nous reste a redescendre la hiérarchie du parent de Y pour trouver Y.

    L'astuce consiste a remarquer que la redescente s'effectue de manière symétrique (en miroir) à la remontée. Cela s'explique car le voisin de droite de X est de l' "autre coté" de la ligne verticale qui sépare les parents.

    Donc, a chaque fois qu'on a fait une remontée de "NE -> parent", alors il faudra faire un redescente "parent -> NW". Et idem pour "SE -> parent" qui devient "parent -> SW".

     -------------------------
    |  ___N_W___   ___N_E___  |
    | |    |    | |    |    | |
    | | NW | NE | | NW | NE | |
    | |____|____| |____|____| |
    | |    |    | |    |    | |
    | | SW | SE | | SW | SE | |
    | |____|____| |____|____| |
    |  _________   _________  |
    | |    |    | |    |    | |
    | | NW | NE | | NW | NE | |
    | |____|____| |____|____| |
    | |    |    | |    |    | |
    | | SW | SE | | SW | SE | |
    | |____|____| |____|____| |
    |     S W         S E     |
     -------------------------
    
    SE -parent-> NW  <-miroir->  NE -enfant-> SW
    
    
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  12. #12
    Invité de passage
    Profil pro chaabane younesse
    Inscrit en
    juillet 2010
    Messages
    1
    Détails du profil
    Informations personnelles :
    Nom : chaabane younesse

    Informations forums :
    Inscription : juillet 2010
    Messages : 1
    Points : 1
    Points
    1

    Par défaut compliment

    tres bon exemple ,
    mais si je veux apliquer cette structure il faut que je sauvgarde un objet dans le noed comme les pixles du quadtrant
    si qlq 1 peut nous aider a faire ca

    et merci

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •