Всем привет! Привожу перевод статьи Penrose Tiling Explained. Мне самому было интересно как устроен алгоритм прорисовки мозаики. Удивился простоте и хочу поделиться.. Помимо почти не исправленного машинного перевода добавил свой перевод предложенного алгоритма на язык TypeScript. Привожу ссылку на песочницу в конце статьи. Версия TypeScript дополнена интерактивной формой изменения параметров алгоритма. Играя с параметрами, можно понять большую часть алгоритма даже без чтения разъяснения.

В оригинальной статье отсутствуют подписи под иллюстрациями.

На прошлой неделе я опубликовал запутанный код на Python, который генерирует мозаику Пенроуза. Сегодня я объясню базовый алгоритм, лежащий в основе этого скрипта на Python, и поделюсь его не запутанной версией.

Алгоритм работает со списком красных и синих равнобедренных треугольников. У каждого красного треугольника угол при вершине равен 36°, а у каждого синего — 108°.

В Python такие треугольники можно представить в виде кортежей вида (color, A, B, C). Первый элемент, color, принимает значение 0 для красного треугольника и 1 для синего. Остальные элементы кортежа представляют собой координаты вершин A, B и C, выраженные в виде комплексных чисел. Комплексные числа хорошо подходят для этой задачи, поскольку они могут представлять любую точку на двумерной плоскости: действительная часть даёт координату по оси X, а мнимая часть — координату по оси Y.

Как видите, мы рисуем контур по сторонам треугольника, но не по основанию. Это позволяет соединить каждый треугольник с другим треугольником того же цвета, образуя ромбовидные плитки, которые видны на готовой мозаике Пенроуза.

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

В приведённом выше разбиении появляется новая вершина P, расположенная в точке на ребре AB, которая соответствует золотому сечению .

Точно так же каждый синий треугольник делится на три треугольника поменьше:

В результате этого разбиения появляются две новые вершины: Q на ребре BA и R на ребре BC в точках, которые также удовлетворяют золотому сечению. Кроме того, два получившихся треугольника являются зеркальными отражениями друг друга. Я выделил углы каждого треугольника, чтобы было понятно, какие из них зеркальные, а какие нет.

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

goldenRatio = (1 + math.sqrt(5)) / 2

def subdivide(triangles):
    result = []
    for color, A, B, C in triangles:
        if color == 0:
            # Subdivide red triangle
            P = A + (B - A) / goldenRatio
            result += [(0, C, P, B), (1, P, C, A)]
        else:
            # Subdivide blue triangle
            Q = B + (A - B) / goldenRatio
            R = B + (C - B) / goldenRatio
            result += [(1, R, C, A), (1, Q, R, B), (0, R, Q, A)]
    return result

const goldenRatio = (1 + Math.sqrt(5)) / 2;

// Реализуется вычисление комплексного числа по по формуле:
// A + (B - A) / goldenRatio
// Где первым вычисляется слагаемое с операцией деления из-за
// приоритета над сложением. А так же используется вызов clone(),
// потому что каждая операция сохраняет результат в this.
const subdividePoint = (A: Complex2, B: Complex2): Complex2 =>
  B.clone().sub(A).divScalar(goldenRatio).add(A);

export function subdivide(triangles: Vertexes): Vertexes {
  const result: Vertexes = [];
  for (const [color, A, B, C] of triangles) {
    if (color === VertexColor.Red) {
      // Subdivide red triangle
      const P = subdividePoint(A, B);
      result.push([VertexColor.Red, C, P, B], [VertexColor.Blue, P, C, A]);
    } else {
      // Subdivide blue triangle
      const Q = subdividePoint(B, A);
      const R = subdividePoint(B, C);
      result.push(
        [VertexColor.Blue, R, C, A],
        [VertexColor.Blue, Q, R, B],
        [VertexColor.Red, R, Q, A]
      );
    }
  }
  return result;
}

// Для магических чисел 0 и 1 обозначающих тип треуголника просто
// написан отдельный тип.
enum VertexColor {
  Red = 0,
  Blue,
}

// В TypeScript можно описывать кортежи через массивы.
type Vertex = [
  Color: VertexColor,
  A: Complex2,
  B: Complex2,
  C: Complex2
];

type Vertexes = Vertex[];

