Followup: "Sorting" colors by distinctiveness

Question

Original Question

If you are given N maximally distant colors (and some associated distance metric), can you come up with a way to sort those colors into some order such that the first M are also reasonably close to being a maximally distinct set?

In other words, given a bunch of distinct colors, come up with an ordering so I can use as many colors as I need starting at the beginning and be reasonably assured that they are all distinct and that nearby colors are also very distinct (e.g., bluish red isn't next to reddish blue).

Randomizing is OK but certainly not optimal.

Clarification: Given some large and visually distinct set of colors (say 256, or 1024), I want to sort them such that when I use the first, say, 16 of them that I get a relatively visually distinct subset of colors. This is equivalent, roughly, to saying I want to sort this list of 1024 so that the closer individual colors are visually, the farther apart they are on the list.

Answer 1

This also sounds to me like some kind of resistance graph where you try to map out the path of least resistance. If you inverse the requirements, path of maximum resistance, it could perhaps be used to produce a set that from the start produces maximum difference as you go, and towards the end starts to go back to values closer to the others.

For instance, here's one way to perhaps do what you want.

1. Calculate the distance (ref your other post) from each color to all other colors
2. Sum the distances for each color, this gives you an indication for how far away this color is from all other colors in total
3. Order the list by distance, going down

This would, it seems, produce a list that starts with the color that is farthest away from all other colors, and then go down, colors towards the end of the list would be closer to other colors in general.

Edit: Reading your reply to my first post, about the spatial subdivision, would not exactly fit the above description, since colors close to other colors would fall to the bottom of the list, but let's say you have a cluster of colors somewhere, at least one of the colors from that cluster would be located near the start of the list, and it would be the one that generally was farthest away from all other colors in total. If that makes sense.

Answer 2

This problem is called color quantization, and has many well known algorithms: http://en.wikipedia.org/wiki/Color_quantization I know people who implemented the octree approach to good effect.