Я реализую квантование цвета, которое работает в итерациях. Во время каждой итерации создается новая цветовая палитра, а затем в этой палитре много раз просматривается запись палитры, которая лучше всего соответствует данному триплету RGB.
Кроме того, мне нужно иметь доступ к палитре в виде массива, чтобы позже я мог построить окончательное изображение. Моей первой мыслью было дерево KD, содержащее только ссылки на элементы массива. Но перестроение такой разреженной структуры данных не кажется идеальным, по крайней мере, наивно, поскольку это означает (пере)распределение пространства для узлов KD все время.
Я полагаю, что лучшим подходом было бы никогда не освобождать узлы, а просто помечать их как неиспользуемые. Это позволило бы гораздо быстрее перестроить, поскольку перераспределение будет происходить только в том случае, если потребуется больше узлов.
Тем не менее, что-то, что по своей сути работает в структуре, подобной массиву, было бы даже лучше, поскольку это было бы более дружественно к кэшу ЦП. Итак, я наткнулся на кучи KD. Вот краткая статья в Википедии и вот статья об этом. Основная идея, по-видимому, заключается в расширении свойства кучи, и это заставит его работать внутри массива. Итак, это звучит идеально, поскольку кучи обычно реализуются с помощью массива. Но я никогда не использовал кучи KD, поэтому не уверен, есть ли какая-то загвоздка.
Итак, стали бы вы использовать кучи KD для поиска ближайшего подходящего цвета в цветовых палитрах? Если нет, то какую другую структуру данных вы бы порекомендовали, которую можно построить быстро и эффективно?
(«Создание» здесь означает, что вся структура данных палитры строится одновременно со всеми значениями цвета, они не добавляются по одному.)