export class Complex2 {
  constructor(public real: number, public imag: number) {}
  clone() {
    return new Complex2(this.real, this.imag);
  }
  // Прямой аналог Python функции cmath.rect()
  static fromPolar(r: number, phi: number): Complex2 {
    return new Complex2(r * Math.cos(phi), r * Math.sin(phi));
  }
  static zero(): Complex2 {
    return new Complex2(0, 0);
  }
  add(x: Complex2): Complex2 {
    this.real += x.real;
    this.imag += x.imag;
    return this;
  }
  sub(x: Complex2): Complex2 {
    this.real -= x.real;
    this.imag -= x.imag;
    return this;
  }
  mulScalar(x: number): Complex2 {
    this.real *= x;
    this.imag *= x;
    return this;
  }
  divScalar(x: number): Complex2 {
    this.real /= x;
    this.imag /= x;
    return this;
  }
  abs(): number {
    return Math.sqrt(this.real ** 2 + this.imag ** 2);
  }
}

А вот код для фактического отображения списка треугольников. Он использует pycairo — оболочку Python для превосходной библиотеки рисования cairo.

# Draw red triangles
for color, A, B, C in triangles:
    if color == 0:
        cr.move_to(A.real, A.imag)
        cr.line_to(B.real, B.imag)
        cr.line_to(C.real, C.imag)
        cr.close_path()
cr.set_source_rgb(1.0, 0.35, 0.35)
cr.fill()    

# Draw blue triangles
for color, A, B, C in triangles:
    if color == 1:
        cr.move_to(A.real, A.imag)
        cr.line_to(B.real, B.imag)
        cr.line_to(C.real, C.imag)
        cr.close_path()
cr.set_source_rgb(0.4, 0.4, 1.0)
cr.fill()

# Determine line width from size of first triangle
color, A, B, C = triangles[0]
cr.set_line_width(abs(B - A) / 10.0)
cr.set_line_join(cairo.LINE_JOIN_ROUND)

# Draw outlines
for color, A, B, C in triangles:
    cr.move_to(C.real, C.imag)
    cr.line_to(A.real, A.imag)
    cr.line_to(B.real, B.imag)
cr.set_source_rgb(0.2, 0.2, 0.2)
cr.stroke()

const ctx = canvas.getContext("2d")!;
ctx.clearRect(0, 0, canvas.width, canvas.height);
ctx.save();
ctx.translate(canvas.width / 2.0, canvas.height / 2.0);
ctx.scale(options.wheelRadius, options.wheelRadius);

// Draw red triangles
ctx.fillStyle = "rgb(255, 89, 89)";
for (const [color, A, B, C] of triangles) {
  if (color == VertexColor.Red) {
    ctx.beginPath();
    ctx.moveTo(A.real, A.imag);
    ctx.lineTo(B.real, B.imag);
    ctx.lineTo(C.real, C.imag);
    ctx.fill();
  }
}

// Draw blue triangles
ctx.fillStyle = "rgb(102, 102, 255)";
for (const [color, A, B, C] of triangles) {
  if (color == VertexColor.Blue) {
    ctx.beginPath();
    ctx.moveTo(A.real, A.imag);
    ctx.lineTo(B.real, B.imag);
    ctx.lineTo(C.real, C.imag);
    ctx.fill();
  }
}

// Determine line width from size of first triangle
const [color, A, B, C] = triangles[0];
ctx.lineWidth = B.clone().sub(A).abs() / 10.0;
ctx.lineJoin = "round";

// Draw outlines
ctx.fillStyle = "rgb(51, 51, 51)";
for (const [color, A, B, C] of triangles) {
  ctx.beginPath();
  ctx.moveTo(C.real, C.imag);
  ctx.lineTo(A.real, A.imag);
  ctx.lineTo(B.real, B.imag);
  ctx.stroke();
}

ctx.restore();

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

Вы даже можете начать последовательность с другого списка треугольников. Вот код для создания «колеса», состоящего из 10 красных треугольников:

# Create wheel of red triangles around the origin
triangles = []
for i in xrange(10):
    B = cmath.rect(1, (2*i - 1) * math.pi / 10)
    C = cmath.rect(1, (2*i + 1) * math.pi / 10)
    if i % 2 == 0:
        B, C = C, B  # Make sure to mirror every second triangle
    triangles.append((0, 0j, B, C))

// Create wheel of red triangles around the origin
let triangles: Vertexes = [];
for (let i = 0; i < 10; ++i) {
  let B = Complex2.fromPolar(1, ((2 * i - 1) * Math.PI) / 10);
  let C = Complex2.fromPolar(1, ((2 * i + 1) * Math.PI) / 10);
  if (i % 2 === 0) {
    // Make sure to mirror every second triangle}
    const Z = B;
    B = C;
    C = Z;
  }
  triangles.push([VertexColor.Red, Complex2.zero(), B, C]);
}

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

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

Наконец, вот не запутанный скрипт на Python, который объединяет всё воедино: скачайте penrose.py. Он начинает с узора в виде колеса, делит его на 10 частей и отображает увеличенный и обрезанный результат в виде изображения размером 1000x1000.