# Best data structure for searching best color match? (4D space)

My current color distance formula is a modified version of Euclidian distance (eDist) because with eDist I was noticing weird issues where blue could be used instead of green in some situations when green would have made more sense. So my formula is:

dR^2 + dG^2 + dB^2 + dHue^1.5

*d means "delta" or "difference"

*dHue is calculated as:

``````        public static float GetDegreeDistance(float alpha, float beta)
{
float phi = Math.Abs(beta - alpha) % 360;       // This is either the distance or 360 - distance
float distance = phi > 180 ? 360 - phi : phi;
return distance;
}
``````

I can use a KDTree for RGB values, but Hue is a bit tricky because it has values that loop around in a circle. That is- 359 is closer to 2 than 10 is. With that in mind, can anyone recommend an ideal data structure that would work for this situation? Should I just use a KDTree, find nearest 10 matches, and do o(10) search on those 10 results to see which item is the best match? Or is there a better way of doing this?

Details about usage: Once the color map is created, it will be called about 4,194,304 times to find best matches. I WILL be making a best match cache, but... the initial match finding can still be optimized.

• You could consider just storing two copies in the tree, one with looped-around hue. Commented Mar 15, 2021 at 11:59

A fairly simple approach would be to do two searches. Do a regular search. If the distance to the found hue is less than `hue` or `360 - hue`, do another search with the hue set to `hue + 360` or `hue - 360` respectively. Make sure to input the max-distance to the second search to limit the number of nodes searched.