Tracer des cercles pavants de diamètre pair

Je travaille actuellement sur un projet pour lequel j’ai besoin de tracer des quarts de cercles avec des pixels. Ces quarts cercles devant avoir une certaine épaisseur, j’ai décidé de procéder en traçant un certain nombre de quarts de cercles concentriques jusqu’à obtenir l’épaisseur désirée. L’algorithme de Bresenham (ou midpoint algorithm en anglais) est le plus courant mais il a l’inconvénient de laisser des trous entre les cercles. Il se trouve qu’il existe un algorithme ne laissant pas de trous entre les cercles : celui d’Andres. J’ai beaucoup de mal à trouver des informations sur cet algorithme.

J’éprouve des difficultés à implémenter correctement l’algorithme d’Andres. Le pseudo-code donné sur Wikipédia ne fonctionne que pour les cercles dont le centre est pris au centre d’un pixel. Ce que je cherche à faire, c’est tracer un cercle dont le centre est le coin d’un pixel. Je ne souhaite pas couper des cercles de diamètre impair pour obtenir mes quarts de cercles car je veux obtenir la meilleure circularité possible pour mon motif global. Fort heureusement, j’ai pu retrouver l’article original ¹ ou Andres explique comment obtenir exactement ce que je veux, et c’est là que ça coince : j’obtiens des trous entre mes cercles !

Pour ceux qui n’ont pas accès à l’article, voici l’algorithme donné et les explications (en pages 7 et 8 du PDF) :

Mon implémentation est la suivante :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def half_integer_centered_circle(xc, yc, R):
    x = 1
    y = R
    d = R
    while y >= x:
        draw_pixel(xc + x, yc + y)
        draw_pixel(xc + x, yc - y + 1)
        draw_pixel(xc - x + 1, yc + y)
        draw_pixel(xc - x + 1, yc - y + 1)
        draw_pixel(xc + y, yc + x)
        draw_pixel(xc + y, yc - x + 1)
        draw_pixel(xc - y + 1, yc + x)
        draw_pixel(xc - y + 1, yc - x + 1)
        if d > x:
            d = d - x
            x = x + 1
        elif d < R + 1 - y:
            d = d + y - 1
            y = y - 1
        else:
            d = d + y - x - 1
            x = x + 1
            y = y - 1

Voici quelques quarts de cercles successifs ayant été calculés par mon implémentation :

Il est évident que non seulement il y a des trous (ce que l’algorithme est censé éviter) mais en plus le quart de cercle de trois pixels de large n’est pas identique à celui donné dans l’article. Par ailleurs, le motif obtenu n’est pas très circulaire. En plus, théoriquement on doit trouver dans certains cas plusieurs pixels en ordonnée pour une même abscisse pour l’octant entre $\frac\pi4$ et $\frac\pi2$, mais je n’en obtient qu’un seul pour tous mes tests.

Autant j’ai réussi à adapter l’algorithme de Bresenham à mon besoin, autant là je sèche et je m’en remets à votre expertise.

Salut,

Où est le centre de ton cercle ?

Tu utilises l'algo pour un centre aux coordonnés non entières, mais sur ton dessin, on dirait que tu le prends en (0,0). As-tu essayé l'algo de la page 698 ?

Ici, ton problème, c'est qu'il reste quelques pixels blancs ? Je ferais quelque chose du genre :

1
2
3
4
5
6
7

Pour i = 1 a largeur
  pour j = 1 a hauteur 
     dist = distance (centre, i,j)
     dist = arrondi(dist, 0) //  Arrondi à l'entier le plus proche
     si mod(dist,2) = 0 alors   colorie(i,j,rouge)   sinon colorie(i,j,bleu) 
  fin
fin

J’admets que ce n’est pas clair dans mon message. Les algorithmes de tracé de cercles prennent généralement les coordonnées entières au centre des pixels. L’algorithme de la page 698 est de ceux-là et donc je ne peux pas l’utiliser directement. L’algorithme qui m’intéresse, à l’inverse, prend le centre des cercles sur des coordonnées demi-entières. Les coordonnées entières correspondant toujours aux centres des pixels, les coordonnées demi-entières correspondent donc aux coins des pixels. Avec cette méthode, je peux obtenir les cercles que je désire.

J’ai posé à nouveau ma question sur Stack Overflow hier après-midi. D’après la réponse que j’ai obtenu, l’algorithme donné semble faux. En repartant de la définition, qui prend en compte les cercles réels de rayon $R\pm\frac12$, on obtient le résultat attendu.

L’algorithme final est :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def half_integer_centered_circle_modified(xc, yc, R):
    x = 1
    y = R
    while y >= x:
        point(xc + x, yc + y)
        point(xc + x, yc - y + 1)
        point(xc - x + 1, yc + y)
        point(xc - x + 1, yc - y + 1)
        point(xc + y, yc + x)
        point(xc + y, yc - x + 1)
        point(xc - y + 1, yc + x)
        point(xc - y + 1, yc - x + 1)
        if (R - 0.5)**2 < (x + 1)**2 + y**2 < (R + 0.5)**2:
            x = x + 1
        elif (R - 0.5)**2 < x**2 + (y - 1)**2 < (R + 0.5)**2:
            y = y - 1
        else:
            x = x + 1
            y = y - 1

Ton algorithme est naïf et ne permet pas d’obtenir le résultat attendu. Si tu veux en savoir plus sur la question, tu peux aller lire l’article de Wikipédia sur l’algorithme de Bresenham et, bien entendu, l’article d’Andres dont je donne le lien dans mon premier message. Merci quand même.