Глава 47. Трассировка растровых изображений

Постановка задачи
	Глава 47. Трассировка растровых изображений

Постановка задачи

Мы напишем программу, которая осуществляет трассировку изображения для заданного графического файла. В отличие от алгоритма, использующего заданное небольшое количество цветов, мы не станем ограничивать себя в выборе цветов графических примитивов, зато ограничим их количество и форму. Трассированное изображение будет состоять из заданного количества цветных треугольников. В идеальном случае расположение, форма и цвета треугольников должны быть такими, чтобы трассированная картинка в некотором смысле была наиболее близка к оригиналу. Если идеальное решение будет трудно найти, поищем насколько возможно близкое к нему.

Результат мог бы выглядеть так:

Напоминает работы художников-конструктивистов начала 20 века:

Любовь Попова. Из серии «Живописная архитектоника» (собрание MoMA)

Эта картинка получена самой первой, самой наивной версией нашей программы. Она далась нам очень нелегко: полсуток работы нашего компьютера, пара сотен мегабайт, занятых полученными файлами. Этот результат может кого-то разочаровать, но только не нас. Разумеется, в следующих версиях программу удалось заметно ускорить, так что подобные результаты стали получаться за полчаса. Кроме того мы теперь можем сохранять историю поиска лучшего решения в виде анимированного файла GIF. Всё равно наша программа не годится для использования в промышленных целях, так как даёт при разных запусках отличающиеся результаты и работает крайне медленно. Но в качестве учебно-тренировочного примера программа очень хороша.

А вот результат работы усовершенствованной версии. Просим прощения у читателей с медленной связью за большой ( 11M) файл GIF. Он получен примерно за 80 минут.

Источником нашего вдохновения при написании этой главы послужил этот блог Пьера Линденбаума.


Глава 47. Трассировка растровых изображений		Идеи реализации