Зона кода

А давайте немного попрограммируем...

Построение изображения треугольника Серпиньского

C99Графические программы

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

Программу напишем на языке программирования C99. Для создания изображений будем использовать графическую библиотеку pgraph, так что читателю крайне желательно быть знакомым, хотя бы в общих чертах, с этой библиотекой. Нами также будут созданы 2 анимации с участием в них треугольников Серпиньского. Для построения видеороликов из статичных изображений будет задействован видеоредактор VirtualDub. Видеоролики после их создания загрузим на Ютьюб.

Статья может быть интересна новичкам в программировании, приступившим к изучению рекурсивных функций.

Итак, начнём.

О треугольнике Серпиньского и построении его изображения

Треугольник Серпиньского — это множество, конструируемое следующим образом. Берём равносторонний треугольник и, соединяя середины его сторон, разбиваем его на 4 равносторонних треугольника. Удаляем центральный треугольник, после чего с каждым из оставшихся трёх проделываем ту же самую операцию: разбиваем каждый из них на 4 треугольника и удаляем центральные. Затем таким же образом обрабатываем 9 оставшихся треугольников и повторяем данную операцию до бесконечности.

Оставшиеся после всех этих операций точки образуют линию, которая называется треугольником Серпиньского. Она играет важную роль в теории множеств, на которой мы сейчас останавливаться не будем.

Заметим, что треугольник Серпиньского состоит из трёх треугольников Серпиньского, имеющих сторону в 2 раза меньшую стороны исходного. Каждый из этих трёх треугольников также, в свою очередь, состоит из трёх треугольников Серпиньского и т. д. Такая "бесконечная повторяемость" исходного объекта его отдельными частями позволяет причислить треугольник Серпиньского к фракталам.

Изображая треугольник Серпиньского на экране компьютера, мы, по сути, рисуем границы входящих в его состав правильных треугольников, переходя от крупных к более мелким до тех пор, пока хватает разрешения экрана.

Легко заметить, что определение треугольника Серпиньского, приведённое в начале текущего раздела, можно назвать рекурсивным. Логично, что алгоритм построения его изображения также является рекурсивным. Этот алгоритм приведён ниже.

  • Шаг 1. Рисуем равносторонний треугольник. Назначаем его "текущим".
  • Шаг 2. Соединяем середины текущего треугольника.
  • Шаг 3. Если стороны полученных треугольников меньше фиксированного заранее выбранного значения, то завершаем работу.
  • Шаг 4. Поочерёдно каждый из трёх треугольников, примыкающих к центральному, назначаем "текущим" и применяем к нему данный алгоритм, начиная с шага 2.

Всё достаточно просто и очевидно. Но перед тем, как приступать к созданию программы, сделаем одно предварительное замечание. Треугольник Серпиньского, изображение которого будет строить наша программа, будет иметь основание, параллельное оси абсцисс, которое будет находиться между этой осью и противолежащей основанию вершиной. Таким образом, чтобы задать треугольник Серпиньского на холсте для рисования, нужно указать 3 числа: абсциссы концов основания и их общую ординату.

А теперь приступаем.

Структура программы

Наша программа будет состоять из файлов, входящих в библиотеку pgraph, и файла main.c, к которому эта библиотека будет подключена. В файле main.c будут определены 3 функции.

Функция create_serp_triangle() будет заниматься построением изображения треугольника Серпиньского в соответствии с переданными ей параметрами.

Рекурсивная функция create_int_triangles() будет рисовать внутренние треугольники в "пустом" треугольнике, информацию о котором она будет получать через параметры. Эта функция будет вызываться из функции create_serp_triangle(), а также из самой себя.

Главная функция программы main() будет создавать холст для рисования в виде объекта типа image, вызывать функцию create_serp_triangle() для нанесения на него изображения треугольника Серпиньского, сохранять изображение в файл и удалять уже ненужный объект.

Помимо функций файл main.c будет содержать директивы препроцессора и определение одной глобальной переменной.

Директивы препроцессора

