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 ?

[CliffeCSTL]

En prenant a.x + b.y + c = 0 il te suffit de trier suivant a puis b puis c et tu auras ton résultat.

[wiwaxia]

Bonjour,

En prenant a.x + b.y + c = 0 il te suffit de trier suivant a puis b puis c et tu auras ton résultat.

L'idée est bonne, à ceci près que le nombre de paramètres indépendants ne dépasse pas 2: pour en revenir à l'exemple cité, toute droite d'équation
(ha).x + (hb).y + hc = 0
se superpose à la précédente.

Une solution simple consisterait à envisager deux sortes de droites:
a) celles qui ne passent pas par l'origine, et admettent une équation de la forme:

a.x + b.y = 1

(elles passent par les points (0 , 1/b) et (1/a , 0) lorsque les coefficients correspondants ne sont pas nuls);

b) celles qui passent par l'origine (0 , 0) et sont caractérisées par un paramètre unique (t):

Sin(t).x - Cos(t).y = 0 .

Mais il se pourrait encore que deux droites de catégories différentes soient en réalité très proches, par exemple celles d'équations:

6x + 8y = 10^-9 ;
(0.6)x + (0.8)y = 0 .

Il vaut donc mieux s'en tenir à une équation "normalisée" unique:

a'.x + b'.y = c'

en posant

K = (a² + b²)^1/2 ; a' = a/K ; b' = b/K ; c' = c/K .

[Flodelarab]

Bonjour

il vaut donc mieux s'en tenir à une équation "normalisée" unique:

L'idée est bonne, à ceci près que ... la norme est toujours positive. Les équations suivantes seront toujours détectées comme différentes car la normalisation ne corrige pas le signe :
-3x-2y-1=0
3x+2y+1=0

Il faut, de surcroît, imposer a' ou c' toujours positif.

Signé l'emmerdeur en chef.

[wiwaxia]

...
L'idée est bonne, à ceci près que ... la norme est toujours positive. Les équations suivantes seront toujours détectées comme différentes car la normalisation ne corrige pas le signe :
-3x-2y-1=0
3x+2y+1=0

Il faut, de surcroît, imposer a' ou c' toujours positif. ...

Exact. J'avais omis de le préciser: faire en sorte que (c') soit positif, en divisant tout par s.(a² + b²)^1/2 ,
en ayant convenu de prendre s = +1 si (c>=0) sinon s = -1 .

On peut aussi simplifier les calculs en prenant K = s.(Abs(a) + Abs(b)) .

[valentin03]

Tu ne précise pas si les deux points dont tu parles sont les points de départ et d'arrivée ou des points quelconques.

[Flodelarab]

On peut aussi simplifier les calculs en prenant K = s.(Abs(a) + Abs(b)) .

Pardon. Je mesure à quel point je n'ai pas été assez précis dans mon objection.
Ton critère n'est toujours pas assez précis.
Car 0 n'est ni positif ni négatif.
Les 2 droites suivantes sont les mêmes, mais identifiées différentes.
0x+3y+0=0
0x-3y+0=0
La norme est bien 3, le signe et bien +1, et pourtant, on tombe sur (0;1;0) et (0;-1;0) dans l'autre cas.
J'aurais pu, de la même manière, mettre b ou b' à 0.

Emmerdeur en chef strikes back.

Tu ne précise pas si les deux points dont tu parles sont les points de départ et d'arrivée ou des points quelconques.

Est-ce que ça change la droite ? Non. Objection rejetée.

[wiwaxia]

Pardon. Je mesure à quel point je n'ai pas été assez précis dans mon objection.
Ton critère n'est toujours pas assez précis.
Car 0 n'est ni positif ni négatif.
Les 2 droites suivantes sont les mêmes, mais identifiées différentes.
0x+3y+0=0
0x-3y+0=0
La norme est bien 3, le signe et bien +1, et pourtant, on tombe sur (0;1;0) et (0;-1;0) dans l'autre cas.
J'aurais pu, de la même manière, mettre b ou b' à 0.

Emmerdeur en chef strikes back ...

La droite d'équation

a'.x + b'.y = c'

"normalisée" à l'aide du facteur K = (a² + b²)^1/2
se caractérise par deux paramètres indépendants:
a) la constante (c'), reliée aux éventuels points d'intersection avec les axes (0 , c'/b') , (c'/a', 0) ;
b) l'inclinaison (t) de la droite par rapport à l'axe des abscisses (x'x), définie par:
# t = -Arctan(a'/b') si (b' <> 0)
# sinon t = Pi/2 .

Ainsi les droites d'équations:

(1) 0.x + 3.y = 0
(2) 0.x - 3.y = 0

se ramènent toutes deux à c₁ = c₂ = 0 et t₁ = t₂ = 0 ;

celles d'équations:

(3) 3.x + 0.y = 0
(4) -3.x - 0.y = 0

se ramènent toutes deux à c₃ = c₄ = 0 et t₃ = t₄ = Pi/2 .

W, emmerdeur en chef adjoint

[valentin03]

@: Flodelarab:
Je demandais si les deux points cités sont les points de départ et d'arrivée ou des points quelconques.
Te cite: "Est-ce que ça change la droite ? Non. Objection rejetée."
Si les points cités sont "départ et arrivée" des droites, ça change tout, car on a deux cas de figure
a): Les droites sont de mêmes longueurs et il suffit de comparer les couples "départs-arrivées et d'éliminer les doublons.
b): Les longueurs sont différentes et la plus courte est forcément contenue dans la plus longue; se pose alors la question du choix de laquelle supprimer (qui n'a pas été évoqué).
D'une droite dont on connaît le départ et l'arrivée , on peut connaître tous les points-->Comparaison, élimination.

[wiwaxia]

... Si les points cités sont "départ et arrivée" des droites, ça change tout, car on a deux cas de figure
a): Les droites sont de mêmes longueurs et il suffit de comparer les couples "départs-arrivées et d'éliminer les doublons.
b): Les longueurs sont différentes et la plus courte est forcément contenue dans la plus longue; se pose alors la question du choix de laquelle supprimer (qui n'a pas été évoqué).
D'une droite dont on connaît le départ et l'arrivée , on peut connaître tous les points-->Comparaison, élimination.

1°) Distinguer les points de "départ" et d'"arrivée" suppose l'intervention de droites orientées, représentées par des équations paramétriques du type:

