Discussion :

[le_nardo]

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

[Le Furet]

Tu cherches un algorithme de remplissage , et au lieu de noircir des pixels, tu comptes le nombre de pixels à noircir.

[khayyam90]

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.

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

[Le Furet]

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.

Je ne comprends pas ta remarque. Ou alors je n'ai pas saisi le problème.

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.

[khayyam90]

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.
[...]
ç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.
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

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

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

Remarque bien, je ne sais pas si les algorithmes de coloriage sont simples, et se comportent bien si ta forme est croisée.

[j.p.mignot]

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é

[mathieu_t]

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+

[j.p.mignot]

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.

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
#include <math.h>
// math.h pour fabs,    cos  sin  et M_PI ( 3.14...) de l'exemple
//---------------------------------------------------------------------------
float area( int Npts, float X[], float Y[])
   {
   float *DX  = new float[Npts];
   float *DY  = new float[Npts];
   float A       =       0;
   for ( int i=0; i < Npts; i++)
      {
      DX[i] = (X[(i+1)%Npts] - X[(i+Npts-1)%Npts])/2;
      DY[i] = (Y[(i+1)%Npts] - Y[(i+Npts-1)%Npts])/2;
      }
   for ( int i=0; i < Npts; i++)
      A = A + (X[i]*DY[i] - Y[i]*DX[i]);
   delete [] DX;
   delete [] DY;
   return ( fabs(A/2) );
   }
// exemple : calcul de l'aire d'1 cercle
float Surface_d_1_cercle(void)
{
//rayon 10
#define Npts 200
#define Ray 10
float U = 2 * M_PI / Npts;
float X[Npts], Y[Npts];
for( short i=0; i < Npts ; i++)
   {
   X[i] =  Ray * cos( i * U );
   Y[i] =  Ray * sin(i * U );
   }
return  area(Npts,X,Y);  // 314.107..     au lieu de    314.1592...
}

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

[le_nardo]

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

[j.p.mignot]

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

[Le Furet]

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 ?

[j.p.mignot]

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 )

[Le Furet]

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.

[j.p.mignot]

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 C++ :

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
float area( int Npts, float X[], float Y[])
   {
   float *DX  = new float[Npts];
   float *DY  = new float[Npts];
   float A       =       0;
   for ( int i=0; i < Npts; i++)
      {
      DX[ i ] = (X[(i+1)%Npts] - X[(i+Npts-1)%Npts])/2;
      DY[ i ] = (Y[(i+1)%Npts] - Y[(i+Npts-1)%Npts])/2;
      }
   for ( int i=0; i < Npts; i++)
      A = A + (X[ i ]*DY[ i ] - Y[ i ]*DX[ i ]);
   delete [] DX;
   delete [] DY;
   return ( fabs(A/2) );
   }

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

[aponchel]

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

[gere34]

Merci beaucoup pour cet algo. Je l'ai implémenté en AS3, je donne le code pour ceux que ça intéresse :

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
//Pour mon cas, les points et la méthode font parti de mon objet, mais ils peuvent très bien être passés en paramètre.
public var points:Vector.<Point> = new Vector.<Point>();
...
protected function calcArea():Number{
	var nbPts:int = points.length;
	var D:Vector.<Point> = new Vector.<Point>(nbPts);
	var a:Number = 0;
	for(var i:int=0;i<nbPts;i++)
		D[i] = new Point(
			(points[(i+1)%nbPts].x - points[(i+nbPts-1)%nbPts].x)/2,
			(points[(i+1)%nbPts].y - points[(i+nbPts-1)%nbPts].y)/2);
	for(i=0;i<nbPts;i++)
		a += points[i].x*D[i].y - points[i].y*D[i].x;
	a = Math.abs(a);
	//arrondi
	a = Math.round(a * 100);
	a/= 100;
	return a;
}

[Aleph69]

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 :

int_Ddx=int{c1}dx+...+int_{cp}dx.

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.

[DrDarko]

Je pense que le_nardo a des formes géométriques assez simple il n'y a pas d'étranglement

voire une forme de pomme de terre, jamais un "huit"

Du coup un simple algo de remplissage avec de la récursivité suffit à remplir son tableau.
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.

[Le Furet]

Ah en effet, j'avais mal compris ton programme d'exemple. Désolé.