[Algo & conception] Géométrie : aire d'un polygone quelconque ?

Le côté programmation du développement d'un jeu vidéo.

Géométrie : aire d'un polygone quelconque ?

Messagepar Odintk45 » 08 Aoû 2010, 20:28

Bonjour tout le monde, :)

Je reviens à la charge avec une nouvelle question de géométrie.
Je cherche maintenant à calculer l'aire d'une surface (en 2D). Cette surface est un polygone quelconque (qui peut être convexe ou concave). Les seules données que je possède sont les coordonnées de chacun des points qui en constituent le contour.
J'imagine qu'il n'existe pas de méthode mathématique toute faite pour obtenir directement l'aire d'une telle surface (si je me trompe n'hésitez pas à me corriger ^^).
J'aimerais avoir votre avis sur la meilleure approche à avoir. Personnellement je pensais à trouver un algorithme (encore à développer, mais ça ne me semble pas insurmontable) qui divise la surface en triangles, et qui calcule indépendamment l'aire de chacun des triangles pour faire la sommes à la fin.

Qu'en pensez-vous ?

Merci d'avance pour vos réponses !
Odintk45
Hello World, I'm new !
 
Messages: 101
Inscription: 10 Avr 2005, 10:48

Messagepar valentin » 08 Aoû 2010, 20:48

Découpe ton polygon en triangle, ensuite tu fais la somme des aires de ses triangles.
Avatar de l’utilisateur
valentin
Hello World, I'm new !
 
Messages: 494
Inscription: 20 Mai 2008, 16:10
Localisation: GRENOBLE

Messagepar deathangel » 08 Aoû 2010, 22:17

la découpe en triangles est trop complexe à réaliser dans le cas des polygones convexes, tu vas perdre énormément de temps alors qu'il existe des algorithmes plus simples à base de calcul d'aire de trapèzes dont l'aire se calcule de la façon suivante :
A = ((b + B) * h ) / 2
avec A = l'aire, b = petite base, B = grande base, h = hauteur.

(ca va paraitre compliqué, mais quand l'idée est comprise, ca passe tout seul tu verras ;))

On considère que les points de ton polygone sont ordonnés.
Les bases correspondent aux ordonnées de tes points, la hauteur la différence des abscisses dans l'ordre des points (on ne prend SURTOUT PAS la valeur absolue, on reste en négatif si besoin)

Avec un dessin ce sera plus simple, on va partir d'un simple triangle dont les points sont :
A = (5,3)
B = (7,1)
C = (8, 10)
Le triangle est défini par les vecteur AB, BC et CA

on part sur le vecteur AB.
L'aire du trapèze sous le vecteur AB est :
A(AB) = ((1+3) * (5-7)) / 2 = -4
on recommence pour BC et CA
A(BC) = ((10+1) * (7-8)) / 2 = -5.5
A(CA) = ((3+10) * (8-5)) / 2 = 19.5

l'aire de ton triangle correspond à la somme des 3 aires sous les vecteurs, donc
A(ABC) = A(AB) + A(BC) + A(CA) = -4 + - 5.5 + 19.5 = 10
si ton aire est négative, prendre la valeur absolue.

on peut vérifier le tout avec la formule classique de calcul d'aire :
Image
A = 1/2 ((7-5)*(10-3) - (8-5)*(1-3)) = 1/2 (2*7 - 3*-2) = 1/2 (14 --6) = 10 :)

il te suffit de reprendre le même algorithme pour des polygones plus complexes. Pour chaque vecteur, calculer l'aire sous ce vecteur et additionner toutes ses aires.

L'idée comme tu peux le voir sur le schéma ci dessus, c'est de calculer la différence d'aire entre le trapeze bleu et les trapezes rouges ce qui te donne l'aire de ton triangle

Image

PS : cet algorithme ne marche pas si tu as des abscisses/ordonnées positives et négatives à la fois dans ton polygone, mais une simple translation de tous tes points pour le calcul suffit à régler le problème
95% des problèmes informatiques se situent entre la chaise et le clavier
--> Créez votre robot chien : http://doggyproject.free.fr/
--> Gagnez des PACK+ gratuitement : http://www.packbarre.com/
--> S.U.S Tennis de table http://www.sus.asso.fr
Avatar de l’utilisateur
deathangel
Hello World, I'm new !
 
Messages: 964
Inscription: 10 Avr 2005, 08:50
Localisation: Strasbourg

Messagepar valentin » 09 Aoû 2010, 08:01

Punaise, c'est beau :00000012:
Jvais me le garder dans un coin de la tête celui là, merci deathangel !
Avatar de l’utilisateur
valentin
Hello World, I'm new !
 
Messages: 494
Inscription: 20 Mai 2008, 16:10
Localisation: GRENOBLE

Messagepar Odintk45 » 09 Aoû 2010, 09:38

Merci pour ta réponse deathangel, je vais essayer d'appliquer ça tout à l'heure ! ^^
Odintk45
Hello World, I'm new !
 
Messages: 101
Inscription: 10 Avr 2005, 10:48

Messagepar dotty » 18 Mai 2013, 20:17

Bonjour à tous

Désolé de faire remonté ce topic de 2010 mais c'est un peu ce que je recherche

je suis nouvelle sur le forum et pas très douée en math...

je voudrais savoir si la formule proposé par deathangel est valable pour un quadrilatère qui n'a pas de coté égaux



En effet, Je cherche a calculer l'aire d'un quadrilatère convexe sur Excel. J'ai les coordonnées X et Y de 4 points
seulement j' ai utilisé la formule suivante :

J'ai fais :

(Xa*Yb)-(Ya*Xb) pour le premier point

puis pour le deuxième j'ai fais la même chose mais en descendant d'une ligne c'est à dire :
(Xb*Yc) - (Yb*Xc)
en gros je croise les coordonnées des points A,B,C,D ...

Ensuite j'utilise la formule Absolu en incluant la somme de tout les résultats que je divise par 2

J'aurai voulu savoir si ce que je fais est juste car j'ai des doutes en essayant sur papier je n'ai pas le même résultat...

Merci d'avance pour vos réponses ^^
dotty
Hello World, I'm new !
 
Messages: 4
Inscription: 18 Mai 2013, 20:12

Messagepar deathangel » 18 Mai 2013, 21:03

Salut,

j'ai un peu de mal à voir ta méthode, peux-tu envoyer ton fichier excel que je puisse jeter un oeil ? Ou alors intègre une image qui parlera un peu mieux si possible :)
La méthode que j'avais proposé à l'époque fonctionne pour tous polygones dans le plan, peu importe le nombre de points ou la (non-)convexité.
95% des problèmes informatiques se situent entre la chaise et le clavier
--> Créez votre robot chien : http://doggyproject.free.fr/
--> Gagnez des PACK+ gratuitement : http://www.packbarre.com/
--> S.U.S Tennis de table http://www.sus.asso.fr
Avatar de l’utilisateur
deathangel
Hello World, I'm new !
 
Messages: 964
Inscription: 10 Avr 2005, 08:50
Localisation: Strasbourg

Messagepar dotty » 18 Mai 2013, 22:03

deathangel a écrit:Salut,

j'ai un peu de mal à voir ta méthode, peux-tu envoyer ton fichier excel que je puisse jeter un oeil ? Ou alors intègre une image qui parlera un peu mieux si possible :)
La méthode que j'avais proposé à l'époque fonctionne pour tous polygones dans le plan, peu importe le nombre de points ou la (non-)convexité.


Merci beaucoup pour ton aide

alors je t'explique brièvement ce que je cherche a faire.
j'ai réalisé es profils en travers sur un cours d'eau tout les 25 mètres pour calculer le volume d'érosion. je voudrais donc calculer l'aire de ce profils pour le multiplier par la longueur... j'ai 44 profils au total.

je n'arrive pas a introduire mon fichier excel:00000012:
je mets donc une capture d'écran avec quelques explications

:)
dotty
Hello World, I'm new !
 
Messages: 4
Inscription: 18 Mai 2013, 20:12

Messagepar dotty » 18 Mai 2013, 22:07

Mince le fichier n'est pas arrivé ...
Je le remets.
Fichiers joints
Capture Profils.png
dotty
Hello World, I'm new !
 
Messages: 4
Inscription: 18 Mai 2013, 20:12

Messagepar deathangel » 19 Mai 2013, 07:49

J'avoue j'ai un peu de mal, ca fait longtemps que je n'ai plus fait ça, mais le calcul de ton K je ne vois pas trop à quoi il correspond. A priori c'est le calcul du déterminant des vecteurs OA et OB qui te donnerait l'aire du parallélogramme basé sur tes vecteur OA et OB (cf wikipedia)

Pour calculer l'aire de ton profil, je dirais que tu peux reprendre la formule que j'avais mise :
l'aire du trapèze sous le segment AB :
A(AB) = ((ya+yb) * (xb-xa)) / 2 = 128828.75
pareil sous BC, CD et DA
A(BC) = ((yb+yc) * (xc-xb)) / 2 = 78000
A(CD) = ((yc+yd) * (xd-xc)) / 2 = 127535
A(DA) = ((yd+ya) * (xa-xd)) / 2 = -378609

tu additionnes les 4, tu fais la valeur absolue et tu devrais avoir l'aire de ton profil = 44245.25 mm²
95% des problèmes informatiques se situent entre la chaise et le clavier
--> Créez votre robot chien : http://doggyproject.free.fr/
--> Gagnez des PACK+ gratuitement : http://www.packbarre.com/
--> S.U.S Tennis de table http://www.sus.asso.fr
Avatar de l’utilisateur
deathangel
Hello World, I'm new !
 
Messages: 964
Inscription: 10 Avr 2005, 08:50
Localisation: Strasbourg

Re: Géométrie : aire d'un polygone quelconque ?

Messagepar dotty » 05 Juin 2013, 01:01

