color_sort

ColorSort

ColorSort sorts an array of colors perceptually, using the CIEDE2000 color distance function.

Unsorted	Sorted

Installation

Add this line to your application's Gemfile:

gem 'color_sort'

And then execute:

$ bundle

Or install it yourself as:

$ gem install color_sort

Usage

Call ColorSort.sort with an array of RGB colors in hex form (with or without preceeding #):

unsorted_colors = ["35c047", "7f40ed", "39ae1e", "5f9d4c", "94ec1e", "93e482"]

sorted_colors = ColorSort.sort(unsorted_colors)
	# => ["94ec1e", "93e482", "39ae1e", "35c047", "5f9d4c", "7f40ed"]

You can also sort multiple groups of colors with ColorSort.sort_groups. This will leave the groups in the order originally given, but will sort the colors within the groups. It will also order them such that the last color in a group and the first color in the next group are as close as possible.

unsorted_colors = [["35c047", "7f40ed"], ["39ae1e"], ["5f9d4c", "94ec1e", "93e482"]]

sorted_colors = ColorSort.sort_groups(unsorted_colors)
	# => [["7f40ed", "35c047"], ["39ae1e"], ["5f9d4c", "93e482", "94ec1e"]]

How it works

Often when dealing with colors on computers, we're working with the RGB color model. As each color has three components, we can think of it as a point in 3D space. This allows us to use the Euclidean distance to see how far apart two colors are.

Unfortunately, the RGB color space doesn't model how people perceive colors, so a pair of colors that are close together in RGB space may actually look quite different, and vice-versa. We can solve this by using the Lab color space and CIEDE2000 distance function. This color space and distance function are tuned to give a smaller distance for perceputally close colors.

Now we have a way of determining the perceptual distance between two colors, but we can't use this with a normal sorting algorithm because we can't define a Total order over all colors. What we really need to do is find the shortest path through our colors in Lab color space, using the CIEDE2000 distance function.

This turns out to be the Travelling salesman problem. We first tried the Nearest neighbour heuristic, but found that it left ugly discontinuities in the sorted colors.

Next we tried Simulated annealing, but found that it didn't converge on a solution anywhere near quickly enough to be useful.

The solution we settled on was to iteratively build of a list of colors, inserting each one in to the list at the point at which it causes the lowest increase in the total distance between all the colors currently in the list. This allows us to sort a few hundred colors in a couple of seconds, and produces visually pleasing results.

Other approaches

Wikipedia lists several other approaches for solving TSP - both exact solutions and approximate solutions. We didn't explore these because we couldn't find libraries that implemented them and didn't have the time to implement them ourselves.

It's almost certain that there's a better approach to solving this particular case of TSP, but we ran out of time/motivation to investigate further. If you know a better approach, please let us know!

Performance

The algorithm used by this gem has complexity O(n²) in the size of the list being sorted. Some example timings on a MacBook Pro:

Number of colors	Time (seconds)
100	0.11
200	0.37
300	0.72
500	2.14
1000	9.01

A note on naming

This gem was authored in the UK, where color is usually spelt colour. However, this gem depends on two others (color and colorscore) that spell it without the u, so for the sake of consistency it's spelt as color in this gem too.

Contributing

• Fork it ( https://github.com/ms-digital-labs/color_sort/fork )
• Create your feature branch (git checkout -b my-new-feature)
• Commit your changes (git commit -am 'Add some feature')
• Push to the branch (git push origin my-new-feature)
• Create new Pull Request