Подключаем к файлу main.c библиотеку pgraph:

#include "pgraph.h"

Определяем макросы:

#define W 641
#define H 641
#define X1 2
#define X2 638
#define Y12 645
#define EPS 6

Смысл макросов следующий:

  • W и H — ширина и высота холста для рисования соответственно;
  • X1 и X2 — абсциссы левого и правого концов основания треугольника Серпиньского соответственно ;
  • Y12 — ордината концов основания треугольника Серпиньского;
  • EPS — предельно допустимое значение разности между абсциссами правого и левого концов верхней стороны центрального треугольника, использующееся в функции create_int_triangles().

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

Глобальная переменная img

Определим в файле main.c глобальную переменную img:

image *img;

В img будет храниться адрес изображения (холста для рисования), формируемого нашей программой. Мы сделали эту переменную глобальной, чтобы не передавать многократно её значение функции create_int_triangles() при рекурсивных вызовах.

Построение внутренних треугольников: функция create_int_triangles()

Поместим в файл main.c следующее определение рекурсивной функции create_int_triangles():

 1.void create_int_triangles(double x1, double x2, double y12, double x3, double y3)
 2.{
 3.    double p = (x1 + x2) / 2;
 4.    double q = (x1 + x3) / 2;
 5.    double r = (y12 + y3) / 2;
 6.    double s = (x2 + x3) / 2;
 7.    uint up = round(p), uq = round(q), ur = round(r), us = round(s), uy12 = round(y12);
 8.    img->cur_pnt = (point) {up, uy12};
 9.    line_to(line_to(line_to(img, us, ur), uq, ur), up, uy12);
10.    if (s - q < EPS)
11.        return;
12.    create_int_triangles(q, s, r, x3, y3);
13.    create_int_triangles(x1, p, y12, q, r);
14.    create_int_triangles(p, x2, y12, s, r);
15.}

Функция рисует на холсте для рисования, адрес которого содержится в глобальной переменной img, треугольники, находящиеся внутри исходного "пустого" треугольника (предполагается, что исходный треугольник уже нарисован на холсте). Под "внутренними" понимаются 4 треугольника, получающиеся соединением середин сторон исходного (1 центральный треугольник и 3 примыкающих к нему), а также треугольники, являющиеся внутренними по отношению к 3-м треугольникам, примыкающим к центральному (разумеется, при выполнении условия продолжения рекурсии).

Исходный треугольник задаётся координатами своих вершин, содержащихся в следующих формальных параметрах: x1 (абсцисса левого конца основания), x2 (абсцисса правого конца основания), y12 (ордината концов основания), x3 (абсцисса вершины, противолежащей основанию), y3 (ордината вершины, противолежащей основанию).

Очевидно, что значения последних двух параметров вычисляются через значения первых трёх. Однако, в момент вызова функции create_int_triangles() значения двух последних параметров уже известны вызывающей функции, и я решил обойтись без повторного их вычисления, несмотря на то, что такой подход приводит к не очень экономному расходу ёмкости стека вызовов функций.

Переходим к описанию функции. В строках 3-7 вычисляем координаты середин сторон треугольника и записываем их в переменные p (абсцисса середины основания), q (абсцисса левой боковой стороны), r (ордината середин боковых сторон), s (абсцисса правой боковой стороны). Округляем координаты середин сторон исходного треугольника до целых, подготавливая их, тем самым, к использованию в функции line_to() (стр. 7).

В качестве текущей точки изображения, адресуемого img, устанавливаем середину основания текущего треугольника (стр. 8). Посредством трёхкратного вызова функции line_to() рисуем на этом изображении внутренний центральный треугольник (стр. 9).

Если разность абсцисс концов средней линии исходного треугольника меньше значения макроса EPS, заканчиваем работу (стр. 10-11). В противном случае, используя рекурсивные вызовы функции create_int_triangles(), рисуем внутренние треугольники в трёх треугольниках, примыкающих к центральному: сначала в верхнем (стр. 12), затем в левом (стр. 13) и, наконец, в правом (стр. 14).

