Discussion :

[Platypus]

bonjour,

voila mon probleme .
j'ai un tableau de point ( structure POINT {long,long} )
le nombre d element est variable entre 1 et 225 .

je reçois un POINT p , et je veux trouver l'index du POINT du tableau précedent le plus proche du POINT p reçu.
le HIC est que le tableau est ordonné mais pas forcement tjrs ds le meme sens . ( en gros y a 4 facons de l ordonner suivant X ou Y croissant ou décroissant )

j'ai trouvé un algo mais franchement c'est une usine a gaz ...

si qq'un une idée ?

pour l'explication , il s'agit d'un algo pour ensuite calibrer une dalle tactile . celle ci n'etant pas forcement monter dans le moniteur toujours dans le meme sens selon constructeur .

ps : j'espere avoir été clair et avoir posté dans le bon forum .

[10_GOTO_10]

Une astuce consiste à ordonner le tableau suivant un mix entre les coordonnées X et Y:

Exemple

X = 1234
Y = 5678

MIX = 15263748

Ca permet d'avoir toujours les chiffres les plus significatifs en début, et donc de retrouver le point plus facilement à partir de coordonnées proches.

[Platypus]

interessant .
ca permettrais effectivement de reduire les comparaisons mais si j'ai bien compris l astuce il reste un probleme .

en effet le tableau peut etre ordonner avec des X Croissant et Y Decroissant .
auquel cas le Mix devient desordonné

exemple:
[1][4] - [1][3] - [1][2] - [1][1] - [2][4] - [2][3] - [2][2] - [2][1] etc ...

[FrancisSourd]

Il est possible d'utiliser des structures de données géométriques du type quadtrees qui permettent de "bien" représenter les points de l'espace.
http://www.cs.umd.edu/~hjs/pubs/kim.pdf

Toutefois, construire une telle structure prend un peu de temps. Pour que cela soit rentable, il faut que la requête "recherche du point le plus proche" soit effectuée un grand nombre de fois...

[vmolines]

Trouver le point le plus proche du point passé en paramètre au sein d'un tableau de points ?

Il suffit de parcourir ton tableau et de calculer la distance du point courant avec le point passé en paramètre. Le calcul de la distance se fait très simplement avec la formule :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

distance = racine((x2-x1)^2 + (y2-y1)^2)

Tu gardes l'indice du point qui a donné la distance minimum... je pense que je t'apprend rien sur ce genre d'algo de recherche de min/max.

[Platypus]

oui je suis d'accords .
toutefois ca m'oblige a parcourir a chaque fois l intégralité de mon tableau .

vu qu'il s'agit d'une matrice de calibration ( le controleur fonctionne a 38400 bps et les coordonnées sont codées sur 5 octets . ) ca fait pas mal de points reçu a la seconde

j'avais une approche différente , cad partir du milieu du tableau et diviser par 2 etc ... malgré tout le tableau est ordonné meme si les axes sont pas dans le meme sens donc je voulais en profiter .

sinon pour le lien donné un peu plus haut ca me parait pas mal . "parait" parce que a la 2eme lecture j'ai pas encore tout compris

en tout cas merci bcp tout le monde pour les idées et solutions

[KiLVaiDeN]

Salut,

Ton idée de travailler un peu à la façon d'une recherche dichotomique me semble interessante, en fait prendre les deux extrémités du tableau et le milieu, calculer les distances pour ces points, et en fonctions des résultats, continuer dans la moitié de tableau, etc. Etant donné que tu as un nombre fixe de points dans ton tableau, tu peux optimiser un peu, sans partir sur des considérations algorithmique généraliste, par exemple faire une dichotomie sur un nombre fixe d'étapes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
test sur : 1 - 113 - 225
 
Si ( (d(1)+d(113)) / 2) < (d(113)+d(225)) / 2) )
   continuer sur 1 - 57 - 113
Sinon
   continuer sur 113 - 170 - 225

[FrancisSourd]

sinon pour le lien donné un peu plus haut ca me parait pas mal . "parait" parce que a la 2eme lecture j'ai pas encore tout compris

Les quadtrees c'est effectivement assez compliqué à mettre en oeuvre. La même idée mise en oeuvre de manière plus simple pourrait donner:

On quadrille le plan (par exemple en 10x10).
Pour chaque carré, on calcule le sous-ensemble des points de ton tableau qui sont le plus proche d'un des points du carré (géométriquement, on peut voir cela comme l'intersection du quadrillage et du diagramme de Voronoï).
Lorsque tu as ton point (x,y), tu regardes d'abord dans quelle carré il se trouve puis tu cherches, dans la liste des points associée au carré, quel est le point le plus proche de (x,y).
Normalement, il n'y a guère plus de 5/6 points associés à chaque carré donc tu n'as besoin de tester que 5/6 points au lieu de l'ensemble des points.

[Platypus]

bon ca me donne pas mal de piste tout ca .

Merci encore , j'vais tester tout ca

[10_GOTO_10]

le nombre d element est variable entre 1 et 225 .

Franchement, j'ai l'impression que vous utilisez une enclume pour écraser une mouche. Les algos que vous proposez sont sans doute efficaces pour des tableaux de plusieurs milliers de points. Là il y en a 225 maxi, ce n'est pas un parcours séquentiel qui va prendre du temps machine (la moindre comparaison de deux strings entraîne une boucle du même type). Au pire, le calcul de la distance peut prendre un peu de temps (deux multiplications et une racine carrée...) et elle peut être optimisée. Sachant que:

(DeltaX + DeltaY) / Racine(2) <= Distance(X1, Y1, X2, Y2) <= (DeltaX + DeltaY)

donc:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
DeltaX = abs(X2 - X1);
DeltaY = abs(Y2 - Y1);
if (DeltaX + DeltaY > DistanceMini) {
  // Alors ce n'est pas la peine de traiter le point
}

[Platypus]

c'est vrai .
j'avais un peu peur d'avoir une latence mais au final c'est beaucoup plus rapide que la vitesse a laquelle je recois les points en fin de compte .