Upload
rchbeir
View
266
Download
0
Embed Size (px)
DESCRIPTION
Citation preview
11/04/2023 1
Cours de Bases de données Avancées
PRÉSENTATION DU QUAD-TREE ET KD-
TREE
Quad-Tree et KD-Tree– Bases de Données Avancées
Aymeric OLIVIER & Patricia MARQUES
11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées
2
Historique des arbres
Présentation du Quad-Tree
Présentation du Kd-Tree
SOMMAIRE
11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées
3
Œuvre de beaucoup de recherches : Mathématiques et Programmation informatique But : trouver un algorithme optimal de segmentation
Point de vue mathématique : James N. Morgan & John A. Sonquist 1963
Point de vue informatique : J. Quinlan 1983
Aucun historique trouvé propres à nos arbres.
HISTORIQUE DES ARBRES
11/04/2023 4Quad-Tree et KD-Tree– Bases de Données Avancées
Source :https://www.enseignement.polytechnique.frhttp://fr.openclassrooms.com
LE QUAD-TREE
11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées
5
Principe d’utilisation
Définition du Quad-Tree
Méthodologie Découpage Collision
Exemple
Inconvénients de la méthode
SOUS-SOMMAIRE
11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées
6
Méthode d’indexation spatiale
Gestion d’objet à deux dimensions
Compression d’objet
Manipulation d’objet
PRINCIPE D’UTILISATION
11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées
7
Arbre ordonné (indexé) qui possède: Des feuilles : aucun fils Des sommets internes: 4 fils uniquement Une profondeur
Si l'image fait une taille NxN, alors le nombre de découpage (le nombre de niveaux dans l'arbre) est de N+1.
DÉFINITION DU QUAD-TREE
11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées
8
Décomposition récursive d’une image Construction de l’arbre
MÉTHODOLOGIE
On obtient le Quad-tree ci-
contre
11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées
9
y
x
Découpage Quand arrêter le découpage?
En fonction du nombre max du segment /feuille(fixé) En fonction de la profondeur max de l’arbre
A quelle branche appartient un segment ?
MÉTHODOLOGIE
Cy
Cx
Py
Px
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
C(x,y): Point central de la
découpe
P(x,y): Point quelconque de
A
11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées
10
Collision
Détermination de la trajectoire de chaque segment
Parcours de l’arbre
MÉTHODOLOGIE
11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées
11
Programme de découpage de Quad-Tree
http://donar.umiacs.umd.edu/quadtree/points/pointquad.html
EXEMPLE
11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées
12
Notion d’équilibrage de l’arbre Zone dense / zone vides
Exemple de la cabane en plein désert
INCONVÉNIENTS
11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées
13
AUTRES EXEMPLE
11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées
Source:http://www.irisa.fr/prive/kadi/DIIC/SDI-2-annee/Expose_KdTree.pdfhttp://courses.cs.washington.edu/courses/cse373/02au/lectures/lecture22l.pdf
14
K-D-TREE
11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées
15
Définition du KD-tree
Cas particulier des BSP-Trees
Construction du KD-tree
Cas particulier de construction
SOUS-SOMMAIRE
11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées
16
Une méthode de subdivision spatiale
Un Kd-tree est une structure de données dans un espace à k-dimensions
Un rôle double : Organiser l’espace pour accélérer le traitement de données
(Recherche des plus proche voisins) Structurer les données sous forme d’un arbre binaire
DEFINITION DU KD-TREE
11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées
17
Cas particulier des BSP trees Décompose l’espace en volumes englobants (voxels) Découpe chaque voxel en deux sous-voxels grace à un plan
séparateur Est réprésenté sous la forme d’un arbre binaire
Particularité du kd-Tree : plans séparateurs toujours perpendiculaires aux axes du repère de l’espace Simplifie la construction mais aussi le parcours de l’arbre
Plusieurs possibilités de constructions
CAS PARTICULIERS DES BSP TREES
11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées
18
CONSTRUCTION DU KD-TREE
11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées
19
Cas particulier de la construction Répétition de l’objet lorsque celui-ci est coupé
CAS PARTICULIER