Journal Algorithme

Posté par .
Tags : aucun
0
31
mar.
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
  • # Re: Algorithme

    Posté par . Évalué à 1.

    Comment sont stockées tes régions/points ? par leur coordonnées x,y ?

    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 (page perso) . Évalué à 1.

    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

      Posté par . Évalué à 1.

      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

        Posté par . Évalué à 1.

        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).
  • # Re: Algorithme

    Posté par (page perso) . Évalué à 1.

    "constructive solid geometry" ou "Space subdivision techniques" sont des mots clés qui te guideront ...
  • # Re: Algorithme

    Posté par . Évalué à 1.

    Faut voir s'il y a vraiment besoin d'optimiser, parce que les comparaisons pour tester si un point est dans un rectangle, c'est quand même particulièrement rapide, à moins qu'il y ait énormément de régions. Il vaut quand même mieux faire des tests avec des données réalistes pour voir si ça vaut le coup de se prendre la tête.

    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 (page perso) . Évalué à 1.

      Le problème des quadtrees, si je ne m'abuse, c'est que :
      - 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 . Évalué à 1.

        > les zones ne peuvent pas sa chevaucher

        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 (page perso) . Évalué à 1.

          Ah bon ? Qu'est ce qui empêche une région d'appartenir à plusieurs carrés du quadtree ?
          Ç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 . Évalué à 1.

            Oui, les carrés définis dans le quadtree ne peuvent pas se chevaucher, c'est le principe de la construction. Mais je ne vois rien qui empêche des régions rectangulaires de se chevaucher. Les noeuds du quadtree ne fournissent que la liste des régions rectangulaires qui lui sont associées (par recouvrement ou inclusion), il n'y a pas de lien direct entre les régions.

            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 . Évalué à 1.

    Une idée comme ça: on va imaginer les régions stockées sous la forme (x_min, x_max, y_min, y_max). Alors si on les range par ordre x_min croissant, on peut traverser la liste pour chercher celles qui contiennent un point (x, y) de la façon suivante:
    * 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 (page perso) . Évalué à 1.

    Les arbres rouge-noir ça se prête pas trop mal à l'implémentation d'arbres d'intervalles, avec des recherches assez efficaces. Par contre en 2D ça doit être légèrement plus chaud pour trouver une relation d'ordre sur les clés (peut-être que la somme xmin + ymin irait bien, après tout ?) l'idéal serait peut-être d'alterner entre xmin et ymin selon la parité de la hauteur du noeud dans l'arbre, c'est pas trop compatible avec le fonctionnement des arbres rouge-noir classiques mais y a ptet moyen d'en faire une adaptation libre où les rotations se feraient entre le grand-père et le petit-fils plutôt qu'entre le père et le fils.
  • # Re: Algorithme

    Posté par . Évalué à 1.

    Merci à tous pour vos réponses, désolé de pas avoir répondu plus tôt, mais le décalage
    horaire + 1er avril, mon journal est vite passé en 3 ème page :)

    Michel

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.