Discussion :

[babaille27]

Je travaille sur un sujet qui parait simple au départ mais sur lequel je bloque depuis un moment déjà. Je pars d'une liste de points 2D, désordonnées. Ces point sont réparties "approximativement" sur une grille dont je cherche les différents paramètres (on tolère une erreur de 10% autour de la position théorique) :

ex:

     *  *  *
     *  *  *

- Nb de point horizontal = 3
- nb de point vertical = 2
- pas moyen horizontal
- pas moyen vertical

Sachant que la grille de points peut-être placés dans n'importe quelle position : diagonal, Vertical ou horizontal.

Voici l'état des lieux :
1°) je cherche à me ramener dans une position "horizontal" pour simplifier l'analyse. Pour cela, il me faut une origine et une direction ensuite je peux faire un changement de repère. => premier hic, comment déterminer "simplement" l'axe horizontal ou vertical de ma matrice de points ?
Perso je suis arrivé à quelque chose en utilisant un algo "convex hull". Mais c'est très lourd et perfectible à mon avis.

2°) une fois changer de repère, j'ai donc quelque chose qui ressemble à ca :

     *    *     *     *
    *      *      *    *
     *    *       *     *

(les points ne sont pas alignés exprès car il y a une certaine tolérance par rapport à la matrice théorique)

A partir de là, j'ai essayé de connaitre le pas moyen. En triant mes points dans l'ordre croissant selon l'axe X par exemple. Mais je me retrouve avec des "paquets de points" espacés les uns des autres. Je ne vois pas comment extraire le pas moyen.

3°) une fois le pas moyen trouvé, je suppose qu'on peut prendre la longueur max selon X et diviser par le pas moyen pour obtenir le nombre d'élément.
quelque chose comme :

Code :

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

nbX =  (MaxX  -  MinX) / StepX +1

Là aussi, selon les configuration, je peux me retrouver avec le bon nombre ou n+1 ...

J'espère que vous avez déjà été confronté à ce genre de problème. J'ai cherché côté algorithme de trie mais je n'ai rien trouvé pour une matrice.

[wiwaxia]

Bonjour,

Si les points s'écartent relativement peu des noeuds d'une grille idéale à maille rectangulaire de paramètres (a, b>a), ils doivent pour la majorité d'entre eux présenter deux voisins à une distance proche de (a), et deux autres à une distance voisine de (b).
Le réseau théorique présente une densité surfacique N/S = 1/ab : il est donc facile de repérer la distance minimale (a), qui doit vérifier:

a <~ (S/N)^1/2 .

La mise en évidence de la seconde distance (b) est probablement plus difficile, car certaines diagonales risquent de présenter une longueur relativement proche, compte tenu des écarts tolérés pour les positions des points.

Exemple d'étude statistique: calculer et mémoriser pour chaque point (i) les deux plus petites distances (d_ij, d_ik) ainsi que les angles polaires correspondants (t_ij, t_ik), ramenés d'office à l'intervalle ]-90°, +90°] ; éliminer les segments pour lesquels l'inclinaison diffère nettement de la moyenne - l'écart angulaire doit être souvent proche de 90° dans le cas d'une maille orthorhombique.
Il doit apparaître un ensemble de lignes brisées d'orientations quasi-parallèles, dont on peut tirer la distance minimale moyenne a, et l'orientation moyenne t.

[Nebulix]

Quelques pistes assez simples pour commencer.
D'abord, si tu as beaucoup de points, tu peux travailler sur une partie seulement comprise dans un petit rectangle.
Je calculerais d'abord les carrés des distances (On peut éviter les racines carrées) entre chaque couple de points (dist2=sqr(x2-x1)+sqr(y2-y1)), et pour tous ceux où ce nombre est inférieur à S/n (ou un peu plus)(cf wiwaxia ) , je calculerais l'azimuth :
phi=arctan((y2-y1)/(x2-x1)).
Ces phi sont distribués autour de la direction du petit côté de la grille. La médiane t'en donnera une bonne approximation.
La médiane des distances te donnera une idée de la longueur du petit côté (a)
Si la direction du grand côté de la grille est perpendiculaire , la longueur de ce côté est déduite de a*b=S/n.
Si la précision n'est pas suffisante, on peut augmenter le nombre de points ou chercher un algo plus précis.

.

[babaille27]

Bonjour,

Merci pour vos réponses. Je suis parti de l'idée "si on prend un point et qu'on recherche le point le plus proche alors on obtient un point approximativement à la distance (pasX ou pasY)". J'ai décidé d'ajouter la simplification que le pasX et le pasY sont identiques (ou très proche). Ce qui correspond à la réalité dans mon cas.
Soit P0 le premier point choisie aleatoirement. P1 est le point le plus proche de P0. J'en déduis une valeur approchée de PasX.
A partir de ce premier couple de point, je détermine le vecteur Vi (de P0 à P1). Je calcule alors les coordonnées du prochain point de la grille selon cette axe : P2 = P0 + 2*Vi.
Je recherche le point Pn le plus proche de P2 qui respecte la contrainte : distP2_Pn < pasX/4.
Si il existe, je continue en cherchant le point suivant. P3 = P0 + 3*Vi. Je vais finir par trouver le dernier point. Je cherche alors dans la direction -Vi. Au final je dois obtenir la liste des points sur cet axe. Je recalcul alors un PasX moyen qui sera plus proche de la réalité. J'ai aussi le nombre de point de la matrice selon cet axe.
Je détermine le vecteur Vj en faisant une rotation de 90° par rapport à Vi. Et j'applique la même méthode pour trouver les points sur cet axe. J'obtiens alors le nombre de point et le Pas (qui doit être proche du PasX) selon cet axe.

Pour simplifier ces opérations, j'aimerai trouver un des points des angles (voir les 4). Quelques soit la position de la matrice de points. Je pense à un tri par coordonnées X, puis Y. Selon si je commence par "trie en X puis Y" ou "trie en Y puis en X", puis "trie croissant ou décroissant" je devrais obtenir les 4 coins. C'est correct ?

[Flodelarab]

Bonjour

Avant même le moindre changement de repère, ne cherches-tu pas simplement à faire une partition ? partitionnement = clustering. Les algorithmes de clustering sont-ils ta solution ? Renseigne-toi.

[babaille27]

Avant même le moindre changement de repère, ne cherches-tu pas simplement à faire une partition ? partitionnement = clustering. Les algorithmes de clustering sont-ils ta solution ? Renseigne-toi.

Bonjour,

Merci de ta réponse. Je ne suis pas trop familier avec ces algos. D'après ce que j'ai compris, l'idée d'un "clustering" est plutôt de regrouper des points qui semble correspondent à un même groupe (ex algo DBSCAN : https://en.wikipedia.org/wiki/DBSCAN). Ensuite, tu peux prendre le centre de gravité du groupe ou déterminer son périmètre.
Ce n'est pas le besoin pour moi. Les points ne doivent pas être regroupés, chacun est à sa place et c'est son centre à lui qui m’intéresse.
Cordialement,