🌲 Quadtree

La profondeur maximale d'un quadtree PR est bornée par la résolution du système de coordonnées. Pour des coordonnées en virgule flottante 32 bits dans un carré unité, la distance minimale distinguable est d'environ 10⁻⁷, donc l'arbre peut atteindre au plus ~23 niveaux avant que deux points « distincts » n'occupent la même feuille. Pour des coordonnées entières dans une grille de 1024×1024, la profondeur maximale est de 10 (puisque 2¹⁰ = 1024). En pratique, des arbres très profonds ne se forment que lorsque de nombreux points se regroupent dans une petite zone ; la profondeur moyenne pour un ensemble de points uniforme est O(log n).

Oui. L'insertion parcourt de la racine jusqu'à la feuille appropriée en temps O(profondeur), divisant la feuille si elle dépasse sa capacité. La suppression retire le point et, si le nombre total de points du parent tombe sous le seuil de fusion, réunit les quatre nœuds enfants dans la feuille parent. Les deux opérations sont en moyenne O(log n) pour des points uniformément distribués. Des insertions et suppressions fréquentes dans un ensemble de points groupés peuvent nécessiter une reconstruction périodique pour éviter un déséquilibre sévère.

Un octree est la généralisation 3D : chaque nœud subdivise son cube en huit sous-cubes égaux (octants). Les octrees sont largement utilisés dans les moteurs de jeux 3D, l'accélération du lancer de rayons et le traitement de nuages de points LiDAR. Les mêmes principes algorithmiques s'appliquent — requêtes de plage, recherche de plus proche voisin et phase large de collision bénéficient tous de la hiérarchie spatiale. En pratique, les arbres BVH 3D (hiérarchie de volumes englobants) surpassent souvent les octrees pour les scènes dynamiques car ils s'adaptent à la distribution des points plutôt que d'utiliser des divisions à point médian fixe.

Le codage d'image en quadtree divise récursivement une image en quadrants. Si tous les pixels d'un quadrant se situent dans un seuil d'une seule valeur de couleur, le quadrant est stocké comme un seul nœud feuille avec cette couleur — aucun stockage par pixel n'est nécessaire. Sinon, le quadrant est subdivisé à nouveau. Cela produit un schéma de compression sans perte (à seuil=0) ou avec perte (seuil>0). La compression d'image fractale (utilisée dans certains anciens jeux sur CD-ROM) est une technique apparentée. Les codecs modernes (HEVC, AV1) utilisent des hiérarchies d'unités de codage (CU) de type quadtree pour partitionner les images en blocs de taille variable pour le codage entropique.

La recherche du plus proche voisin commence à la racine et descend dans le quadrant enfant contenant le point de requête, en maintenant un candidat « meilleur actuel ». En remontant la récursion, chaque quadrant frère est vérifié : si la distance minimale possible entre la requête et le quadrant (la distance de son coin le plus proche) est inférieure au meilleur actuel, le quadrant doit être exploré — sinon il est élagué. En pratique, cela visite O(log n) nœuds pour des données aléatoires uniformes, bien que le pire des cas (placement de points adversarial) soit O(n).

Un arbre k-d (arbre k-dimensionnel, Bentley 1975) est un arbre de partitionnement d'espace binaire qui alterne entre les axes de coordonnées pour ses divisions, en choisissant le point médian le long de l'axe courant comme valeur de division. Pour des données 2D, un arbre k-d alterne entre divisions en x et en y. Contrairement à un quadtree PR, un arbre k-d s'équilibre toujours parfaitement (profondeur O(log n) pour n points), mais il a de moins bonnes performances de cache et est plus difficile à mettre à jour dynamiquement. Empiriquement, les arbres k-d surpassent les quadtrees pour les ensembles de points statiques et les dimensions inférieures ; les quadtrees sont préférés pour les données 2D dynamiques et la phase large de collision.

La courbe en Z (Morton) associe des coordonnées 2D à un index 1D en entrelaçant les bits des coordonnées x et y : pour x = b₁b₂b₃ et y = c₁c₂c₃, le code de Morton est b₁c₁b₂c₂b₃c₃. Cette linéarisation préserve la localité spatiale : des points proches sur la courbe en Z sont spatialement proches en 2D. Le code de Morton d'un point est exactement le chemin de la racine à la feuille dans un quadtree PR encodé sous forme de chaîne binaire. Les systèmes de bases de données (par ex., DynamoDB, Google S2) utilisent les courbes de Morton ou de Hilbert pour indexer des données spatiales dans des arbres B 1D, obtenant des performances de requête équivalentes à celles d'un quadtree avec des structures d'index standard.

Oui — le quadtree de région stocke quelles cellules (pixels) sont « à l'intérieur » d'un polygone en subdivisant jusqu'à ce que les cellules soient entièrement à l'intérieur, entièrement à l'extérieur, ou à la limite de résolution (alors stockées comme partiellement couvertes). Les quadtrees vectoriels insèrent des segments de ligne ou des polygones en testant chaque niveau de subdivision pour une intersection. Stocker de grands polygones naïvement provoque une duplication à travers de nombreux nœuds ; les arbres R (Guttman, 1984) sont généralement préférés pour l'indexation de rectangles et de polygones en SIG car ils englobent étroitement les objets et évitent un stockage redondant multi-nœuds.