Quadtree
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
Un quadtree est une structure de données de type arbre dans laquelle chaque nœud peut compter jusqu'à quatre enfants. Les quadtree sont le plus souvent utilisés pour partitionner un espace bidimensionnel en le subdivisant récursivement en quatre nœuds.
Quelques utilisations courantes des quadtree:
- L'indexation spatiale
- La détection efficace de collision dans le cadre de la 2D
- Une compression basique en regroupant les éléments de composition identique ou similaire
- Une gestion de collisions bidimensionnelles
- Le view frustum culling
Les quadtree sont l'analogie bidimensionnelle des octree. 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.
