Discussion :

[G3G3]

Bonjour,

Je suis à la recherche d'un algorithme d'association de points 2D (x,y) en paquets (typiquement un rectangle). Le nombre de points est variable et se situe entre 1200 et 1500 environ.

La méthode utilisée actuellement consiste à calculer les distances entre chaque point 2 à 2 et à seuiller mais c'est très consommateur de ressources...
Quelqu'un aurait-il une méthode plus rapide ?

Merci.

[souviron34]

classer les points par distance x par exemple (qsort, O(N logN))

puis calculer les distances (N)

je l'ai fait pour des polygones quelquonques, et en gros c'est en 5*N*log(N)

[G3G3]

Salut souviron34,

Merci pour la réponse, mais pourrais-tu être un peu plus précis, je ne suis pas un expert en algorithmie et j'avoue ne pas avoir tout compris.

Si je comprends bien la complexité pour N = 1300 par exemple reviendrait à 5*1300*log(1300) ~= 20 240 itérations, c'est çà ?

Comment retrouve-t-on aussi les zones de points et leurs caractéristiques (taille de la zone par exemple)

[souviron34]

en fait ca revient a de l'etiquetage, mais sur des points et non sur des images



D'abord tu classes en x ;

Code :

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

1
2
3
4
5
6
 
        ***
  *     ******
*  *
  * * *          *
                  * ****

deviendra :

Code :

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

1
2
3
4
5
6
 
        7911
  2     81012131617
1  4
  3 5 6          15
                  14 18192021

puis tu etiquettes en prenant les points les uns a la suite des autres :

Code :

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

1
2
3
4
5
6
 
        222
  1     2222222
1  1
  1 1 1          3
                  3 3333

comme c'est classe en x, des que en x tu as plus que ton seuil -> autre "paquet"

si maintenant a x constant tu as plusieurs y, kif kif..

j'ai un algo, je te posterais le principe exact...

[G3G3]

Ok merci pour les illustrations, c'est beaucoup plus clair.
Pour l'algo avec le principe exact, je suis preneur.

Bonne soirée.

[souviron34]

tu programmes en quoi ?

le principe exact est :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
tri en X des donneées
 
intialisation d'un tableau d'indicateurs (taille du nombre de points)
 
numero paquet = 0
pour tous les points
    si indicateur = valeur initialisation
         appel d'une routine recursive qui explore le vosinage de'un point de chaque côté
   fin si
   numero paquet = numero paquet + 1
fin pour

la routine recursive est :

routine ( pts, j, indics )

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
point j appartient a paquet
indicateur (j) = paquet
 
   pour point de j -> 0 (décroissant)
      si indicateur = valeur initialisation
           si distance est dans le seuil : 
                 appel routine recursive avec cet indice
           sinon
                  sortie pour
           fin si
      fin si
   fin pour
 
   pour point de j -> N (croissant)
      si indicateur = valeur initialisation
            si distance est dans le seuil : 
                  appel routine recursive avec cet indice
            sinon
                   sortie pour
            fin si
     fin si
  fin pour