Journal : Algorithme
Posté par LeMagicien Garcimore () le 31 mars 2004
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
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
> Lire le journal (13 commentaires, moyenne: 1).
Vous avez demandé le commentaire #383768.
Run by 
Cette page a été générée par Templeet en 0.045s (dont 0.0047 de SQL).
Cette page est peut-être conforme xhtml 1.0.
Information sur le site.
Re: Algorithme
Faut-il optimiser l'insertion des rectangles dans ta structure, ou la recherche des rectangles contenant une position ?
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
En fait j'ai déjà une structure de grille en dessous.
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
Solution lente à l'insertion, mais qui devrait être rapide :
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).