Structure de donnée ordonnée sur deux dimensions?

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour,

Je suis en train de travailler sur un algorithme qui aurais besoin de filtrer efficacement un ensemble d'éléments avec des critères linéaires. Ces éléments peuvent être triés totalement sur chaque dimension séparément, mais pas sur toutes en même temps.

Par exemple, une liste de points peut être trié par rapport à une dimension ou par rapport à la deuxième, mais pas par rapport aux deux en même temps. Du coup, pour trouver les éléments qui satisfont à des contraintes sur les deux dimensions, je vois pas très bien comment on pourrait faire pour éviter de regarder toute la liste.

En faite, vu que l'on peut trier totalement une liste d'entier, il est simple de sélectionner ceux qui sont supérieur à 150 et inférieur à 300. En triant cette liste en avance, on peut rechercher le premier élément en $\mathcal{O}(\log{n})$, puis on itère jusqu'à atteindre un élément supérieur à 300.

Le problème, c'est que je n'arrive pas à trouver un moyen d'adapter ce genre d'algo sur plusieurs dimensions. Donc dans ce cas, avec une liste de points, on veut ceux qui sont contenus dans un rectangle.

Est-ce que quelqu'un a déjà entendu parler d'un algo/structure de donnée qui correspondrait à ce que je cherche? Si non, est-ce que quelqu'un à un moyen de montrer que ce n'est pas possible de le faire efficacement (par exemple, parce qu'il n'y a pas d'ordre total).

+0 -0

Bonsoir,

Il y a le range tree, le kd tree. Regardes du côté de « range searching ».

edit : mais je n'ai pas bien compris ce que tu veux. Tes contraintes sont forcément de la forme d'une boite ou bien c'est juste des contraintes linéaires ?

Édité par blo yhg

+0 -0
Staff

Cette réponse a aidé l'auteur du sujet

Salut,

Il me semble que les quadtree correspondent à ce que tu cherches.

Un quadtree est une structure de données de type arbre dans laquelle chaque nœud a quatre fils. Les quadtrees sont le plus souvent utilisés pour partitionner un espace bidimensionnel en le subdivisant récursivement en quatre nœuds.

Wikipédia

C'est très utilisé pour des bounding box, ou pour la recherche de points appartenant à des rectangle comme tu dis. C'est une généralisation de la dichotomie sur deux dimensions.

Édité par Algue-Rythme

+0 -0
Auteur du sujet

Oui, j'avais pensé aux quadtree, mais sur le moment j'arrivais pas à voir comment les utiliser. Notamment parce que je voulais lier les éléments qui étaient sur la même dimension réelle. Par exemple, pour stocker un rectangle avec le point haut-gauche et le point bas-droit, il y a 2 dimensions réelles, mais il faut un "quadtree" à 16 entrées pour faire une recherche en séparant les deux positions sur x et les deux sur y. Du coup, après réflexion, ça correspond parfaitement à ce que je cherche.

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte