Version imprimable
Bjr, j'ai un petit pb a resoudre
je voudrais calculer l'aire d'une surface de forme quelconque
je connais les coordonnées (x,y) de chaques points du contour dans un repère
y a t il un algo simple qui puisse me donner l'aire de la surface incluse dans la forme
Merci
Tu cherches un algorithme de remplissage , et au lieu de noircir des pixels, tu comptes le nombre de pixels à noircir.
tout dépend de ce que le_nardo cherche à faire. dans le cas d'une recherche d'aire géométrique, sans tenir compte de pixels, ça n'ira pas.Citation:
Envoyé par Le Furet
il faut donc considérer la figure à étudier comme étant un assemblage de triangles rectangles et non de carrés (pixels)
un aspect à prendre aussi en compte et qui pourrait poser des soucis si l'on n'y prend pas gare est la forme de la polyligne dont tu cherches l'aire, il faudra légèrement changer le calcul des triangles si elle est convexe ou concave.
De plus, si elle est croisée (en forme de 8 par exemple), il faudra la décomposer en plusieurs sous polylignes plus simples à évaluer
Je ne comprends pas ta remarque. Ou alors je n'ai pas saisi le problème.Citation:
Envoyé par khayyam90
J'imagine l'image de base comme une discrétisation d'un contour. Déjà, dans tous les cas, l'aire ne pourra être qu'approchée, et il est nécessaire d'avoir un grand nombre de points pour considérer l'approximation comme correcte.
Je veux bien qu'en utilisant des triangles rectangle, on ait une approximation légèrement meilleure, encore que, mais je ne vois pas comment le résultat pourrait être sensiblement différent.
Je ne suis pas spécialiste de ce genre de problèmes mais ça m'intéresserait si tu pouvais développer un peu ta pensée.
il est tout à fait possible de calculer l'aire exacte. C'est pas forcément facile, mais c'est tout à fait possible.Citation:
Envoyé par Le Furet
la liste des points connus permet de dessiner un polygone et il est possible de calculer l'aire exacte de n'importe quel polygone au nombre de sommets fini.
par contre, si on cherche à connaître le nombre de pixels contenus dans un polygone, ta solution avec un algo de remplissage fonctionne.
en réfléchissant un peu plus, il n'est pas utile de prendre des triangles rectangles, des simples triangles seront amplement suffisants.
Ce que je propose :
- découper le polygone en sous-polygones non croises
- découper chaque nouveau polygone en sous polygones convexes
- calculer l'aire de chaque nouveau polygone suivant le modèle suivant :
calculer l'aide de chacun des triangles définis par [centre du polygone, sommet n, sommet n+1]
on somme tout ça, et hop, on a l'aire totale
Mais on n'a jamais dit que la forme originelle était un polygone. Donc tu ne fais, dans tous les cas, qu'une approximation de l'aire. Ta méthode permettra d'avoir une plus grande précision sur la frontière de la forme, mais comme a priori sa contribution à l'aire totale est faible, je ne sais pas s'il est nécessaire de sortir un algorithme compliqué.Citation:
Envoyé par khayyam90
Remarque bien, je ne sais pas si les algorithmes de coloriage sont simples, et se comportent bien si ta forme est croisée.
si les points forment le contour de la surface , l'aire s'exprime par
A = 0.5 *| Somme ( x*dy - y*dx) | =
| Somme ( x*dy) | =
| Somme ( y*dx) |
l'intégralle se fait le long du contour fermé
Les algos de remplissage sont tout à fait adaptés... En plus le fait de connaître les points de contour est un avantage qui facilite le calcul de l'aire...
J'ai essayé de faire un petit dessin mais c'est pas simple, et puis il est tard... Mais j'essairai demain de présenter une méthode simple que j'ai déjà vu...
A+
Un calcul d'aire est TRES simple à implémenter
Pour illuster Somme (Xdy-Ydx) proposé dans mon précedant mail, voici 1 petit code en C.
Bien entendu, l'erreur sur l'aire, hormis les erreurs liées au codage et au calcul, sont surtout du au nombre de points et leurs précisions.Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
De façon générale il n'est pas possible "d'inventer" les points manquants, mais, si le contour est suffisamment lisse, des techniques de lissage, interpolations, ... permettent d'ajouter des points et ceci peut nettement participer à une bonne évaluation de l'aire.
On note qu'il s'agit d'une aire ALGEBRIQUE ( d'où la || ). Si la courbe devait se croiser comme dans "8" ou certaines lemniscates, on pourrait alors trouver une aire nulle ou nettement inférieure à sa valeure géométrique. Cela refète que sur une partie de la courbe on tourne dans le sens trigonométrique alors que sur une autre partie on tourne dans son sens inverse.
Cette relation d'aire n'est en fait qu'un cas particulier de la relation plus générale du théorème de Stokes ( somme Rot(A) dl = Somme A dS ) pour un champ vectoriel du type A(x,y,z) = ( 0,x,1) ou ( -y,0,1) ou bien d'autres encore
Bjr et merci de tout c'est petit calcul d'aire par les formules de STOKES et compagnie, mais je précise plusieurs points :
* d'abord ma forme est vraiment quelconque (concave ou convexe) voire une forme de pomme de terre, jamais un "huit"
* ensuite je cherche l'aire en comptant mon nombre de points inclus dans cette forme
si je prends mon image ligne à ligne je peux avoir :
* 0 points (pas de contour)
* 1 point (sommet du contour)
* 2 points (interieur du contour)
* 2*n points (si partie convexe)
En clair avez vous un algo de remplissage qui compte le nombre de points entre 2 points du contour.
merci
1- La méthode décrite fonctionne pour TOUTE forme de contour
2- Il est INNUTIL d'essayer de trouver ymax, ymin par des intersections par des droites verticales ( resp. Xmin, Xmax par des intersections par des droites horizontales).
3- Il n'y a AUCUNE influence du fait que la forme soit concave ou convexe
4- Il est seulement opportun de s'assurer que la courbe ne se "croise" pas
5- Essayer de "pixeliser" la surface conduit à un temps de calcul variant comme n^2 alors que l'intégralle sur le contours varie comme n. - Sans compter le temps nécessaire à la "pixelisation"
Il est SANS interet de compter un nombre de points ( ce qui par ailleur n'a pas de sens mathématique)
Appliquez mon code et vous obtiendrez le résultat. Il n'est PAS possible de faire + simple si les points sont à prioris non localisés sur une forme connue comme ellipse, parabole, ....
Il n'y a pas d'hypothèses sur la régularité de la courbe avec cette méthode ? Au cas où les hypothèses ne sont pas vérifiées, l'erreur reste minime ?
AUCUNE hypothèse. Le théorème de stokes s'applique sans problème. si la courbe est très irrégulière, il faut juste le nombre de points suffiants pour la définir. suivant le cas il est numériquement préférable d'intégrer X.dY OU Y.dX ou 0.5*(X.dY-Y.dX). J'aime bien la dernière formulation car elle symétrise le rôle de X et Y.
Il faut faire attention au fait qu'il sagit d'une aire ALGEBRIQUE. Sur une lemniscate de bernouilli, par exemple le résultat sera = à 0 alors que la surface "Géométrique" est évidement non nulle!
Si on regarde une intégralle de Rieman 'normale' on a en fait une surface définie par 1 droite verticale (X1,0), ->(X1,f(X1)) une courbe (X1,f(X1)->(X2,f(X2)) une droite (X2,f(X2)) -> (X2,0) une droite (X2,0)->(X1,0)
sur les droites 1 et 3 Y*dx =0 car dx=0, sur la droite 4 y*dx=0 car Y=0 et on retouve
Somme Y.dx comme on l'écrit de façon naturelle.
Ces équations intégralles sont très utiles car on réduit de 1 la dimention ce qui recourcit singulièrement les calculs.
Le passage de 3D à 2D (quand cela est possible) se fait via l'équation d'Ostrogradsky ( Somme surface fermée A. dS = Somme volume div(A) .dTau )
Mais ta courbe, elle est quand même donnée par une équation là. le_nardo n'a pas précisé que sa surface était donnée par une équation. :?
La courbe n'a pas à être donnée par une équation. L'intégration des points est numérique: on a une somme de N elements du type X*dy-Y*dx. Pour le petit test j'ai mis les points Xi, Yi sur un cercle pour permettre au lecteur de verifier le résultat
Rappel du code
Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Le calcul de l'aire ne fait jamais appel à une équation.
Si vous en avez une tant mieux : il sera possible d'accroître à discression le nombre de points si nécessaire.
De plus il ne sera pas necessaire de calculer numériquement dY ou dX si on a les dérivées.
si non on se contente des points donnés.
Comme je l'ai dit precedemment, si on fait l'hypothèse d'1 courbe relativement lisse alors on peut, si necessaire, ajouter quelques points par des méthodes d'interpollation ( FFT 2D, splines, ... )
Ah en effet, j'avais mal compris ton programme d'exemple. Désolé.
Salut !!
M... c'est ce que je voulais expliquer !!Citation:
* d'abord ma forme est vraiment quelconque (concave ou convexe) voire une forme de pomme de terre, jamais un "huit"
* ensuite je cherche l'aire en comptant mon nombre de points inclus dans cette forme
si je prends mon image ligne à ligne je peux avoir :
* 0 points (pas de contour)
* 1 point (sommet du contour)
* 2 points (interieur du contour)
* 2*n points (si partie convexe)
Mais l'algo de jp mignot me plaît bien !!! ça a l'air sympa !
A+
Ben comme il dit, l'avantage, c'est que sauf courbe complètement débile (avec beaucoup de circonvolutions), c'est plus en O(n) qu'en O(n²). C'est marrant, je ne m'étais jamais dit que la formule de Stokes pouvait EFFECTIVEMENT servir :D
je vous engage alors à revoir vos equations de maxwell et tout l'electromagnétisme, calcul de flux, ...!
l'analyse vectorielle y est reine.
Si je veux ! :D
Ce n'est pas exactement ce que j'entendais par "servir".
Je sais très bien à quoi sert la formule de Stokes, c'est juste que je l'ai apprise dans un cadre beaucoup plus théorique (variétés différentielles, forme différentielle, et tout le bataclan, qui ne m'a jamais vraiment passionné) et c'est amusant de se rendre compte qu'elle sert, bien sûr sous sa forme la plus simple. J'ai étudié tellement de choses qui ont peu d'applications.
j'aime beaucoup la methode proposee par j.p.mignot, tres propre et efficace. bien joué :ccool:
je ne m'attendais pas non plus a voir ressurgir Stokes :D
1- Je tiens à m'excuser de ma réaction un peu vive à l'encontre de 'Le Furet'. Je suis moi-même passionné de math et de physique ( modélisation ) et ai réagit un peu vite.
Au vu des autres mails de ce correspondant je ne doute pas qu'il ait les bases mathématiques pour maîtriser des outils de base.
2- "étudié bien des choses qui ont peu d'application" ... oui et non : on utilise bien des outils dont on "oublie" faute de temps les fondements et dont l'exactitude dépend de "vérité" bien + profondes: on les utilises donc sans s'en rendre toujours compte! Je trouve que, malheureusement, on utilise de + en + des "formules" quasi "magiques" sans + prendre vraiment le temps d'en vérifier ni l'origine ni même les domaines d'applications. D'autre part par manque de réflexion sur les bases même de l'édifice des mathématiques, il y a de + en + de problèmes qui sont abordés sur 1 aspect numérique via des computer de + en + puissant sans même se rendre compte qu'une solution analytique est possible ( =>perte de temps, perte des conclusions qu'une équation apporte quant aux comportements, stabilités, ... ) ceci même dans le cadre de programmes réputés "professionnels". - j'ai des exemples frappants dans les équations différentielles -
Mais je suis, par la force des choses, dans le même dilemme que notre interlocuteur: J'ai aussi appris bien des choses en prépa, grandes écoles, 3eme cycle qui ne sont plus que de la culture que j'essaie de maintenir mais dont je n'ai plus réellement le temps de me préoccuper.
3- Pour en revenir à Stokes et Ostrogradsky, trouver un champ vectoriel ( resp scalaire) qui ramène de 2D à 1D ( resp. 3D à 2D) représente un gain de temps + que considérable. Cela représente entre autre l'1 des avantages de la modélisation BEM ( Boudry Element Method ) avec la FEM ( Finite Element Method ).
Calculer une aire revient à calculer le flux de k à travers la surface ( du plan i,j) donc pour appliquer Stokes il faut trouver A tel que rot(A) = k. ceci trouve facilement 1 solution ( voir mail + haut ). On remarquera un intérêt encore + accru d'appliquer stokes pour la calcul du flux à travers des courbes non planaires si div (A)=0 ( flux concervatif) !
de façon + générale trouver A tel que rot(A) = fi(x,y,z)i + fj(x,y,z)j + fk(x,y,z)k amène à des équations différentielles partielles en général non linéaire... Mais même comme cela une solution numérique à ce système permet utiliser Stokes ( avec moins d'efficacité qu'en présence d'une solution analytique ) mais certainement plus d'efficacité que d'essayer de traiter le problème 2D. Ces remarques se reportent avec Ostrograsky et le passage 3D->2D
Bonsoir,
j'ai pu tester le petit algo pour calculer l'aire avec Stokes et c'est vrai que c'est vraiment pratique et en plus ca marche !!! :lol:
Mais le probleme se complique un peu, en fait ma surface definie par les points est incluse dans un tableau de 2 dimensions
le but est que tous les points inclus dans la surface doivent etre égal à 1 et ceux en dehors égaux à zero.
dans la fonction je lui passe un tableau qui va donc se remplir au fur et à mesure suivant que les points appartiennent ou non a la surface
J'espere que je me suis bien fait comprendre.
En clair, j'aurai besoin d'une fonction de remplissage de tableau en fonction de la position du point
merci
Non vous ne vous êtes pas fait comprendre! soyez plus précis SVP!
Le problème du calcul d'aire ne se compliquera pas seul l'invoquation de l''algorithme pourra être affectée ( légèrement )
D'autre part à mon avis tout a été + ou - dit sur ce sujet et je vous suggère de le noter comme [résolu]. Je ne pense pas que vous puissiez raisonnablement en attendre + d'infos.
OK
je vais essayer de faire le plus clair
je connais ma liste de points de contour (x,y) inclus dans une image de taille (taille_X, taille_Y)
je voudrais mettre dans une table de dimension identique (taille_X,taille_Y) des "1" ou des "0" suivant que le points correspond à la surface ou non !
voila espere que c'est plus simple
Il ne s'aggit STRICTEMENT PLUS d'un problème de calcul d'aire. Cela pose des problèmes de nature TRES différentes, par ailleurs sensiblement plus difficiles à formuler de façon unnivoque. Pouvez-vous préciser les hypotèses que l'on peut admettre pour considerer un point ( élément de la matrice ) comme etant sur le contour ( continuité, dérivabilité, arrondi, ... )
Je maintiens
1- Clore le topic " calul d'aire"
2- ouvir un nouveau thème de discussion " Comment savoir si un point est situé dans la surface sous-tentue par une courbe fermée"
Je sais qu'il ne s'agit plus d'un probleme de calcul d'aire mais ca devient un probleme de remplissage
mes points sont connus par des coordonnées (x,y)
je connais ma limite en x et y que j'appelle taille_X et taille_Y (par exemple taille_X = 5000, taille_Y=6000)
mes coordonnees de points sont par exemple (1251,1687) (1252,1687) ...
Donc pour tous les points de contour et tous les points inclus dans ce contour je voudrais mettre une valeur 1 dans un tableau correspondant aux memes coordonées de ces points et 0 ailleurs
le_nardo --> Bah... L'algo que tu décrivais me semblait approprié non ?
Sinon tu as moults algos de remplissage, tu n'as que l'embarras du choix... Un bien efficace et surtout rapide est la croissance par régions, si tant est que tu puisses connaître au moins un point à l'intérieur de ta région... Sinon il y en a plein d'autres, dont celui que tu citais...
A+
Je ne pense pas que cela soit aussi simple. Preuve en est le nombre de fois où le remplissage est incomplet ou, au contraire "fuit" dans des soft tout de même robuste comme photoshop.
Peuvent se poser des problèmes comme
1- discontinuité de la fronzière du au manque de points
2- apparente fermeture car la pixelisation a contuit à un étranglement de la forme qui "cache" la suite du dessin.
Il doit être possible de trouver sans trop de difficulté des solutions à se probléme
il faut affecter une variable d'état à chaque pixel le notant comme "non traité", "dans la surface"," Hors de la surface" ou "sur la courbe définitiant la frontière"
je dirais de faire
a- ajouter une ligne de plus "en haut et en bas de la matrice" ainsi qu'1 colone de plus "à gauche et à droite de la matrice" afin d'assurer que dans ce nouveau cadre la frontière ne touche aucun bord.
b- clore la courbe par adjonction des pixels manquant.
c- marquer les pixel de la courbe comme "sur la courbe définitiant la frontière"
d- Faire diffuser l'info " Hors de la surface" depuis un coin.
e- recherche des étranglements.
si aucun alors marquer tous les points non traités comme "dans la surface"
f- si non
- tant qu'il y a des points de la courbe hors des positions d'étranglement qui cotoient à la fois des points marqués comme "hors..." et des points marqué come "non traité", aller sur le point " non traité" et faire diffuer l'info "dans la courbe"
- tant qu'il y a des points de la courbe hors des positions d'étranglement qui cotoient à la fois des points marqués comme "Dans la surface..." et des points marqué come "non traité", aller sur le point " non traité" et faire diffuer l'info "Hors la courbe"
Ceci n'est qu'une idée et n'est ni testé ni même vérifié quant à l'exactitude de l'approche.
Je n'ai pas encore réfléchit à une détection automatique des occlusions mais je ne pense pas que cela soit difficile à mettre sur pied. Il faut aussi analyser le cas des courbes qui se croissent comme 8 ou projection des fenêtres de viviani. Ici à l'intersection les pentes diffèrent alors que sur une occlusion, les tangentes sont identiques mais les sens de déplacement sont inverses.
Ton idée est certes plus robuste (et donc plus longue), mais apparemment le_nardo dispose de tous les points de frontière, auquel cas il ne peut y avoir de fuites....
Tu peux regarder du côté du remplissage de trous (si ton image est binaire (enfin on peut l'adapter sinon)):
http://www.developpez.net/forums/vie...419&highlight=
L'algo remplir toutes les formes fermés d'une image binaire (utile s'il y a des risques de goulot d'étranglement dans ta forme). Puis y'a plus qu'à compter le nombre de pixels de la surface en question (il suffit de connaître un point de la surface).
S'il n'y a pas de goulot d'étranglement, le simple algo de remplissage d'une surface (du milieu de la page du lien) suffit puis après compter les pixels de ta surface (algo similaire)
Certaines réponses mixent encore le problème de "remplissage" et de "calcul d'aire"...
Je réitère ma suggestion auprès de l'auteur de cette rubrique: Ouvrir un deuxième thème de débat. Cela sera bien plus clair pour ceux qui cherchent des réponses. A mon avis le problème du calcul de l'aire est clos tandis que celui du remplissage peu encore suggérer des commentaires éclairés. Et continuer à vouloir calculer l'aire à partir du remplissage des formes ...
Vraiment pratique ta méthode... juste une question: peux-tu stp préciser ce que signifient en code C les "%Npts" dans le calcul des dx et dy ?
Je te remercie par avance
AP
Merci beaucoup pour cet algo. Je l'ai implémenté en AS3, je donne le code pour ceux que ça intéresse :
Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Bonjour,
le volume d'un ouvert D de R^n est par définition l'intégrale sur D de la mesure, disons dx (Lebesgue). L'"équation" de D intervient bien dans cette définition. Si on cherche à calculer exactement le volume, et sauf choix particuliers de D, la seule solution qui me vient à l'esprit est de partitionner D en cellules, disons c1,...,cp, dont les volumes sont facilement calculables, puis d'appliquer la relation de Chasles généralisée :
D'un point de vue algorithmique, je ne pense pas qu'on puisse faire mieux. En revanche, on peut gagner en rapidité dès que l'on ne cherche plus la valeur exacte du volume mais seulement une approximation.Citation:
int_Ddx=int{c1}dx+...+int_{cp}dx.
Je pense que le_nardo a des formes géométriques assez simple il n'y a pas d'étranglementDu coup un simple algo de remplissage avec de la récursivité suffit à remplir son tableau.Citation:
voire une forme de pomme de terre, jamais un "huit"
Il faut pour cela que les points que tu connais soient déjà répertoriés dans ton tableau. Et après tu laisses l'algo travailler.
PS : Ton algo j.p.mignot est assez intéressant.
Pour un polygone quelconque, la solution eacte est donnée dans la FAQ du Usenet NewsGroup comp.graphics.algorithms (FAQ) sujet 2.01
:mrgreen: