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.