Discussion :

[etiennep17]

Bonjour à tous,

J'ai récupéré les coordonnées des nœuds du maillage suivant sur Abaqus (surface avec maillage affinée)



Après les avoir stockés dans une liste, j'aimerais pouvoir les trier afin de les manipuler aisément. Attention: petite subtilité, il faudrait que ça soit trié selon 2 critères d'importance équivalente (ici, x et y) afin d'obtenir un tri qui a du sens par rapport à l'image ci-dessus.

Voici un exemple basique de ce j'obtiens:

Code :

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

1
2
3
 coord = [ [1,0,2],[5,9,4],[4,1,5],
           [6,3,9],[10,4,12],[8,2,9], 
           [0,9,1],[3,1,3],[7,10,8] ]

Voici ce que j'aimerais obtenir:

Code :

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

1
2
3
 coord = [ [8,2,9],[10,4,12],[7,10,8],
           [4,1,5],[9,3,9],[5,9,4], 
           [1,0,2],[3,1,3],[0,9,1] ]

Représenté comme des matrices pour visualiser plus facilement.

Méthode de tri souhaité: Y croissant de gauche vers droite / X croissant de bas en haut (afin d'être cohérent par rapport aux référentiel de l'image)
Là où c'est compliqué pour moi, c'est quand il y a des croisements, ex dans la matrice souhaitée: A(1,1)=[8,2,9] et B(3,2)=[3,1,3] -> on remarque que By < Ay. Pourtant le tri est correct car fidèle aux coordonnées de la surface (voir image)
Autre ex: A(1,1)=[8,2,9] et C(2,2)=[9,3,9] -> on remarque que Cx > Ax. Pourtant le tri est correct car fidèle aux coordonnées de la surface (voir image)

Voilà, j'espère avoir été claire, n'hésitez à me demander des détails.
Sachez que j'ai déjà posé cette question ici: https://www.developpez.net/forums/d2.../#post11678559
Malheureusement, ça n'a pas abouti et on m'a suggéré de poster mon message dans ce forum. Mais n'hésitez pas à y faire un tour pour comprendre le problème plus en détails (j'y ai apporté des précisions)

J'attends vos réponses avec impatience,
Bonne soirée.

[tbc92]

Effectivement, il faut aller lire l'autre discussion, pour apprendre quelques trucs supplémentaires, mais le besoin n'est toujours pas clair du tout.

Tu as n*p points extraits d'une surface. Cette surface est plus ou moins plane. Pas forcément parfaitement plane, mais quasiment.

Ces n*p points, ils proviennent d'un quadrillage dessiné sur la surface. Tu sais qu'il y a une façon de répartir ces points en n lignes 'horizontales' croisées avec p lignes 'verticales', on aura des points assez bien alignés sur chaque ligne.
Les n*p points ne sont pas des points pris au hasard dans un carré, on a la certitude qu'ils viennent d'un quadrillage.
Mais comme on est dans la vraie vie, on est en géologie, donc les lignes ne sont pas parfaitement droites, comme illustré sur le dessin.

Pour redire ça autrement, ton collègue qui a ponctionné n lignes de p points sur la surface, il s'est amusé à mélanger les n*p points avant de te les envoyer.
Et tu dois reconstituer la grille initiale.

C'est ça le problème ?

Et donc, si c'est ça, une fois qu'on a réussi à trouver les 4 points qui sont les plus éloignés ( les 4 coins de la matrice) , on a quasiment fini... il reste juste à deviner si on a n lignes et p colonnes, ou à l'inverse, n colonnes et p lignes. Et c'est presque fini.

C'est ça ?

[etiennep17]

Bonjour,

Merci pour votre retour.

Tu as n*p points extraits d'une surface. Cette surface est plus ou moins plane. Pas forcément parfaitement plane, mais quasiment.

Disons qu'elle est suffisamment courbe pour que le maillage présente des lignes courbes et que cela génère des "croisements" dans le tri des points. Voir mes différentes explication à ce sujet. Au besoin, je peux tenter une nouvelle approche pour l'expliquer.

