Automatic Generation of Color Palettes

A problem I've had several times is how to automatically generate colors for use in graphs. The user will be able to select some set of items that should be included and I need to select colors for each item. The requirements are:

• The color for an item should be easy to distinguish from other items. Of course, it would also be nice if the colors looked decent, but from a functional perspective, the requirement is to be able to distinguish the items in the graph.
  
• I need to be able to generate an arbitrary number of colors and avoid a fixed color palette with a predefined number. For practical purposes the number will be limited by the ability to distinguish different colors, but it would be nice for the mechanism to scale gracefully as the number of items increases.
  
• The color of the background, for my purposes white, cannot be used.

When I examined a few tools, I found that most worked by having a fixed set of colors. My first attempt was to perform a naive increment of RGB pixel values. A trivial increment works well for shades of gray. This produces a palette like:

Hex	2	4	8	16
000000
0E0E0E
1C1C1C
2A2A2A
383838
464646
545454
626262
707070
7E7E7E
8C8C8C
9A9A9A
A8A8A8
B6B6B6
C4C4C4
D2D2D2

The problem is that grayscale can be difficult to distinguish with more than a few colors. That is why tools like gnuplot use line patterns and shapes. However, most of my use cases are for graphs shown on a color monitor so there is no need to limit to grayscale. What happens if we try a naive increment with color? My first attempt was to treat the color as a three byte integer and simply divide the desired number of colors to get the increment value. Looking at the palette below you can see the results are poor:

Hex	2	4	8	16
000000
0FFFF0
1FFFE0
2FFFD0
3FFFC0
4FFFB0
5FFFA0
6FFF90
7FFF80
8FFF70
9FFF60
AFFF50
BFFF40
CFFF30
DFFF20
EFFF10

After looking around for a bit I found that the HSV representation is fairly well suited for this problem. HSV stands for hue, saturation, and value. The color space is represented as a cylinder:

For more background the paper Color Spaces for Computer Graphics gives a good overview and discusses how the various color spaces were designed with respect to human perception of color. To generate a palette the saturation and value settings can be fixed. The 360^o for the hue can be divided by the desired number of colors and then we just increment the angle for each color. This technique gives a nice palette, but for more than around 8 colors it will be difficult for a person to distinguish some shades.

Hex	2	4	8	16
FF0000
FF5F00
FFBF00
DFFF00
7FFF00
1FFF00
00FF3F
00FF9F
00FFFF
009FFF
003FFF
1F00FF
7F00FF
DF00FF
FF00BF
FF005F

The Scala code I used for generating the palettes is shown below.

object Colors {

    import java.awt.Color

    def grayscale(num: Int): Seq[Color] = {
        // Truncate the full range of values to make sure we can distinguish
        // from the color white, i.e., (256, 256, 256).
        val range = 256 - 32

        // Determine how much to increment for each color.
        val delta = range / num
        if (delta == 0) {
            throw new IllegalArgumentException(
                "grayscale can support at most " + range + " colors")
        }

        // Generate the sequence of colors
        (0 until num).map(n => {
            val value = n * delta
            new Color(value, value, value)
        })
    }

    def naiveIncrement(num: Int): Seq[Color] = {
        // Truncate the full range of values to make sure we can distinguish
        // from the color white, i.e., (256, 256, 256).
        val range = 0xFFFFFF - 0xFF

        // Determine how much to increment for each color.
        val delta = range / num
        if (delta == 0) {
            throw new IllegalArgumentException(
                "naive increment can support at most " + range + " colors")
        }

        // Generate the sequence of colors
        (0 until num).map(n => {
            val value = n * delta
            new Color((value >> 16) & 0xFF, (value >> 8) & 0xFF, value & 0xFF)
        })
    }

    def hsv(num: Int): Seq[Color] = {
        // Range is 360 degrees for the hue
        val range = 360.0

        // Determine how much to increment for each color.
        val delta = range / num
        if (delta < 1.0) {
            throw new IllegalArgumentException(
                "hsv can support at most " + range + " colors")
        }
        // Generate the sequence of colors
        (0 until num).map(n => {
            val hue = n * delta
            val h = hue / 60.0
            val x = ((1 - Math.abs(h % 2 - 1)) * 255).toInt
            val c = h match {
                case h if 0.0 <= h && h < 1.0 => (255, x, 0)
                case h if 1.0 <= h && h < 2.0 => (x, 255, 0)
                case h if 2.0 <= h && h < 3.0 => (0, 255, x)
                case h if 3.0 <= h && h < 4.0 => (0, x, 255)
                case h if 4.0 <= h && h < 5.0 => (x, 0, 255)
                case h if 5.0 <= h && h < 6.0 => (255, 0, x)
                case _ => (0, 0, 0)
            }
            new Color(c._1, c._2, c._3)
        })
    }

    def main(args: Array[String]): Unit = {
        if (args.length < 2) {
            println("Usage: scala Colors <palette> <num>")
            exit(1)
        }

        // Supported palettes
        val palettes = Map(
            "grayscale" -> grayscale _,
            "naive"     -> naiveIncrement _,
            "hsv"       -> hsv _
        )

        // Generate colors and print
        palettes(args(0))(args(1).toInt).foreach(c => {
            println(c.getRGB.toHexString.toUpperCase.substring(2))
        })
    }
}