Генератор треугольника Серпинского

Генератор треугольника Серпинского строит самый известный фрактал в компьютерных науках и занимательной математике — для любой глубины, из любого внешнего треугольника, используя либо детерминированный алгоритм рекурсивного разбиения, либо удивительное случайное блуждание игры в хаос. Режим параллельного сравнения отображает оба метода одновременно, позволяя убедиться, что случайность и рекурсия сходятся к абсолютно одинаковой форме. Инструмент показывает количество листьев, точную оставшуюся площадь и размерность Хаусдорфа (log 3 / log 2 ≈ 1.5849625), а также экспортирует чистый SVG, подходящий для слайдов, рабочих листов или лазерной резки.

Как строится треугольник Серпинского — пошаговое руководство

Чем отличается этот генератор треугольника Серпинского

Что такое треугольник Серпинского?

Треугольник Серпинского (также называемый салфеткой или ковром Серпинского) — это самоподобный фрактал, впервые формально описанный польским математиком Вацлавом Серпинским в 1915 году. Он строится путем рекурсивного удаления центрального перевернутого подтреугольника из каждого остающегося треугольника, в результате чего по углам остаются три меньшие копии оригинала. Этот процесс повторяется до бесконечности; предельное множество имеет меру ноль (вообще не имеет площади), но содержит несчетное множество точек и имеет нецелую фрактальную размерность log 3 / log 2 ≈ 1.5849625, что означает, что оно «толще» одномерной кривой, но «тоньше» двумерной области.

Игра в хаос: порядок из случайности

Игра в хаос, популяризированная Майклом Барнсли в его книге 1988 года Фракталы повсюду (Fractals Everywhere), является одним из самых поразительных результатов в теории динамических систем. Выберите любую начальную точку внутри треугольника и следуйте этому правилу: выберите одну из трех вершин случайно и равновероятно, переместитесь ровно на половину расстояния от вашей текущей точки к этой вершине и поставьте точку. Повторите тысячи раз. После короткого начального периода каждая последующая точка с вероятностью 1 оказывается на треугольнике Серпинского — фрактал является единственным аттрактором этого случайного блужания. Детерминированное рекурсивное разбиение и случайная игра в хаос — это два примера системы итерируемых функций (IFS) с одними и теми же тремя отображениями середины; по теореме о сжимающих отображениях каждая IFS со строгими сжатиями имеет единственный непустой компактный аттрактор, к которому сходится любая рандомизированная траектория.

Справочник по глубине рекурсии

Где встречается треугольник Серпинского

• Треугольник Паскаля по модулю 2: окрасьте каждую ячейку треугольника Паскаля в черный цвет, если она нечетная, и в белый, если четная. Черные ячейки в точности образуют треугольник Серпинского — удивительный мост между комбинаторикой и фрактальной геометрией.
• Клеточный автомат Правило 90: одномерный клеточный автомат «Правило 90» Стивена Вольфрама, запущенный из одной черной ячейки, генерирует треугольник Серпинского строку за строкой.
• Фрактальные антенны: монопольные и дипольные антенны Серпинского используют самоподобие для достижения многодиапазонного резонанса — одна антенна может охватывать множество частотных диапазонов. Они используются в современных мобильных телефонах и устройствах Wi-Fi.
• Обучение компьютерным наукам: канонический пример для рекурсии, принципа «разделяй и властвуй», IFS и теории размерности. Он также отлично подходит в качестве цели для модульного тестирования графических библиотек.
• Генеративное искусство и дизайн: текстиль, логотипы, костеры с лазерной гравировкой, плакаты музыкальных фестивалей — сочетание математической глубины и визуальной простоты фрактала делает его бесконечным источником для ремиксов.
• Граф состояний Ханойской башни: граф состояний головоломки «Ханойская башня» с N дисками представляет собой в точности граф Серпинского глубины N — та же структура под другой оболочкой.

Треугольник Серпинского против треугольника Паскаля: удивительное тождество

Выпишите треугольник Паскаля на много строк, затем окрасьте ячейки с нечетными биномиальными коэффициентами в темный цвет, а с четными — в светлый. Получится идеальный треугольник Серпинского. Причина кроется в теореме Куммера о биномиальных коэффициентах по модулю простого числа: C(n, k) mod 2 равно 1 тогда и только тогда, когда двоичное представление числа k побитово меньше или равно двоичному представлению числа n. Рекурсивно это в точности воссоздает правило Серпинского — три копии сверху, центральная отсутствует, — и предельной картиной является фрактал. Переключите этот генератор в «Макет треугольника Паскаля», чтобы увидеть эту связь в соответствующей ориентации.

Распространенные заблуждения

• «Треугольник Серпинского имеет нулевую площадь». Верно — но только в бесконечном пределе. При любой конечной глубине N листья все еще заполняют (3/4)N внешней площади. На глубине 9 это по-прежнему около 7.5%, что вполне заметно.
• «Для начала нужен равносторонний треугольник». Ложно. Рекурсия работает на любом треугольнике (прямоугольном, тупоугольном, вырожденном — главное, чтобы точки не лежали на одной прямой). Форма фрактала сохраняется при любом аффинном преобразовании. Измените внешние формы в этом инструменте, чтобы убедиться в этом самостоятельно.
• «Для игры в хаос нужны особые случайные числа». Нет — достаточно равномерной случайности среди трех целых чисел. Подойдет также любая начальная точка (после короткого начального периода, чтобы «забыть» старт).
• «Фрактальная размерность — это просто модное название для целого числа». Нет — размерность треугольника Серпинского действительно находится между 1 и 2. Не существует целой размерности, которая могла бы описать его масштабирование.

Часто задаваемые вопросы