Апериодические замощения и место P3 среди них
Начнём с определения. Замощение — это набор фигур, который покрывает плоскость без пропусков и наложений. Фигуры, из которых складывается узор, называются прототипами. Пример простейшего замощения — бесконечная шахматная доска: её единственный прототип — квадрат.
Замощение называется периодическим, если его можно сдвинуть так, что рисунок совпадёт с исходным. Шахматная доска периодична: сдвиг на одну клетку вправо возвращает тот же узор. Если ни один сдвиг не даёт точного совпадения, замощение называют апериодическим.
Роджер Пенроуз в 1970-х открыл первые апериодические замощения, обходящиеся всего двумя прототипами. Он предложил три варианта — P1, P2 и P3. В P1 используется четыре прототипа, а P2 (змей и дротик) и P3 — только два. В P3 прототипы — ромбы.
Однако сгенерировать P3 напрямую из ромбов неудобно. Вместо этого применяют набор из четырёх правил подразбиения, где каждый прототип — треугольник определённого цвета. Правило показывает, как заменить один треугольник набором меньших. Запуская правила рекурсивно, вы получаете всё более детальное замощение.
Эти треугольники названы треугольниками Робинсона в честь Рафаэля Робинсона, который открыл их вскоре после публикации Пенроуза. Подразбиение всегда порождает треугольники парами: острые соединяются с острыми, тупые — с тупыми, основание к основанию (исключение — плитки по краю). Сшив такие пары, вы и получаете ромбы P3: красные ромбы — это пары острых треугольников, синие — пары тупых.
Треугольники Робинсона и парная структура
Откуда в P3 берутся ромбы, если правила подразделения оперируют треугольниками? Ответ — в парах, и это ключ ко всему алгоритму.
Прототипы, на которых работают правила подразделения, называются треугольниками Робинсона — в честь Рафаэля Робинсона, открывшего их вскоре после того, как Пенроуз предложил P2 и P3. Треугольники бывают двух видов: острые и тупые. Каждый из них при подразделении распадается на несколько меньших треугольников, но есть закономерность: треугольники всегда возникают парами, соединёнными по основанию.
Острые треугольники образуют пары острых, тупые — пары тупых. Исключение — треугольники по краю области: там пара может оказаться неполной, потому что сосед за границей просто отсутствует. Но в глубине картина стабильна.
После завершения подразделения пары сшиваются в ромбы. Пара острых треугольников даёт красный ромб, пара тупых — синий. Именно эти красные и синие ромбы вы видите в готовом замощении P3.
Почему пары гарантированы? Доказательство строится структурной индукцией по правилам подразделения: каждое правило применяется к треугольнику определённого типа, и в результате всегда получается набор, который на следующем шаге снова распадётся на пары нужного вида. Индукция здесь не формальность — она объясняет, почему алгоритм вообще имеет право называться алгоритмом генерации P3, а не просто рисованием треугольников.
Практический смысл такой: вы можете генерировать замощение на уровне треугольников, не беспокоясь о ромбах, — они соберутся сами. Достаточно корректно реализовать четыре правила подразделения, и структура пар возникнет автоматически.
От геометрии к символам: термы и правила подразделения
Геометрический чертёж с треугольниками компьютер выполнить не может — ему нужен текст. Формализм, который превращает картинку подразделения в исполняемые правила, называется переписыванием термов: у нас есть выражения (термы) и правила, по которым одно выражение заменяется другим.
Каждый треугольник Робинсона однозначно задаётся своим цветом и тремя вершинами. Обозначим четыре цвета буквами C, D, X, Y в том порядке, в котором они приведены в правилах. Тогда треугольник цвета C с вершинами p, q, r записывается как терм C(p, q, r). Символы C, D, X, Y называются функциональными символами: у каждого фиксированное число аргументов (арность). Буквы p, q, r — переменные, они пробегают произвольные термы. Левая часть правила — это образец; правило срабатывает, как только найдётся подстановка переменных, при которой образец совпал с фрагментом терма.
Осталось объяснить, как в терме появляются новые вершины. Каждое правило подразделения порождает как минимум одну новую точку; на чертежах они помечены S и T. У треугольников Робинсона есть удобное геометрическое свойство: точки S и T всегда лежат на расстоянии 1/φ вдоль ребра, где φ — золотое отношение. Оно возникает здесь потому, что золотое отношение равно отношению диагонали правильного пятиугольника к его стороне, а вся плитка P3 построена на пятикратной симметрии. Введём инфиксный символ ⇒: запись p ⇒ q означает точку, до которой дошли от p к q, пройдя 1/φ всего расстояния.
Теперь четыре правила подразделения читаются как правила переписывания:
C(p, q, r) → C(q, r ⇒ q, p) × Y(r, p, r ⇒ q)
D(p, q, r) → D(r ⇒ p, p, q) × X(q, r, r ⇒ p)
X(p, q, r) → C(r, p ⇒ r, p ⇒ q) × X(q, r, p ⇒ q) × Y(p, p ⇒ q, p ⇒ r)
Y(p, q, r) → D(q ⇒ r, r, q ⇒ p) × X(q ⇒ p, q, q ⇒ r) × Y(r, p, q ⇒ p)Символ × — тоже функциональный символ, только записанный инфиксно; строго говоря, для результата из двух треугольников и из трёх понадобились бы разные символы умножения, отличающиеся арностью. Правые части показывают, что происходит при одном шаге: острый треугольник C распадается на два меньших — C и Y, тупой D — на D и X, а X и Y дают по три потомка.
Проверить правила можно рекурсивной функцией generateP3(type, p, q, r, depth), которую автор статьи использовал для отрисовки картинок. Внутри неё для ветвей C, D, X, Y вычисляются середины сторон (midpoint) и рекурсивно вызывается та же функция с уменьшенной глубиной — по сути, те же самые правила переписывания, только в виде кода.
Точка ⇒: золотое сечение и шаг подразделения
Откуда в правилах подразделения берётся множитель 1/φ? Дело в геометрии: новые вершины S и T всегда лежат на 1/φ пути вдоль ребра — здесь φ — золотое сечение. Это не совпадение: отношение диагонали правильного пятиугольника к его стороне равно φ, а все мозаики Пенроуза построены на пятикратной симметрии. Именно поэтому в формулах появляется именно это число.
Обозначение p ⇒ q читается буквально: точка, до которой нужно пройти 1/φ расстояния от p к q. Это сокращение для линейной интерполяции: p + φ⁻¹(q − p). Если координаты вершин выбраны так, что все они выражаются целочисленными коэффициентами по базису {ζ³, ζ², ζ, 1}, где ζ = e^(πi/5), то операция p ⇒ q не выходит за пределы этого базиса — она сводится к сложению, вычитанию и умножению, замкнутым в этом пространстве.
Запишем правила переписывания для каждого типа треугольника. Слева — образец, справа — результат подразделения:
C(p, q, r) → C(q, r ⇒ q, p) × Y(r, p, r ⇒ q)D(p, q, r) → D(r ⇒ p, p, q) × X(q, r, r ⇒ p)X(p, q, r) → C(r, p ⇒ r, p ⇒ q) × X(q, r, p ⇒ q) × Y(p, p ⇒ q, p ⇒ r)Y(p, q, r) → D(q ⇒ r, r, q ⇒ p) × X(q ⇒ p, q, q ⇒ r) × Y(r, p, q ⇒ p)
Символ × здесь — функция-произведение: она соединяет два или три подтреугольника в один результат. Для строгости пришлось бы ввести отдельные функциональные символы для арности 2 и 3, но в инфиксной записи читается проще.
Как это выглядит в коде? Рекурсивная функция generateP3(type, p, q, r, depth) на каждом шаге вычисляет const s = midpoint(r, q) и создаёт два или три дочерних треугольника с уменьшенной глубиной. Функция midpoint реализует ровно ту же интерполяцию: sum(p, shorten(side)), где shorten — умножение на phiInverse. Всё, что было геометрическим чертежом, теперь стало текстовыми правилами и рекурсивным вызовом.
Рекурсивная генерация: функция generateP3
Функция generateP3 принимает пять аргументов: type, p, q, r и depth. Первые четыре задают текущий треугольник — его цвет и три вершины, — а depth управляет числом раундов подразделения. Каждый вызов строит объект triangle с полями type, depth, p, q, r. Пока depth > 0, выполняется switch по type; при depth == 0 функция просто возвращает готовый треугольник, то есть служит базой рекурсии.
Дальше всё решает цвет. Ветка "C" вычисляет одну новую точку s = midpoint(r, q) и порождает два подтреугольника: Y от (r, p, s) и C от (q, s, p). Обратите внимание на порядок вершин — он не произвольный: от него зависит, какая вершина станет «началом», а какая «концом» при следующем разбиении.
Ветка "D" устроена похоже: s = midpoint(r, p), затем X от (q, r, s) и D от (s, p, q). Симметрия между C и D здесь почти зеркальная, но вершины переставлены так, чтобы сохранить ориентацию фигуры.
Острые треугольники "X" и "Y" дают по три потомка. Ветка "X" вводит две точки d = midpoint(p, q) и e = midpoint(p, r), после чего вызывает X от (q, r, d), Y от (p, d, e) и C от (r, e, d). Ветка "Y" симметрична: d = midpoint(q, p), e = midpoint(q, r), и на выходе — X от (d, q, e), Y от (r, p, d) и D от (e, r, d). Каждый рекурсивный вызов уменьшает depth на единицу, поэтому дерево вызовов гарантированно конечно.
Все четыре ветки опираются на одну операцию — midpoint. Именно она делает код компактным: правило подразделения для каждого цвета сводится к паре-тройке вызовов с переставленными аргументами. Если в switch приходит неизвестное значение, срабатывает default — сообщение "Unexpected color." в консоль. Это полезная страховка: опечатка в строке цвета не приведёт к тихому пропуску ветки, а сразу даст знать о себе.
Наконец, результат работы — не готовая мозаика, а дерево треугольников. Каждый узел хранит ссылки на потомков в именованных полях (triangle.c, triangle.x, triangle.d, triangle.y) плюс собственные координаты. Такое представление удобно и для отрисовки, и для обхода: вы всегда можете спуститься на нужный уровень depth и увидеть, как выглядит подразделение на конкретном шаге.
Координаты в поле Q(ζ): линейная алгебра для P3
Точки P3-тайлинга можно хранить как четвёрки целых чисел, а не как пары вещественных. Это избавляет от проблемы сравнения координат: два узла, математически совпадающие, не разойдутся из-за накопленной ошибки округления.
Базисом служат четыре вектора: ζ³, ζ², ζ и 1, где ζ = e^(πi/5). Любая точка тайлинга записывается как линейная комбинация этих векторов с целыми коэффициентами — то есть в виде объекта {a, b, c, d}, где коэффициент a отвечает за ζ³, b — за ζ², c — за ζ, d — за единицу. Например, начало координат — это {0, 0, 0, 0}, а единичный вектор вдоль Q — {0, 0, 0, 1}.
Доказательство замкнутости такого представления строится по структурной индукции на правилах подразделения. Ключевые величины уже выражаются через базис:
- φ = 1 + ζ² − ζ³, то есть
{a: -1, b: 1, c: 0, d: 1}; - 1/φ = ζ² − ζ³, то есть
{a: -1, b: 1, c: 0, d: 0}; - стартовая вершина
Rравна ζ/φ.
Сложение и вычитание работают покомпонентно. Умножение сложнее: при раскрытии скобок получаются слагаемые вплоть до шестой степени, и их нужно понижать обратно до третьей. Помогает тождество, вытекающее из обращения в нуль суммы вершин правильного пятиугольника (чередующихся вершин десятиугольника радиуса один):
ζ⁴ = ζ³ − ζ² + ζ − 1
Оно связано с циклотомическими многочленами и позволяет свести произведение к комбинации тех же четырёх базисных векторов.
Поскольку midpoint — это линейная интерполяция p ⇒ q = p + (q − p)/φ, достаточно уметь складывать, вычитать и умножать точки базиса. Реализация получается короткой: difference вычитает покомпонентно, shorten(p) умножает на 1/φ, а
midpoint(p, q) = sum(p, shorten(difference(q, p)))Собрав это вместе, вы получаете все новые вершины d и e из веток X и Y — и каждый шаг рекурсии остаётся в мире целых коэффициентов.
Ключевые выводы и практический совет
Тайлинг P3 строится из двух кирпичиков: геометрии и формальной системы. Сначала четыре правила подразделения превращают треугольники Робинсона в мозаику, а затем попарное склеивание даёт ромбы Пенроуза. Но рисунок — не алгоритм: чтобы его исполнила машина, те же правила записывают как переписывание термов, где вершины выражаются через переменные p, q, r и операцию p ⇒ q — сдвиг на 1/φ вдоль ребра.
Второй вывод: числовое представление можно сделать точным. Если хранить координаты как четвёрки целых коэффициентов при базисе {ζ³, ζ², ζ, 1}, где ζ = e^(πi/5), то сравнение точек сводится к сравнению целых чисел — без накопления ошибки округления. Замкнутость этого представления относительно сложения, вычитания и умножения доказывается структурной индукцией, а сама операция деления на φ реализуется умножением на заранее известный вектор phiInverse.
Практический совет: если вы реализуете подразделение рекурсивно, как в функции generateP3, держите глубину ограниченной и вычисляйте новые вершины через midpoint(p, q) = sum(p, shorten(difference(q, p))). Такой порядок — сначала разность, потом масштабирование, потом сложение — напрямую повторяет математическое определение и не требует отдельных формул для каждой из четырёх ветвей C, D, X, Y.
