Chercher sans tout regarder
Une question revient sans cesse dès qu'on manipule des données spatiales : « quels points se trouvent dans cette zone ? ». La réponse naïve teste chaque point un à un — parfait pour quelques dizaines d'éléments, ruineux dès qu'on en a des milliers, et pire encore quand la question se répète à chaque image. Le quadtree répond à ce problème en organisant l'espace lui-même, de sorte qu'une requête ne visite que les régions réellement concernées.
Subdiviser dès qu'une case se remplit
Le principe tient en une phrase : un carré garde jusqu'à N points, puis se subdivise en quatre quadrants dès qu'il déborde, en redistribuant ses points aux enfants. Là où les points sont denses, l'arbre plonge et les cases deviennent minuscules ; là où l'espace est vide, une seule grande case suffit. La structure épouse ainsi la distribution des données — c'est visible à l'écran : les subdivisions se resserrent exactement où les points s'agglutinent.
Une requête qui ignore l'inutile
Quand vous déplacez la souris, le rectangle indigo définit une zone de requête. L'algorithme part de la racine et ne descend que dans les nœuds dont le carré intersecte ce rectangle : un quadrant entièrement hors zone est écarté d'un seul test, avec tous les points qu'il contient. Seuls les points des nœuds effectivement visités sont comparés à la requête, puis mis en évidence en ambre. Le compteur en haut le rend concret : on ne visite qu'une poignée de nœuds là où l'approche naïve testerait la totalité des points.
Le compromis capacité, profondeur et reconstruction
Rien n'est gratuit. Une capacité de nœud faible produit un arbre profond, précis mais coûteux à parcourir et à mémoriser ; une capacité élevée donne un arbre plat qui se rapproche de la recherche linéaire. Et parce que les points bougent, je reconstruis ici l'arbre à chaque image : c'est simple et robuste, mais ce coût de reconstruction devient l'arbitrage central. Selon les cas, on choisit de reconstruire, de mettre à jour l'arbre de façon incrémentale, ou de basculer sur une autre structure (grille régulière, arbre k-d) — il n'y a pas de meilleure structure dans l'absolu, seulement celle qui colle à vos données et à vos requêtes.
Pourquoi ce détail compte pour votre projet
Le partitionnement spatial n'est pas une curiosité d'école : c'est ce qui sépare une carte interactive qui rame d'une carte fluide, une détection de collisions qui tient soixante images par seconde d'une qui s'effondre, un moteur de recherche de proximité tenable d'un qui explose en charge. Choisir la bonne structure de données au bon endroit, mesurer avant d'optimiser et documenter le compromis retenu : c'est exactement la rigueur que j'apporte aux projets où la performance et la montée en charge ne sont pas négociables.
