IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
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 :

Transformation de polylignes en polygones


Sujet :

Algorithmes et structures de données

  1. #1
    nkd
    nkd est déconnecté
    Nouveau membre du Club
    Inscrit en
    Mars 2004
    Messages
    38
    Détails du profil
    Informations forums :
    Inscription : Mars 2004
    Messages : 38
    Points : 29
    Points
    29
    Par défaut Transformation de polylignes en polygones
    Bonsoir les amis

    J'ai un problème un peu complexe (du moins pour moi) et j'aimerais que m'aidiez . Le voici :

    Je conçoit un logiciel dans lequel on est amené à dessiner des polylignes
    qui s'interceptent (de sorte à ce qu'obtienne des figures géometrique) et je voudrais mettre en place un algo qui transformerait ces derniers en polygones pour qu'un puisse avoir la surperficie ou le centre de gravité des figures géometriques(quadrilatères etc...) que forment l'ensemble des polylignes.

    j'espère avoir été clair et simple.
    merci

  2. #2
    Membre actif Avatar de Steki-kun
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    222
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Janvier 2005
    Messages : 222
    Points : 281
    Points
    281
    Par défaut
    Et quelle est la question ? Ton problème est clair en effet mais qu'est-ce que tu n'arrives pas à faire ?
    I'm the kind of guy that until it happens, I won't worry about it. - R.H. RoY05, MVP06

  3. #3
    Membre éprouvé Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 53

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Points : 1 213
    Points
    1 213
    Par défaut
    pour le centre de gravité, il suffit de déterminer les sommets de ton polygone à partir des intersections de tes "poly-lignes" (?). Après tu "barycentrises".

    Pour la superficie, c'est plus chaud!! Il faut une notion supplémentaire de "voisins", pour découper ton polygone en triangles...
    Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre

  4. #4
    Membre habitué Avatar de PINGOUIN_GEANT
    Profil pro
    Inscrit en
    Juin 2004
    Messages
    149
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2004
    Messages : 149
    Points : 155
    Points
    155
    Par défaut
    n'y a-t'il pas une formule à base de produits vectoriels (?) pour calculer la superfiice d'un polygone ?
    " Tout homme est digne d'un parapluie." Stavroguine dans Les Démons de Dostoïevski.

  5. #5
    Membre éclairé
    Avatar de Kangourou
    Profil pro
    Inscrit en
    Mars 2003
    Messages
    579
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2003
    Messages : 579
    Points : 859
    Points
    859
    Par défaut
    Salut,

    oui, y'a une formule a base de produit vectoriel pour l'aire d'un polygone. cf Mathworld :
    http://mathworld.wolfram.com/PolygonArea.html

    Ca donne un resultat qui peut etre negatif, selon l'orientation des points, mais il suffot de prendre la valeur absolue.


    Pour le centre de gravite, ce n'est pas le barycentre des sommets, mais ce n'est pas beaucoup plus complique. cf P. Bourke :
    http://astronomy.swin.edu.au/~pbourk...etry/polyarea/
    il y a aussi la formule pour l'aire, d'ailleurs, et meme des prog en C et Java.


    A+

  6. #6
    Membre averti
    Avatar de JHelp
    Inscrit en
    Octobre 2002
    Messages
    185
    Détails du profil
    Informations forums :
    Inscription : Octobre 2002
    Messages : 185
    Points : 444
    Points
    444
    Par défaut
    Citation Envoyé par PINGOUIN_GEANT
    n'y a-t'il pas une formule à base de produits vectoriels (?) pour calculer la superfiice d'un polygone ?
    J'ai fait un peu de math dans mes études et je n'ai pas entendu parler d'une formule générale pour n'importe quel polygone
    Par contre on peut triangulariser se polygone et calculer l'aire de chaque triangle et faire une addition.
    J'ai un algo de triangularisation de polygone, mais il ne marche que pour les polygones convexes a coups sur, pour les autres non.
    Mais on peut trouver sur le net de quoi transformer des polygonnes non convexex en plusieurs polygones convexes, mais là j'ai pas récupéré l'algo car j'en avais pas besoin.
    JHelp

    [Edit]kangourou tu as répondu en même temps que je rédigeais ma réponse.
    Tres bons liens. Juste un détail ca marche pas pour n'importe quel polygone, seulement pour les convexes.[/Edit]
    Pour avoir une réponse efficace :
    1) Soyez précis dans vos questions
    2) Choisssez bien votre forum
    3) Consultez la FAQ et la doc avant

  7. #7
    Membre éprouvé Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 53

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Points : 1 213
    Points
    1 213
    Par défaut
    Citation Envoyé par Kangourou
    Salut,

    oui, y'a une formule a base de produit vectoriel pour l'aire d'un polygone. cf Mathworld :
    http://mathworld.wolfram.com/PolygonArea.html

    Ca donne un resultat qui peut etre negatif, selon l'orientation des points, mais il suffot de prendre la valeur absolue.


    Pour le centre de gravite, ce n'est pas le barycentre des sommets, mais ce n'est pas beaucoup plus complique. cf P. Bourke :
    http://astronomy.swin.edu.au/~pbourk...etry/polyarea/
    il y a aussi la formule pour l'aire, d'ailleurs, et meme des prog en C et Java.

    A+
    Bon sang, mathworld, que je cite tout le temps!!

    Joli, je ne connaissais pas l'aire d'un polygone (convexe)!! Ceci dit pour programmer la formule, le problème va être de trouver les sommets dans l'ordre (direct ou indirect); d'où la notion de voisin dont j'avais parlé.

    Pour le centre de gravité, effectivement, j'étais allé un peu vite. Mais j'avoue que la géométrie de base, c'est loin, très loin
    Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre

  8. #8
    Membre averti
    Avatar de JHelp
    Inscrit en
    Octobre 2002
    Messages
    185
    Détails du profil
    Informations forums :
    Inscription : Octobre 2002
    Messages : 185
    Points : 444
    Points
    444
    Par défaut
    Pour l'ordre des points, la je peut te répondre.
    Je suppose que ton polygone est convexe, donc ne se coupe pas lui même.
    1) tu tris les points come ceci la plus petite ordonées et en cas d'égalité, celui avec la plus petite abscisse. Je le met dans la liste TRI
    2) avec ce tri tu prend comme point de départ le premier point de TRI. Ce point tu l'ajoutes à ton polygone (qui n'a donc pour le moment qu'un seul point), ensuite tu retire ce point de TRI
    3) Ensuite, tu prend le premier point de TRI qui est une abscise plus petite ou égale au premier point de ton polygone. Si yen a pas alors passe en (5)sinon tu le retire de TRI et tu l'ajoutes à ton polygone
    4) si tu n'est pas à la fin de TRI, hop retour en 3)
    5) tu lis cette fois TRI du dernier vers le premier et tu ajoutes à ton poluygone les points un a un

    Un chtit exemple si je suis pas clair :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
     
             3
           /   \
          1    5
          |    |
          2 -  4
     
    L'etape 1 done pour TRI : 3,1,5,2,4
    P() : Polygone vide au départ
    Etape 2 :
    TRI 1,5,2,4 et P(3)
    Etape 3 :
    1 conviens, doù
    TRI 5,2,4 et P(3, 1)
    Etape 3 :
    2 conviens, doù
    TRI 5,4 et P(3,1,2)
    Etape 3 :
    pas de point qui convienent d'ou on passe en 5
    Etape 5 :
    Comme TRI est TRI 5,4, P devient P(3,1,2,4,5)
    Et voila
    Pour connaitre le sens de parcours, penses aux produits vectoriel, et si le sens ne te conviens pas, t'a juste à inverser l'ordre des points.
    JHElp
    Pour avoir une réponse efficace :
    1) Soyez précis dans vos questions
    2) Choisssez bien votre forum
    3) Consultez la FAQ et la doc avant

  9. #9
    Membre éclairé
    Avatar de Kangourou
    Profil pro
    Inscrit en
    Mars 2003
    Messages
    579
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2003
    Messages : 579
    Points : 859
    Points
    859
    Par défaut
    Citation Envoyé par Nemerle
    Bon sang, mathworld, que je cite tout le temps!!
    Ha Ha !
    Comme quoi le lien est bien utile. Mais un peu pauvre pour ce qui concerne les problemes plus 'informatiques', enfin ...

    Citation Envoyé par Nemerle
    Joli, je ne connaissais pas l'aire d'un polygone (convexe)!! Ceci dit pour programmer la formule, le problème va être de trouver les sommets dans l'ordre (direct ou indirect); d'où la notion de voisin dont j'avais parlé.
    pas besoin :
    que l'on prenne un sens ou l'autre, on obtient la meme aire, au signe pres. valeur absolue, et le tour est joue ...
    Et ca marche aussi pour les polygones non convexes. Si c'est pas boooo !! Faut juste eviter qu'ils se croisent (logique ....).

    A+

  10. #10
    Membre éprouvé Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 53

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Points : 1 213
    Points
    1 213
    Par défaut
    Kangorou>> tu n'as pas compris le problème de l'ordre... mais qu'à cela ne tienne, un éminent collègue vient de te fournir l'algo...
    Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre

  11. #11
    Membre éclairé
    Avatar de Kangourou
    Profil pro
    Inscrit en
    Mars 2003
    Messages
    579
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2003
    Messages : 579
    Points : 859
    Points
    859
    Par défaut
    Salut,

    dixit P. Bourke :
    The only restriction that will be placed on the polygon for this technique to work is that the polygon must not be self intersecting
    et il donne d'ailleurs un exemple avec un polygone qui n'est convexe. Mathworld aussi ne requiert que des polygones qui ne se coupent pas, donc pas forcement convexes.

    J'avais utilise sur des polygones non convexes, et ca marchait sans probleme. A moins que vous me trouviez un beau contre-exemple ...


    Sinon pour l'ordre des pixels, j'ai peut-etre pas compris le probleme de base. Pour moi on a en entree des polylnes ou polygone, et on veut l'aire du polygone, donc pas besoin de relier les points si ils le sont deja. Mais bon, faut peut-etre demander a nkd ce qu'il veut exactement ?


    A+

  12. #12
    nkd
    nkd est déconnecté
    Nouveau membre du Club
    Inscrit en
    Mars 2004
    Messages
    38
    Détails du profil
    Informations forums :
    Inscription : Mars 2004
    Messages : 38
    Points : 29
    Points
    29
    Par défaut
    nooon
    excusez moi j'ai été un peu absent (en voyage),je n'ai pas pu suivre mon sujet.
    Je crois que le sens pris par les amis n'est pas celui auquel je m'attendait.
    je ne demande pas comment calculer la surperficie ou le centre de gravité d'un polygone mais au contraire comment retrouver un polygone à partir de polylignes déjà tracées ?

    merci

  13. #13
    Membre éprouvé Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 53

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Points : 1 213
    Points
    1 213
    Par défaut
    Relis les posts + haut bon sang: la notion de VOISIN!!
    Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre

Discussions similaires

  1. Réponses: 20
    Dernier message: 15/01/2022, 20h38
  2. Transformation de cercle, arc de cercle en polyligne
    Par thedante dans le forum Mathématiques
    Réponses: 14
    Dernier message: 26/02/2013, 18h19
  3. [2D] Transformer un polygone complexe en triangle
    Par Kewlcool dans le forum Développement 2D, 3D et Jeux
    Réponses: 11
    Dernier message: 11/12/2008, 22h20
  4. découper polyligne et polygone
    Par gracerare dans le forum 2D
    Réponses: 1
    Dernier message: 26/07/2007, 10h15
  5. Transformer une ligne en polygone
    Par bl4d3 dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 02/09/2003, 10h35

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