Discussion :

[valda117]

Bonjour,

Je possède des objets dont le nombre est inconnu. Pour être plus précis, l'utilisateur peut créer un nombre n de ces objets.
A ces objets, j'aimerais associé une couleur qui les distingue bien au format rgb.
La contrainte pour ce problème c'est qu'à un objet n'est associé qu'une et une seule couleur. Ainsi, si l'objet est détruit puis reconstruit, la couleur qu'il possédait avant doit lui être associée.
Chaque objet est identifié par un entier(int positif).

Le problème est vraiment très simple.
Si on nomme l'identifiant de l'objet X, on peut lui associer par ex la couleur :
R = (RougeDeBaseDesObjets + X * 10) % 256
G = (VertDeBaseDesObjets - X * 10) % 256
B = (BleuDeBaseDesObjets + X * 10) % 256
Ainsi chaque objet a une couleur propre et à la destruction/création de ce objet, cette même couleur lui sera réattribué.

Ma solution présente cependant un gros soucis. Toutes les couleurs se ressemblent..
Je veux dire par là qu'un objet dont l'identifiant est 0 n'est pas visiblement très différent de l'objet ayant l'identifiant 1.
En utilisant l'algo plus haut, on va en fait créé un dégradé de couleur ce qui ne m’intéresse pas.
Il faut que l'objet d'identifiant X soit d'une couleur fort différente de l'objet d'identifiant X-1.
Pour terminer, un objet d'identifiant X peut avoir une couleur similaire ou approchée d'un objet d'identifiant Y pourvu que valeur_absolue(X-Y) > 1. Idéalement, il faudrait que ce ne soit jamais le cas.

Auriez-vous une idée ?
Je planche dessus depuis ce matin et je n'ai pas trouvé un semblant d'idée ^^'
Si vous pouviez m'aider ou m'orienter, cela me serait d'une grande utilité.

Merci.

[Médinoc]

Je me souviens avoir eu une idée pour faire ça en jouant sur les bits (en inversant leur ordre et répartissant sur les trois couleurs).

Code C++ :

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
20
int red=0, green=0, blue=0;
if(id & 0x000001)
	red |= 0x80;
if(id & 0x000002)
	green |= 0x80;
if(id & 0x000004)
	blue |= 0x80;
if(id & 0x000008)
	red |= 0x40;
if(id & 0x000010)
	green |= 0x40;
if(id & 0x000020)
	blue |= 0x40;
//etc, 24 bits en tout
if(id & 0x200000)
	red |= 0x01;
if(id & 0x400000)
	green |= 0x01;
if(id & 0x800000)
	blue |= 0x01;

Il y a probablement moyen de faire ça avec les boucles qui vont bien.

Avec ça, les bits de poids faible de l'ID affectent en premier les bits de poids fort des couleurs.

[valda117]

Pas mal comme idée, je vais la tester de suite

[jblecanard]

Salut

J'ai déjà eu ce problème plusieurs fois et il n'est pas du tout trivial à résoudre. Une solution "optimale" nécessite de connaître à l'avance le nombre d'objets. Sinon, il faut faire une sorte de dichotomie.

On peut implémenter l'algorithme proposé par médinoc comme ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
using uchar_t = unsigned char;
using color_t = std::array<uchar_t, 3>;
 
color_t ComputeColorFromIndexSimple(size_t index) {
  color_t result {{0,0,0}};
  for(size_t i = 0; i < 8; ++i) {
    size_t power = 7 - i;
    for(uchar_t& elem : result) {
      elem |= ((index%2) << power);
      index /= 2;
    }
  }
  return result;
}

