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

[G3G3]

Hello
Je programme en C++
Je vais essayer de tester le pseudocode aujourd'hui.
Encore merci pour ton aide.

[souviron34]

j'ai oublié un truc d'optimisation dans la routine récursive

dans les 2 boucles il faut faire :

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
 
   pour point de j -> 0 (décroissant)

      si delta X (point, j) > seuil
           sortie pour
      fin si

      si indicateur = valeur initialisation
           si delta Y (point , j) < seuil )
                 si distance (point, j) est dans le seuil : 
                        appel routine recursive avec cet indice
                 fin si
           fin si
      fin si

   fin pour

note : j'ai le code en C, mais ce serait mieux que tu te débrouilles avec ce que tu as, et fasse fonctionner un peu ta tête maintenant

[ToTo13]

Bonjour,

la méthode n'est valable que si tous les rectangles sont connexes et avec des coordonnées assez petites pour être mises dans une matrice...

Si ce n'est pas le cas, tu peux tenter une transformée de Hough pour déterminer les bords des rectangles.

Si tu connais le nombre de rectangles que tu dois trouver, tu peux tenter une classification par KMeans.

[souviron34]

Bonjour,

la méthode n'est valable que si tous les rectangles sont connexes et avec des coordonnées assez petites pour être mises dans une matrice...

Si ce n'est pas le cas, tu peux tenter une transformée de Hough pour déterminer les bords des rectangles.

Si tu connais le nombre de rectangles que tu dois trouver, tu peux tenter une classification par KMeans.

euh Toto, je crois qu'en cette après-midi t'as loupé ton café

C'est au contraire valable pour un nuage de points de forme irrégulière.... et SANS matrice...


C'est bien la raison pour laquelle j'avais fait cet algo... pas de place mémoire pour faire la matrice nécessaire (60K * 60K). Pas de figure géométrique connue à priori.

(le problème était regrouper les éclairs observés en cellules orageuses sur l'Amérique du Nord, seuil de distance 500m).

et pour finir : 150 000 points répartis en moins 1/40 seconde sur un Toshiba Satellite de 1999....

[ToTo13]

Bonjour,

je comprends ce que tu veux dire maintenant , mais en regardant ton dessin, on aurait dit que tous les points qui formaient un rectangle étaient connexes... d'où ma remarque.