Fastest way to generate a color that is not in an array of colors

Question

I'm wondering what the best way to approach this problem is...

I have an array of user defined colors that get pushed onto a stack as rgb values. I want to find a second color for each user-defined color. These second colors must be completely unique from the user-defined array, but can be completely random and do not need to have any visual relationship with any of the user colors.

Would generating random rgb values and testing it against the stack be fast, since it is highly unlikely that random numbers would find the same color on the first try. Or would simply starting at 255,254,253 and substracting 1 from each value, then testing it against the stack be better, also very unlikely and less operations. Or any other idea?

Answer 1

Here's some code to start off:

var colors = [];

function getRandUniqColor()
{
    var r = getRGBString(),
        g = getRGBString(),
        b = getRGBString(),
        rgb = r + g + b;

    if ( colors.indexOf(rgb) == -1 )
    {
        colors.push(rgb);
        return {
            r: r,
            g: g,
            b: b
        }
    }
    else
    {
        return getRandUniqColor()
    }
}

function getRGBString()
{
    var num = Math.floor( Math.random() * 255 ).toString();
    while (num.length < 3)
    {
        num = '0' + num;
    }
    return num;
}

Just call getRandUniqColor(), and you'll get an object literal of RGB values.

Note: If there'll be a lot of colors involved, you should not use a recursive function.

...and here's the fiddle: http://jsfiddle.net/wV6Mw/

Answer 2

I would suggest generating random RGB values (combine three random numbers) and then create a function that measures the color difference between your generated random color and the ones in your data structure. If your generated color is too close to one you already have, generate a new one. You will have to decide how "different" you want the random color to be from what you already have, but a difference of only a few points in R, G an B won't be discernibly different so you should be looking for some minimum separation in at least one channel.

Searching for "calculate rgb color difference" gives you a bunch of references on how to calculate a meaningful difference between two color values. This link from that search has a specific equation and here's a previous question on SO about color differences.

You can also generate complementary colors from what you already have if you just want different colors and don't need/want truly random colors.

You could generate a random color like this in either data form or hex string form:

// generate r,g,b data structure like {r: 255, g: 30, b: 09}
function generateRandomColorData() {
    function randomColorVal() {
        return(Math.floor(Math.random() * 256));
    }
    return {r:randomColorVal(), g: randomeColorVal(), b: randomColorVal()};
}

// generate hex string color value like FF4409
function generateRandomColorHex() {
    function randomColorVal() {
        var val = Math.floor(Math.random() * 256).toString(16);
        if (val.length < 2) {
            val = "0" + val;
        }
        return(val);
    }
    return(randomColorVal() + randomColorVal() + randomColorVal());
}

Answer 3

As others have said, the easiest way would probably be to just create random colors and check for collisions.

If you are filling up the color space a lot (users selecting millions of colors) then another way would be to create a color cube of 256^3 bits, and let "1" represent the used colors. Then you could start from position 0 and use the first "0" as your generated color, the next "0" as the second and so on. The data structure would be just over 2 MB of ram.

But random is probably the way to go.