x = x₀₁ + v_x1.t ; y = y₀₁ + v_y1.t ;
x = x₀₂ + v_x2.t ; y = y₀₂ + v_y2.t .

Ce n'est pas le cas ici, et heureusement, car la comparaison des graphes devrait être établie sur huit données au lieu de quatre.

2°) Une droite est par définition illimitée, et évoquer sa longueur n'a pas de sens; c'est éventuellement la longueur d'un segment qu'il faut envisager, et cela me paraît ici inutile.

3°) On pourrait, pour comparer les droites, localiser leur points d'intersection avec l'un des axes du repère (x = 0 ou y = 0), ou l'une de ses bissectrices (y - x = 0 ou y + x = 0); le procédé présente l'inconvénient d'être inapplicable lorsque la droite considérée est parallèle à la droite de référence.

On en revient toujours à l'équation standard définie précédemment.

[valentin03]

@: wiwaxia:
Cite nekcorp: "c'est une droite (ou segment pour les puristes) avec deux nœuds (deux points)".
Ma question revient à demander s'il s'agit de droites infinies (points quelconques) ou de segments.
Et si l'orientation est la même pour toutes les droites (ou segments ?), (exemple: Droites alignées sur l'axe des x (spectrogramme)); il suffit de comparer les x.

[nekcorp]

@: wiwaxia:
Cite nekcorp: "c'est une droite (ou segment pour les puristes) avec deux nœuds (deux points)".
Ma question revient à demander s'il s'agit de droites infinies (points quelconques) ou de segments.
Et si l'orientation est la même pour toutes les droites (ou segments ?), (exemple: Droites alignées sur l'axe des x (spectrogramme)); il suffit de comparer les x.

Alors je ne pensais pas que ma question allait déchaîner tant de commentaires . Du coup je vais être plus précis.

Je travail sur des modèles éléments finis et je construit des éléments 1D qui relis des noeuds (des points). Donc je parle bien de segments finis.

Alors pour faire simple, à partir d'un fichier de nœuds, je génère une table de connectivités entre mes nœuds TAB_COONEC = [[1,2], [2,3], [1,3]] -> Les nœuds 1 2 et 3 sont alignés pour l'exemple.
Cette table signifie que je dois créer un élément_12 entre le nœud 1 et le nœud 2, ensuite un élément_23 entre le nœud 2 et 3 et finalement un élément_13 entre le nœud 1 et le nœud 3.

Le soucis c'est que le code qui génère ces éléments va également générer un élément_13 entre 1 et 3, normal puisqu'il est dans la table de connectivité, sauf que je ne souhaite pas conserver cet élément.

Mon idée est de vérifier dans un premier temps que mes éléments sont confondus (ils ont donc la même équation réduite) et ensuite comparer leur longueur et supprimer le plus grand ....

J'espère que c'est plus clair.

[Flodelarab]

Dès le début, ça sentait l'énoncé foireux.

Tu n'as pas besoin des équations de droites. Juste de vérifier que les vecteurs sont colinéaires.
(x_B-x_A)*(y_C-y_A)-(x_C-x_A)*(y_B-y_A)=0
5 soustractions et 2 multiplications et tu sais si 3 points sont alignés. (à partir des coordonnées des points A, B et C)

Une fois qu'ils sont alignés, tu n'as pas de problème pour les mettre dans l'ordre.
Et supprimer les vecteurs qui sont la somme des autres.

[nekcorp]

Dès le début, ça sentait l'énoncé foireux.

Tu n'as pas besoin des équations de droites. Juste de vérifier que les vecteurs sont colinéaires.
(x_B-x_A)*(y_C-y_A)-(x_C-x_A)*(y_B-y_A)=0
5 soustractions et 2 multiplications et tu sais si 3 points sont alignés. (à partir des coordonnées des points A, B et C)

Une fois qu'ils sont alignés, tu n'as pas de problème pour les mettre dans l'ordre.
Et supprimer les vecteurs qui sont la somme des autres.

Merci pour ton retour, mais les vecteurs colinéaires c'est pas ce qu'il y a de mieux dans mon cas. Deux vecteurs peuvent être colinéaires sans pour autant que les segments associés ne soient pas confondus.

D'où l'idée de passer par les équations réduites. Car deux segments avec la même équation réduite signifie directement que les segments sont confondus.

Dans le cas ou j'ai un maillage régulier (une plaque maillée en carrés) je vais avoir une multitude de vecteurs colinéaires à vérifier, ce qui risque de faire des temps de check assez long .

En tout cas j'ai creusé et la solution n'est pas si évidente que ça. Je pense que la solution optimale sera la réponse de 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…

Merci pour vos retours.