Algorithme d'Andres : pas de pavage sans trou

Salut à tous,

J'utilise l'algorithme d'Andres fourni par Wikipédia pour tracer un cercle de largeur x. D'ailleurs j'ai à peu près compris son fonctionnement : on découpe le cercle en huit parties qu'on dessine en même temps et chacune de ces parties est la symétrique de l'autre par rapport au centre du cercle. Bon après j'avoue que l'aspect mathématique m'échappe complètement…

En tout cas, afin de permettre à l'utilisateur-final de créer des cercles de différentes largeurs, j'ai très légèrement adapté cet algorithme. Je l'ai en fait placé dans une boucle for qui permet de le lancer autant de fois que nécessaire (ie. : un cercle par unité de largeur, ie. : une exécution de l'algo par unité de largeur).

Et j'ai également modifié l'initialisation de deux variables, ce qui donne :

1
2

                    y = (int) (radius + current_thickness);
                    double d = radius + current_thickness - 1;

Le problème, c'est que je suis censé obtenir un pavage sans aucun trou d'après Wikipédia et pourtant ce n'est pas ce que je constate : en effet, il y a deux ou trois pixels blancs sur le pourtour du cercle (je précise que c'est un cercle non-plein) lorsque ce dernier a une largeur de 5 par exemple.

J'ai pensé à une imprécision due aux types mais a priori ce n'est pas ça (à un moment donné, j'avais déclaré d comme étant int et avais donc fait un cast : je l'ai changé en double mais les points sont toujours présents).

Voici l'algo :

 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

for(double current_thickness = 0; current_thickness < this.thickness; current_thickness++) {
    x = 0;
    y = (int) (radius + current_thickness);
    double d = radius + current_thickness - 1;

    while (y >= x) {
        max_counter++;
        updates.add(new Pixel(x0 + x, y0 + y, Color.BLACK)); // octant n°1
        updates.add(new Pixel(x0 + y, y0 + x, Color.RED));
        updates.add(new Pixel(x0 - x, y0 + y, Color.BLUE));
        updates.add(new Pixel(x0 - y, y0 + x, Color.ORANGE)); // octant n°4
        updates.add(new Pixel(x0 + x, y0 - y, Color.YELLOW)); // octant n°5
        updates.add(new Pixel(x0 + y, y0 - x, Color.GREEN));
        updates.add(new Pixel(x0 - x, y0 - y, Color.VIOLET));
        updates.add(new Pixel(x0 - y, y0 - x, Color.DARKGRAY)); // octant n°8

        if (d >= 2 * x) {
            d -= 2 * x + 1;
            x++;
            } else if (d < 2 * (radius - y)) {
            d += 2 * y - 1;
            y--;
            } else {
            d += 2 * (y - x - 1);
            y--;
            x++;
            }
        }
    }

Merci d'avance !

En ligne 20, je remplacerais radius par radius+current_thickness.

Oui c'était bien ça, désolé de ne pas avoir mis en résolu le topic il y a deux/trois heures, mais merci !

Par contre je n'ai pas compris : pour déboguer, j'aurais dû donner une couleur aléatoire à chaque cercle (donc à chaque nouvelle valeur de current_thickness) ?

Si mon diagnostic est bon, tu verras que le 1er cercle est correct, mais que les suivants ne sont pas bons.

Qu'aurais-je vu de bizarre qui m'aurait fait penser que les suivants n'étaient pas bons ?

Je ne sais pas exactement à quoi ça aurait ressemblé, mais tu peux faire le test très facilement.

Mais une chose est sûre, tu aurais vu que le premier cercle était bon, mais pas les suivants, c'était un indice pour dire que le bug était dans une mauvaise gestion de current_thickness.

Chercher un bug dans un programme c'est comme une enquête, ou comme une visite chez le médecin. Il faut renoncer pendant un certain temps à résoudre le problème de façon directe, il faut au préalable chercher à DIAGNOSTIQUER pourquoi ça ne marche pas. Et pour ça, il faut viser un objectif un peu différent de l'objectif de départ : ici, pour comprendre le bug, une piste était de chercher à savoir si chaque boucle dessinait un cercle correct ou non.

D'acc merci

Est-ce que tu aurais une idée de comment faire pour colorier chaque octant (= arc de cercle) avec un dégradé de couleur, de façon à faire apparaître un dégradé de couleur chromatique coloriant tout le cercle ?

Avec l'aide de quelques forumeurs, j'ai réussi à créer un algo qui trace un dégradé chromatique, celui-ci peut être utilisé pour n'importe quelle forme (cercle, rectangle…). Le souci c'est qu'ici on dessine 8 arcs de cercle dont on doit tracer un dégradé "local" et que si l'on regarde le cercle ainsi formé, ce dernier doit être un dégradé global chromatique.

EDIT

Pour l'instant, j'ai réussi à tracer un dégradé chromatique dans chaque arc de cercle.

Tu dois pouvoir construire une fonction qui va ressembler à ça :

1
2
3
4
5
6
7

CouleurMoyenne( Coul1, k1, Coul2, k2)
// Décomposer Coul1 en r1,g1,b1
// Décomposer Coul2 en r2,g2,b2
r3 = (k1*r1 + k2*r2) / (k1+k2)
r3 = (k1*g1 + k2*g2) / (k1+k2)
r3 = (k1*b1 + k2*b2) / (k1+k2)
renvoyer RGB(r3,g3,b3)

Et ensuite dans les lignes 8 à 15 de ton code précédent, tu vas mettre par exemple :

updates.add(new Pixel(x0 + y, y0 + x, CouleurMoyenne( Color.RED , current_thickness, Color.WHITE, this.thickness-current_thickness )));

Juste pour savoir, à quoi correspondent k1 et k2 ?

Après j'ai déjà écrit l'algorithme pour créer un dégradé chromatique, seulement ça fait plusieurs heures que j'essaie de l'utiliser dans le cadre d'Andres et j'ai du mal (par contre je l'ai déjà utilisé avec les équations paramétriques de cercle, et également pour créer un dégradé horizontal).

Oui, j'avais vu cette discussion, mais je ne la retrouve pas. Dommage. Il y avait eu une réponse très utile … mais visiblement tu n'avais pas saisi l'importance de cette réponse.

Et ta question sur (k1, k2) confirme cette incompréhension. Le concept essentiel que tu sembles n'avoir pas compris, c'est le concept de fonction.

Dans la précédente discussion, quelqu'un te disait : Si tu sais calculer un dégradé de couleur, tu sauras l'appliquer à n'importe quelle forme (rectangle, cercle, ligne…).

Ma fonction MoyenneCouleur, elle fait quoi ? Elle simule un peintre qui a 2 pots de peinture, de couleur coul1 et coul2 ; le peintre prend k1 centilitres dans le pot 1, et k2 centilitres dans le pot 2, et il fait un mélange homogène avec ça. Et en retour de ma fonction, j'obtiens une couleur intermédiaire entre coul1 et coul2, avec les proportions k1, k2.

A partir de 2 couleurs coul1 et coul2, en faisant varier k1 et k2, on obtient un dégradé. Par exemple :

1
2
3
4

for k1 in range(101)
    k2 = 100-k1
    coul3 = CouleurMoyenne( Color.WHITE, k1, Color.BLACK, k2 )
    //  Dessiner un pixel ou un carré ou un cercle de couleur k3

Le premier dessin sera Noir (0 cl de Blanc et 100 cl de noir), puis gris foncé… et tous les dégradés de gris jusqu'à blanc.

Peu-importe que je dessine des carrés ou des cercles ou autre chose, j'utilise une et une seule fonction pour calculer des couleurs qui varient de blanc à noir.

Cette fonction, je vais la sauvegarder dans une classe commune, que je vais éventuellement réutiliser dans plein de projets.

Je connais bien la notion de fonction (encore heureux ! je suis en master d'info =P), je me demandais juste si k1 et k2, dans ton raisonnement, étaient plus que des coefs. Mais apparemment non.

Du coup je n'ai pas de problème pour créer un dégradé hein, j'ai déjà l'algorithme (en fait j'en ai même deux : un algo pour faire un dégradé chromatique et un autre pour faire un dégradé noir->blanc/blanc->noir).

Le souci que j'ai est uniquement le suivant : à quel pixel associer la couleur XXX pour appliquer au cercle, tracé à l'aide de l'algorithme d'Andres très précisément, un dégradé chromatique (= arc-en-ciel) ? J'ai insisté sur Andres car j'ai déjà la solution pour un cercle tracé à l'aide d'équations paramétriques.

Je pense créer un autre topic, ce sera plus propre que d'en discuter ici. Je me laisse encore la nuit et demain matin pour y réfléchir cependant !

Bon… je vais redire ce que d'autres t'ont dit par ailleurs : repose toi, profite de tes vacances.

Là, tu n'es plus réceptif du tout.

?

Bein comment ça ? En fait je crois que j'ai mal expliqué mon souci : je sais bien que les algorithmes de dégradé (ce sont des fonctions à 2 paramètres) que j'ai écrits marchent quelle que soit la forme de dégradé, cependant ces paramètres diffèrent selon l'algorithme mis en place (pour dessiner telle ou telle forme, mais aussi pour dessiner une même forme selon différentes manières : équations paramétriques et Andres pour un cercle).

D'où ma question. Sinon plus particulièrement :

repose toi, profite de tes vacances.

En fait j'aime ce que je fais hein, y a pas de souci de ce côté-là, d'ailleurs j'ai ajouté un ou deux trucs non-demandés dans le TP qui agrémentent un peu le programme (transitions, animations par exemple).

En tout cas pour éviter d'apporter du contenu non-pertinent à ce topic, je pense en créer un autre.