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 :

Calcul de distance entre points


Sujet :

Algorithmes et structures de données

  1. #1
    Membre régulier
    Calcul de distance entre points
    Bonjour,
    Je stocke dans une BDD des coordonnées de points sous la forme (X,Y).
    L'utilisateur de mon service va émettre une requête avec des coordonnées concernant sa localisation sous cette même forme (X,Y) et un rayon de recherche (un entier).

    Il s'agit pour moi ensuite de renvoyer le premier élément (point) de la base inclus dans le périmètre de recherche.

    Pour cela, la première méthode qui me vient à l'esprit c'est de calculer la norme du vecteur que forme le pointUtilisateur avec chacun des points de la BDD. Si cette norme est inférieure au rayon alors le point est dans le périmètre de recherche.

    Le pb évident, c'est que le temps de traitement va exploser si la BDD est grosse.
    Est ce que vous voyez un moyen d'organiser les données de manière à optimiser ce type de traitement ou est ce que vous voyez une méthode plus simple pour renvoyer le premier élément inclus dans le périmètre.

    Je continue à réfléchir de mon côté. Merci d'avance pour votre aide

  2. #2
    Modérateur

    Bonsoir,

    je sais qu'il y a des optimisations de ce type utilisées dans l'algorithmes des k plus proches voisins.
    C'est des partitions de l'espace afin de limiter la recherche.
    Mais je n'ai rien programmé de ce genre... donc je ne peux t'aider plus.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  3. #3
    Expert éminent
    Soit X0 et Y0 les coordonées point et R la distance.
    On peut faire une préselection ainsi
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
     
    SELECT * WHERE (X<= X0+D) AND (X>= X0-D) AND (Y<= Y0+D) AND (Y>= Y0-D)

    Puis sur les quelques records selectionnés, faire le vrai calcul de la norme
    ou si le gestionnaire de la base de donnée est rapide et optimise les "AND" :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    D2=D*D
    SELECT * WHERE (X<= X0+D) AND (X>= X0-D) AND (Y<= Y0+D) AND (Y>= Y0-D) 
    AND ( (X0-X)(X0-X)+(Y0-Y)(Y0-Y)<D2 )


    Si on veut encore plus optimiser, on peut :
    - diviser l'espace en carrés,
    - associer un nombre à chacun des carrés et ajouter ce champs à la table de la base de donnée,
    - indexer ce champ,
    - lors d'une recherche, déterminer les carrés C1, C2, Cn qui peuvent être concernées,
    Exemple :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
     
    SELECT * WHERE (CARRE=C1 OR CARRE=C2 ....) AND ( (X0-X)(X0-X)+(Y0-Y)(Y0-Y)<D2 )-
    " Le croquemitaine ! Aaaaaah ! Où ça ? " ©Homer Simpson

  4. #4
    Membre expérimenté
    Tu peux aussi utiliser les quadtree, qui sont en principe assez performants pour ce genre de recherche.

    Attention, il faut tester la proximité par rapport aux segments du périmètre, et non par rapport aux sommets comme tu semble le faire: si les segments sont grands, un point peut être très proche d'un segment tout en étant éloigné des sommets.

  5. #5
    Membre expérimenté
    Les algos de recherche sont performants si les données sont triées
    mais
    il n'existe pas de relation d'ordre à 2 dimensions
    Un bon compromis serait de trier tes données selon X
    la recherche des points entre X-R et X+R serait d'ordre log(N)
    Passer les points de cet intervalle en revue devrait être possible en un temps raisonnable
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

  6. #6
    Rédacteur

    Citation Envoyé par Nebulix Voir le message
    il n'existe pas de relation d'ordre à 2 dimensions
    ?

    (a,b) &#8804; (c,d) <==> (a < c) ou (a = c et b &#8804; d)
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  7. #7
    Membre expérimenté
    Citation Envoyé par pseudocode Voir le message


    (a,b) &#8804; (c,d) <==> (a < c) ou (a = c et b &#8804; d)
    Je voulais dire pas de relation d'ordre ayant une quelconque utilité dans R²
    Qui a entendu parler d'une relation d'ordre pour les nombres complexes ?
    (1,1)<(1,99999999)<(2,1)
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

  8. #8
    Expert éminent sénior
    Citation Envoyé par Nebulix Voir le message
    Un bon compromis serait de trier tes données selon X
    Un meilleur compromis encore serait de trier les points en "matrice-like", selon X, et à X égal selon Y..

    En un seul quick sort (N logN)

    "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

  9. #9
    Membre expérimenté
    Citation Envoyé par souviron34 Voir le message
    Un meilleur compromis encore serait de trier les points en "matrice-like", selon X, et à X égal selon Y..

    En un seul quick sort (N logN)
    Si les X sont des réels, le cas d'égalité n'arrivera jamais (tu connais le problème des tests d'égalité de réels )
    Si les X prennent un nombre fini de valeurs, il faudra quand même chercher les bons Y pour un nombre >1 de valeurs de X donc dans une liste non triée...
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

  10. #10
    Membre expérimenté
    Bonjour,

    l'approche classique consiste à utiliser des KD-trees et on peut trouver tout ce qu'il faut d'un point de vue informatique pour le calcul rapide des plus proches voisins dans la troisième édition des Numerical Recipes (celle de 2007).

  11. #11
    Expert éminent sénior
    Citation Envoyé par Nebulix Voir le message
    Si les X sont des réels, le cas d'égalité n'arrivera jamais (tu connais le problème des tests d'égalité de réels )
    Si les X prennent un nombre fini de valeurs, il faudra quand même chercher les bons Y pour un nombre >1 de valeurs de X donc dans une liste non triée...
    D'une part un seuil en précision règle le problème d'égalité.

    D'autre part, cela réduit quand même considérablement...

    On n'explore plus que dans un rayon R... (avec des raccourcis possibles et un arrêt si on explore dans chaque sens autour du X le plus proche)..

    Mais ma formulation n'était pas tout à fait exacte...
    "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

  12. #12
    Membre expérimenté
    Citation Envoyé par souviron34 Voir le message
    D'une part un seuil en précision règle le problème d'égalité.

    D'autre part, cela réduit quand même considérablement...
    Un tri grossier peut être fait en 2D et se révèle donc plus efficace qu'un tri fin.
    Joli !
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)