Bonjour,
je suis désolé pour cette absence , j'ai déménagé et eu de nouveau internet seulement hier...
Merci deathangel pour ta réponse et ton aide ! seulement j'ai appliqué cette formule mais j'ai des aires exorbitantes ! comme 33m2 pour l'un de mes profils qui a pour mesure AB= 104cm BC= 700cm CD= 121cm et AD= 760cm... je ne comprend vraiment pas ou est le problème ... :00000021:
Merci de ton aide...
dotty
Hello World, I'm new !
 
Messages: 4
Inscription: 18 Mai 2013, 20:12

Re: Géométrie : aire d'un polygone quelconque ?

Messagepar deathangel » 08 Juin 2013, 08:11

Tu aurais les coordonnées ?
Avatar de l’utilisateur
deathangel
Hello World, I'm new !
 
Messages: 964
Inscription: 10 Avr 2005, 08:50
Localisation: Strasbourg

Re: Géométrie : aire d'un polygone quelconque ?

Messagepar remram44 » 10 Juin 2013, 02:41

deathangel a écrit:Tu aurais les coordonnées ?

Les longueurs des côtés d'un quadrilatère, c'est pas suffisant pour avoir une réponse unique sur l'aire... il va falloir plus d'info en effet :/
Avatar de l’utilisateur
remram44
Hello World, I'm new !
 
Messages: 684
Inscription: 27 Juil 2005, 16:18
Localisation: New York City, NY, USA

Re: Géométrie : aire d'un polygone quelconque ?

Messagepar jeng » 29 Sep 2013, 17:56

Désolé pour le up, mais vu la qualité du post je me permets de re-poser une question,

Qu'en est-il de la formule pour calculer le périmètre d'un polygone irrégulier/quelconque ?

D'avance merci!

EDIT: formule en (x,y) evidemment :)
jeng
Hello World, I'm new !
 
Messages: 2
Inscription: 29 Sep 2013, 17:53

Re: Géométrie : aire d'un polygone quelconque ?

Messagepar Gavos » 29 Sep 2013, 18:46

Il n'y a pas de formule universelle pour un polygone irrégulier. Il faut simplement découper ton polygone en polygones "classiques" pour lesquels il existe une formule, et additionner (on peut aussi faire l'inverse, obtenir ton polygone avec un polygone classique plus grand auquel on enlève un autre polygone classique).
Gavos
 
Messages: 1072
Inscription: 19 Mar 2005, 13:00

Re: Géométrie : aire d'un polygone quelconque ?

Messagepar jeng » 30 Sep 2013, 15:25

Merci de votre aide, mais j'ai trouvé ma réponse entre-temps... Soustraction des abscisses et des ordonnées entre eux puis calcul de l'hypoténuse du triangle formé!
jeng
Hello World, I'm new !
 
Messages: 2
Inscription: 29 Sep 2013, 17:53

Re: Géométrie : aire d'un polygone quelconque ?

Messagepar remram44 » 02 Oct 2013, 20:39

Gavos a écrit:Il n'y a pas de formule universelle pour un polygone irrégulier.

On parle de périmètre et plus d'aire ici. Donc c'est carrément facile, t'additionnes les tailles des côtés (cf. formule de distance entre deux points : racine_carrée((x1 - x2)² + (y1 - y2)²), ce qui revient à ce que tu as dit).
Avatar de l’utilisateur
remram44
Hello World, I'm new !
 
Messages: 684
Inscription: 27 Juil 2005, 16:18
Localisation: New York City, NY, USA

Re: Géométrie : aire d'un polygone quelconque ?

Messagepar ggga65 » 29 Déc 2013, 23:14

Bonjour
si on nomme les points n points de 0 a n-1 dans l ordre horlogique ou antihorlogique, on peut obtenir la surface interieure comme,la demi somme de x(i+1)*y(i)-x(i)*y(i+1) avec les points i allant de 0 a n. A la fin, x(n+1) , y(n+1) correspondent au premier point x(0), y(0)

Cela devrait marcher.
Justification: on construite des trapezes verticaux qui vont de l axe x vers les points i et i+ 1 (qui sont ordonnes) . on calcule laire de chaque trapeze ...qui vaut 1/2( x(i+1)-x(i))(y(i+1)+y(i)) . Les aires seront positives ( si le point i+1 est a droite ) ou negatives si le point i+1 est a gauche. Tout se simplifiera pour donner la formule initiale

Bon courage
ggga65
Hello World, I'm new !
 
Messages: 2
Inscription: 29 Déc 2013, 22:34

Re: Géométrie : aire d'un polygone quelconque ?

Messagepar ggga65 » 30 Déc 2013, 00:29

Pour completer:
http://translate.googleusercontent.com/ ... 8lD-VIocIw

La demonstration generale est egalement fournie ...theoreme de stokes
:00000014:
ggga65
Hello World, I'm new !
 
Messages: 2
Inscription: 29 Déc 2013, 22:34


Retourner vers Programmation

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 1 invité