[Algorithme] Correspondance de points
Bonjour à tous,
Je suis à la recherche d'un algorithme (normal vous me direz vu où l'on se trouve dans le forum ...). Je vous explique ce que je cherche :
Soit deux ensembles E1 et E2. La taille de ces ensembles pouvant être différente. Les éléments de E1 et E2 étant des points (une valeur X et une valeur Y).
Ce que je cherche à faire c'est, dans la mesure du possible pour tous les éléments de E1, trouver l'élément de E2 le plus proche (pour le calcul de la distance on pourra simplifier par distance(), peut importe ma méthode). Sachant que un élément de E2 ne peut être associé qu'à 0 ou 1 élément de E1.
Pour le moment je fais ça :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
// Calcul des distances
Pour tout e1 élément de E1 faire
Pour tout e2 élément de E2 faire
dist[e1,e2] = distance(e1,e2)
Fin pour
Fin pour
associe = 0
// Traitement de la matrice
Tant que (associe < size(E1) && associe < size(E2)) faire
valeur = MAX
e1c = NULL
e2c = NULL
// Recherche de la valeur minimum dans notre table de distance
Pour tout e1 de E1 faire
Pour tout e2 de E2 faire
si dist[e1,e2] < valeur alors
valeur = dist[e1,e2]
e1c = e1
e2c = e2
Fin si
Fin pour
Fin pour
Traitement(e1c,e2c)
// Suppression des distances correspondantes à e2c
Pour tout e1 élement de E1 faire
dist[e1,e2c] = MAX
Fin pour
// Suppression des distances correspondantes à e1c
Pour tout e2 élément de E2 faire
dist[e1c,e2] = MAX
Fin pour
incrémente associe
Fin tant que |
Bon ... c'est l'algo que j'utilise (après évidemment je ne l'ai pas implémenté tel quel ... mais le principe est le même derrière).
Que pouvez-vous me proposer de plus disons ... performant et peut-être même plus intelligent.
Je dis intelligent car, admettons la matrice de distance suivante :
---------E11-|--E12--|--E13--|-E14
E21-|--- 3 ---|---2---|---12--|--1
E22-|--- 7 ---|---7---|---8 --|--8
E23-|--- 9 ---|---4---|---4 --|--5
E24-|--- 7 ---|---11--|---11--|--3
E25-|--- 6 ---|---8---|---12--|--4
E26-|---10---|---3---|---9 --|--1
L'algorithme que je donne va donner les appels suivants :
Traitement(E14,E21)
Traitement(E12,E26)
Traitement(E13,E23)
Traitement(E11,E25)
Alors qu'une réorganisation des éléments dans les ensembles aurait donnée un autre résultat (ceci à cause des valeurs égales en fait).
Donc : comment améliorer cet algorithme ? Tant en terme de performance que d'un point de vue ... précision si je puis dire.
Concernant la performance, sachez juste que, la manière dont j'ai codé l'algorithme, distance n'est qu'un simple tableau à une dimension ... Je le parcours avec seulement une boucle for (pour la recherche du minimum).
Voilà, j'espère avoir été plus ou moins clair. Si vous avez besoin de plus d'informations, surtout N'HESITEZ PAS à me le dire ... Je détaillerai plus ou je ré-expliquerai les choses différemment ou je ne sais quoi :D
Merci de m'avoir lu et de votre éventuelle réponse ;)
Bonne journée
