Color sorting

Lately I’ve been rather fascinated by the idea of sorting colors in an aesthetically pleasing fashion. I’ve been working a bit on and off to create a color picker very similar to Flexi, but more powerful and entirely based on CSS gradients, and I thought it would be cool to be able to incorporate a small palette area. (In the process, I learned that you can’t simulate bilinear gradients no matter how hard you try. The SVG code that should work to that effect seems broken in Pale Moon, a Firefox derivative, or else it’s broken entirely. This means no red, green, or blue-only editing mode.)

Colors are tricky animals to sort because for most humans—except the totally or partially colorblind, or women who are tetrachromatic—they’re three-dimensional. All concepts of “color space”, a fascinating area of study, are based on at least three dimensions. RGB is the one most people are familiar with for computer graphics, CMYK for printing (technically that’s four-dimensional, but the black kind of counts as some of each of the other three), the primary pigment colors we learned as kids which fit something like the RYB color space, and then there are others like CIE LAB, CIE XYZ, etc. that have more relevance to visual science. Of course video has others, including YUV, and Rec. 709 used by HDTV. Back in the computer graphics world, we also have HSV (hue, saturation, value) and HSL (hue, saturation, luminance) which are cousins of each other and can be converted back and forth.

For sorting colors in a pleasing way in just one dimension, I found a very nice algorithm online. Start by sorting by your primary criterion, like hue. Then, go through the array one item at a time and find out each color’s “fitness” in its current position, and compare to other places where it could be inserted between two colors (or against an end). If you find a better place for it, move it there. Each time through the loop, if there were changes you go again. The complexity (possible iterations) of the algorithm is quite high, but in practice it stops after not too many changes. The un-fitness of a color is, on the end, just its distance to the next color; in between two others, it the combined distance between itself and each of its neighbors, minus the distance between those two neighbors directly. The end result is a line of color that experiences as little variation as possible from one to the next, with smooth transitions.

But this algorithm cannot be extended to two dimensions. There’s just no way to make it work.

After a lot of trial and error, I eventually discovered a method that did work and is actually very fast. I call it grid-fitting, because the goal is to map colors to a rectangular space. And I will share it now.

  1. Set up your grid, e.g. a 10×10 square. Any positions that will not be used, or you pre-fill with a color that will not be sorted (e.g., you might want grayscales off to one side), mark as locked. Every position on the grid has a simple x,y from 0 to length-1, so for instance this 10×10 square goes from 0,0 to 9,9. If you prefer to go from 1 to length it really doesn’t matter. The number of unlocked spaces must be exactly the same size as the number of colors to be sorted.
  2. Make a list of colors, where each one has an associated x,y position. Unlike the grid, x and y need not be integers or even conform to the grid’s scale at all. The x and y should be based on your dominant criteria. For instance, I made x my hue (scaled from 0 to 360), and for y I found simple luminance (0 to 1) worked best; this was in HSL color space. Working saturation into it didn’t result in any better sort for me.
  3. Begin fitting. The part of the grid that has not yet been filled (not counting locked spaces) will be called, appropriately, the unfilled grid in these next steps. We keep track of its corners throughout the process, because ultimately this will shrink and we’ll be filling it from the outside in. Colors not yet assigned will be called the color pool.
  4. Figure out which side of the unfilled grid’s rectangle is shortest: the vertical or horizontal. With a square you can go either way. The length of this shortest side will be L. Sort your color pool by the other direction. That is, if your shortest side is vertical, sort the color pool by x.
  5. Take a size-L slice from the beginning of the color pool, where the values you sorted by are lowest. Sort this slice by the same direction L goes in, so if you sorted by x in step 4, this is a vertical slice and you’ll now sort the slice by y. Fill in the grid with the colors in this slice, starting at the appropriate corner of the unfilled grid and moving down. If you encounter a locked space, skip that color. (Note: This algorithm will break down in cases where the number of locked spaces is very high, so that there’s not enough color pool left to get an L-sized slice.) Any unused colors go back into the pool, at the beginning; you can re-sort them by the pool’s sort (e.g., by x), but unless you’re running into a lot of locked spaces in the middle of the grid this is moot. Adjust the unfilled grid’s corner to account for the grid being filled in further.
  6. If this wasn’t the last column or row in the unfilled grid, repeat step 5 for the opposite side, this time taking an L-sized slice from the end of the color pool. Once again, skip locked spaces and put any unused colors back into the pool.
  7. Until the unfilled grid is empty, return to step 4.

The upshot of this algorithm in basic terms is that you’re filling the grid by filling in its outermost edges first. You pick a set of colors that belong in that row/column, and then choose the column/row for each; if the space it would fill is already taken, it goes back in the pool.

I tested this with the 140 colors defined in the CSS3 standard, but with duplicates removed so it was actually 138. This was in a 12×12 grid, with six spaces locked (unused) on the lower end of the rightmost column. The nine grayscale colors (no saturation) I moved over to the top of the left column, and locked them there. This is the result:

colorsort1

It came out much more aesthetically pleasing than I had hoped. The hue range looks quite smooth, with only the odd color here or there seeming out of place from its like-hued friends. This is obviously not as smooth a result as you’d get by hand-picking the palette to have an even distribution, but for an arbitrary set of colors, I was quite happy with it. (Boy, CSS3 sure has a lot of off-white defined, doesn’t it?)

The reason that you don’t simply take a smaller slice, when any spaces are locked, is that the sort can end up working against you. In the example above, when I tried to just take six values for the rightmost column, it ended up going from dark to very light in just six colors, which would look out of place next to the adjacent column. By taking twelve and then only choosing the darkest six (the spaces for the lightest being locked), it looks the way it should.

This algorithm can be expanded to other shapes such as a hexagon, although the sorting criteria would differ and there would be more corners to keep track of. For instance with a hexagon, you’d probably want hue arranged conically so that red was at one corner, yellow the next, green the next, and so on. The sort would still use linear directions, but instead of simple x and y you’d be sorting by, for example, x*sqrt(3)-y, depending on the side. (One side would be straight and would allow for just x and y.)

What I don’t think this can do is an arbitrary non-grid shape, such as a circle. If the positions were setup so that you could approximate a circle but used a square or hexagonal shape instead, it’d be fine; you could simply cut off the corners as locked spaces. A spiral would not be fittable with this method, though, and I’m at a loss to determine what would work there.

Advertisements

About Lummox JR

Aspiring to be a beloved supervillain
This entry was posted in Uncategorized and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s