Quad-Tree et Kd-Tree (par MARQUES Patricia et OLIVIER Aymeric)

  • View
    265

  • Download
    0

Embed Size (px)

DESCRIPTION

 

Text of Quad-Tree et Kd-Tree (par MARQUES Patricia et OLIVIER Aymeric)

  • 1. PRSENTATION DU QUAD-TREE ET KD-TREE Cours de Bases de donnes Avances Aymeric OLIVIER & Patricia MARQUES 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 1
  • 2. SOMMAIRE Historique des arbres Prsentation du Quad-Tree Prsentation du Kd-Tree 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 2
  • 3. HISTORIQUE DES ARBRES uvre de beaucoup de recherches : Mathmatiques et Programmation informatique But : trouver un algorithme optimal de segmentation Point de vue mathmatique : James N. Morgan & John A. Sonquist 1963 Point de vue informatique : J. Quinlan 1983 Aucun historique trouv propres nos arbres. 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 3
  • 4. LE QUAD-TREE Source : https://www.enseignement.polytechnique.fr http://fr.openclassrooms.com 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 4
  • 5. SOUS-SOMMAIRE Principe dutilisation Dfinition du Quad-Tree Mthodologie Dcoupage Collision Exemple Inconvnients de la mthode 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 5
  • 6. PRINCIPE DUTILISATION Mthode dindexation spatiale Gestion dobjet deux dimensions Compression dobjet Manipulation dobjet 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 6
  • 7. DFINITION DU QUAD-TREE Arbre ordonn (index) qui possde: Des feuilles : aucun fils Des sommets internes: 4 fils uniquement Une profondeur Si l'image fait une taille NxN, alors le nombre de dcoupage (le nombre de niveaux dans l'arbre) est de N+1 . 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 7
  • 8. MTHODOLOGIE Dcomposition rcursive dune image Construction de larbre On obtient le Quadtree ci-contre 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 8
  • 9. MTHODOLOGIE Dcoupage Quand arrter le dcoupage? En fonction du nombre max du segment /feuille(fix) En fonction de la profondeur max de larbre A quelle branche appartient un segment ? y P(x,y): Point quelconque de A Py Algorithme Si Px < Cx et Py > Cy alors fils 1 Si Px > Cx et Py > Cy alors fils 2 Si Px < Cx et Py < Cy alors fils 3 Si Px > Cx et Py < Cy alors fils 4 Cy C(x,y): Point central de la dcoupe Cx 27/12/2013 Px x Quad-Tree et KD-Tree Bases de Donnes Avances 9
  • 10. MTHODOLOGIE Collision Dtermination de la trajectoire de chaque segment Parcours de larbre 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 10
  • 11. EXEMPLE Programme de dcoupage de Quad -Tree http://donar.umiacs.umd.edu/quadtree/points/pointquad.html 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 11
  • 12. INCONVNIENTS Notion dquilibrage de larbre Zone dense / zone vides Exemple de la cabane en plein dsert 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 12
  • 13. AUTRES EXEMPLE 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 13
  • 14. K-D-TREE Source: http://www.irisa.fr/prive/kadi/DIIC/SDI -2annee/Expose_KdTree.pdf http://courses.cs.washington.edu/courses/cse373/02au/lect ures/lecture22l.pdf 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 14
  • 15. SOUS-SOMMAIRE Dfinition du KD-tree Cas particulier des BSP -Trees Construction du KD-tree Cas particulier de construction 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 15
  • 16. DEFINITION DU KD-TREE Une mthode de subdivision spatiale Un Kd-tree est une structure de donnes dans un espace k dimensions Un rle double : Organiser lespace pour acclrer le traitement de donnes (Recherche des plus proche voisins) Structurer les donnes sous forme dun arbre binaire 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 16
  • 17. CAS PARTICULIERS DES BSP TREES Cas particulier des BSP trees Dcompose lespace en volumes englobants (voxels) Dcoupe chaque voxel en deux sous-voxels grace un plan sparateur Est rprsent sous la forme dun arbre binaire Particularit du kd-Tree : plans sparateurs toujours perpendiculaires aux axes du repre de lespace Simplifie la construction mais aussi le parcours de larbre Plusieurs possibilits de constructions 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 17
  • 18. CONSTRUCTION DU KD-TREE 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 18
  • 19. CAS PARTICULIER Cas particulier de la construction Rptition de lobjet lorsque celui-ci est coup 27/12/2013 Quad-Tree et KD-Tree Bases de Donnes Avances 19