Corrigé Mines-Ponts 2026 Informatique II MPI — Partie 4 (Q34 à Q38) : Arbres BSP : parcours infixe, dérécursivation, génération de carte

Un arbre BSP (Binary Space Partitioning) partitionne récursivement l'espace ; il est rangé dans un tableau global bsp de nœuds ; les champs valent l'indice du fils, ou $-1$ s'il n'existe pas. On dispose de void visite(int n), qui traite le nœud d'indice n. Le parcours infixe traite le sous-arbre « devant », puis le nœud, puis le sous-arbre « derrière ».

struct _noeud {
    int filsDevant;
    int filsDerriere;
};
typedef struct _noeud noeud;

Q34. Écrire la version récursive de void infixe(int n).
Q35. On dérécursive avec une pile explicite : un tableau d'entiers pile et un entier sommet, nombre d'éléments empilés (le sommet est en pile[sommet-1]). Compléter L1 et L2 (initialisation de la pile non précisée) pour obtenir l'ordre de visite du parcours récursif :

void infixe(int n) {
  /* pile : tableau d'indices, sommet : taille courante */

  while (true) {
    while (bsp[n].filsDevant != -1) {
      pile[sommet] = n;
      sommet++;
      n = bsp[n].filsDevant;
    }

    while (true) {
      visite(n);
      if (bsp[n].filsDerriere != -1) {
        n = bsp[n].filsDerriere;
        break;
      }

      if (sommet == 0) { return; }

      /* L1 */
      /* L2 */
    }
  }
}

Génération procédurale.

Une salle carrée est coupée récursivement en deux, dans une direction aléatoire, à une position aléatoire entre $30\%$ et $70\%$ de la dimension coupée, jusqu'à obtenir une puissance de deux de salles. Chaque nœud de l'arbre est une coupe : direction ($0$ : verticale, $1$ : horizontale) et proportion, entier de $300$ à $700$ (en millièmes) ; les feuilles sont les salles finales. La racine coupe $A$ en $A_1$, $A_2$ ; ses fils coupent $A_1$ en $A_{11}$, $A_{12}$ et $A_2$ en $A_{21}$, $A_{22}$, etc.

Les $n$ nœuds sont numérotés à partir de $0$ (racine) dans l'ordre du parcours en largeur ; pour la figure :

Q36. rand() renvoie un entier uniforme entre $0$ et RAND_MAX, assimilé à $+\infty$. Écrire int alea(void), uniforme sur $[[300,700]]$.
Q37. Écrire coupe* repartition(int n), qui alloue et remplit aléatoirement le tableau des n coupes d'un arbre BSP.

struct _coupe {
   int dir;        // 0 ou 1
   int proportion; // entre 300 et 700 inclus
};
typedef struct _coupe coupe;

struct _region {
    int xmin;
    int xmax;
    int ymin;
    int ymax;
};
typedef struct _region region;

Dans un repère orthonormé, la salle initiale est le carré de coins $(0,0)$ et $(100n,100n)$, avec $n={\log }_2(p)$ où $p$ est le nombre final de salles ; une région est décrite par son coin inférieur gauche $(x_{\min },y_{\min })$ et son coin supérieur droit $(x_{\max },y_{\max })$.
Q38. À l'aide de repartition et d'un arbre binaire complet à n nœuds, écrire region* creation(int n), qui renvoie le tableau de toutes les régions (initiale, intermédiaires, finales) : $15$ régions $A,A_1,A_2,A_{11},A_{12},A_{21},A_{22},\dots$ pour les $7$ coupes de l'exemple.

Une salle par feuille et un couloir par séparation donnent ensuite une carte connexe :