Построение изображения треугольника Серпиньского: функция create_serp_triangle()

Вот код функции create_serp_triangle(), который мы помещаем в файл main.c:

1.void create_serp_triangle(uint x1, uint x2, uint y12)
2.{
3.    uint x3 = (x1 + x2) / 2;
4.    uint y3 = y12 - 1 + round((x2 - x1 + 1) * 0.86602540378);
5.    img->cur_pnt = (point) {x1, y12};
6.    line_to(line_to(line_to(img, x2, y12), x3, y3), x1, y12);
7.    create_int_triangles(x1, x2, y12, x3, y3);
8.}

Функция рисует изображение треугольника Серпиньского на холсте для рисования, адресуемым глобальной переменной img. Предполагается, что основание треугольника параллельно оси абсцисс, а вершина, противолежащая основанию, расположена над ним (т. е. имеет ординату, превышающую ординату точек основания). Формальные параметры x1, x2, y12 содержат координаты вершин, полностью задающие данный треугольник: абсциссы левого и правого концов основания и их ординату соответственно.

Также предполагается, что длина основания нечётна. В этом случае абсцисса середины основания (она же — абсцисса вершины, противолежащей основанию) является целым числом. Вычисляем эту абсциссу и помещаем её в переменную x3 (стр. 3).

Как известно, высота равностороннего треугольника со стороной a равна 3½ / 2 a. Вычисляем высоту нашего треугольника, округляем её до целых и, прибавляя результат к ординате точек основания, уменьшенной на единицу, получаем округлённую до целых ординату вершины, противолежащей основанию, которую помещаем в переменную y3 (стр. 4).

Думаю, нужно пояснить наличие единиц с плюсом и минусом в правой части оператора присваивания в стр. 4. Объясняется это наличие тем, что длина отрезка, параллельного оси абсцисс (ординат), в пикселях равна, очевидно, модулю разности абсцисс (ординат) концов отрезка, увеличенному на единицу.

Итак, координаты всех вершин треугольника Серпиньского известны. Строим его "оболочку", т. е. соединяем эти три вершины замкнутой ломаной (стр. 5-6). А теперь заполняем эту "оболочку", рисуя в ней внутренние треугольники посредством вызова рекурсивной функции create_int_triangles() (стр. 7).

Управление процессом: функция main()

Вот мы и добрались до функции main(), управляющей процессом построения изображения треугольника Серпиньского. Вот её код, содержащийся в файле main.c:

1.int main()
2.{
3.    img = create_image(W, H);
4.    create_serp_triangle(X1, X2, Y12);
5.    save_to_file(img, "out.bmp");
6.    free(img);
7.    return 0;
8.}

Выделяем динамически память для хранения холста для рисования; адрес созданного объекта помещаем в глобальную переменную img (стр. 3). Рисуем на холсте треугольник Серпиньского посредством вызова функции create_serp_triangle() (стр. 4). Записываем созданное изображение в графический файл out.bmp (стр. 5). Удаляем уже ненужный нам объект типа image, содержащий это изображение (стр. 6).

Результат работы программы

Компилируем программу и запускаем её на выполнение. В итоге получаем в директории исполняемого файла графический файл out.bmp, содержащий следующее изображение:

Треугольник Серпиньского

Треугольник Серпиньского

Изображение треугольника Серпиньского успешно построено!

Создание анимации, демонстрирующей построение изображения треугольника Серпиньского

Первая анимация, которую мы изготовим, позволит наблюдать этапы построения изображения треугольника Серпиньского в том порядке, в котором они реализуются вызовами функции create_int_triangles(). Видеоролик будет являться наглядной демонстрацией работы рекурсивных вызовов и может быть интересен новичкам, изучающим рекурсию в программировании.

Принцип построения анимации будет довольно простой: после того, как функция create_int_triangles() внесёт изменение в изображение, но до того, как она начнёт троекратно вызывать себя рекурсивно, изображение будет сохранено в виде отдельного кадра анимации. Так что каждому вызову данной функции будет соответствовать один кадр.

