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

Et quelle est la question ? Ton problème est clair en effet mais qu'est-ce que tu n'arrives pas à faire ?

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...

n'y a-t'il pas une formule à base de produits vectoriels (?) pour calculer la superfiice d'un polygone ?

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+

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]

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 :oops:

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:

---

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

Citation:

---

Envoyé par Nemerle

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

---

Ha Ha ! :D
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+

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...

Salut,

dixit P. Bourke :

Citation:

---

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+

:oops: 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

Relis les posts + haut bon sang: la notion de VOISIN!!