Cet algo présente l'avantage d'être simple. On va avoir un résultat comme ça :

 Objet 0     Objet 1     Objet 2     Objet 3     Objet 4     Objet 5     Objet 6     Objet 7    
 Objet 8     Objet 9     Objet 10    Objet 11    Objet 12    Objet 13    Objet 14    Objet 15   
 Objet 16    Objet 17    Objet 18    Objet 19    Objet 20    Objet 21    Objet 22    Objet 23   
 Objet 24    Objet 25    Objet 26    Objet 27    Objet 28    Objet 29    Objet 30    Objet 31   

 Objet 8000  Objet 8001  Objet 8002  Objet 8003  Objet 8004  Objet 8005  Objet 8006  Objet 8007 
 Objet 8008  Objet 8009  Objet 8010  Objet 8011  Objet 8012  Objet 8013  Objet 8014  Objet 8015 
 Objet 8016  Objet 8017  Objet 8018  Objet 8019  Objet 8020  Objet 8021  Objet 8022  Objet 8023 
 Objet 8024  Objet 8025  Objet 8026  Objet 8027  Objet 8028  Objet 8029  Objet 8030  Objet 8031 

 Objet 160000  Objet 160001  Objet 160002  Objet 160003  Objet 160004  Objet 160005  Objet 160006  Objet 160007 
 Objet 160008  Objet 160009  Objet 160010  Objet 160011  Objet 160012  Objet 160013  Objet 160014  Objet 160015 
 Objet 160016  Objet 160017  Objet 160018  Objet 160019  Objet 160020  Objet 160021  Objet 160022  Objet 160023 
 Objet 160024  Objet 160025  Objet 160026  Objet 160027  Objet 160028  Objet 160029  Objet 160030  Objet 160031 

Par contre comme il parcourt tout le cube RGB, il va taper dans des couleurs pas forcément flashy.

On peut écrire un autre algorithme, plus compliqué, qui consiste à parcourir les faces externes du cube RGB, pour se garantir une certaine force dans les couleurs. En utilisant les modulos pour sélectionner différentes parties des faces. Cela présente l'inconvénient de n'avoir "que" 390152 couleurs différentes au lieu de 16 millions. Voici l'implémentation que je propose (C++11):

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
namespace colorscale {
  using uchar_t = unsigned char;
  using color_t = std::array<uchar_t, 3>;
  // First element is the abcissa, second is the direction
  // Third element is the ordinate, 4th is the direction
  // 5th tells if the last dimension must be set to 0 (false) or 255 (true)
  using range_t = std::tuple<uchar_t, bool, uchar_t, bool, bool>;  
  using cube_8th_t = std::array<range_t, 3>;
 
  color_t ComputeColorFromIndex(size_t index) {
    // Defining constants data describing the RGB cube face parts
    std::array<color_t, 8> const summits {{ 
      {{0,0,0}}
      , {{255,0,0}}
      , {{255,255,0}}
      , {{0,255,0}}
      , {{0,0,255}}
      , {{255,0,255}}
      , {{255,255,255}}
      , {{0,255,255}}
    }};
 
    std::array<cube_8th_t, 8> const faces_parts {{ 
      {{ range_t(0,true,2,true, false), range_t(2,true,1,true,false), range_t(1,true,0,true,false) }}
      , {{ range_t(1,true,2,true,true), range_t(2,true,0,false,false), range_t(0,false,1,true,false) }}
      , {{ range_t(0,false,2,true,true), range_t(2,true, 1, false, true), range_t(1,false,0,false, false) }}
      , {{ range_t(1,false,2,true,false), range_t(2,true,0,true,true), range_t(0,true,1,false,false) }}
      , {{ range_t(2,false,0,true,false), range_t(0,true,1,true,true), range_t(1,true,2,false,false) }}
      , {{ range_t(2,false,1,true,true), range_t(1,true,0,false,true), range_t(0,false,2,false,false) }}
      , {{ range_t(2,false,0,false,true), range_t(0,false,1,false,true), range_t(1,false,2,false,true) }}
      , {{ range_t(2,false,1,false,false), range_t(1,false,0,true,true), range_t(0,true,2,false,true) }}
    }};
 
    auto const choose_bucket = [](size_t i) -> size_t { 
      switch (i) {
        case 0: return 2;
        case 1: return 5;
        case 2: return 0;
        case 3: return 3;
        case 4: return 6;
        case 5: return 1;
        case 6: return 4;
        case 7: 
        default: return 7;
      }
    };
 
    // This algorithm is limited to the external faces of the RGB cube
    index %= (2*256*256 + 2*256*254 + 2*254*254);
 
    // The first 3 bits choses the summit
    size_t summit_index = index % 8;
    index /= 8;
 
    color_t result {{ 0, 0, 0 }};
    if(0u == index) {
      result = summits[summit_index];
    }
    else {
      // Choose a face then normalize the index
      --index;
      size_t chosen_face_index = index % 3;
      index /= 3;
 
      // Extract x component and y component
      size_t x_comp = index%128;
      size_t y_comp = index/128;
 
      // The following lines works for 128x127 zones but is not
      // easily extendable to other dimensions
      size_t x_coord = 16*choose_bucket(x_comp%8) + x_comp/8;
      size_t y_coord = 16*choose_bucket(y_comp%8) + y_comp/8 + 1;
 
      // Project that position on the given face
      range_t const & face = faces_parts[summit_index][chosen_face_index];  
      result[std::get<0>(face)] = std::get<1>(face) ? x_coord : 255 - x_coord; 
      result[std::get<2>(face)] = std::get<3>(face) ? y_coord : 255 - y_coord; 
 
      // Finding the third axis
      size_t sum = std::get<0>(face) + std::get<2>(face);
      size_t third_axis = (1 == sum) ? 2u : ((2 == sum) ? 1u : 0u);
      result[third_axis] = std::get<4>(face) ? 255u : 0u;
    }
 
    return result;
  }
}  // namespace colorscale

