algorithm - Generate Visually Different Colors With An Unknown Color Collection Size

Question

I am trying to generate colors on the fly for a chart control. I want the colors to be visually distinctive. I don't just want the colors to be distinctive from the adjacent colors, but all colors generated so far.

I also don't want to have to have a known color collection size. Some algorithms I have seen for this require the number of things to color to be known. I want to implement a GetNextColor() for my color generator so I will not know at the time of choosing how many colors I will ultimately have and choosing a number up front feels wrong.

I am not just trying to graph a bunch of stuff in different colors, I am interested in this problem and want some feedback.

Here's where I'm at:

• Using the HSV color space.
• The hue is a value from [0-360] where 0 and 360 are the same (reddish).
• Hue starts at 0, I ad 27 (so that when it cycles around it doesn't land on the same color it started on), take MOD 360.
• For S and V (both between 0 and 1) I start out at a low number like .25
• Run through about 20 hues
• Then take a high number like .85
• Run through 20 hues
• Then start bisecting to get the most distant values that haven't been used yet.

This isn't a very effective method, it works OK, but it could be much more scientific. It started out with a lot of thought and then morphed into this mess.

Any ideas on how to do this elegantly?

(It shouldn't matter, but I am using C# and I will post code when I get back to my computer I have all this stuff on.)

Answer 1

I believe that your question should be split into two questions:

1. How to map colors into a n-dimensional Cartesian space, and define an Euclidean distance function between colors, such that the distance reflects the difference for a human observer.
2. Given a n-dimensional cuboid, generate a sequence of dots such that minimal Euclidean distance between any two dots generated so far would be maximized.

And now the answers:

1. Color difference is calculated using the The CIEDE2000 Color-Difference Formula. The CIEDE2000 formula is based on the LCH color space (Luminosity, Chroma, and Hue). LCH color space is represented as a cylinder (see image here).

   However, the difference formula is highly nonlinear. Therefore it would be impossible to map the colors into a square grid such that Euclidean distance would give the CIEDE2000 color-difference.

   Settling on a less accurate model, we can use the CIE76 Color-Difference formula, which is based on the Lab color space ( L*a*b*). We can use Euclidean distance directly on this color space to measure the difference. There are no simple formulas for conversion between RGB or CMYK values and L*a*b*, because the RGB and CMYK color models are device dependent. The RGB or CMYK values first need to be transformed to a specific absolute color space, such as sRGB or Adobe RGB. This adjustment will be device dependent, but the resulting data from the transform will be device independent, allowing data to be transformed to the CIE 1931 color space and then transformed into L*a*b*. This article explains the procedure and the formulas.

2. For the L*a*b* color space and the CIE76 Color-Difference formula - we'll need to solve the problem for a 3D cube.

   I believe that your best strategy would be to divide the cube into 8 cubes, which will generate 27 points. Use these points. Now divide each of the 8 cubes into another 8 cubes. For each of these cubes, 12 out of the 27 points have already been used, so you're left with 15*8 new points. In each additional step n, you can generate 15*8^n additional points.

   The points-set in each step should be sorted such that the minimal distance between two consecutive points would be maximized. I don't know how to do it - I've just posted a question.

Edit:

I've crossposted on https://cstheory.stackexchange.com/ and got a good answer. See https://cstheory.stackexchange.com/questions/8609/sorting-points-such-that-the-minimal-euclidean-distance-between-consecutive-poin.