Quadtree

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Un Quadtree

Un quadtree 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.

Quelques utilisations courantes des quadtree :

  • L'indexation spatiale
  • La détection efficace de collisions 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 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.

Voir aussi[modifier | modifier le code]