Pour redire ça autrement, ton collègue qui a ponctionné n lignes de p points sur la surface, il s'est amusé à mélanger les n*p points avant de te les envoyer.
Et tu dois reconstituer la grille initiale.

C'est ça le problème ?

C'est juste ! (Mis à part que le collègue mystère, c'est moi ) Lors de l'extraction des coordonnées des nœuds/points avec Abaqus, les points sont triés selon leur index/numéro de nœud. Or il n'y a aucune suite logique dans la répartition de ses index. On obtient donc une liste de points en apparence désordonnés.

Et donc, si c'est ça, une fois qu'on a réussi à trouver les 4 points qui sont les plus éloignés ( les 4 coins de la matrice) , on a quasiment fini... il reste juste à deviner si on a n lignes et p colonnes, ou à l'inverse, n colonnes et p lignes. Et c'est presque fini.

C'est ça ?

Je sais pas, ça semble intéressant.

- Je peux connaître les 4 coins de la matrice: faire un 1er tri avec y comme critère, ensuite comme les bords gauche et droite de la surface sont des arrêtes physiques et seront toujours quasiment verticale, leur coordonné selon y varie peu. Donc on peut déterminer parmi ses quelques valeurs de y laquelle est associée à un x max et x min pour trouver le coin haut et bas de chaque côté)
- Je peux connaître le nombre de ligne et colonne: de même que pour le 1er tiret, faire un tri selon y, puis compter le nombre de point sur le bord gauche (pour y décroissant, tant que y varie très peu, on sait que c'est le bord de gauche). Cela me donne la hauteur, on en déduit facilement la largeur grâce au nombre total de point et une division.

Pour rappel, la surface étudiée ressemble à ça (ou voir 1er image ici: https://www.developpez.net/forums/d2.../#post11678559)


Si ensuite c'est presque fini, j'ai très envie d'en savoir plus ! Comment fait-on ?

Bonne journée.

[tbc92]

Tu es capable de déterminer les 4 points qui seront aux A sommets de ta matrice.
Puis tu sais trouver les points qui vont être sur la 1ère colonne de ta matrice.
Super.
Ces 2 étapes ne me paraissent pas si évidentes que ça.
Donc si on part d'une grille de 34x8, tu as su traiter les 8 premiers points.
Il te reste 33x8 points.
Et en répétant ce processus, tu vas savoir identifier les 4 sommets de cette nouvelle matrice, et la première colonne de cette nouvelle matrice.
De fil en aiguille, tu arrives à la solution.

On parle algorithme , on a établi un plan, et c'est ça l'objectif de l'algorithme. Ensuite, la traduction en Python ou en autre chose, c'est autre chose.

Il y aurait éventuellement une phase préliminaire.
Ici, tu raisonnes uniquement avec les variables x et y. Tu considères que la variable z est inutile, parce que les points viennent d'un plan pratiquement vertical.
Il faudrait probablement rechercher un plan qui 'approche' le mieux l'ensemble des points, et projeter l'ensemble des points sur ce plan .

[etiennep17]

Et en répétant ce processus, tu vas savoir identifier les 4 sommets de cette nouvelle matrice, et la première colonne de cette nouvelle matrice.
De fil en aiguille, tu arrives à la solution.

Ah non ça ne marche pas malheureusement.

Le problème c'est encore ces fameux "croisements" de points.

Considérons l'image suivante:


Sois la colonne passant par A étant la 2nd colonne du maillage. (La 1ère a été triée)
Si j'applique la même méthode pour trouver les nouveaux 4 coins et les points de cette nouvelle 1ère colonne (donc la 2ème en absolu), il faut faire un tri selon y. Or, on voit bien sur l'image que le point B va venir s'intercaler avant le point A dans le tri. Donc si je cherche à récupérer les 8 prochains points dont la coordonné en y est maximale, je vais récupérer certains points de la colonne suivante, ce qui n'est pas souhaitable. En résumé, le point A ne sera pas considéré comme étant un coin et ne sera pas considéré comme étant sur la colonne 2 puisque d'autres points (dont la coordonnée en y est supérieure) auront pris sa place dans le tri.

La méthode fonctionne pour la 1er colonne (bord de gauche) car les 8 points de cette colonne sont ceux qui ont une coordonné en y maximale. Il n'y aucun croisement. Pour la suite, c'est différent.

Auriez-vous une autre idée ?

[tbc92]

J'ai fait des tests, avec des résultats satisfaisants.
Les hypothèses :
1/ On a une grille avec des lignes 'x plus ou moins constant' et des colonnes 'y plus ou moins constant'. Dans mes tests, le plus ou moins constant peut être très souple ; la première colonne peut parfaitement contenir des points avec y allant de 100 à 200, et la 2ème colonne avec des points allant de 130 à 240 ... alors que y est supposé constant.
2/ J'ai supposé qu'on connaissait à l'avance le nombre de lignes nlig et le nombre de colonnes ncol, mais ceci pourrait facilement être contourné.

Démarche.
Etape 1 : Je normalise les données. Je calcule une estimation de l'écart entre 2 lignes successives, et de l'écart entre 2 colonnes successives, et idem sur la dimension z, et je divise toutes les valeurs par ces valeurs.
Ainsi , on recherche un quadrillage avec des formes relativements carrées ; ça permet d'avoir une fonction fdist() qui fonctionne bien pour calculer les distances entre 2 points.

Etape 2 :
2a : Je recherche les 2 points extrèmes A et B de la 1ère colonne (ceux qui minimisent y-kx et y+kx) k est un coefficient aléatoire proche de 1. je mets un peu partout des coefficients aléatoire, car j'envisage de boucler et de faire différents essais si nécessaire.
2b : A partir du point A ( ymini, xmini), je vais chercher nlig points, de proche en proche, pour aller en principe jusqu'au point B. Pour chercher le successeur d'un point A(x0,y0), je positionne un point fictif B(x0+1, Y0-1), et je cherche parmi tous les points non utilisés le point le plus proche de ce point fictif. Comme j'ai divisé tous mes x et mes y par un coefficient adapté, le point cherché est théoriquement en (X0+1,Y0), si le quadrillage était parfaitement vertical/horizontal/régulier.
Je ne cherche pas le point le plus proche de (X0+1,Y0) parce que je pourrais tomber sur un point de la 2ème colonne.
2c : Idem, à partir du point B, je cherche de proche en proche, en remontant la ligne.
Normalement la liste des points obtenus dans ces 2 traitements est la même. Si oui, je considère que cette liste est bien la 1ère colonne de mon quadrillage.
Si les 2 listes sont différentes, il y a un problème. Je recommence, et comme j'avais des paramètres aléatoires ici et là, je peux retrouver soit la même liste, soit une autre liste ...

Etape 3 : On cherche ensuite les colonnes suivantes.
La démarche est la même ; Si le 1er point de la colonne c est en (x0,y0) , le premier point de la colonne suivante est proche de (x0,y0+1), je cherche le point le plus proche possible de (x0-1, Y0) ; même principe pour le dernier point de chaque colonne.
Et pareil, quand on pense avoir le 1er et le dernier point de chaque colonne, on recherche de proche en proche en montant, et en descendant, et si les 2 listes obtenues coïncident, je valide.
Sinon, je boucle, et comme j'ai des paramètres aléatoires, je vais trouver des résultats différents.
Pour chercher les points 'centraux', je sais que le point (i,j) doit être voisin de (i,j-1) et de (i-1,j), je vais donc utiliser ces 2 points pour construire ma recherche.

J'ai fait ça dans un langage très éloigné de Python, je suis conscient que c'est assez artisanal. C'était cette nuit, donc j'ai peu testé. Je peux partager des choses ce soir.