Discussion :

[progfou]

Bonjour tout le monde !
J'ai deux matrices A et B de taille (n*p) (toutes les deux).
Elles correspondent à des nuages de points.
Sur celles-ci, je calcule une matrice des distances (donc, de taille n*n), et j'aimerais extraire les N points les plus proches deux à deux.
Le minimum va me donner les deux points des nuages A et B qui sont les plus proches, ça c'est bon, par contre, extraire les N points...

J'ai bien pensé à trier mais c'est une matrice, pas un vecteur...
Des idées ?

Merci d'avance !

[diogene]

Si on cherche le minimum des n*n points de la matrice, puis qu'on recommence pour trouver le suivant etc., on va devoir explorer N*n*n fois la matrice ce qui peut être coûteux en temps si la matrice est grosse.

On peut peut-être l'explorer une seule fois et garder les N plus petites valeurs parmi les valeurs déjà explorées. Si on mémorise le maximum de ces N valeurs, on pourra déjà à priori éliminer les nouvelles valeurs supérieures.Toutefois, cela conduit à chaque fois qu'on introduit une nouvelle valeur (inférieure au maximum actuel) à un reclassement des N valeurs (ou à rechercher le nouveau maximum dans ces N valeurs).

Pour accélerer ce processus, je pense à un arbre binaire de recherche : Dans un tel arbre, il est facile de trouver le maximum ou, après une insertion, de trouver la position du nouveau maximum par rapport à l'ancien. De plus, les données sont intrinsèquement classées.
On pourrait en lisant les éléments de la matrice dans l'ordre le plus commode
- remplir un arbre binaire de recherche avec les N premières valeurs et rechercher son maximum ( Peut-il y avoir des doublons ?)
- à chaque nouvelle valeur
---- si elle est supérieure au maximum, passer à la suivante
---- sinon
------- à partir de la position du maximum actuel, trouver la position de la valeur immédiatement inférieure -> nouveau maximum
------- détacher l'ancien maximum de l'arbre , lui donner la nouvelle valeur et l'insérer dans l'arbre
------- A partir du nouveau maximum, rechercher le maximum de l'arbre

[mchk0123]

Bonjour progfour.

Ce que tu ne nous à pas dit, c'est si :

- tu veux retirer les points a1 et b1 (les 2 plus proches) avant de rechercher de nouveaux les points a2 et b2 (les 2 suivants). Autrement dit est-ce que tes N plus proches doivent être disjoints ?

- ensuite entre 2 recherches est-ce que ton nuage de points change (comme par exemple insertion d'un nouveau point) ?

Selon chaque cas tu peux avoir une solution différente (bien que je ne soit pas expert dans ce domaine).

[jayjay.f]

Hello,

Allé, je me lance dans une réponse (certainement foireuse...)
Ma solution serait que lorsque tu calcule ta matrice des distance, tu la calcule élément par élément (genre tu a une boucle).
donc tu fais une matrice (nommons la A) Nx2 par exemple, avec la premiere colonne les valeurs des distances, et la deuxième, làindice associé à la distance.

Pour les N premiers calculs de ta matrice distance, tu rempli ta A. Ensuite à chaque fois que tu calcule un nouvel élément de ta matrice distance, tu le compare avec les élément de ta matrice A et s'il est plus petit quàun élément tu la remplace.

voila pource que je ferai
c'est certainement du bricolage, mais c'est pour cela que je ne suis pas informaticien!!!!!!

Jay

[souviron34]

moi j'i une question sur la base du problème :

tu parles simulatnément de nuages de points et de matrices..

Est-ce vraiment le cas : tu es FORCE d'explorer des matrices dans lesquelles tu as des points isolés ? ou bien tu as des nuages de points (sans matrices en dessous) ?


J'ai un algo qui fait ça, mais ce soir pas le temps....

Demain peut-être

[Nemerle]

Bonjour tout le monde !
J'ai deux matrices A et B de taille (n*p) (toutes les deux).
Elles correspondent à des nuages de points.
Sur celles-ci, je calcule une matrice des distances (donc, de taille n*n), et j'aimerais extraire les N points les plus proches deux à deux.
Le minimum va me donner les deux points des nuages A et B qui sont les plus proches, ça c'est bon, par contre, extraire les N points...

J'ai bien pensé à trier mais c'est une matrice, pas un vecteur...
Des idées ?

Merci d'avance !

TU prends les 10 valeurs mini en parcourant ta matrice, ou est le probleme?

[progfou]

Pfiou que de réponses !

souviron34 :
J'ai deux nuages de points.
Chacun de ces deux nuages est composé de p vecteurs de n points
A partir de là, je calcule la distance d'un point d'un nuage à tous les autres (de l'autre).

Nemerle :
Moi je veux bien, mais je n'arrive pas à écrire un algo qui le fasse facilement, car je retombe sur la remarque de diogene :

Si on cherche le minimum des n*n points de la matrice, puis qu'on recommence pour trouver le suivant etc., on va devoir explorer N*n*n fois la matrice ce qui peut être coûteux en temps si la matrice est grosse.

jayjay.f :
J'ai pas bien tout compris...

mchk0123 :
Je n'insère pas de point entre les recherches, les nuages sont figés.

[mchk0123]

Bon si ta matrice est vraiment trés grosse (genre n = 10.000). Tu peux essayer une solution approchée :

- tu calcul le centre d'inertie de tes 2 nuages (cia et cib). En gros cela te donne un représentant du centre de tes nuages.

- ensuite tu calcul l'hyperplan partageant le segment de droite [cia, cib] en son centre

- enfin pour chaque point de A puis de B tu le projete sur l'hyperplan et tu calcul la distance à l'hyperplan

- tes 2 points les plus proches entre eux seront "à peut prés" les 2 points les plus proches de l'hyperplan

- même chose pour les N-1 autres points (tu retire de A et B les points trouvés)

Avantages :

- pas de calcul de matrice de distance
- temps de calcul en O(N * (|A| + |B|)) au lieu de O(N * |A| * |B|)

Inconvénients :

- solution approchée
- surement valable uniquement si A et B sont bien séparés (?)

[souviron34]

Bon ça s'éclaire..

Tu n'as pas des matrices, tu as des nuages de points.

Donc algo :

Trier points du 1er nuage en X croissant par exemple (qsort)
Même chose avec 2ième nuage (qsort)

Faire un tableau de 10 réels, et 2 tableaux de 10 entiers

Prendre le nuage ayant le plus grand nombre d'éléments
Pour chaque point de ce nuage
calculer les distances avec les points du second nuage
stocker les distances et les indices dans les buffers, en file (stocker 0, puis passer 0 dans 1 et stocker 0, etc..) en comparant.
dès que les tableaux sont pleins, éliminer le dernier élément, décaler, et insérer en première position.

[diogene]

souviron34 :

Trier points du 1er nuage en X croissant par exemple (qsort)
Même chose avec 2ième nuage (qsort)

A quoi servent ces tris ?

calculer les distances avec les points du second nuage
stocker les distances et les indices dans les buffers, en file (stocker 0, puis passer 0 dans 1 et stocker 0, etc..) en comparant.
dès que les tableaux sont pleins, éliminer le dernier élément, décaler, et insérer en première position.

Mais le tableau des distances lui n'est pas trié. On n'aura pas les 10 plus petites distances à la fin.