Мы напишем программу, которая осуществляет трассировку изображения для заданного графического файла. В отличие от алгоритма, использующего заданное небольшое количество цветов, мы не станем ограничивать себя в выборе цветов графических примитивов, зато ограничим их количество и форму. Трассированное изображение будет состоять из заданного количества цветных треугольников. В идеальном случае расположение, форма и цвета треугольников должны быть такими, чтобы трассированная картинка в некотором смысле была наиболее близка к оригиналу. Если идеальное решение будет трудно найти, поищем насколько возможно близкое к нему.
Результат мог бы выглядеть так:
Эта картинка получена самой первой, самой наивной версией нашей программы. Она далась нам очень нелегко: полсуток работы нашего компьютера, пара сотен мегабайт, занятых полученными файлами. Этот результат может кого-то разочаровать, но только не нас. Разумеется, в следующих версиях программу удалось заметно ускорить, так что подобные результаты стали получаться за полчаса. Кроме того мы теперь можем сохранять историю поиска лучшего решения в виде анимированного файла GIF. Всё равно наша программа не годится для использования в промышленных целях, так как даёт при разных запусках отличающиеся результаты и работает крайне медленно. Но в качестве учебно-тренировочного примера программа очень хороша.
А вот результат работы усовершенствованной версии. Просим прощения у читателей с медленной связью за большой ( 11M) файл GIF. Он получен примерно за 80 минут.
Источником нашего вдохновения при написании этой главы послужил этот блог Пьера Линденбаума.