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.
Types[modifier | modifier le code]
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»[modifier | modifier le code]
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 2n × 2n pixels, 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.
Le quadtree «point»[modifier | modifier le code]
Le quadtree «point» est une adaptation d'un arbre binaire, utilisé pour représenter une donnée «point» à deux dimensions (par exemple, une coordonnée géographique). Il partage les caractéristiques de tous les quadtrees tout en étant un véritable arbre, puisque le centre d'une subdivision est toujours sur un point. La forme de l'arbre dépend de l'ordre dans lequel les données sont traitées. Une telle représentation est souvent très efficace en comparaison des données «points» ordonnées bidimensionnelles, opérant habituellement en un temps O(log n).
Structure d'un nœud d'un quadtree «point»[modifier | modifier le code]
Le nœud d'un quadtree «point» est similaire à celui d'un arbre binaire, avec cette grosse différence : le premier possède quatre pointeurs (un pour chaque quadrant), tandis que le second n'en possède que deux («gauche» et «droite»). Une autre différence, une clé est habituellement décomposée en deux parties, se référant aux coordonnées x et y. Un nœud contient donc les informations suivantes :
- quatre pointeurs : quad['NO'], quad['NE'], quad['SO'] et quad['SE']
- un point, qui à son tour contient :
- une clé : habituellement des coordonnées (x,y)
- une valeur : par exemple, un nom.
Le quadtree «bord»[modifier | modifier le code]
Les quadtrees «bord» sont spécifiquement utilisés pour stocker des lignes, plutôt que des points. Les courbes sont approximées en subdivisant les cellules jusqu'à une très fine résolution. Ceci peut résulter en des arbres extrêmement déséquilibrés, annulant ainsi l'intérêt de l'indexation.
Le quadtree «carte polygonale»[modifier | modifier le code]
Le quadtree «carte polygonale» (ou CP-quadtree) est une variante d'un quadtree, utilisée pour stocker des collections de polygones potentiellement dégénérés (c'est-à-dire, ayant des sommets ou des bords isolés)[1]. Il existe trois classes principales de CP-quadtrees, variant en fonction de quelles informations ils stockent à l'intérieur de chaque «nœud noir». Les CP3-quadtrees peuvent stocker n'importe quelle quantité de «bords non-coupants» et au plus un point. Les CP2-quadtrees sont les mêmes que les CP3-quadtrees, excepté que tous les bords doivent partager le même point final. Pour finir, les CP1-quadtrees sont similaires aux CP2-quadtrees, mais les «nœuds noirs» peuvent contenir un point et ses bords ou juste un ensemble de bords partageant un point (mais vous ne pouvez pas avoir un point et un ensemble de bords qui ne contiennent pas ce point).
Quelques utilisations courantes de quadtrees[modifier | modifier le code]
- Compression sans perte d'une image binaire
- De manière générale, compression basique en regroupant les éléments de composition identique ou similaire
- Indexation spatiale
- Détection de collision efficace, en deux dimensions
- Élimination des objets hors du cône de vue d'une surface 3D
- Stockage de données parsemées, tel qu'une information de formatage pour un tableur ou pour quelques calculs matriciels
- Solution de champs multidimensionnels (mécanique des fluides numérique, électromagnétisme)
- Programme de simulation du jeu de la vie de Conway[2]
- Observateur d'état[3]
- Les quadtrees sont également utilisés pour l'analyse d'images fractales
Pseudo-code[modifier | modifier le code]
Le pseudo-code suivant montre une implémentation possible d'un quadtree gérant uniquement les points. Il existe d'autres approches valables.
Prérequis[modifier | modifier le code]
Il est supposé que les structures suivantes sont utilisées.
// Objet de coordonnées simples pour représenter des points et des vecteurs
struct XY
{
float x;
float y;
function __construct(float _x, float _y) {...}
}
// Zone de délimitation alignée sur l'axe, représentée par sa demi-dimension et son centre
struct AABB
{
XY center;
XY halfDimension;
function __construct(XY center, XY halfDimension) {...}
function containsPoint(XY p) {...}
function intersectsAABB(AABB other) {...}
}
Classe QuadTree[modifier | modifier le code]
Cette classe représente à la fois un quadtree et son nœud parent.
class QuadTree
{
// Constante arbitraire indiquant combien d'éléments peuvent être stockés dans ce nœud de quadtree
constant int QT_NODE_CAPACITY = 4;
// Zone de délimitation alignée sur l'axe (représentée par sa demi-dimension et son centre)
// représentant les limites de ce quadtree
AABB boundary;
// Points de ce nœeud de quadtree
Array of XY [size = QT_NODE_CAPACITY] points;
// Enfants
QuadTree* northWest;
QuadTree* northEast;
QuadTree* southWest;
QuadTree* southEast;
// Méthodes
function __construct(AABB _boundary) {...}
function insert(XY p) {...}
function subdivide() {...} // créer quatre enfants permettant de diviser ce quadrant en quatre quadrants d'égales dimensions
function queryRange(AABB range) {...}
}
Insertion[modifier | modifier le code]
La méthode suivante permet d'insérer un point dans le quadrant approprié d'un quadtree, réalisant une partition si nécessaire.
class QuadTree
{
...
// Insérer un point dans le QuadTree
function insert(XY p)
{
// Ignorer les objets qui n'appartiennent pas à ce quadtree
if (!boundary.containsPoint(p))
return false; // l'objet ne doit pas être ajouté
// S'il reste de la place dans ce quadtree, y ajouter l'objet
if (points.size < QT_NODE_CAPACITY)
{
points.append(p);
return true;
}
// Sinon, subdiviser le quadtree, puis ajouter le point au nœud qui l'acceptera
if (northWest == null)
subdivide();
if (northWest→insert(p)) return true;
if (northEast→insert(p)) return true;
if (southWest→insert(p)) return true;
if (southEast→insert(p)) return true;
// Sinon, le point ne peut être inséré, pour une raison inconnue (cela ne devrait jamais arriver)
return false;
}
}
Recherche dans une zone[modifier | modifier le code]
La méthode suivante permet de trouver tous les points à l'intérieur d'une «zone de recherche».
class QuadTree
{
...
// Trouver tous les points apparaissant à l'intérieur d'une «zone de recherche»
function queryRange(AABB range)
{
// Préparer le tableau de résultats
Array of XY pointsInRange;
// Tout interrompre si la «zone de recherche» n'intersecte pas ce quadrant
if (!boundary.intersectsAABB(range))
return pointsInRange; // liste vide
// Vérifier les objets à ce niveau de quadrant
for (int p := 0; p < points.size; p++)
{
if (range.containsPoint(points[p]))
pointsInRange.append(points[p]);
}
// Terminer ici, s'il n'y a pas d'enfant
if (northWest == null)
return pointsInRange;
// Sinon, relancer la recherche sur les 4 enfants et ajouter les points trouvés
pointsInRange.appendArray(northWest→queryRange(range));
pointsInRange.appendArray(northEast→queryRange(range));
pointsInRange.appendArray(southWest→queryRange(range));
pointsInRange.appendArray(southEast→queryRange(range));
return pointsInRange;
}
}
Notes et références[modifier | modifier le code]
Notes[modifier | modifier le code]
- Hanan Samet et Robert Webber. "Storing a Collection of Polygons Using Quadtrees". ACM Transactions on Graphics July 1985: 182-222. InfoLAB. Web. 23 mars 2012
- Tomas G. Rokicki, « Un algorithme pour la compression de l'espace et du temps », (consulté le )
- Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation, Proceedings of the 13th International Conference on Information Fusion, Édimbourg, Royaume-Uni, juillet 2010.
Références générales[modifier | modifier le code]
- Raphael Finkel et J.L. Bentley, « Quad Trees: A Data Structure for Retrieval on Composite Keys », Acta Informatica, vol. 4, no 1, , p. 1–9 (DOI 10.1007/BF00288933)
- Mark de Berg, Marc van Kreveld, Mark Overmars, et Otfried Schwarzkopf, Computational Geometry, Springer-Verlag, (ISBN 3-540-65620-0) Chapter 14: Quadtrees: p. 291–306.
- Hanan Samet et Robert Webber, « Storing a Collection of Polygons Using Quadtrees », (consulté le )
Voir aussi[modifier | modifier le code]
Articles connexes[modifier | modifier le code]
- Partition binaire de l'espace
- Arbre kd
- Octree
- R-arbre
- Arbre UB (en)
- Base de données spatiales
- Sous-pavage (en)
