Supprimer rapidement des droites confondues
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 :mouarf:).
Je dois pour chaque éléments définir l'équation réduite et ensuite les comparer les unes aux autres :roll:.
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.
Supprimer rapidement des droites confondues
Bonjour, :D
Citation:
Envoyé par
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.
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 = (a2 + b2)1/2 ; a' = a/K ; b' = b/K ; c' = c/K .
Supprimer rapidement des droites confondues
Citation:
Envoyé par
Flodelarab
...
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.(a2 + b2)1/2 ,
en ayant convenu de prendre s = +1 si (c>=0) sinon s = -1 . :D
On peut aussi simplifier les calculs en prenant K = s.(Abs(a) + Abs(b)) .
Supprimer rapidement des droites confondues
Citation:
Envoyé par
Flodelarab
:oops: 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 = (a2 + b2)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 à c1 = c2 = 0 et t1 = t2 = 0 ;
celles d'équations:
(3) 3.x + 0.y = 0
(4) -3.x - 0.y = 0
se ramènent toutes deux à c3 = c4 = 0 et t3 = t4 = Pi/2 .
W, emmerdeur en chef adjoint :D
Supprimer rapidement des droites confondues
Citation:
Envoyé par
valentin03
... 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 = x01 + vx1.t ; y = y01 + vy1.t ;
x = x02 + vx2.t ; y = y02 + vy2.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.