Discussion :

[khayyam90]

j'aime beaucoup la methode proposee par j.p.mignot, tres propre et efficace. bien joué

je ne m'attendais pas non plus a voir ressurgir Stokes

[j.p.mignot]

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

[le_nardo]

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

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

[j.p.mignot]

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.

[le_nardo]

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

[j.p.mignot]

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"

[le_nardo]

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

[mathieu_t]

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+

[j.p.mignot]

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.

[mathieu_t]

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

[Guigui_]

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)

[j.p.mignot]

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

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

[souviron34]

Pour un polygone quelconque, la solution eacte est donnée dans la FAQ du Usenet NewsGroup comp.graphics.algorithms (FAQ) sujet 2.01