On va obtenir ceci en résultat :

 Objet 0     Objet 1     Objet 2     Objet 3     Objet 4     Objet 5     Objet 6     Objet 7    
 Objet 8     Objet 9     Objet 10    Objet 11    Objet 12    Objet 13    Objet 14    Objet 15   
 Objet 16    Objet 17    Objet 18    Objet 19    Objet 20    Objet 21    Objet 22    Objet 23   
 Objet 24    Objet 25    Objet 26    Objet 27    Objet 28    Objet 29    Objet 30    Objet 31   

 Objet 8000  Objet 8001  Objet 8002  Objet 8003  Objet 8004  Objet 8005  Objet 8006  Objet 8007 
 Objet 8008  Objet 8009  Objet 8010  Objet 8011  Objet 8012  Objet 8013  Objet 8014  Objet 8015 
 Objet 8016  Objet 8017  Objet 8018  Objet 8019  Objet 8020  Objet 8021  Objet 8022  Objet 8023 
 Objet 8024  Objet 8025  Objet 8026  Objet 8027  Objet 8028  Objet 8029  Objet 8030  Objet 8031 

 Objet 160000  Objet 160001  Objet 160002  Objet 160003  Objet 160004  Objet 160005  Objet 160006  Objet 160007 
 Objet 160008  Objet 160009  Objet 160010  Objet 160011  Objet 160012  Objet 160013  Objet 160014  Objet 160015 
 Objet 160016  Objet 160017  Objet 160018  Objet 160019  Objet 160020  Objet 160021  Objet 160022  Objet 160023 
 Objet 160024  Objet 160025  Objet 160026  Objet 160027  Objet 160028  Objet 160029  Objet 160030  Objet 160031 

C'est moins terne, et le contraste local est meilleur visuellement. Globalement, les objets situés à un modulo 8 de distance n'auront pas un super contraste mais c'est le cas pour les deux algos. Le 2ème algo est par contre méga chiant à implémenter et pas naturel du tout, mais je l'ai fait donc zéro boulot pour toi, l'exercice m'a plu. Cet algo est "propre", c'est à dire que j'ai bien vérifié que toutes les couleurs possibles dans les 390152 sont bien parcourues.

Avec tout ça, tu devrais pouvoir te débrouiller . Un exécutable complet est disponible ici. Attention à mon choix d'utiliser des unsigned char pour économiser un peu de place : faut penser à les convertir si on les met dans un flux sortant.

[therwald]

390152 couleurs différentes au lieu de 16 millions.

Inconvénient minime si l'on songe que le nombre de teintes réellement distincte aux yeux d'une personne entraînée (du style spécialiste de la décoration, peintre professionnel ou restaurateur de tissus anciens) se situe quelque part entre 10000 et 20000 ...

Et merci pour cette proposition d'algo dans un domaine pas simple du tout (personnellement la dernière fois que je m'y suis frotté j'ai dû me contenter une fois de plus d'un pis aller faute de temps pour creuser le sujet...)

bonnes fêtes