Fabien LE LEZ wrote:

On Wed, 10 Oct 2007 12:46:40 +0200, Nicolas Hervé :

ACP et projection sur le premier vecteur propre, non ?

Je peux essayer, mais je suis quelque peu dubitatif.

En effet, j'ai des nuages indépendants de points.
Si deux points sont plutôt proches, ça veut dire qu'il y a un rapport
entre eux ; s'ils sont éloignés, ça veut dire qu'il n'y a aucun
rapport, et la distance ne veut plus dire grand-chose (dans l'idéal,
elle serait infinie).

Hello,

Pour quelques milliers de points, un algorithme naïf donne
de bons résultats:

- On part d'un point (n'importe lequel, donc pourquoi pas le
premier)
- On marque ce point comme "utilisé"
- On cherche le point le plus proche de ce point, parmi
les points non utilisés
- on recommence depuis ce point

L'algorithme est en O(n^2) (en n^2/2 en fait) mais c'est
très suffisant pour quelques milliers de points.

Je trouve une bonne liste ordonnée en moins de 1 seconde
sur un PC "normal", avec 2000 points.

pour implémenter la chose, il faut :
- une structure de données permettant d'avoir pour
  chaque point un attribut qui indique si il a déjà été
  utilisé ou non
- Une fonction "distance" qui retourne la distance entre
  2 points.

L'implémentation (basic) donne quelques chose comme ceci:
- t() est le tableau de points
- nb_points une globale : nombre de points dans le tableau
- la liste est affichée ici avec "debug.print".


' fonction principale

Dim i_dep As Long
Dim i_best As Long
Dim n As Long

    i_dep = 1
    n = 0
    Debug.Print i_dep & " ";
    While n < nb_points
        t(i_dep).used = True
        i_best = find_prox(i_dep)
        Debug.Print i_best & " ";
        i_dep = i_best
        n = n + 1
    Wend

Et la fonction find_prox:

Private Function find_prox(id As Long) As Long
Dim i As Long
Dim d_min As Single
Dim id_min As Long
Dim d As Single

    d_min = 1000000000#
    id_min = -1
    For i = 1 To nb_points
        If Not t(i).used Then
            d = distance(t(id), t(i))
            If d < d_min Then
                d_min = d
                id_min = i
            End If
        End If
    Next i
    find_prox = id_min
End Function

Voir ici quelques exemples de résultats:
http://users.skynet.be/candide/points/points.html

Ca me semble pas mal.

A noter qu'on peut choisir n'importe quel point comme point
de départ. On aura alors des listes différentes mais respectant
toujours la contrainte de "groupage" des points proches.

pour avoir les "groupes" (au sens ou tu les définis) il suffit de
reparcourir la liste dans l'ordre et de créer un nouveau groupe
à chaque fois que la distance entre un point et son suivant est
plus grande qu'une certaine valeur (20 dans ton cas).


--
Jean-marc Noury (jean_marc_n2)
Microsoft MVP - Visual Basic
FAQ VB: http://faq.vb.free.fr/
mailto: remove '_no_spam_' ; _no_spam_jean_marc_n2@yahoo.fr