Quadtree

Un quadtree ou arbre quaternaire (arbre Q) est une structure de données de type arbre dans laquelle chaque nœud a quatre fils. Les quadtrees sont le plus souvent utilisés pour partitionner un espace bidimensionnel en le subdivisant récursivement en quatre nœuds. Les quadtrees sont l'analogie bidimensionnelle des octrees. Le nom est formé à partir de quad et de tree (arbre, en anglais). Chaque nœud d'un quadtree subdivise l'espace qu'il représente en quatre sous-espaces. Les quadtrees peuvent être classés selon le type de données qu'ils représentent, incluant régions, points, lignes et courbes. Voici quelques types communs de quadtrees : Le quadtree «région» représente une partition de l'espace en deux dimensions en décomposant la région en quatre quadrants égaux, puis chaque quadrant en quatre sous-quadrants, et ainsi de suite, avec chaque «nœud terminal» comprenant des données correspondant à une sous-région spécifique. Chaque nœud de l'arbre a exactement : soit quatre enfants, soit aucun (cas d'un nœud terminal). Le quadtree «région» est un type d'arbre préfixe. Un quadtree «région» ayant une profondeur n peut être utilisé pour représenter une image de , où la valeur de chaque pixel est 0 ou 1. Le nœud parent représente l'image tout entière. Si les pixels d'une région donnée ne sont pas tous à 0 ou tous à 1, celle-ci est subdivisée. Dans une telle représentation d'une image, chaque nœud terminal représente un bloc de pixels qui sont tous à 0 ou tous à 1. Un quadtree «région» peut également être utilisé comme une représentation de résolution variable d'un champ de données. Par exemple, les températures d'une zone peuvent être stockées dans un quadtree, dans lequel chaque nœud terminal stocke la température moyenne de la sous-région qu'il représente. Si un quadtree «région» est utilisé pour représenter un ensemble de points (par exemple, les latitudes et longitudes d'un groupe de villes), les régions sont subdivisées jusqu'à ce que chaque nœud terminal ne contienne plus qu'un point.