Salut !
Je cherche un algorithme (ou plutôt une structure de donnée) pour le problème suivant :
On considère un plan. Sur ce plan, on a plusieurs régions rectangulaires qui peuvent se chevaucher. Je voudrais connaitre une façon de trouver rapidement quelles régions contiennent un point donné.
La solution évidente est de parcourir la totalité des régions, mais je trouve ca pas vraiment efficace...
J'ai l'intuition qu'une structure d'arbre peut améliorer l'efficacité, mais j'arrive pas à
mettre le doigt dessus.
Merci!
Garci
Journal Algorithme
31
mar.
2004
# Re: Algorithme
Posté par Toto . Évalué à 1.
Si oui, dans ce cas, tu peux faire un tableau qui contient tous les rectangles (coord x, y du haut gauche + longueur + largeur). Quand tu cherches le point, tu regarde si
x >= x_pt && x <= x+longueur && y >= y_pt && y <= y+largeur
Mais bon il y a surement mieux, c'est juste une idée qui me passe par la tete
# Re: Algorithme
Posté par Lucas . Évalué à 1.
Par exemple, une structure où l'insertion est lente, mais la recherche très rapide, te convient-elle ?
Si oui, Tu peux essayer de faire une sorte de grille au dessus de ton plan. Pour chaque case de la grille, une liste chainée de rectangles recouvrant au moins une partie de la grille. Mais c'est un peu bourrin.
C'est un problème pour quoi ?
Sinon, il faut chercher du coté de tableaux à plusieurs dimensions triés pour limiter le nombre de tests...
[^] # Re: Algorithme
Posté par LeMagicien Garcimore . Évalué à 1.
L'insertion lente n'est pas un problème, par contre, la recherche doit être assez rapide.
Ton idée de liste chaînée me fait penser à autre une autre solution au problème de départ.
En fait, je cherche, au cours d'un pathfinding, a savoir si le chemin courant va traverser un chemin déjà existant. J'ai déjà un façon de détecter si 2 chemins se croisent, mais je cherche à optimiser l'appel à cet algo en le l'appelant uniquement pour les points qui se situent dans la "bounding box" des chemins déjà tracés.
Je sais pas si mon explication est bien clair ...
A+
Michel
[^] # Re: Algorithme
Posté par Lebas Sébastien . Évalué à 1.
Une table de hashage associant les coordonnées des points (clé) à une liste de régions.
A noter que si ce qui t'intéresse c'est juste la présence d'une région, tu n'a même pas besoin de faire une liste chaînée, un simple tableau d'identifiant suffit.
Bon, par contre, il faut faire l'insertion des régions case par case dans la table de hashage, ce qui peut être un peu long ...
Je ne pense pas qu'il soit possible de faire mieux avec un arbre au niveau de la recherche (a vue de nez, ta vitesse de recherche dans l'arbre dépendra de la profondeur de ce que tu cherche dans l'arbre, donc augmentera avec le nombre de données insérées, alors que la recherche dans une table de hashage se fait en temps constant).
# Re: Algorithme
Posté par Mouns (site web personnel) . Évalué à 1.
# Re: Algorithme
Posté par Frédéric Lopez . Évalué à 1.
Sinon, tu peux peut-être utiliser des quadtrees (voir http://www.flipcode.com/tutorials/tut_octrees.shtml(...) ) pour ta structure de données.
[^] # Re: Algorithme
Posté par Pierre Tramo (site web personnel) . Évalué à 1.
- les zones ne peuvent pas sa chevaucher
- ça n'est adapté qu'à des données statiques, une modification risque d'être _très_ coûteuse (ça n'est ptet pas important ici)
[^] # Re: Algorithme
Posté par Frédéric Lopez . Évalué à 1.
Ah bon ? Qu'est ce qui empêche une région d'appartenir à plusieurs carrés du quadtree ?
> ça n'est adapté qu'à des données statiques, une modification risque
> d'être _très_ coûteuse (ça n'est ptet pas important ici)
Oui, il faudra sans doute regénérer le quadtree entier à chaque insertion, mais comme la lenteur de l'insertion ne semblait pas être un problème...
[^] # Re: Algorithme
Posté par Pierre Tramo (site web personnel) . Évalué à 1.
Ça n'est pas ce que j'ai dit : un carré d'une feuille de l'arbre ne peut appartenir qu'à une région (enfin si j'ai bien compris le principe (je n'ai parcouru ton lien que rapidement), ça a l'air d'être une tétrachotomie, et la surface totale est une partition (au sens ensembliste du terme) de carrés qui sont des parties de régions), donc on ne peut pas avoir deux régions qui se superposent.
[^] # Re: Algorithme
Posté par Frédéric Lopez . Évalué à 1.
Enfin, c'est peut-être juste un problème de vocabulaire, pour moi le mot région à le même sens que celui utilisé dans la formulation de la question d'origine.
# Re: Algorithme
Posté par Snark_Boojum . Évalué à 1.
* tant que x_max < x, on peut continuer, aucune chance que le point soit dedans (un seul test par zone, donc);
* dès que x_max >= x, on regarde la condition x_min <= x ; tant qu'elle est vraie, on fait la vérification y >= y_min et y <= y_max (ie: on regarde complètement ces zones: quatre tests par zone);
* dès que x_min > x, on s'arrête de parcourir la liste, il n'est plus possible que le point soit dans les zones (zéro test par zone).
Ca doit accélérer un peu les choses ; sachant qu'on peut encore améliorer les points suivants:
1) s'assurer que le compilo fait une évaluation paresseuse des conditions sur y (ie: pas de test de la seconde si la première est déjà fausse);
2) pour les zones qui ont le même x_min, les ranger par x_max croissant;
3) et pour les zones qui ont les mêmes x_min et x_max, les ranger par y_min croissant;
4) et pour les zones qui ont les mêmes x_min, x_max et y_min, les ranger par y_max croissant.
Le 1) coûte pas cher. Par contre 2), 3) et 4), suivant les configurations qui apparaissent dans le problème, on n'a rien à gagner. En fait, elles ne coûtent pas si cher à l'insertion, mais l'algo de parcours devient un peu lourd à écrire.
Et naturellement, si le problème fait qu'il vaut mieux ranger par y_min que par x_min, il ne faut pas se gêner!
Bon courage
# Re: Algorithme
Posté par Pierre Tramo (site web personnel) . Évalué à 1.
# Re: Algorithme
Posté par LeMagicien Garcimore . Évalué à 1.
horaire + 1er avril, mon journal est vite passé en 3 ème page :)
Michel
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.