Version imprimable
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.
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)
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)
en fait ca revient a de l'etiquetage, mais sur des points et non sur des images
D'abord tu classes en x ;
Code:
2
3
4
5
6*** * ****** * * * * * * * ****
deviendra :
puis tu etiquettes en prenant les points les uns a la suite des autres :Code:
2
3
4
5
67911 2 81012131617 1 4 3 5 6 15 14 18192021
comme c'est classe en x, des que en x tu as plus que ton seuil -> autre "paquet"Code:
2
3
4
5
6222 1 2222222 1 1 1 1 1 3 3 3333
si maintenant a x constant tu as plusieurs y, kif kif..
j'ai un algo, je te posterais le principe exact...
Ok merci pour les illustrations, c'est beaucoup plus clair.
Pour l'algo avec le principe exact, je suis preneur.
Bonne soirée.
tu programmes en quoi ?
le principe exact est :
la routine recursive est :Code:
2
3
4
5
6
7
8
9
10
11
routine ( pts, j, indics )
Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Hello
Je programme en C++
Je vais essayer de tester le pseudocode aujourd'hui.
Encore merci pour ton aide.
j'ai oublié un truc d'optimisation dans la routine récursive :oops:
dans les 2 boucles il faut faire :
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 :DCode:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16pour 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
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.
8OCitation:
Envoyé par ToTo13
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....
Bonjour,
je comprends ce que tu veux dire maintenant :oops:, mais en regardant ton dessin, on aurait dit que tous les points qui formaient un rectangle étaient connexes... d'où ma remarque.