Quadtree

Un article de Wikipédia, l'encyclopédie libre.
Aller à : Navigation, rechercher
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Un Quadtree

Un quadtree est une structure de données de type arbre dans laquelle chaque nœud peut compter jusqu'à 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]

v · d · m
Arbre enraciné
Arbre binaire Arbre binaire de recherche · Arbre de fouille · Cartesian tree (en) · MVP Tree (en) · Top tree (en) · T-tree (en)
Arbre équilibré AA tree (en) · Arbre AVL · LLRB tree (en) · Arbre bicolore · Scapegoat tree (en) · Arbre splay · Treap
Arbre B B+ tree · B*-tree (en) · Bx-tree (en) · UB-tree (en) · 2-3 tree (en) · Arbre 2-3-4 · (a,b)-tree (en) · Dancing tree · Htree (en)
Trie Arbre des suffixes · Arbre radix · Arbre ternaire de recherche · X-fast trie (en) · Y-fast trie (en)
Partition binaire de l'espace trees Quadtree · Octree · Arbre kd · Implicit k-d tree (en) · vp-tree (en)
Arbres non binaires Exponential tree (en) · Fusion tree (en) · Interval tree (en) · PQ tree (en) · Range tree (en) · SPQR tree (en) · Van Emde Boas tree (en)
Arbre de base de données spatiales R-tree (en) · R+ tree (en) · R* tree (en) · X-tree (en) · M-tree (en) · Segment tree (en) · Hilbert R-tree (en) · Priority R-tree (en)
Autres arbres Arbre de Merkle · Arbre couvrant de poids minimal · Arbre syntaxique · Arbre syntaxique abstrait · Finger tree (en) · Order statistic tree (en) · Metric tree (en) · Cover tree (en) · BK-tree (en) · Doubly chained tree (en) · iDistance (en) · Link-cut tree (en) · Fenwick tree (en) · Tas · Tas binomial · Tas de Fibonacci
Ce document provient de « http://fr.wikipedia.org/w/index.php?title=Quadtree&oldid=90417607 ».