A journey of color sorting

Somewhat surprisingly, color sorting is a little harder than you’d think. Prompted by @Merely’s tweet I started looking at it and came up with some interesting results.

Disclaimer: I can’t think of many (if any) practical uses for this. It’s still fun to play with, though.

Why’s it so hard?

It’s hard because color representations don’t make a whole lot of sense to sorting functions without some extra work. Here’s an example of a naive sorter that sorts a randomly generated array of Color3s like so:

local function SortRGB(colorA, colorB)
	return colorA.r < colorB.r and colorA.g < colorB.g and colorA.b < colorB.b
end

Here’s the output, overlayed onto a SurfaceGui:

There’s not much in the way of “sorting” here - it’s mostly all noise. The only observable sorting is the light-to-dark shift from left to right, and even that’s pretty noisy. This is because the RGB color space is really bad at making sense to a sorting function.

HSV to the rescue

HSV is a more ordered color space which is best represented by a cylinder:

As shown in the image, HSV changes the hue, or overall color, as you rotate around the cylinder. The further you are from the center, the more saturated, or vivid, your color is. The further to the top you are, the brighter it is - the value’s higher. HSV colors can be relatively easily sorted. Let’s try this sorting function:

local function SortHSV(colorA, colorB)
	local hA, sA, vA = Color3.toHSV(colorA)
	local hB, sB, vB = Color3.toHSV(colorB)
	return hA < hB and sA < sB and vA < vB
end

Here’s the output when applied to a randomly-generated array of 1000 colors:

Still a bunch of noise. Why is that? It has to do with how the sorting function is constructed. Because it checks if all components of the first color are less than the second, the function isn’t grouping hues together.

What if it just sorted by hue?

local function SortHue(colorA, colorB)
	local hA, sA, vA = Color3.toHSV(colorA)
	local hB, sB, vB = Color3.toHSV(colorB)
	return hA < hB
end

This produces a neater output:

It’s still a little noisy though - it’s grouping hue values correctly, but it’s got bright and dark colors all over the place. It’d be nice if we could normalize that a little.

Unfortunately, this is where things start to come apart. To sort these perfectly, the function would need three dimensions: one for hue, one for saturation, and one for value. Compromises have to be made in order to fit it in two.

Compromising

The largest problem that the function has right now is hues are noisy. This yields a pretty rainbow effect, but it also cripples any further attempts to improve the sorting. To improve further, the hue noise needs to be reduced; I’ve done this by grouping hue values into 8 segments. This leaves room for two colors to have “equal” hues, allowing the sorting function to compare other criteria. Grouping is just a rounded multiply, since hue values range from 0-1:

local function ClampHue(h, segments)
	return math.floor(h * segments)
end

These clamped hues can be used to produce a much better sorting function (note: SEGMENTS is defined as 8):

local function SortClampedHSV(colorA, colorB)
	local hA, sA, vA = Color3.toHSV(colorA)
	local hB, sB, vB = Color3.toHSV(colorB)
	
	local clampedHA = ClampHue(hA, SEGMENTS)
	local clampedHB = ClampHue(hB, SEGMENTS)
	
	if clampedHA == clampedHB then
		return vA < vB
	else
		return clampedHA < clampedHB
	end
end

If the clamped hue value is the same, the function compares the brightness of the colors. This produces a cleaner output:

Luma

There are still some white streaks in the output. This is because the HSV concept of “value”, or brightness, doesn’t exactly match what humans perceive. To fix this, the sorting function needs to sort based on luma, not value, which is a more accurate representation of the perceived brightness of a color. The luma transformation involves accounting for gamma, and has (to my knowledge) only been calculated for RGB values. Here’s a function to do it:

local function Luminosity(color)
	return math.sqrt((color.r * 0.299) ^ 2 + (0.587 * color.g) ^ 2 + (0.114 * color.b) ^ 2)
end

The output cleans up significantly when this function is used:

local function SortLuma(colorA, colorB)
	local hA, sA, vA = Color3.toHSV(colorA)
	local hB, sB, vB = Color3.toHSV(colorB)
	
	local clampedHA = ClampHue(hA, SEGMENTS)
	local clampedHB = ClampHue(hB, SEGMENTS)
	
	local lumA = Luminosity(colorA)
	local lumB = Luminosity(colorB)
	
	if clampedHA == clampedHB then
		return lumA < lumB
	else
		return clampedHA < clampedHB
	end
end

There’s still some noisiness. Fine tweaking will resolve most of that.

Sorting the Palette

I sorted the Studio palette as a test. It’s a little weird because of the color balances in the palette (there’s a bunch of yellows, mainly):

There are some visual artifacts where colors don’t seem to be sorted quite right - that’s the hue segmentation in effect. Bumping down the number of segments from 8 to 6 yields this:

And changing it to 12 gives:

Full code

Anyway. That’s all of what has become a surprisingly long post. Hopefully this interested at least some of you - maybe it’ll be useful sometime. This is the final code used to produce the ending images:

local SEGMENTS = 12

local function VisualizeGuis(colors)
	local container = Instance.new("Part", workspace)
	container.Size = Vector3.new(10, 1, #colors / 10)
	container.Anchored = true
	container.Position = Vector3.new(-200, 10, -200)
	
	local gui = Instance.new("SurfaceGui", container)
	gui.Face = Enum.NormalId.Top
	gui.CanvasSize = Vector2.new(#colors * 10, 100)
	
	for index, color in ipairs(colors) do
		local point = UDim2.new(0, (index - 1) * 10, 0, 0)
		local size = UDim2.new(0, 10, 1, 0)
		local frame = Instance.new("Frame", gui)
		frame.Size = size
		frame.Position = point
		frame.BorderSizePixel = 0
		frame.BackgroundColor3 = color
	end
end

local function VisualizeParts(colors)
	for index, color in ipairs(colors) do
		local point = Vector3.new(2 * index - math.floor(#colors / 2), 10, 0)
		local part = Instance.new("Part")
		part.Anchored = true
		part.Material = Enum.Material.SmoothPlastic
		part.Size = Vector3.new(2, 1, 10)
		part.BrickColor = BrickColor.new(color)
		part.Position = point
		part.Parent = workspace
	end
end

local function Luminosity(color)
	return math.sqrt((color.r * 0.299) ^ 2 + (0.587 * color.g) ^ 2 + (0.114 * color.b) ^ 2)
end

local function ClampHue(h, segments)
	return math.floor(h * segments)
end

local function SortLuma(colorA, colorB)
	local hA, sA, vA = Color3.toHSV(colorA)
	local hB, sB, vB = Color3.toHSV(colorB)
	
	local clampedHA = ClampHue(hA, SEGMENTS)
	local clampedHB = ClampHue(hB, SEGMENTS)
	
	local lumA = Luminosity(colorA)
	local lumB = Luminosity(colorB)
	
	if clampedHA == clampedHB then
		return lumA < lumB
	else
		return clampedHA < clampedHB
	end
end

local colors = {}
for i = 1, 1000 do
	table.insert(colors, Color3.new(math.random(), math.random(), math.random()))
end

table.sort(colors, SortLuma)
VisualizeGuis(colors)

local palette = {}

for i = 0, 127 do
	table.insert(palette, BrickColor.palette(i).Color)
end

table.sort(palette, SortLuma)
VisualizeParts(palette)
30 Likes

Check this out:

I’ve done a bit with brickcolor sorting. here’s a picture of my color palette.

here’s all of the colors rounded to the nearest brickcolor

1 Like