Понимаю, что прошло уже много лет, но вдруг кому-то пригодиться позже :)
На самом деле ситуация с цветами - она простая, т.к. это дискретное пространство. Грубо говоря, у нас RGB - это координаты точки в трехмерном пространстве. У точки есть окрестности - сферы, неким радиусом. Точки, которые лежат на поверхности этой сферы - равноудалены от исходной точки на расстояние равное радиусу сферы. Задача свести поиск - к прямому поиску, т.е. берем сферу с радиусом 0 - есть точки, отличные от нашей - значит они ближайшие, нет - увеличиваем радиус на 1, есть точки - отлично, нашли, нет увеличиваем радиус дальше и т.п. Возможно, тут можно применять не прямой поиск, а деление пополам в заданном интервале - тут уже творческий момент :) Как все это дело реализовать (это будет хорошо работать как раз для ситуации выше, когда поиск по фиксированному набору надо выполнять очень много раз).
1. Создаем три массива [0..255]. Массивы R, G, B. Элементом массива является множество индексов элементов исходного массива точек. Т.е. пусть точка с цветом 100, 25, 250 имеет индекс в исходом массиве 200. Тогда мы должны сделать R[100].add(200); G[25].add(200); B[250].add(200);
2. Поскольку мы наполняем массивы последовательно, то каждый элемент массивов R,G,B уже будет упорядоченным множеством. Если, по каким-то причинам, это не так - то вторым шагом надо упорядочить каждое множество.
3. Строим три двумерных массива UR[0..255,0..255]. UG. UB. Где UR[i,j] = пересечение множеств R[i] и R[j]. Прелесть в том, что множества у нас уже упорядоченные и их пересечение строится довольно быстро. Можно подробней тут
https://habrahabr.ru/post/250191/
На этом наша подготовительная работа закончилась. Она займет определенное время, но дальше поиск будет осуществляться очень быстро.
Итак, собственно сам поиск ближайшей точки до искомой прост. Для i=0 to 255. координаты искомой точки r, g, b. Берем множество значений UR[r-i, r+i] - объединяем в URi, так для каждого массива. Дальше смотрим пересечение множеств URi, UGi, UBi - если пусто, i++, иначе - любой (или множество - зависит от задачи) из найденных элементов - исходный. Конечно, тут надо следить, что бы не выйти за границы массивов и т.п., главное - идея - мы ищем ближайшие точки, как точки лежащие на поверхности сферы с центром в исходной точке, с наименьшим радиусом. А что бы не бегать каждый раз по массиву - мы подготовили три массива - с проекциями точек по каждой оси.
Можно было бы ограничится массивами R, G и B, но тогда при каждом поиске надо было бы находить пересечение - это, возможно, выгодней, для небольшого кол-ва итераций поиска. Для большого выгодней построить множества пересечений и искать по ним.
Простой
