algorithme itératif de calcul de distance
WebShaker
l'algorithme de Bresenham
http://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_d'arc_de_cercle_de_Bresenham
permet de tracer un cercle en utilisant des op�ration simple.
existe t-il un algorithme pour remplir le disque avec la valeur de la
distance des points par rapport � leur centre ?
Etienne
Pascal J. Bourguignon
Bien sur. En doutes tu?
Algorithme Rempli rayon
Entr�e: c, centre du cercle
rmax, rayon maximum
Sortie: un disque de rayon rmax et centre c, �tiquet� par la distance au
centre.
Faire:
r := 0
boucle:
appliquer l'algorithme de Bresenham sur le cercle de center c, rayon
r, en assignant � chaque point trac� la valeur r.
r := r+1
si r<=rmax aller a boucle.
fin.
--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
Fabien LE LEZ
>existe t-il un algorithme pour remplir le disque avec la valeur de la
>distance des points par rapport � leur centre ?
Pas s�r de comprendre. Si tu veux tracer des cercles concentriques
pour obtenir un disque, regarde la section "Limites de la m�thode" sur
la page que tu as toi-m�me indiqu�e.
Si tu veux juste tracer un disque de fa�on efficace, il suffit de
remplacer
tracerPixel( x+x_centre, y+y_centre ) ;
tracerPixel( -x+x_centre, y+y_centre ) ;
par
Tracer une ligne horizontale de -x+x_centre � x+x_centre, d'ordonn�e
y+y_centre.
Remplacer les 3 autres couples de lignes de code de la m�me fa�on.
WebShaker
> Bien sur. En doutes tu?
>
> Algorithme Rempli rayon
> Entr�e: c, centre du cercle
> rmax, rayon maximum
> Sortie: un disque de rayon rmax et centre c, �tiquet� par la distance au
> centre.
> Faire:
> r := 0
> boucle:
> appliquer l'algorithme de Bresenham sur le cercle de center c, rayon
> r, en assignant � chaque point trac� la valeur r.
> r := r+1
> si r<=rmax aller a boucle.
> fin.
>
Merci pour cette r�ponse rapide, mais en fait. j'aurai du pr�ciser que
je cherche � ne calculer le pixel destination qu'une seule fois.
En gros j'aimerai que mes boucles it�rent sur le carre contenant mon
cercle et calculer pour chaque valeur (x, y) la distance par rapport au
centre.
Voila.
WebShaker
> Pas s�r de comprendre. Si tu veux tracer des cercles concentriques
> pour obtenir un disque, regarde la section "Limites de la m�thode" sur
> la page que tu as toi-m�me indiqu�e.
non en gros je voudrais arriver a fabriquer cette image
http://www.webshaker.net/distance.jpg
ou l'intensit� du pixel repr�sente la distance.
Et ceci le plus rapidement possible sans passer par des op�rations
complexes.
Pascal J. Bourguignon
> Le 07/08/2011 14:59, Pascal J. Bourguignon a �crit :
>> Bien sur. En doutes tu?
>>
>> Algorithme Rempli rayon
>> Entr�e: c, centre du cercle
>> rmax, rayon maximum
>> Sortie: un disque de rayon rmax et centre c, �tiquet� par la distance au
>> centre.
>> Faire:
>> r := 0
>> boucle:
>> appliquer l'algorithme de Bresenham sur le cercle de center c, rayon
>> r, en assignant � chaque point trac� la valeur r.
>> r := r+1
>> si r<=rmax aller a boucle.
>> fin.
>>
>
> Merci pour cette r�ponse rapide, mais en fait. j'aurai du pr�ciser que
> je cherche � ne calculer le pixel destination qu'une seule fois.
Mais c'est le cas.
> En gros j'aimerai que mes boucles it�rent sur le carre contenant mon
> cercle et calculer pour chaque valeur (x, y) la distance par rapport
> au centre.
Tu ne connais pas le th�or�me de Pythagore? r = sqrt(x^2+y^2)
Pascal J. Bourguignon
J'ai ajout� une addtion � l'algorithm de Bresenham qui n'utilise pas
d'op�ration complexe, donc mon algorithme n'utilise pas d'op�ration
complexe.
Fabien LE LEZ
<p...@informatimago.com>:
>J'ai ajout� une addtion � l'algorithm de Bresenham qui n'utilise pas
>d'op�ration complexe, donc mon algorithme n'utilise pas d'op�ration
>complexe.
Ne parles-tu pas de racine carr�e dans ton autre message ?
Pascal J. Bourguignon
Oui, et alors?
Fabien LE LEZ
octant.
Tu auras donc un truc du style :
int const r= 10000;
for (int x=0, x2=0; x<=r; ++x) // Le carr� de 0 est 0.
{
for (int y=0, y2=0; y<=x; ++y)
{
// Des calculs ici.
y2+= y+y+1; // (y+1)^2-y^2 = 2y+1
}
x2+= x+x+1; // Idem
}
}
Le calcul de la distance se fait sur le m�me principe :
Le carr� de la distance est x2+y2.
La distance pour x=y=0 est d=0.
Le carr� de d, d2, vaut �galement 0.
Si x2+y2 >= (d+1)^2, alors il faut incr�menter d.
(d+1)^2 = d2 + d+d + 1
Donc :
if (x2+y2 >= d2 + d+d + 1)
{
d2+= d+d+1;
++d;
}
Il faut garder les valeurs interm�diaires de d et d2 quand on commence
chaque boucle y, et il doit y avoir quelques autres d�tails � r�gler,
mais le principe g�n�ral me semble fonctionner. Attention, j'ai pondu
�a � l'instant ; ne t'attends donc � aucune garantie.
WebShaker
> Il faut garder les valeurs interm�diaires de d et d2 quand on commence
> chaque boucle y, et il doit y avoir quelques autres d�tails � r�gler,
> mais le principe g�n�ral me semble fonctionner. Attention, j'ai pondu
> �a � l'instant ; ne t'attends donc � aucune garantie.
J'ai compris l'id�e.
Donc si �a me semble bien, c'est sans doute que �a marche.
je vais tester.
le seul truc c'est que je me demande s'il n'est pas possible que dans
certain cas, le pixel suivant ne va pas sauter plusieurs valeurs de d.
c'est a dire passer d'une distance de 4 a 8 par exemple (pour le tous
petit carres) mais cela doit pouvoir se corriger...
mais c'est d�j� bien.
merci.
Fabien LE LEZ
>le seul truc c'est que je me demande s'il n'est pas possible que dans
>certain cas, le pixel suivant ne va pas sauter plusieurs valeurs de d.
� l'int�rieur de la boucle "y", on ajoute 1 � y � chaque it�ration. La
distance va donc augmenter de 1 au plus.
� l'ext�rieur, on ajoute 1 � x � chaque it�ration, et on commence avec
y=0. Idem, la distance ne peut pas augmenter de plus de 1.
� v�rifier dans le d�tail, mais a priori c'est bon.
WebShaker
> On Sun, 07 Aug 2011 15:51:11 +0200, WebShaker<eti...@tlk.fr>:
>
>> le seul truc c'est que je me demande s'il n'est pas possible que dans
>> certain cas, le pixel suivant ne va pas sauter plusieurs valeurs de d.
>
> distance va donc augmenter de 1 au plus.
> y=0. Idem, la distance ne peut pas augmenter de plus de 1.
Ca semble correct en effet.
Autant pour moi.
Merci.
Bon je ne voudrais pas abuser, mais j'aurai aussi besoin du même
algorithme mais au lieu de remplir le rectangle par la distance par
rapport au centre, j'aurai besoin de l'angle !
Là, c'est plus compliqué me semble t-il !
Etienne