Кроме этого, функция create_serp_triangle(), нарисовав "пустой" треугольник, перед вызовом функции create_int_triangles() сохранит его в нескольких одинаковых кадрах, так что начало анимации будет статичным. Статичным будет и конец анимации, поскольку функция main() напоследок сгенерирует несколько кадров, содержащих уже окончательное изображение треугольника Серпиньского.

Итак, приступим созданию второй версии программы посредством изменения её первой версии, которую мы написали ранее.

Начнём с изменения блока макроопределений. В новой версии программы он будет выглядеть так:

#define W 720
#define H 720
#define X1 2
#define X2 718
#define Y12 50
#define EPS 6

Мы собираемся загрузить наш ролик на Ютьюб, и поэтому ориентируемся на одно из стандартных разрешений, поддерживаемых этой платформой — 1280 на 720. Однако для экономии размера файла создадим ролик с размером кадра 720 на 720, переложив на плечи Ютьюба добавление чёрных прямоугольников по обеим сторонам кадра.

Именно использованием новых размеров изображения и объясняются изменения значений некоторых макросов в приведённом выше блоке.

Под объявлением глобальной переменной img разместим следующее определение функции save():

1.void save()
2.{
3.    static int count = 0;
4.    char filename[17];
5.    sprintf(filename, "results\\%04d.bmp", ++count);
6.    save_to_file(img, filename);
7.}

Функция сохраняет изображение, содержащееся в объекте, адресуемом img, в графическом файле, помещаемом в каталог results, находящемся в директории исполняемого файла. При первом вызове функции изображение сохраняется в файле 0001.bmp, при втором — в файле 0002.bmp и т. д. Количество файлов, созданных функцией, являющееся частью имени файла, будет храниться в переменной-счётчике count. Т. к. значения счётчика должны сохраняться между вызовами функции, объявим эту переменную статической (стр. 3).

Файлы, создаваемые функцией save(), будут содержать кадры будущей анимации. В дальнейшем, для упрощения, такие файлы иногда будем называть просто "кадрами".

Создадим массив filename для хранения пути к файлу (стр. 4). Сгенерируем путь к файлу относительно директории исполняемого файла и запишем его в данный массив, попутно увеличив на единицу значение счётчика (стр. 5). Наконец, создадим файл, путь к которому содержится в filename, содержащий изображение из объекта, адресуемого img (стр. 6).

Изменим функцию create_int_triangles(), новая версия которой теперь будет выглядеть так:

 1.void create_int_triangles(double x1, double x2, double y12, double x3, double y3)
 2.{
 3.    double p = (x1 + x2) / 2;
 4.    double q = (x1 + x3) / 2;
 5.    double r = (y12 + y3) / 2;
 6.    double s = (x2 + x3) / 2;
 7.    uint up = round(p), uq = round(q), ur = round(r), us = round(s), uy12 = round(y12);
 8.    img->cur_pnt = (point) {up, uy12};
 9.    line_to(line_to(line_to(img, us, ur), uq, ur), up, uy12);
10.    save();
11.    if (s - q < EPS)
12.        return;
13.    create_int_triangles(q, s, r, x3, y3);
14.    create_int_triangles(x1, p, y12, q, r);
15.    create_int_triangles(p, x2, y12, s, r);
16.}

Единственное отличие новой версии функции от предыдущей состоит в появлении вызова функции save() сразу после отрисовки границ внутреннего центрального треугольника (см. стр. 10).

А вот и новая версия функции create_serp_triangle():

 1.void create_serp_triangle(uint x1, uint x2, uint y12)
 2.{
 3.    uint x3 = (x1 + x2) / 2;
 4.    uint y3 = y12 - 1 + round((x2 - x1 + 1) * 0.86602540378);
 5.    img->cur_pnt = (point) {x1, y12};
 6.    line_to(line_to(line_to(img, x2, y12), x3, y3), x1, y12);
 7.    for (int i = 0; i < 25; i++)
 8.        save();
 9.    create_int_triangles(x1, x2, y12, x3, y3);
10.}

После того, как "пустая заготовка" треугольника Серпиньского (т. е. обычный равносторонний треугольник) создана, мы сохраняем содержащее её изображение в 25-ти одинаковых кадрах (стр. 7-8). Таким образом, при частоте кадров 25кадр./c. эта "заготовка" будет демонстрироваться зрителю в течение одной секунды.

Больше никаких изменений в функцию create_serp_triangle() мы не вносим.

Остаётся лишь привести новую версию функции main(), что мы и делаем:

1.int main()
2.{
3.    img = create_image(W, H);
4.    create_serp_triangle(X1, X2, Y12);
5.    for (int i = 0; i < 24; i++)
6.        save();
7.    free(img);
8.    return 0;
9.}

Мы лишь заменили инструкцию, сохраняющую изображение в файле out.bmp, циклом, в котором в 24-х одинаковых кадрах сохраняются итоговые изображения треугольника Серпиньского (стр. 5-6). Всего таких кадров будет 25 (первый из них будет сгенерирован последним вызовом функции create_int_triangles()). Так что окончательный вид треугольника Серпиньского будет демонстрироваться зрителю ролика в самом его конце в течение одной секунды.

Компилируем программу, создаём в директории исполняемого файла каталог results, после чего запускаем программу на выполнение, в результате которого в данном каталоге обнаруживаются 1142 файла. Из них 49 сгенерированы функциями create_serp_triangle() и main(), а остальные — функцией create_int_triangles(), из чего можно сделать вывод о том, что функция create_int_triangles() вызывалась 1093 раза.

С помощью видеоредактора VirtualDub создаём из отдельных кадров видеоролик, имеющий частоту кадров 25кадр./c., используя для кодирования видеопотока кодек Huffyuv, сжимающий без потерь. О том, как это делать, можно узнать из этой и этой статей.

В итоге получаем видеоролик в AVI-контейнере размером 427 МБ. Загружаем его на Ютьюб. Вот что получаем в итоге:

Продолжительность видеоролика — чуть больше 45с. Читатель, при желании, сможет сократить время его просмотра вдвое, если установит в настройках двойную скорость воспроизведения.

Анимация: приближение к вершине треугольника Серпиньского

Создадим анимацию, имитирующую приближение к вершине (падение в вершину) треугольника Серпиньского. По сути, мы просто будем от кадра к кадру увеличивать масштаб картинки таким образом, чтобы одна из вершин треугольника Серпиньского (левый конец основания) всегда оставалась неподвижной.

Наша анимация будет наглядно демонстрировать фрактальную (самоповторяющуюся) структуру треугольника Серпиньского. В частности, она покажет, что любой внутренний треугольник, принадлежащий исходному треугольнику Серпиньского и имеющий с ним общую вершину, также является треугольником Серпиньского.

Первый кадр будет содержать "маленькое" изображение треугольника Серпиньского, занимающего лишь небольшую его часть. Но, переходя от кадра кадра, мы будем "растягивать" изображение, увеличивая длину основания. Левый конец основания будет неподвижен, а правый (в дальнейшем будем назвать его, для краткости, "правой вершиной") будет "двигаться" вправо с постоянной скоростью, т. е. его абсцисса на каждом следующем кадре будет превышать абсциссу на предыдущем на фиксированное число.

Разумеется, в результате такого увеличения изображение треугольника рано или поздно займёт весь кадр и дальше ему "расти" будет некуда. Для предотвращения такой ситуации поступим следующим образом. Как только абсцисса правой вершины достигнет некоторого критического значения, так сразу же изменим её значение: присвоим ей абсциссу середины основания. И только после этого построим кадр.

Такой подход, очевидно, приведёт к тому, что процесс зациклится. Каждый раз, достигая какого-то определённого размера, изображение треугольник Серпиньского будет скачком уменьшаться, после чего снова начинать "расти".

Но такие резкие уменьшения размеров треугольника Серпиньского мы скроем от глаз зрителя. Их исходного кадра мы будем каждый раз вырезать некоторый прямоугольный фрагмент и сохранять его в виде графического файла. Размеры этих фрагментов будут таковы, что резкое уменьшение размера изображения треугольника (назовём его "сбросом размера") никак не будет на них отражаться.

Именно из сохранённых кадров, т. е. фрагментов исходных изображений, и будет генерироваться видеоролик. Зрителю будет казаться, что изображение треугольника Серпиньского постоянно растёт, а зрителю демонстрируется всё меньшая и меньшая его часть.

Как и в предыдущем случае, кадр видеоролика будет квадратным со стороной 720 пикселей. Левая нижняя вершина фрагмента будет всегда совпадать с левой нижней вершиной исходного изображения, а левый конец основания треугольника будет близок к началу координат. Несложно вычислить примерные размеры исходных изображений. Исходить будем из условия: в момент сброса размера вершина треугольника, противолежащая основанию, должна находиться вне фрагмента, т. е. высота треугольника должна превышать 720.

Таким образом, примерная высота треугольника 720, значит, его примерное основание — 830. Но запас по основанию должен быть близок к двукратному, так что ширина изображения — около 1660, а его высота должна приближённо совпадать с высотой треугольника с основанием 1660. Получаем приблизительное значение высоты изображения, равное 1440.

Полученные размеры 1660 на 1440 — грубые, возьмём их лишь в качестве ориентира. В любом случае, нужно будет их увеличить, чтобы был запас.

Начнём переделывать вторую версию программы, чтобы получить третью.

Вот как теперь будет выглядеть блок макросов:

#define F 3000
#define W 1675
#define H 1450
#define A 720
#define X1 2
#define X2_MIN 10
#define X2_MAX 1682
#define DX 8
#define X3 842
#define Y12 2
#define EPS 4

Теперь будем генерировать изображения шириной 1675 пикселей и высотой 1450. Сторона кадра, имеющего квадратную форму (макрос A) — 720 пикселей. Левый конец основания теперь будет иметь координаты (2, 2).

Минимальное значение абсциссы правой вершины составит 10 (макрос X2_MIN), а максимальное (макрос X2_MAX) — 1682. Шаг увеличения абсциссы (макрос DX) — 8. Отметим, что треугольник с максимальным значением абсциссы правой вершины никогда построен не будет, поскольку, как только значение X2_MAX будет достигнуто, так сразу же произойдёт сброс абсциссы до значения макроса X3 (т. е. до 842), и треугольник будет построен уже для нового значения абсциссы.

Чтобы программа работала корректно, нужно, чтобы значения макросов X1, X2_MIN, X2_MAX, X3, DX были согласованы между собой. А именно: X3 должно являться средним арифметическим X1 и X2_MAX, а разности X3 - X2_MIN и X2_MAX - X2_MIN должны делиться на DX.

Наш видеоролик будет иметь продолжаться 2 минуты, так что состоять он будет из 3000 кадров (макрос F). Эксперимент показал, что лучше воспринимается видеоролик, кадры которого содержат более мелкие детали, чем статичное изображение, которое мы построили ранее, так что значение макроса EPS было уменьшено с 6 до 4.

Теперь мы будем записывать в файлы не изображения, хранящиеся в объекте, адресуемом глобальным указателем img, а их фрагменты. Адрес объекта, содержащего записываемое изображение, будем каждый раз передавать функции save() через формальный параметр img. Так что заголовок функции изменится и будет выглядеть так:

void save(image *img)

Тело функции останется прежним, поэтому приводить его не будем.

Из функций create_int_triangles() и create_serp_triangle() уберём фрагменты, отвечающие за запись изображений в файл посредством вызовов функции save(). Таким образом, эти функции полностью совпадут с функциями из первой версии программы, так что демонстрировать их код не будем.

Наконец, переходим к функции main(). Вот её новый код:

 1.int main()
 2.{
 3.    img = create_image(W, H);
 4.    image *img2 = create_image(A, A);
 5.    for (uint i = 0, x = X2_MIN; i < F; i++, x += DX)
 6.    {
 7.        if (x == X2_MAX)
 8.            x = X3;
 9.        fill_all(img, WHITE);
10.        create_serp_triangle(X1, x, Y12);
11.        copy_rect(img, 0, 0, A, A, img2, 0, 0);
12.        save(img2);
13.    }
14.    free(img);
15.    free(img2);
16.    return 0;
17.}

Создаём объект для хранения исходных изображений и присваиваем его адрес глобальной переменной img (стр. 3). Создаём объект для хранения их фрагментов и присваиваем его адрес локальной переменной img2 (стр. 4).

На каждой итерации цикла for (стр. 5-13) генерируем отдельный кадр анимации. В переменной x, принимающей начальное значение X2_MIN (см. стр. 5), в ходе цикла хранится текущее значение абсциссы правой вершины треугольника Серпиньского. Если х достигает максимального значения X2_MAX, то выполняем сброс размера (стр. 7-8).

Заливаем изображение, адресуемое указателем img, белым цветом (стр. 9) и рисуем на нём треугольник Серпиньского (стр. 10). Копируем фрагмент этого изображения в объект, адресуемый img2 (стр. 11), и сохраняем этот фрагмент в графическом файле (стр. 12).

По окончании цикла удаляем объекты, адресуемые указателями img и img2 (стр. 14, 15).

Программа готова! Компилируем её и запускаем на выполнение. В результате получаем 3000 графических файлов в директории results. С помощью VirtualDub создаём из них видеоролик продолжительностью 2 минуты размером 1,1 ГБ, который заливаем на Ютьюб. Результирующий ютьюбовский ролик можете просмотреть прямое сейчас. Не забывайте о возможности удвоения скорости воспроизведения.

Можно заметить, что скорость "увеличения" треугольника Серпиньского непостоянна. Действительно, здесь применима аналогия с резинкой, один конец которой закреплён, а другой движется с постоянной скоростью в направлении от первого: скорость точки резинки пропорциональна расстоянию от неё до закреплённого конца в начальный момент времени. В частности, скорость середины резинки в 2 раза меньше скорости движущегося конца.

В нашем случае роль резинки выполняет основание треугольника, а скорость произвольной точки треугольника равна скорости её проекции на основание. По мере того, как часть треугольника скрывается за кадром, в кадре остаются точки, движущиеся всё с меньшими и меньшими скоростями. Из-за этого возникает иллюзия замедления "увеличения" треугольника Серпиньского.

А вот в момент сброса размера точка, являвшаяся ранее серединой основания, становится правой вершиной треугольника. После того, как треугольник с этой точкой в качестве правой вершины отрисован, на каждом из следующих шагов её абсцисса получает те же приращения, что ранее получала абсцисса "старой" правой вершины. Таким образом, скорость нашей точки, а значит, и скорости всех точек нашего треугольника (уже нового, являющегося частью "старого") возрастают вдвое. Такие резкие скачки скорости на видео хорошо заметны.

Таким образом, зрителю сначала кажется, что скорость "разрастания" треугольника уменьшается, а потом вдруг резко увеличивается, после чего этот процесс повторяется снова, снова и снова.

Заключение

Ну что ж, все поставленные задачи успешно решены. Изначально я опасался, что рекурсивный подход в написании программ может не сработать, поскольку количество рекурсивных вызовов в программах (особенно, в 3-ей) достаточно велико. А большое количество рекурсивных вызовов может привести к переполнению стека вызовов функций.

Так что я был готов создавать нерекурсивные варианты программ, основанные на использовании стека. К счастью, никаких переполнений не происходило, и к запасным вариантам решений, более, кстати сказать, громоздким, чем рекурсивные, прибегать не пришлось.

Все 3 варианта программ можно скачать по ссылке ниже.

Скачать исходный код