Программирование → Дракон Хартера - Хейтуэя

Читал книжку "Математические новеллы" Мартина Гарднера и попалась мне на глаза эта штука - кривая дракона. Сразу же захотелось её повторить, что я и проделал.

Придумал эту кривую физик Джон Хейтуэй, а теорию разработали Вильям Хартер, Хейтуэй и Брюс Бенкс. Относится этот объект к фрактальным кривым и может быть получен рекурсивным способом, но о нём ниже. На рисунке выше изображён дракон 12-го порядка.

Для получения кривой было использовано её двоичное представление. В последовательности цифр двоичного числа единице соответствует поворот налево, а нулю - направо. Числа представлены ниже:

• 1 - дракоша 1-го порядка
• 110 - 2-го
• 1101100 - 3-го
• 110110011100100 - 4-го

и т.д. Алгоритм для любого порядка кривой следующий - к числу дракона Х предыдущего порядка справа дописываем 1 и тот же X, только с 0 в центре.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

FUNCTION dragon(x1, y1, x2, y2, k)
    IF (k > 0)
        xs = (x1 + x2) / 2 + (y2 - y1) / 2
        ys = (y1 + y2) / 2 - (x2 - x1) / 2
        dragon(x2, y2, xs, ys, k-1)
        dragon(x1, y1, xs, ys, k-1)
    ELSE
        line (x1, y1)-(x2, y2)
    END IF
END FUNCTION

Теперь логарифмическая спираль стала просто очевидной, ведь при каждой итерации начальный отрезок поворачивается на 45º и уменьшается в √2 раз

Ниже кривая 14-го порядка. Поверх каждого дракона нарисован дракон с меньшим на единицу порядком и цвета их чередуются (это чтобы лучше видеть, как они держутся крючковатыми своими плавниками за Spira mirabilis).

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