Есть массив цветов (rgb). Элементов — около миллиона. В массиве ищется наиболее близкий цвет к заданному (критерий близости- это близость точки rgb к точке r1g1b1, т.е. корень из суммы квадратов разниц каждой из трех компонентов цвета). Задача такая — осуществить поиск максимально быстро. Перебирать все элементы массива и для каждого искать близость к заданному цвету — слишком накладно (задача стоит заполнить новый массив еще на несколько миллионов элементов, для каждого делать полный перебор — долго). Как можно осуществить этот поиск? Может какие алгоритмы существуют?
Пока удалось реализовать алгоритм разбиения пространства известных цветов на сектора. И поиск по ним. Но проблема в том, что вокруг сектора, в который входит цвет еще 26 секторов (по каждой из трех координат).
Поиск на данный момент занимает 1.5-2 секунду на каждую тысячу запросов.
Поиск с линейным пробегом по всему массиву известных цветов — 10-15 секунд на тысячу.
Поиск с перебором всех цветов начиная от искомой точки и по радиусу — 8 секунд на тысячу.
Пытаюсь разобраться с kd-tree. Есть где-то подробности их реализации для 3х мерного пространства? Я нашел пока 1 — на C# (то что надо), но уж больно она была медленной. Или хотя бы нормальное описание алгоритма. В wiki понять что-то сложно — там научная статья, с практикой расходящаяся.
Если массив совершенно рандомный, и нужно найти наиболее близкий элемент. То думаю тут не обойтись без прямого перебора. Для ускорения расчетов можно использовать GPU видеокарты.
Естественно, если у нас линейный неупорядоченный массив, то другого выхода, кроме как просканнировать его целиком, нет.
Любой алгоритм быстрого поиска предполагает предварительную обработку / создание структуры.
Так не проблема предварительно массив обработать. Сейчас экспериментирую с пространственным разбиением массива на области.
Один предварительный расчет даже требующий 10 минут расчетов — это ерунда по сравнению с 24 часами перебора массива в миллион элементов 16.7 миллионов раз (именно столько поисковых запросов надо сделать).
