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

Algorithmes et structures de données Discussion :

Supprimer rapidement des droites confondues


Sujet :

Algorithmes et structures de données

  1. #21
    Membre habitué
    Questions:
    D'où sort ton fichier de noeuds ?
    Pourquoi veux-tu supprimer les confondus ?
    Quel est le but final ?
    Merci pour tes réponses.
    Savoir pour comprendre et vice versa.

  2. #22
    Membre averti
    Le fichiers nœuds c'est ma donné d'entrée, je peux le créer moi même ou le récupérer.

    Parce que je dois faire des études de treillis derrière et que certains éléments ne respectent pas la structure dite de treillis.

    Le but final c'est d'avoir une structure dite treillis.

  3. #23
    Membre habitué
    Où peux-tu récupérer le fichier ? ("sur le net", n'est pas une réponse).
    A quoi va servir la structure dite "treillis".
    Savoir pour comprendre et vice versa.

  4. #24
    Membre averti
    C'est un interrogatoire de police ?

  5. #25
    Membre habitué
    Rien ne t'oblige à répondre, et tu peux même répondre n'importe quoi (mais ça risque de provoquer d'autres questions).
    Savoir pour comprendre et vice versa.

  6. #26
    Responsable Qt & Livres

    Aussi, tes réponses pourront suggérer d'autres approches pour résoudre ton problème initial, peut-être même pour éliminer le besoin de supprimer ces segments.
    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 !

  7. #27
    Membre habitué
    Et même éliminer carrément le problème.
    Savoir pour comprendre et vice versa.

  8. #28
    Membre éclairé
    Revenir au problème
    Bonjour,

    Sauf si je n'ai rien compris, le problème de base est de supprimer les grands cotés des triangles de surface nulle.

    Si c'est exact, j'ai deux questions :
    • Peut-il y avoir des points redondants ?
    • Il est fait allusion à un treillis. Dans ce cas seuls les triangles élémentaires sont intéressants à étudier. Est-ce exact ?

    La compréhension du véritable problème à résoudre est indispensable à une réelle solution.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  9. #29
    Membre expert
    Salut, je reprend ton énoncé pour être sure que j'ai bien compris.

    - Tu as une liste de points
    - Tu as une liste de segment de ligne (donc bornée) défini par un indice dans la table des points

    1ere passe :
    - Trouver les lignes avec des indices similaires
    - Si 2 indices identiques on peut supprimer une des lignes directement
    - Si 1 indice on vérifie l'intersection du 2eme point avec les autres points des autres lignes. Si correspondance on supprime la ligne de la liste
    EDIT : On peut réduire le nombre de test en vérifiant simplement le Slope, l'angle ou la direction des lignes

    2eme passe : On vérifie les intersections des lignes restantes pour trouver si un segment en chevauche un autre si c'est la cas on supprime le segment de ligne le plus petit

    Pour l'optimisation :
    - Entre les 2 passes un trie sur un élément de l'équation pourrait être fait (désolé je ne suis pas assez doué en maths, là à chaud pour préciser lequel) EDIT : Idem que plus haut du coup : slope, angle..., et le faire dès le début
    - Diviser la liste en 2 puis en 2... ("divide and conquer")
    - utiliser des threads,
    -...

    voila à part ça, c'est avec quel langage de programmation que tu codes ?

    Sinon il y a quelques mois j'ai fait quelques recherches sur les équations de ligne pour un besoin personnel: ici c'est avec Lazarus

    A+

    EDIT : Désolé, pour le "sur-éditage"
    Je suis en plein dans la 3D en ce moment. Un autre truc au quel je viens de penser. Pour l'optimisation, vue que tu as énormément de points. Ce serait de regrouper cet énorme nuage de points en plus petits et utiliser des "Bounding Box/Sphere" pour tester les collisions, afin d'éliminer un maximum de points et de faire des tests inutiles par la suite. On ne testerai plus que les potentiels nuages susceptibles d'avoir un segment de ligne en commun entre eux. En gros cela revient à faire ce que dourouc dit faire du partitionnement dans l'espace.
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  10. #30
    Expert confirmé
    salut

    pour qu'il y ai connectivité :
    il faut qu'il ai la même définition de l’équation de droite passant par deux point
    il faut que l'un des points du segment S1 soit sur l’intervalle du segment S2 ou inversement

    pour rappel
    - calcul d'une droite à partir de 2 points :
    droite d'équation : Y = aX + b

    soit deux segments S1,S2 défini par 2 point (X1,Y1) et (X2,Y2)

    a = (S1.Y1 - S1.Y2 ) / (S1.X1 - S1.X2)
    b = S1.Y1 - a*S1.X1

    a' = (S2.Y1 - S2.Y2 ) / (S2.X1 - S2.X2)
    b' = S2.Y1 - a*S1.X1

    si a = a' et b=b' les droites sont parallèle et non sécante

    il reste a savoir si elles sont confondu

    pour cela il suffit juste de savoir si (( S2.X1 > S1.X1 < S2.X2) et ( S2.Y1 > S1.Y1 < S2.Y2)) ou (( S2.X1 > S1.X2 < S2.X2) et ( S2.Y1 > S1.Y2 < S2.Y2))
    ou (( S1.X1 > S2.X1 < S1.X2) et ( S1.Y1 > S2.Y1 < S1.Y2)) ou (( S1.X1 > S2.X2 < S1.X2) et ( S1.Y1 > S2.Y2 < S1.Y2))

    je pense que si toutes les conditions son remplit alors tes segments sont confondu en parti ou complètement
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  11. #31
    Membre éclairé
    Treillis
    bonjour,

    Citation Envoyé par nekcorp Voir le message
    Le fichiers nœuds c'est ma donné d'entrée, je peux le créer moi même ou le récupérer.

    Parce que je dois faire des études de treillis derrière et que certains éléments ne respectent pas la structure dite de treillis.

    Le but final c'est d'avoir une structure dite treillis.
    Une structure de treillis (Delaunay ou autre) est composée de triangles élémentaires et il faut s'assurer qu'aucun de triangles du treillis ne soit de surface nulle (ie. composé de segment colinéaires). Mais ce sont seulement les triangles élémentaires qui sont à vérifier (le nombre est de l'ordre de N et non d'un N^3). De plus, par efficacité, en général on vérifie ces cas au moment du maillage c'est à dire à la création des triangles élémentaires.

    C'était la raison de mes questions car j'avais le sentiment, peut être erroné, que le problème réel est plus simple que d'éliminer tout grand segment AC colinéaire à deux autres, AB et BC, avec recouvrement quelque soit leur distance.


    Ce treillis triangulaire très régulier montre que les points ABC correspondent au problème tel que traité actuellement mais vraisemblablement pas s'il s'agit d'éviter des triangles élémentaires de surface nulle.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)