Is there any effective way to find colors like this?

Question

In our project, we will try to use different color for different figures. These colors should satisfy the following condition:

All colors should meets: abs(A.R - A.G) + abs(A.G - A.B) + abs(A.B - A.R) > 250
All colors should be different enough. If color A and B meet: abs(A.R - B.R) + abs(A.G - B.G) + abs(A.B - B.B) >= 50, then they are different enough. The question is maximally how many colors we can get? Is there any fast way to get the colors without enumerating all combinations?

Since you're not using color properties, just coordinates, this is a geometry problem. Take a cube, restrict yourself to a subset of it using criterion 1, then pick points within that subset which are pairwise restricted by criterion 2. Unfortunately it's not quite **sphere packing** (which has been studied), because your distance metric isn't Euclidean distance. — AakashM, Nov 12 '12 at 10:54

score 2 · Answer 1 · edited May 23 '17 at 12:04

It depends on where you need your colors (website, picture, ...). I once ran across a very similar problem, Below is what I found. In the end, I just used a HSV color space (which was easy in my application) which allows you to divide the hue range into equally-sized intervals and get different colors each time.

This is what I found useful:

Generate distinctly different RGB colors in graphs

How to automatically generate N "distinct" colors?

Generate unique colours

Leon Bouquiet · Accepted Answer · 2012-11-12T14:19:47.043

I think the easiest way to get an accurate result is through a Las Vegas algorithm, where you try to compose a set of colours that is as large as possible by incrementally adding a random colour that doesn't invalidate the current set. If there is no such colour available (e.g. because the last 100 attempts at finding such a colour failed), the current set forms the result.

Note that it doesn't try to "undo" possible wrong additions when it gets stuck, it just terminates, which makes the algorithm report lots of suboptimal sets, but very quickly. Hence, you'll want to run this algorithm several (thousand?) times to see how large a set you can compose.

I think this is one of the quicker ways to obtain a decent result with relatively little programming or analysis effort.

Edit: Did several quick runs: the maximum set size consisting of non-conflicting colours I found was 273.

Edit 2 As requested, the corresponding (relevant) sourcecode:

public class Colour
{
    public int Red;
    public int Green;
    public int Blue;

    public int Primality
    {
        get { return Math.Abs(Red - Green) + Math.Abs(Green - Blue) + Math.Abs(Blue - Red); }
    }

    public int Difference(Colour other)
    {
        return Math.Abs(this.Red - other.Red) + Math.Abs(this.Green - other.Green) + Math.Abs(this.Blue - other.Blue);
    }

    public Colour(int red, int green, int blue)
    {
        Red = red;
        Green = green;
        Blue = blue;
    }

    public static Colour Generate(Random rnd)
    {
        return new Colour(rnd.Next(256), rnd.Next(256), rnd.Next(256));
    }

    public static Colour GeneratePrimal(Random rnd)
    {
        Colour candidate = null;
        do
        {
            candidate = Generate(rnd);
        } while (candidate.Primality <= 250);

        return candidate;
    }
}

Using this class, a single run of the described algorithm would then look like this:

private Random _rnd = new Random();

public List<Colour> Run()
{
    List<Colour> resultSet = new List<Colour>();

    //Shouldn't find a set larger than 1000 Colours.
    for (int colourCount = 0; colourCount < 1000; colourCount++)
    {
        Colour candidate = null;
        bool found = false;

        //100000 means: Try *very* hard to find a next candidate
        for (int index = 0; index < 100000; index++)
        {
            candidate = Colour.GeneratePrimal(_rnd);
            if (resultSet.Any(col => candidate.Difference(col) < 50) == false)
            {
                resultSet.Add(candidate);
                found = true;
                break;
            }
        }

        if (found == false)
            return resultSet;
    }

    return resultSet;
}

Done... by the way, if this was the most helpful post, would you be so kind as to flag it as the answer? — Leon Bouquiet, Nov 13 '12 at 12:11

Is there any effective way to find colors like this?

2 Answers2