Tracer des cercles pavants de diamètre pair

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

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 1 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) :

Notez que $x$ est initialisé à $S$ au début de l’algorithme. Je pense qu’il s’agit d’une erreur car d’une part il n’est fait mention nulle part de ce $S$ dans tout l’article, et d’autre part il est dit juste avant que le premier point est $(1,R)$. De plus, l’indentation n’est pas des plus claires notamment pour le else if.

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.


  1. C’est moi qui ai ajouté la référence sur Wikipédia. 

« LaTeX is to a book what a set of blueprints is to a building » (Paul Dulaney) | Mon planétaire

+0 -0

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

Édité par elegance

+0 -0
Auteur du sujet

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 ?

Rockaround

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

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

elegance

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.

« LaTeX is to a book what a set of blueprints is to a building » (Paul Dulaney) | Mon planétaire

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte