Драконы, шире круг!

17-04-2017

Тема этой статьи – два семейства математических объектов, первое из которых известно под именем  «кривые дракона», а второе… Второе семейство настолько близко к кривым дракона по способу построения, что  его членов можно рассматривать как двоюродных родственников  первого семейства. В то же время эти двоюродные братья и сёстры кривых дракона имеют собственные лица, характеры и, надо полагать, имеют право на собственное имя, которое подчёркивало бы, с одной стороны, их общие корни с кривыми дракона, а с другой стороны – их своеобразие, выделяющее это семейство в отдельную ветвь родословного дерева. Поскольку конфигурация кривых второго семейства часто имеет «слоистый»  характер, что будет раскрыто во второй части статьи, то и всему семейству предлагается дать имя "слоистые драконы" или «слой-драконы» (что, кстати, созвучно с английским «layer-dragon»). Таким образом, тема этой статьи – семейство кривых дракона и семейство слоистых драконов.

Кривая дракона, открытая Джоном Хейтуэем, названная так Уильямом Хартером и ставшая широко известной  благодаря публикациям Мартина Гарднера в его разделе  "Математические игры" в журнале  "Scientific American"  (03  1967 г.),   в  2017 г.  отмечает  своё  50-летие.

Популярность кривой дракона необычайна: в учебниках по программированию её построение предлагается в качестве задачи для школьников и студентов;  люди, склонные к художественному творчеству,  вносят в неё эстетический элемент.  Математики создали теорию кривых дракона. Серьёзные математические сайты (mathworld.wolfram.com, oeis.org)                                          посвящают кривой дракона отдельные статьи,  сайты о фракталах       наполнены  впечатляющими  изображениями  этой  линии.

А вот о кривых, названных здесь слоистыми драконами, автору данной статьи не удалось найти ни одного упоминания, В потоке информации отсутствуют какие-либо описания или изображения этих кривых.

Цель этой статьи - представить новое (как полагает автор) семейство кривых, изложить способ их построения и привлечь внимание к этому математическому объекту.

Здесь не будет серьёзных математических проработок (автор не математик), просто будут представлены некоторые наблюдаемые свойства кривых из семейства "слой-драконов".

Семейство кривых дракона

История кривой дракона началась со складывания бумажной полоски (в первый раз это была долларовая купюра) пополам и ещё несколько раз пополам, расправив которую так, чтобы углы на сгибах были равны 90о , Дж. Хейтуэй и увидел будущую знаменитую кривую. Если присвоить сгибам, как показано на рис.1а), числовые значения 0 для "долин" и 1 для "холмов", получим последовательность нулей и единиц, составляющую полный код кривой. При вычерчивании линии элементы кода - нули и единицы - последовательно считываются и при значении  ноль линия совершает поворот направо, а при значении единица - налево. Углы поворота равны 90о и слегка скругляются (рис.1е).  На всех представленных здесь рисунках первый поворот не скруглён: он указывает на начало линии. (Эта же область рисунков отмечена маленьким белым прямоугольником).

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

Screenshot_195

Рис.1  Сложение бумажной полоски и соответствующее разбиение отрезка прямой.

Разделим отрезок прямой пополам сечением s1-1, присвоим этому сечению значение 0 и порядковый номер 1, как показано на рис.1б) справа. Соответствующее физическое действие - складывание бумажной полоски пополам в направлении по часовой стрелке с образованием "долины" (отсюда 0 для s1-1) изображено на этом рисунке слева.

Следующее складывание бумажной полоски пополам в направлении по часовой стрелке равносильно разбиению отрезка сечениями s2-1 и s2-2 (рис.1в).  Расправим полоску,  присвоим образовавшемуся "холму" значение 1, "долине"- значение 0 и присвоим всем сечениям порядковые номера 1, 2, 3.

Сложим полоску в третий раз, но теперь против часовой стрелки, и проведём соответствующее разбиение отрезка сечениями s3-1...s3-4. Обозначим вновь образовавшуюся череду "долин" и "холмов" числами 0 и 1 и опять пронумеруем все сечения подряд  (рис.1г).

Теперь, анализируя изображённое на рис.1б), в). г) деление отрезка сечениями, можно видеть следующее:

  • при каждом новом разбиении отрезка возникающим новым сечениям соответствуют нечётные порядковые номера .
  • со второго разбиения присвоение сечениям значений 0 или 1 на нечётных позициях зависит от направления изгибания бумажной полоски: при повороте по часовой стрелке чередуются 1 и 0,  при повороте против часовой стрелки чередуются  0  и

Если бумажная полоска имеет достаточную длину, то при 4-м, 5-м и т.д. повторении вышеописанных действий с изгибаниями в разных направлениях, можно убедиться в справедливости этих выводов. На рис.4д)  приведены значения сечений для  4-го изгибания по часовой стрелке.

Таким образом, становится ясным, как можно без затруднений создать полный код любой линии из семейства кривых дракона, производя разбиение отрезка прямой вышеописанным способом и приписывая сечениям желаемое направление поворота. Также видно, что суммарное количество нулей и единиц - элементов полного кода - составляет:  Qо=2k-1, а количество элементов кривой - отрезков, образующих линию,  равно Q=2k, где k- число произведённых разбиений прямой. Это число называется порядком кривой.  Кривая дракона 3-го порядка с полным кодом 0, 1, 1, 0, 0, 0, 1 представлена на рис.1е).  Для неё  k=3,  Qо=7,  Q=8.  Количество сечений, возникающих на нечётных позициях при каждом новом разбиении отрезка, составляет: qi =2i-1, где i - порядковый номер разбиения.  Например, для кривой 4-го порядка (рис.1д)   k =4,   i=1...k,   q1=1,   q2=2,   q3=4,   q4=8,  а  их  сумма  Qo=15.

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

Линии из семейства кривых дракона имеют замысловатые конфигурации. Если программа позволяет видеть их прорисовку на экране компьютера в динамике, то такой "мультик" просто завораживает. Основные же их свойства следующие: эти линии (со скруглёнными углами) независимо от величины порядка кривой не имеют точек самопересечения и эти линии никогда не замыкаются.

Screenshot_196

Рис.2  Регулярная (слева) и альтернативные кривые дракона

Screenshot_197

Рис.3  Произвольные кривые дракона

В онлайн - энциклопедии целочисленных  последовательностей (oeis.org) полный код классической кривой дракона А014577 называется "the regular paper-folding sequence (or dragon curve sequence)".  Ещё одна интересная линия из этого семейства определяется последовательностью  А106665 и называется "Alternate paper-folding (or alternate dragon curve) sequence".  Заметим, что английское словосочетание  "paper-folding", дословно - "бумагосложение, бумагосгибание",  фактически приобрело статус математического термина. Определения "regular" (регулярный) и "alternate"  (переменный) указывают на то, что "бумагосложение" производится в первом случае каждый раз в одном направлении (например, по часовой стрелке), а во втором случае каждое следующее направление изгиба противоположно предыдущему. На рис.2 слева представлена регулярная кривая дракона 9-го порядка, справа - две альтернативные кривые дракона 9-го  и 10-го порядка.  На рис.3  две произвольно выбранные кривые дракона 10-го порядка приведены для иллюстрации разнообразия линий этого семейства.

Семейство слоистых драконов

Так как каждому новому разбиению отрезка прямой соответствует пара чисел 0, 1 или 1, 0 и применение этих пар порождает полный код кривой, то саму последовательность этих пар (вместе с непарным первым сечением) можно рассматривать как короткий код кривой, обозначенный на рисунках аббревиатурой  SC (short  code).

Воспользуемся алгоритмом генерации полного кода кривой с помощью короткого кода, добавив к последнему ещё два типа сечений: 0, 0 и 1, 1. Полный набор типов сечений теперь будет выглядеть так: 0 или 1 для центрального сечения s1-1 и 0, 0 или 0, 1 или 1, 0 или 1, 1 для остальных сечений.  Линии,  полный код которых  содержит хотя бы одно сечение типа 0,  0 или 1,  1,  будем называть слой-драконами.

Здесь необходимо и важно отметить следующее:  последовательность элементов полного кода (их очерёдность)  имеет внутреннюю симметрию: элементы, равноотстоящие от центрального элемента кода s1-1, составляют пару, равнозначную типу сечения, применённому в данном разбиении отрезка. То есть, если при очередном разбиении для образовавшихся сечений использовалась, например, пара 0, 1, то и сечения этого разбиения, равноотстоящие от центрального, так же составят пару 0, 1 (см. рис 1д).  Введением новых сечений типа 0, 0 и 1, 1 эта симметрия не нарушается, процедура разбиения отрезка не изменяется, полный код по-прежнему сохраняет свою структуру и может быть применён к построению кривой.  Но процесс "paper-folding" изменяется:  вместо многократного сложения бумажной полоски пополам, когда сгибы "холм" и "долина" образуются одновременно, теперь  полоску, предварительно размеченную в соответствии с полным кодом, придётся изгибать последовательно сечение за сечением. При этом сечения, равноотстоящие от центрального, оказываются только "холмами" или только "долинами".  Компьютерная программа для вычерчивания линий остаётся без изменений.

Свойства кривых дракона - отсутствие самопересечений и разомкнутость - не зависят от структуры короткого кода и всегда сохраняются при любой величине порядка k.  Свойства слоистых драконов определяются главным образом структурой короткого кода.  Слоистые драконы одного и того же порядка  могут  иметь различные свойства.  На рис.4 линия слой-дракона 10-го порядка не имеет точек самопересечения и не замкнута.  Эта кривая не помещается целиком на экране компьютера - её длина составляет "два экрана".  В верхней части рисунка приведена её уменьшенная копия, а ниже – правая  и  левая части.

Screenshot_198

Рис.5   Кривая из семейства слой – драконов незамкнутая и без самопересечений

На рис.5 все слой-драконы имеют порядок k=10, каждая линия замкнута и самопересекается.  Линии состоят из Q=1024 отрезков,  но  визуально  первая линия воспринимается как состоящая всего из 32 отрезков, вторая  из 128, а шестая - из  64 отрезков. Здесь проявляется эффект самоналожения (слоистости) - свойство,  которое  отсутствует  в семействе кривых дракона.

Screenshot_199

Рис.5  Кривые из семейства слой – драконов замкнутые и самопересекающиеся

Свойства замыкания, самоналожения  (слоистости)  и самопересечения проиллюстрированы  на примере преобразования регулярной кривой дракона 7-го порядка. На рис.6 показано поэтапное изменение этой классической линии - «рост дракона» - при увеличении её порядка введением дополнительных обычных сечений типа 1, 0.  А на рис.7 можно проследить трансформацию этой линии при увеличении её порядка введением в её полный код вместо классического сечения типа 1, 0, как на рис.6, сечений типа 0, 0.      Эффект самоналожения  легко обнаруживается при анализе  слой-драконов 8-го, 9-го и 10-го порядков на этом рисунке. Одна и та же конфигурация линии при k=8 состоит из 256 элементов, при k=9 содержит Q=512 элементов, а при k=10 ещё 512 элементов накладываются на эту линию, создавая четырёхслойную линию из 1024 элементов по 256 отрезков в каждом слое. Все слои этой линии совершенно идентичны друг другу. (Конечно, выражения "многослойная линия", "разложение линии на слои",  "расслоение кривой" звучат необычно, но в контексте изложенного понятны.  Простая  аналогия:   черчение  окружности  несколькими оборотами  циркуля).

Screenshot_200

Рис.6  Изменение регулярной кривой дракона с увеличением её порядка («рост дракона»)

Преобразование кривой дракона 7-го порядка в кривую 8-го порядка введением сечения типа 0, 0  открывает неизвестную до сих пор тайну этих семейств. В литературе описывается линия под названием «двойной дракон» - Twindragon.   Двойной дракон конструируется из двух (!) регулярных кривых дракона одного порядка, которые располагаются «спиной к спине» так, чтобы начало второй линии совпадало с концом первой, а начало первой – с концом второй. В результате получается замкнутая  линия, принадлежность которой к семейству кривых дракона  именно по причине её замкнутости  теперь вызывает сомнение. Поскольку  двойной дракон конструируется искусственно, то и традиционный способ генерации  полного кода  только сечениями 1, 0  в этом случае  неприменим.

Переход от кривой дракона 7-го порядка к слоистому дракону 8-го порядка введением сечения типа 0, 0   как раз и привёл к конфигурации  «двойной дракон»  (на рис.7  в  центре).   Альтернативную или любую произвольную линию из семейства кривых  дракона также можно  легко сделать двойной,  применяя сечение типа 0, 0, и, тем самым, получившиеся кривые поместить  в семейство слой - драконов  и  снабдить  собственными  полными  кодами.

Screenshot_201

Рис.7 Трансформация регулярной кривой дракона сначала в двойной дракон (в центре), затем в слоистый дракон сечением типа 0, 0

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

Упомянутые ранее линии на рис.5 содержат: первая -  32 слоя по 32 элемента в каждом слое, вторая - 8 слоёв по 128 элементов и шестая - 16 слоёв по 64 элемента.

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

Родство семейств кривых дракона и слоистых драконов обеспечивается  единым способом формирования их полных кодов. Взяв за основу какую-либо кривую дракона k-того порядка, можно создать  слоистые драконы более высокого порядка,  сохранив в них конфигурацию исходной линии как части этих новых кривых.  Или, формируя короткий код произвольным набором типов сечений  (как на рис.5),  можно получить слой-драконы совершенно  не  похожие  на  линии  кривых  дракона.

 Слой-драконы  и  заполнение  плоскости

При рассмотрении вопроса о заполнении плоскости всегда подразумевается, что такое заполнение производится линиями, не имеющими самопересечений   и  самоналожения.  Этому правилу вполне соответствуют  отдельно взятые кривые дракона или их сочетания, такие, например, как двойной дракон, составленный из двух одиночных  кривых. Из плотно подогнанных друг к другу двойных драконов можно составить узор, заполняющий плоскость, подобно красивой  ковровой  дорожке.   В левой верхней части  рис.8  представлена  такая дорожка,  «сотканная»  из четырёх двойных драконов  12-го  порядка (очень распространённая в интернете).  Схема под дорожкой  показывает, что прорисовка каждого двойного дракона  начинается в новой точке и производится  независимо.

В семействе слой-драконов можно создать полный код непрерывной  линии (с соблюдением требований об отсутствии самопересечений и самоналожения), заполняющей плоскость  таким же узором.  На рисунке справа   это выполнено  замкнутой  линией  10-го порядка    Схема под ней  иллюстрирует процесс прорисовки,  из которого  видно, что полученная линия представляет собой восемь обычных кривых дракона, соединённых последовательно  и  расположенных на плоскости  так, что они образуют четыре двойных дракона.  В рамке (на рис.8 - слева) альтернативная кривая дракона 7-го порядка превращена в слой-дракон 10-го порядка и тоже заполняет  плоскость  единой  линией.

Screenshot_202

Рис.8  Заполнение плоскости отдельными кривыми  «двойной дракон» (слева вверху) и заполнение плоскости непрерывной линией из семейства слой-драконов (справа)

     Дополнительные материалы. 

-  S. Tabachnikov,  «Dragon  curves  revisited».

В  статье удачно  сочетаются популярный стиль  изложения и математика. Дан большой перечень  работ  математиков  по этой теме.  (https://www.math.psu.edu/tabachni/prints/DragonCurves.pdf).

-  Н.Б. Васильев,  В.Л. Гутенмахер,  «Кривые  дракона».  Журнал «Квант» №2, 1970 г.  Это, вероятно,  первая статья на русском языке о кривых дракона.

(kvant.mccme.ru>1970  год>02/krivye_drakona.htm.).

- Мартин  Гарднер,  «Математические новеллы», изд. «Мир», Москва,1974 г.

- журнал  «Scientific American»  №№ 03, 04, 07  1967 г.                                         

Комментарии
  • someone - 19.04.2017 в 09:13:
    Всего комментариев: 10
    Спасибо, очень интересно. А если добавить измерение? Строить подобные фигуры не на плоскости, а в пространстве. Если ли работы на эту тему?
    Рейтинг комментария: Thumb up 1 Thumb down 0
    • v.tor - 20.04.2017 в 18:07:
      Всего комментариев: 1
      Спасибо за интерес к статье. Кривых дракона в трёхмерном пространстве в сети не обнаруживал. Но есть интересные "объёмные" кривые на некоторых сайтах, Показать продолжение
      Рейтинг комментария: Thumb up 1 Thumb down 1

Добавить изображение