IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

[Complexité] recherche des n points les plus proches d'un point dans une liste


Sujet :

Algorithmes et structures de données

  1. #1
    Membre du Club
    Profil pro
    Inscrit en
    février 2006
    Messages
    127
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : février 2006
    Messages : 127
    Points : 49
    Points
    49
    Par défaut [Complexité] recherche des n points les plus proches d'un point dans une liste
    Bonjour,

    Voici le problème auquel je suis confronté:

    Je dispose d'un vecteurs de points. Chaque points est caractérisé par des coordonnées cartésiennes x et y. Ce vecteur contient tout de même la bagatelle de 15 millions d'éléments ...

    Je dois régulièrement chercher dans le vecteur les n points les plus proches selon la distance d1 de points A(x,y) en entrée de la méthode.
    (d1(A,B)= |xA-xB|+|yA-yB|)


    Actuellement je suis tenté de faire comme il suit:
    Je maintiens un arbre binaire B qui contient les n points de distances minimales trouvés dans la liste. Chaque noeud du tas binaire forme un couple N(indice du point dans le vecteur, distance à A).
    J'initialise mon tas binaire vide, je parcours mon vecteur de points.
    - Si mon tas contient moins de n éléments, alors j'insère l'élément courant.
    - Sinon, j'extrais l'élément N1 de distance à A maximale du tas. Si l'élément courant (point) de la liste a une distance à A inférieure, alors j'insère cette élément dans le tas et je retire l'élément de distance à A maximale dans le tas.

    Ainsi, je n'effectue qu'un seul parcours de liste et qui plus est, la liste des points candidats est codé par un tas binaire qui offre des complexités plutôt correctes pour les opérations sur cette liste de candidats (extraction du maximum, insertion d'un nouvel élément, suppression d'un élément).

    Mon problème est le suivant:
    - Je parcours toute la liste à chaque recherche !
    Je pense qu'il y a peut être possibilité de trier la liste pour pruner les espaces de recherche lors d'une requête, et ce indépendamment du point A en entrée. J'ai quelques doutes cependant. J'imagine que je ne suis pas le premier à rencontrer ce problème. Peut-être certains auront t'ils des solutions élégantes, plus rapide. Je précise que les coordonnées sont entières et bornées (minX, maxX, minY, maxY).

    Cordialement,

  2. #2
    Membre éclairé
    Avatar de panda31
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    juin 2003
    Messages
    670
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : Conseil

    Informations forums :
    Inscription : juin 2003
    Messages : 670
    Points : 848
    Points
    848
    Par défaut
    Je vais essayer de reformuler ton problème pour mieux le comprendre moi-même .

    p point caractérisé par ses coordonnées 2D (x,y)
    V vecteur de grande taille contenant des points

    Tu veux isoler ("régulièrement" comme tu dis) les couples de points les plus proches grâce au calcul de la distance.

    Tu ne veux pas calculer toutes les distances une fois pour toutes (ordre N²)
    En effet, si tu as N points, tu auras N² calculs.

    As-tu des valeurs seuil ?
    Quel est le problème final auquel tu es confronté ?

    Dis-moi si j'ai dit des absurdités
    Michaël Mary
    Consultant PLM dans une société de conseil toulousaine
    Auditeur CNAM-IPST depuis septembre 2008
    "Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live."
    John F. Woods
    mon cv et mon domaine et mon blog
    Aucune question technique par MP, svp

  3. #3
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 062
    Points : 15 892
    Points
    15 892
    Par défaut
    Citation Envoyé par Benoit_T Voir le message
    Mon problème est le suivant:
    - Je parcours toute la liste à chaque recherche !
    Je pense qu'il y a peut être possibilité de trier la liste pour pruner les espaces de recherche lors d'une requête, et ce indépendamment du point A en entrée. J'ai quelques doutes cependant. J'imagine que je ne suis pas le premier à rencontrer ce problème. Peut-être certains auront t'ils des solutions élégantes, plus rapide. Je précise que les coordonnées sont entières et bornées (minX, maxX, minY, maxY).
    En découpant ton espace en zones, tu peux tout d'abord réduire ta recherche aux points qui sont dans la même zone que A(x,y). Puis, si tu n'as pas ton compte de "n" points, étendre la recherche aux zones voisines, etc.

    Il te faut donc une structure hiérarchique de découpage en zones, qui te permette de "dézoomer" progressivement autour du point A(x,y). Le découpage en zone peut être uniforme (structure Quad-Tree) ou non-uniforme (structure kd-tree).
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  4. #4
    Membre du Club
    Profil pro
    Inscrit en
    février 2006
    Messages
    127
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : février 2006
    Messages : 127
    Points : 49
    Points
    49
    Par défaut
    Citation Envoyé par panda31 Voir le message

    Tu ne veux pas calculer toutes les distances une fois pour toutes (ordre N²)
    En effet, si tu as N points, tu auras N² calculs.
    Le vecteur fait quelques fois autour de 15 millions de points, 15000000² = 2,25*10^16 ce qui fait, à raison de 4octets par valeur de distance une matrice de distance de ... 22,5 petaocets ...
    Citation Envoyé par panda31 Voir le message
    As-tu des valeurs seuil ?
    Quel est le problème final auquel tu es confronté ?
    En fait je dispose de ce vecteur et dedans je "pioche" un sommet. Ensuite, je cherche dans la vecteur de points les n points les plus proches de ce sommet, c'est pas plus compliqué que ça !

  5. #5
    Membre du Club
    Profil pro
    Inscrit en
    février 2006
    Messages
    127
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : février 2006
    Messages : 127
    Points : 49
    Points
    49
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    En découpant ton espace en zones, tu peux tout d'abord réduire ta recherche aux points qui sont dans la même zone que A(x,y). Puis, si tu n'as pas ton compte de "n" points, étendre la recherche aux zones voisines, etc.

    Il te faut donc une structure hiérarchique de découpage en zones, qui te permette de "dézoomer" progressivement autour du point A(x,y). Le découpage en zone peut être uniforme (structure Quad-Tree) ou non-uniforme (structure kd-tree).
    Intéressant ça, je vais y jeter un coup d'oeil, merci !

  6. #6
    Membre éclairé
    Avatar de panda31
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    juin 2003
    Messages
    670
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : Conseil

    Informations forums :
    Inscription : juin 2003
    Messages : 670
    Points : 848
    Points
    848
    Par défaut
    Citation Envoyé par Benoit_T Voir le message
    Le vecteur fait quelques fois autour de 15 millions de points, 15000000² = 2,25*10^16 ce qui fait, à raison de 4octets par valeur de distance une matrice de distance de ... 22,5 petaocets ...
    Oui c'est pour cela que j'écrivais "Tu ne veux pas". Et c'est normal . Ce n'était pas une question

    Citation Envoyé par Benoit_T Voir le message
    En fait je dispose de ce vecteur et dedans je "pioche" un sommet. Ensuite, je cherche dans la vecteur de points les n points les plus proches de ce sommet, c'est pas plus compliqué que ça !
    Je comprends mieux maintenant. Des problèmes comme celui-ci, il ne faut pas s'y atteler de bon matin.

    Quand je parlais de valeurs seuil, je pensais également à établir des zones.

    Tiens nous au jus
    Michaël Mary
    Consultant PLM dans une société de conseil toulousaine
    Auditeur CNAM-IPST depuis septembre 2008
    "Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live."
    John F. Woods
    mon cv et mon domaine et mon blog
    Aucune question technique par MP, svp

  7. #7
    Membre émérite
    Avatar de SpiceGuid
    Homme Profil pro
    Inscrit en
    juin 2007
    Messages
    1 701
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : juin 2007
    Messages : 1 701
    Points : 2 974
    Points
    2 974
    Par défaut
    Comme l'a déjà dit pseudocode tu as le choix entre un Quadtree et un KD-tree.
    Vu le nombre d'éléments j'opterais pour un KD-tree car plus économe en mémoire.

    L'inconvénient du Quadtree et du KD-tree c'est qu'aucun des deux ne te donne directement les n plus proches voisins. Par contre ils peuvent te donner facilement l'ensemble de tous les points inclus dans un rectangle. À toi de (re-)dimensionner ce rectangle (au besoin dynamiquement, au cours de la remontée dans l'arbre) pour t'assurer qu'il contienne bien les n points recherchés.
    Du même auteur: mon projet, le dernier article publié, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.

  8. #8
    Membre éprouvé
    Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mars 2009
    Messages
    552
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : mars 2009
    Messages : 552
    Points : 1 060
    Points
    1 060
    Par défaut
    Bonsoir,

    Citation Envoyé par SpiceGuid Voir le message
    Comme l'a déjà dit pseudocode tu as le choix entre un Quadtree et un KD-tree.
    Vu le nombre d'éléments j'opterais pour un KD-tree car plus économe en mémoire.
    S'il a une répartition (sensiblement) homogène de ses points dans l'espace, un bête maillage reposant sur une grille régulière peut être suffisant...

    C'est d'ailleurs plus économe pour la mémoire et plus facile à parcourir que les arbres cités. Aussi, c'est plus facile de trouver les mailles voisines d'une autre que les éléments voisin d'une feuille de l'arbre...

    La version simple est la suivante :
    - Choisir une taille de grille : nx,ny
    - Numéroter l'ensemble de tes points : [1..NPT]
    - Générer une liste des points dans chaque maille
    => Pour chaque point, l'ajouter à la liste des points de la maille concernée

    Pour chaque maille, tu as un pointeur "direct" sur les points qu'elle contient via la liste que tu as généré.

    Ensuite, prenons un point P(X,Y) pour lequel tu cherches le voisinage. Tu trouve la maille correspondant à ce point (I,J). Au besoin, tu récupères les mailles voisines de (I,J) (et les points qu'elles contiennent) si tu n'as pas assez de points dans (I,J)

    Remarques :

    - C'est pas très snobe comme méthode. Au diable l'élégance, faut que ça fonctionne et vite

    - Je ne suis pas fan de ces arbres d'indexation spatiale. (La relation père fils de l'arbre que l'on traine ne sert pas à grand chose et complexifie la recherche de voisinage entre les points) Quitte à avoir une structure de données complexes, il faudrait au moins que celle ci possède la notion de voisinage...

    - Quadtree et Kdtree ne sont utiles qu'en cas de répartition non homogène.

    - Le "rattachement" des points, segment et surface à un "tree" est beaucoup plus couteux que le rattachement à une grille régulière.

    - En cas de répartition non homogène des points, rien n'interdit de faire des grilles dans la grille là où c'est nécessaire. La notion d'arborescence est là, on la connait, mais on ne la parcourt pas systématiquement en mémoire. On a, pour chaque niveau de maillage, une indication sur le nombre d'éléments contenus dans une maille et un pointeur sur les éléments qu'elle contient.

    Bye

    ps : C'est quoi tes données? Répartition sensiblement homogène ou non? Répartition régulière par hasard (genre un point tout les 250m en x et en y)?

  9. #9
    Membre du Club
    Profil pro
    Inscrit en
    février 2006
    Messages
    127
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : février 2006
    Messages : 127
    Points : 49
    Points
    49
    Par défaut
    Citation Envoyé par bretus Voir le message
    ps : C'est quoi tes données? Répartition sensiblement homogène ou non? Répartition régulière par hasard (genre un point tout les 250m en x et en y)?
    Merci pour cette réponse, cette approche me semble très intéressante. Le gain en temps de calcul semble conséquent, l'implémentation aisée et qui plus est la structure est économe en mémoire.

    Concernant les données, il s'agit de coordonnées cartésiennes de sommets d'un graphe routier. A l'échelle française, mon graphe de travail contient tout de même 10 millions de sommets et 20 millions d'arêtes. A l'échelle Européenne, c'est carrément 20 millions de sommets et 100 millions d'arêtes. La répartition des sommets est relativement uniforme; si ce n'est qu'en zone urbaine, la densité de sommet par unité d'aire est nettement supérieure à la moyenne.

    Cordialement,

  10. #10
    Membre éprouvé
    Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mars 2009
    Messages
    552
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : mars 2009
    Messages : 552
    Points : 1 060
    Points
    1 060
    Par défaut
    De rien, content que ça t'aide!

    Essaye peut être de faire un niveau spécifique pour les régions urbaines si vraiment.

    Par contre, question bête, mais tu gagnerais pas plus de temps avec un SGBD géographique? Genre postgres/postgis? (ces bêtes là assurent elles même une indexation spatiale)

    ++

  11. #11
    Expert éminent sénior

    Profil pro
    Inscrit en
    janvier 2007
    Messages
    10 591
    Détails du profil
    Informations personnelles :
    Âge : 64
    Localisation : France

    Informations forums :
    Inscription : janvier 2007
    Messages : 10 591
    Points : 17 295
    Points
    17 295
    Billets dans le blog
    2
    Par défaut
    ce que je proposerais (je l'ai déjà exposé ailleurs ici) c'est :

    1. tout d'abord un tri simultané X,Y, une fois pour toutes :

      • en X croissant
      • pour X constant en Y croissant


    2. Puis découper en "bin", c'est à dire évaluer une taille "raisonnable" de découpage en X, donnant un résultat relativement correct en taille (par exemple en France au km = 1000 points), et stocker dans une table l'adresse (je suppose que tu as une liste chaînée) du point correspondant (si ce n'est pas une liste chaînée tu stockes directement l'indice).

    3. Enfin, chaque fois qu'on te demande le voisinage de (x,y) :
      • trouver le numéro de "bin" (simple division)
      • partir de ce point et explorer dans les 2 sens. On s'arrête dès que la distance en X devient supérieure à ta distance limite.



    ça devrait être pas mal rapide..


    Je le fais sur 300 à 500 000 points, et ça prend, sur un petit PC "normal", pas boosté du tout, moins de 1/10 seconde...
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

Discussions similaires

  1. Identifier les points les plus proches
    Par Wel Kol dans le forum MATLAB
    Réponses: 8
    Dernier message: 11/04/2014, 13h12
  2. Repérer le couple de points les plus proches dans des matrices
    Par lolo-40 dans le forum Mathématiques
    Réponses: 0
    Dernier message: 23/02/2014, 17h12
  3. Recherche de lieux les plus proches d'un point donné
    Par Quentz dans le forum Performance Web
    Réponses: 2
    Dernier message: 25/10/2013, 17h22
  4. [Google Maps] récuperer les itineraires les plus proche d'un point.
    Par su4p aka dans le forum APIs Google
    Réponses: 1
    Dernier message: 25/02/2012, 19h45
  5. algorithme des deux points les plus proches
    Par biba1980 dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 10/11/2009, 05h18

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo