Однажды мой коллега для кругозора заинтересовался темой построения треугольника Серпинского с помощью «игры в хаос». И познакомил с ней меня. Показал видео. Потом он сказал: «Ты же учишься программировать – попробуй написать программу, в которой это будет реализовано».

Я не специалист в этой области, могу ошибаться в терминах или не очень правильно их интерпретировать и применять.

Про этот треугольник

Треугольник Серпинского - это вот такая штука:

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

Игра в хаос

Способ его построения с помощью игры в хаос заключается в следующем (здесь рассказывается с математикой). Берётся равносторонний треугольник (пусть углы будут A, B и C). Внутри произвольным образом выбирается начальная точка. Бросается игральная кость. Будем говорить для определённости, что выпадение того или иного числа на кости соответствует следующим результатам:

• "1" или "4" - это А;

• "2" или "5" - это В;

• "3" или "6" - это С.

Разумеется, это условно. Важно лишь, чтобы А, В и С имели одинаковую вероятность выпадения.

Допустим, в результате первого броска выпала А. Тогда вершина А мысленно соединяется с начальной точкой отрезком, а на середине этого отрезка ставится точка. Пусть теперь она будет начальной.

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

После достаточно большого количества повторений из точек получим изображение того самого треугольника Серпинского. В теории, по крайней мере.

Ты же учишься программировать...

Я не работаю в сфере IT. Учусь программировать на C++ по учебникам. Но скорее просто для того, чтобы заставлять свою голову работать. Полагаю, сейчас, чтобы податься в IT нужно учиться владеть каким-то более высокоуровневым инструментом или чему-то более прикладному. Зерокодингу, например. Так что для меня это что-то вроде хобби или аналога разгадывания сканвордов.

Мой коллега знает об этом и не видит ничего плохого в том, чтобы подкинуть мне практику. На тот момент всё, что я умел, это выводить что-то в консоли. Я взял задачку себе на заметку. Со временем я пришёл к тому, как реализовать это в виде приложения для Windows. В итоге я написал эту программу с использованием WinAPI. В этом мне помогла книга Юрия Щупак «Win32 API. Эффективная разработка приложений», 2007. Это было довольно занятно.

Интерфейс приложения

Есть несколько рабочих версий программы. Последняя выглядит так:

На зелёную рамку не обращайте внимания. Я уже не помню точно, но, скорее всего, так я отрабатывал использование геометрических примитивов и разные цвета.

Ну так вот, всё просто. Пожалуй, прежде пройдусь по control’ам интерфейса.

• Как видите, тут есть меню. Правда, не очень функциональное. «Выход» реально это и делает. А вот всё остальное просто выводит информационное диалоговое окно, у которого надо нажать «ОК» или закрыть:

А вот пункту «Параметры» в конструкторе меню его свойству «Всплывающее окно» присвоен «false», поэтому он не является раскрывающимся подменю следующего уровня:

Почему-то мне кажется, будто от горячих клавиш там лишь одно название. Пожалуй, не буду возвращаться и проверять это. Но знайте, что тему эту я прошёл и при желании могу реализовать. По крайней мере, знаю, где про это написано.

Так я осваивал создание меню.

• Поле с контролами слева – это Modeless Dialog Box, или же диалоговое окно, которое не забирает себе монопольно фокус приложения, а вполне себе сосуществует с ним.

• Кнопка "Do it!" выполняет установленное количество итераций с бросками игральной кости и рисованием точек внутри треугольника. Но делает она это только, если на рабочем поле имеются четыре точки – три вершины и начальная точка. А иначе:

Итерация – это:

1. генерация рандомного числа от 1 до 6;

2. на основании этого расчёт положения следующей точки;

3. её рисование.

Если для кого-то это важно, то перед rand() идёт srand(time(NULL)).

• "Refresh" это "Clear".

• Следующий элемент интерфейса – Edit Control для ввода количества выполняемых за одно нажатие «Do it!» итераций:

При запуске программы эта величина по умолчанию равна единице.

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

Уже много позже я научился обходиться без кнопки для ввода нового значения. Реализовал я это уже в другой тренировочной программе.

• Combo Box позволяет выбрать радиус точки, рисуемой «Do it!». Под точкой подразумевается круг небольшого радиуса.

• Про ввод количества углов позже.

• Внизу есть Status Bar, где видна дежурная информация:

1. сколько итераций при нажатии «Do it!» происходит;

2. текущий радиус точки;

3. количество уже нарисованных точек;

4. какой n-угольник будет вначале (опять же, про это позже).

Работа приложения

Вначале я ввожу количество точек, рисуемых одним нажатием «Do it!», ну скажем, 10000. Затем делается три клика на рабочем поле, появляются вершины треугольника, которые автоматически последовательно соединяются линиями. Ещё один клик – создаёт начальную точку. Дальше нажимаем «Do it!». И Вуа ля!

Если ещё несколько раз понажимать, то линии станут чётче:

Когда я впервые в рабочем виде реализовал эту программу, я, честно говоря, был в шоке. Шеогоратова математика!

Вот ещё несколько реализаций:

Как я ранее писал, действительно, треугольник может быть каким-угодно. А ещё, если поставить начальную точку вне треугольника, то это ни на что не повлияет. Оно и логично! Потому что рано или поздно точка попадёт внутрь треугольника, а там уже по накатанной.

Итак, задача решена!

Про количество углов фигуры

Мне стало интересно, что же будет с n-угольником, где n > 3. Я добавил кое-какие изменения в код программы и реализовал задачу. В начальных версиях этого функционала не было.

Собственно, вводим в соответствующий Edit Control количество углов и смотрим. Как мне показалось, разные угольники ведут себя по-разному.

Для очень неправильного четырёхугольника выходит что-то такое:

Чем «параллельнее» несмежные стороны, тем однороднее получается распределение точек:

В центре можно разглядеть степень «ошибки параллельности».

И ещё кое-что. Если две вершины поставить достаточно близко друг к другу, получается эффект треугольника, но в той стороне, где находятся эти две близкие друг к другу вершины, плотность точек больше. Довольно логично.

С пентагоном и гексагоном тоже, вроде как, можно выделить какие-то закономерности:

А эффект треугольника на них тоже распространяется:

Наращивая дальше количество углов ничего особо интересного я уже не нашёл. Думал, может с октагоном будет что-то интересное, но нет.

Надеюсь, кому-то было интересно. Всем добра!