Discussion :

[nekcorp]

Bonjour à tous,

J'ai un modèle éléments finis 1D dans lequel je dois vérifier que des éléments ne sont pas confondus. Pour ceux qui ne serait pas familier avec le langage, un élément 1D c'est une droite (ou segment pour les puristes) avec deux nœuds (deux points).

Je suis partie du principe que deux droites sont confondus si et seulement si leurs équations réduites sont identiques (facile ).
Je dois pour chaque éléments définir l'équation réduite et ensuite les comparer les unes aux autres .

Le soucis c'est qu'en terme d'algo c'est assez violent surtout si j'ai des milliers voir des millions d'éléments (c'est normal d'avoir un modèle avec 1 million d'éléments).

Dans un soucis de performance je viens vers vous afin que vous m'orientez vers une solution optimale qui me permettrait d'isoler assez rapidement les éléments qui sont susceptibles d'être en double pour ensuite les traiter (autrement dit : les supprimer).

J'espère avoir été clair, si ce n'est pas le cas, n'hésitez pas à me poser des questions.

Merci par avance.

[dourouc05]

Une idée, comme ça : une fois que tu as tes équations réduites, pourquoi ne pas trier selon un coefficient ? Dès que tu trouves un élément qui a un coefficient "suffisamment proche", tu vérifies si les deux segments sont confondus. En complexité, c'est du O(n log n) pour n segments, je ne sais pas si c'est suffisamment réduit…
Ou alors un arbre à k dimensions (chaque segment étant représenté par un point dans l'espace, dont les coordonnées sont données par ses coefficients), pas mal utilisé pour effectuer des requêtes rapides dans l'espace ?

[nekcorp]

Une idée, comme ça : une fois que tu as tes équations réduites, pourquoi ne pas trier selon un coefficient ? Dès que tu trouves un élément qui a un coefficient "suffisamment proche", tu vérifies si les deux segments sont confondus. En complexité, c'est du O(n log n) pour n segments, je ne sais pas si c'est suffisamment réduit…

Merci pour ton retour.

Alors l'idée du tri est intéressante. Mais du coup tu parcours ton tableau tant que le rapport coeff_1/coeff_i = 1 par exemple et lorsque le rapport n'est plus égale à 1 tu passe au coeff_2 et tu fait coeff_2/coeff_i etc .....

Sinon j'ai eu l'idée de créer deux tableaux, le premier de dimension (l,c) contiendrait l'ensemble des coefficients de mes équations réduites

Tab_1 = [[a1,b1],[a2,b2], ....[ai,bi]]

ensuite je créé un deuxième tableau de dimension (l,c) identique au premier mais qui contiendra uniquement les coefficients de ma droite 1.

Tab_2 = [[a1,b1], [a1,b1], .....,[a1,b1]]

Ensuite je fait soit le rapport des deux tableaux et je sors les index des lignes dont les coefficients sont égales à 1, et je réitère

Tab_1 / Tab_2 = [[1,1], [a2/a1, b2/b1], ....., [ai/a1,bi/b1]]

Remarque : Éventuellement je peux retirer de Tab_1 le coefficients de la droite 1

Tab_1 / Tab_2 = [[a2/a1, b2/b1], ....., [ai/a1,bi/b1]]

De ce fait les vecteurs [1,1] correspondront à des éléments confondus.

Je réitère ensuite pour l'ensemble des droites du modèle ....

Ou alors un arbre à k dimensions (chaque segment étant représenté par un point dans l'espace, dont les coordonnées sont données par ses coefficients), pas mal utilisé pour effectuer des requêtes rapides dans l'espace ?

Par contre j'ai pas très bien compris le concept de l'arbre à k dimensions

[dourouc05]

Alors l'idée du tri est intéressante. Mais du coup tu parcours ton tableau tant que le rapport coeff_1/coeff_i = 1 par exemple et lorsque le rapport n'est plus égale à 1 tu passe au coeff_2 et tu fait coeff_2/coeff_i etc .....

Non, tu fais un seul parcours du tableau : tu regardes si les éléments i et i+1 sont suffisamment près ; si oui, tu compares les segments correspondants.

Pour les arbres : https://pierre-benet.developpez.com/...octree-morton/, https://en.wikipedia.org/wiki/K-d_tree

[bertry]

Hello,

D'après les tableaux que tu donnes en exemple, tu utilises l'équation y = ax + b pour modéliser tes droites. Ca posera problème si tu as des droites verticales. Je te conseille d'utiliser l'équation ax + by = c pour modéliser tes droites et éviter ce problème.

[nekcorp]

Pour les arbres : https://pierre-benet.developpez.com/...octree-morton/, https://en.wikipedia.org/wiki/K-d_tree

Ok merci pour la biblio je vais regarder ça.

D'après les tableaux que tu donnes en exemple, tu utilises l'équation y = ax + b pour modéliser tes droites. Ca posera problème si tu as des droites verticales. Je te conseille d'utiliser l'équation ax + by = c pour modéliser tes droites et éviter ce problème.

Salut,

Merci pour cette précision je n'y avais pas réellement pensé en fait.

[Nebulix]

Le segment qui va de (1,1) à (2,2) est sur la même droite que celui qui va de (3,3) à (4,4). Ca ne pose pas de problème ?