19
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 1 14/06/2022 Aymeric OLIVIER & Patricia MARQUES

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

  • Upload
    rchbeir

  • View
    266

  • Download
    0

Embed Size (px)

DESCRIPTION

 

Citation preview

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées

13

AUTRES EXEMPLE

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

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

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

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

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

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

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

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

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

11/04/2023 Quad-Tree et KD-Tree– Bases de Données Avancées

18

CONSTRUCTION DU KD-TREE

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

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