Recherche de points dans un rectangle

Introduction

Ce TP consiste à écrire des procédures pour créer et maintenir une structure de recherche de points dans le plan. Pour cela, on va utiliser un arbre binaire de recherche (pas nécessairement équilibré) qui est légèrement modifié : lors de la descente dans l'arbre, la comparaison effectuée à chaque noeud se fait alternativement sur les coordonnées x et y. Chaque noeud de l'arbre contient un point du plan, en plus des deux pointeurs sur les fils gauche et droit. La structure de donnée principale sera donc de ce type :

type
        Typecle=Point;
        Arbre=^Noeud
        Noeud= record
                       cle: Typecle;
                       fg,fd: Arbre;
               end;

Description du travail demandé

On demande d'impléménter les procédures suivantes :

• L'insertion d'un point dans l'arbre au moyen d'une procédure récursive:

   insertion(p:Point; niveau:boolean;var a:Arbre)

  La variable niveau indiquera si la racine de l'arbre est un noeud effectuant une séparation en x ou en y. On pourra alors écrire une procédure EntrePoints(var a:Arbre) qui permet d'entrer un ensemble de points à la souris et qui les range dans l'arbre, et tester le programme au moyen d'une procédure TracePoints( a:Arbre) qui affiche tous les points faisant partie de l'arbre a.
  
• La recherche de tous les points contenus dans un rectangle donné : c'est un exemple de recherche par intervalle, où l'on effectue un parcours en profondeur d'abord limité par des comparaisons aux bornes de l'intervalle. On utilisera une procédure récursive :

   RechercheRect(r:Rect; niveau:boolean; a:Arbre)

  Cette procédure parcourt l'arbre en commençant par la direction x ou y suivant la valeur du niveau. L'exploration des branches doit être limitée à celles qui peuvent contenir des points dans le rectangle r. Chaque fois qu'un point est trouvé dans ce rectangle, il doit être mis en valeur dans la fenêtre graphique.
  
• La suppression d'un point de la structure. Cette opération est beaucoup plus complexe que pour un arbre binaire de recherche simple. Ceci est dû au fait que les comparaisons se font soit selon x soit selon y. Pour notre application, le plus simple consiste à marquer certains noeuds comme éliminés tout en les gardant dans l'arbre. Ne traitez pas ceci tout de suite et, s'il vous reste du temps, passez à la question suivante.
  
• Dessin d'un arbre binaire.
  Il s'agit de représenter de manière esthétique un arbre binaire relativement important. La difficulté réside dans le placement des noeuds. On pourra suivre la méthode suivante:
  On ne dessine que les segments reliant un noeud à son père. Les noeuds sont placés aux intersections d'un maillage rectangulaire de pas dx, dy.
  Soit à dessiner un arbre dont on spécifie que sa racine aura pour ordonnée yrac et que son élément le plus à gauche aura pour abscisse xmin, on fait l'hypothèse de récurrence suivante : une fois cet arbre dessiné on connaîtra les abscisses de sa racine et de son élément le plus à droite, respectivement, xrac et xmax.
  • Si le sous-arbre gauche existe, on le dessine en spécifiant que sa racine aura pour ordonnée yrac+dy et que son élément le plus à gauche aura pour abscisse xmin. Par hypothèse de récurrence, on connait alors xracGauche et xmaxGauche, les abscisses de la racine et de l'élément le plus à droite de ce sous-arbre gauche. On en déduit que l'absisse de la racine de l'arbre considéré sera xrac=xmaxGauche+dx et on trace donc le segment reliant les points (xracGauche,yrac + dy) et (xrac,yrac).
  • Si le sous-arbre gauche n'existe pas, on décide simplement que l'abscisse de la racine de l'arbre considéré sera xrac=xmin.
  • De manière comparable, on traite le cas du sous-arbre droit et on connait alors xmax, l'abscisse de l'élément le plus à droite de l'arbre considéré.
  On pourra faire afficher, à la position d'un noeud, un petit rectangle contenant l'élément associé au noeud. Pour cela on insèrera par exemple dans le rectangle les deux coordonnées x et y du noeud.

N'oubliez pas de :