Correction : TP Partition de l'espace ( arbres quaternaires )

Construction du quadtree

def inserer(self, points):
        if len(points) <= MAX_POINTS: # si on a encore de la place dans le quadtree,
            self.points = points  # alors, on stocke les points

        else: # sinon, on le divise :

            # 1. répartition des points dans la liste de leur région respective
            points_NO = []
            points_NE = []
            points_SE = []
            points_SO = []

            for point in points:
                # SO
                if self.is_in(self.x0, self.y0, self.l/2, self.h/2, point):
                    points_SO.append(point)
                # SE
                elif self.is_in(self.x0+self.l/2, self.y0, self.l/2, self.h/2, point):
                    points_SE.append(point)
                # NE
                elif self.is_in(self.x0+self.l/2, self.y0+self.h/2, self.l/2, self.h/2, point):
                    points_NE.append(point)
                # NO
                else:
                    points_NO.append(point)


            # 2. création des quadtree-fils, et insertion de leur liste de points respectives
            self.SO = QuadTree(self.x0, self.y0, self.l/2, self.h/2)
            self.SO.inserer(points_SO)

            self.SE = QuadTree(self.x0+self.l/2, self.y0, self.l/2, self.h/2)
            self.SE.inserer(points_SE)

            self.NE = QuadTree(self.x0+self.l/2, self.y0+self.h/2, self.l/2, self.h/2)
            self.NE.inserer(points_NE)

            self.NO = QuadTree(self.x0, self.y0+self.h/2, self.l/2, self.h/2)
            self.NO.inserer(points_NO)
			

Instanciation des points, insertion et affichage :

points = [Point(randint(1,254), randint(1,254)) for i in range(100)]

qt = QuadTree(0, 0, 255, 255)
qt.inserer(points)
qt.afficher()
			

On constate bien l'efficacité de cette structure de données : les nœuds ne sont créés que "si besoin", c'est à dire dans les zones où la densité de points est importante; dans les zones peu denses, le nombre de divisions, donc de nœuds nécessaires, est plus réduit.

Remarque : un problème de cette implémentation de la méthode inserer est qu'il n'est plus possible ensuite d'insérer des nouveaux points dans le quadtree, il faut le réinitialiser...

Recherche dans le quadtree des plus proches voisins

    def trouver_voisins(self, point):
        if self.SO is None: # cas de base
            return self.points        # on renvoie la liste des points de la feuille, donc les plus proches du point
              
        else:        # cas général
            if self.is_in(self.x0, self.y0, self.l/2, self.h/2, point):               # le point est dans la zone SO ?
                return self.SO.trouver_voisins(point)                                 # alors on recherche récursivement dans cette zone,
            elif self.is_in(self.x0+self.l/2, self.y0, self.l/2, self.h/2, point):    # sinon si il est dans la zone SE,
                return self.SE.trouver_voisins(point)                                 # etc....
            elif self.is_in(self.x0+self.l/2, self.y0+self.h/2, self.l/2, self.h/2, point):
                return self.NE.trouver_voisins(point)
            else:
                return self.NO.trouver_voisins(point)
			

Recherche des résultats et affichage :

point = Point(randint(1,254), randint(1,254))
qt.afficher_voisins(point)   
			

On constate que les "points les plus proches" sont en fait les "points dans la zone" du point témoin; si cette zone est grande ( parce qu'il y a peu de points ), alors la recherche n'est pas vraiment précise. Cette précision dépend donc de la taille des zones "élémentaires", c'est à dire de la "profondeur" du découpage récursif.
De plus, si on voulait vraiment avoir les points les plus proches, il faudrait chercher dans toutes les zones autour du point, l'algorithme de recherche serait plus complexe...

Script complet

Correction quadtree