Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Membre averti Avatar de nekcorp
    Homme Profil pro
    Étudiant
    Inscrit en
    décembre 2006
    Messages
    525
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : décembre 2006
    Messages : 525
    Points : 336
    Points
    336

    Par défaut 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 ).
    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.

  2. #2
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 593
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 24 593
    Points : 164 268
    Points
    164 268

    Par défaut



    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 ?
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  3. #3
    Membre averti Avatar de nekcorp
    Homme Profil pro
    Étudiant
    Inscrit en
    décembre 2006
    Messages
    525
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : décembre 2006
    Messages : 525
    Points : 336
    Points
    336

    Par défaut

    Citation Envoyé par dourouc05 Voir le message


    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

  4. #4
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 593
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 24 593
    Points : 164 268
    Points
    164 268

    Par défaut

    Citation Envoyé par nekcorp Voir le message
    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
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  5. #5
    Membre éclairé

    Homme Profil pro
    Inscrit en
    octobre 2008
    Messages
    420
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : octobre 2008
    Messages : 420
    Points : 825
    Points
    825

    Par défaut

    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.
    Fonctionnalité forum : balise LATEX pour inclure des formules mathématiques

    Article 12 of the United Nations Universal Declaration of Human Rights states: “No one shall be subjected to arbitrary interference with his privacy, family, home or correspondence, nor to attacks upon his honour and reputation. Everyone has the right to the protection of the law against such interference or attacks.”

  6. #6
    Membre averti Avatar de nekcorp
    Homme Profil pro
    Étudiant
    Inscrit en
    décembre 2006
    Messages
    525
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : décembre 2006
    Messages : 525
    Points : 336
    Points
    336

    Par défaut

    Ok merci pour la biblio je vais regarder ça.

    Citation Envoyé par bertry Voir le message
    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.

  7. #7
    Membre éprouvé
    Profil pro
    chercheur
    Inscrit en
    avril 2004
    Messages
    787
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : avril 2004
    Messages : 787
    Points : 1 280
    Points
    1 280

    Par défaut

    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 ?
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

  8. #8
    Membre actif
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2012
    Messages
    503
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2012
    Messages : 503
    Points : 228
    Points
    228

    Par défaut

    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.

  9. #9
    Membre chevronné

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    959
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 72
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 959
    Points : 1 831
    Points
    1 831
    Billets dans le blog
    5

    Par défaut Supprimer rapidement des droites confondues

    Bonjour,

    Citation Envoyé par CliffeCSTL Voir le message
    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 .


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  10. #10
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 821
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 821
    Points : 9 285
    Points
    9 285

    Par défaut

    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.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  11. #11
    Membre chevronné

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    959
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 72
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 959
    Points : 1 831
    Points
    1 831
    Billets dans le blog
    5

    Par défaut Supprimer rapidement des droites confondues

    Citation Envoyé par Flodelarab Voir le message
    ...
    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 .

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


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  12. #12
    Membre habitué
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    196
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 196
    Points : 142
    Points
    142

    Par défaut

    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.
    Savoir pour comprendre et vice versa.

  13. #13
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 821
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 821
    Points : 9 285
    Points
    9 285

    Par défaut

    Citation Envoyé par wiwaxia Voir le message
    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.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  14. #14
    Membre chevronné

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    959
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 72
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 959
    Points : 1 831
    Points
    1 831
    Billets dans le blog
    5

    Par défaut Supprimer rapidement des droites confondues

    Citation Envoyé par Flodelarab Voir le message
    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


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  15. #15
    Membre habitué
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    196
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 196
    Points : 142
    Points
    142

    Par défaut

    @: 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.
    Savoir pour comprendre et vice versa.

  16. #16
    Membre chevronné

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    959
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 72
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 959
    Points : 1 831
    Points
    1 831
    Billets dans le blog
    5

    Par défaut Supprimer rapidement des droites confondues

    Citation Envoyé par valentin03 Voir le message
    ... 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.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  17. #17
    Membre habitué
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    196
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 196
    Points : 142
    Points
    142

    Par défaut

    @: 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.
    Savoir pour comprendre et vice versa.

  18. #18
    Membre averti Avatar de nekcorp
    Homme Profil pro
    Étudiant
    Inscrit en
    décembre 2006
    Messages
    525
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : décembre 2006
    Messages : 525
    Points : 336
    Points
    336

    Par défaut

    Citation Envoyé par valentin03 Voir le message
    @: 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.

  19. #19
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 821
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 821
    Points : 9 285
    Points
    9 285

    Par défaut

    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.
    (xB-xA)*(yC-yA)-(xC-xA)*(yB-yA)=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.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  20. #20
    Membre averti Avatar de nekcorp
    Homme Profil pro
    Étudiant
    Inscrit en
    décembre 2006
    Messages
    525
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : décembre 2006
    Messages : 525
    Points : 336
    Points
    336

    Par défaut

    Citation Envoyé par Flodelarab Voir le message
    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.
    (xB-xA)*(yC-yA)-(xC-xA)*(yB-yA)=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.

Discussions similaires

  1. Réponses: 5
    Dernier message: 21/03/2016, 13h46
  2. [dos] supprimer un compte des droits d'un repertoire
    Par sun19 dans le forum Scripts/Batch
    Réponses: 1
    Dernier message: 29/01/2008, 18h12
  3. Comment afficher rapidement des images ?
    Par Michel_57 dans le forum Composants VCL
    Réponses: 5
    Dernier message: 16/01/2005, 04h07
  4. Gestion des droits d'accès
    Par soulryo dans le forum Décisions SGBD
    Réponses: 2
    Dernier message: 12/01/2005, 10h50
  5. Configuration des droits pour samba avec ftp et www
    Par Alkmie dans le forum Réseau
    Réponses: 2
    Dernier message: 07/11/2004, 13h50

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo