Discussion :

[PrettyMan]

Bonjour,
J'ai une carte formée par plusieurs polygones et je voudrai rechercher un polygone qui contient le point A (x, y). Afin d'accélérer la recherche, je pense d'utiliser un arbre binaire. De cela, je construits les structures de données suivantes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
typedef struct Point2D{
  double x;
  double y ;
};
typedef struct Polygone{
 int numero ;
 double xMin, yMin, xMax, ymax ;
 vector<Point2D>vectSommet ;
}* tabPolygone;
 
typedef struct noeud{
  Polygone contenu ;
  struct noeud* filsGauche ;
  struct noeud* filsDroite ;
}*arbre ;

le struct Polygone contient les informations relatives à un polygone et tabPolygone est un pointeur sur Polygone. Chaque polygone est délimité par le point min(xMin, yMin) et le point max(xMax, yMax) et vectSommet contient l'ensemble des sommets qui forment le polygone. Comment devrai je construire mon arbre afin d'avoir un meilleur temps de recherche ?
merci pour votre aide.

[pseudocode]

le struct Polygone contient les informations relatives à un polygone et tabPolygone est un pointeur sur Polygone. Chaque polygone est délimité par le point min(xMin, yMin) et le point max(xMax, yMax) et vectSommet contient l'ensemble des sommets qui forment le polygone. Comment devrai je construire mon arbre afin d'avoir un meilleur temps de recherche ?

Est-ce que, par hasard, une structure kd-tree ne répondrait pas à ton bonheur ?

[PRomu@ld]

Est-ce que, par hasard, une structure kd-tree ne répondrait pas à ton bonheur ?

En fait, pas tout à fait. Un KdTree permet d'accélérer la recherche du(des) plus proche(s) voisin(s). Pas nécessairement ce qui contient qui (en tout cas par directement). En tout cas, j'ai un peu de difficulté à appliquer directement un KdTree pour la recherche.

Dans un premier temps, je pense qu'il vaut mieux utiliser une grille régulière ( ou un quadtree. ) Tu peux récupérer en O(1) le voxel qui contient le point que tu recherches. Après ça il te suffira de chercher dans les polygones qui ont une intersection non nulle avec le voxel courant celui qui contient ton point.

Si tu es dans le cas particulier où tes polygones forment une partition de l'espace tu peux construire un BSP (avec comme plan de découpe les segments de tes polygones), et là la recherche sera un simple parcours de ta structure. (mais la construction est plus compliquée qu'avec une grille).

[pseudocode]

En fait, pas tout à fait. Un KdTree permet d'accélérer la recherche du(des) plus proche(s) voisin(s). Pas nécessairement ce qui contient qui (en tout cas par directement). En tout cas, j'ai un peu de difficulté à appliquer directement un KdTree pour la recherche.

Bah, le kd-tree tout comme le quad-tree sépare l'espace en petites zones.

En utilisant les 4 droites formant une bounding-box, on peut créer un découpage de l'espace (interieur/exterieur de la bounding-box). Il suffit de stocker un pointeur dans la feuille de l'arbre qui indique l'intérieur de la BB.

Pour la recherche, on prend un point A(x,y) quelconque et on descend l'arbre jusqu'a une feuille, et on collecte tous les pointeurs stockés dans les noeuds traversés.

[SpiceGuid]

En fait, pas tout à fait. Un KdTree permet d'accélérer la recherche du(des) plus proche(s) voisin(s). Pas nécessairement ce qui contient qui (en tout cas par directement). En tout cas, j'ai un peu de difficulté à appliquer directement un KdTree pour la recherche.

Le KD-tree est très bien adapté à la recherche à l'intérieur d'un rectangle/paralléloide aligné sur les axes. Si tu sais renvoyer la liste des éléments d'un arbre binaire de recherche contenus dans un certain intervalle alors tu sais généraliser à un KD-tree en dimension quelconque.
Le tout est de l'avoir déjà fait au moins une fois car ça n'est pas le même paramorphisme que pour la recherche d'un point :

• au lieu de n'avoir qu'une fonction de parcours tu en as 3, la 1ière est un parcours complet, la 2nd est un parcours de la branche gauche qui s'arrête lorsque tu franchis le minimum, la 3ième est un parcours de la branche droite qui s'arrête lorsque tu dépasse le maximum
• au lieu de n'explorer qu'une seule branche tu explore systématiquement les deux, c'est le dépassement des bornes qui arrête la récursion
• au cours de ce parcours tu collecte tous les points contenus dans un intervalle/rectangle/paralléloide

[PRomu@ld]

Le KD-tree est très bien adapté à la recherche à l'intérieur d'un rectangle/paralléloide aligné sur les axes.

Comme d'habitude, j'ai encore lu trop vite le PO, j'ai zappé le aligné aux axes