Кривая Серпинского

Кривые Серпинского представляют собой рекурсивно определенную последовательность непрерывных замкнутых плоских фрактальных кривых , открытых Вацлавом Серпинским , которые в пределе полностью заполняют единичный квадрат: таким образом, их предельная кривая, также называемая кривой Серпинского , является примером кривой, заполняющей пространство . ${\displaystyle n\to \infty }$

Поскольку кривая Серпинского заполняет пространство, ее размерность Хаусдорфа (в пределе ) равна . Евклидова длина i-й ^{итерационной} кривой равна ${\displaystyle n\to \infty }$ ${\displaystyle 2}$
${\displaystyle n}$ ${\displaystyle S_{n}}$

${\displaystyle {\begin{aligned}l_{n}&={2 \over 3}(1+{\sqrt {2}})2^{n}-{1 \over 3}(2-{\sqrt {2}}){1 \over 2^{n}},\\&={\frac {2^{7/4}}{3}}\sinh(n\log(2)+\mathrm {asinh} ({\frac {3}{2^{5/4}}}))\end{aligned}}}$

т. е. он растет экспоненциально, выходя за пределы любого предела, тогда как предел площади, заключенной в него, равен квадрату (в евклидовой метрике). ${\displaystyle n}$ ${\displaystyle n\to \infty }$ ${\displaystyle S_{n}}$ ${\displaystyle 5/12\,}$

«квадратная кривая» Серпинского ^[2] порядков 2–4.

Использование кривой

Кривая Серпинского полезна в нескольких практических приложениях, поскольку она более симметрична, чем другие обычно изучаемые кривые, заполняющие пространство. Например, он использовался в качестве основы для быстрого построения приближенного решения задачи коммивояжера ( которая требует кратчайшей последовательности заданного набора точек): Эвристика заключается в простом посещении точек в одной и той же последовательности. так, как они выглядят на кривой Серпинского. ^[3] Для этого требуется два шага: сначала вычислить прообраз каждой точки, которую необходимо посетить; затем отсортируйте значения. Эта идея была использована для создания систем маршрутизации для коммерческих автомобилей, основанных только на картотеках Rolodex. ^[4]

Кривая, заполняющая пространство, представляет собой непрерывное отображение единичного интервала на единичный квадрат, поэтому (псевдо) инверсия отображает единичный квадрат на единичный интервал. Один из способов построения псевдообратного состоит в следующем. Пусть нижний левый угол (0, 0) единичного квадрата соответствует 0,0 (и 1,0). Тогда левый верхний угол (0, 1) должен соответствовать 0,25, правый верхний угол (1, 1) — 0,50, а правый нижний угол (1, 0) — 0,75. Обратная карта внутренних точек вычисляется с использованием рекурсивной структуры кривой.

Вот функция, закодированная на Java, которая вычисляет относительное положение любой точки на кривой Серпинского (то есть псевдообратное значение). В качестве входных данных он принимает координаты инвертируемой точки (x,y) и углы охватывающего прямоугольного равнобедренного треугольника (ax, ay), (bx, by) и (cx, cy). (Единичный квадрат представляет собой объединение двух таких треугольников.) Остальные параметры определяют уровень точности, с которой должно вычисляться обратное.

 static long sierp_pt2code ( double ax , double ay , double bx , double by , double cx , double cy , int currentLevel , int maxLevel , длинный код , double x , double y ) { if ( currentLevel <= maxLevel ) { currentLevel ++ ; if (( sqr ( x - ax ) + sqr ( y - ay )) < ( sqr ( x - cx ) + sqr ( y - cy ))) { code = sierp_pt2code ( ax , ay , ( ax + cx ) / 2.0 , ( ay + cy ) / 2.0 , bx , by , currentLevel , maxLevel , 2 * код + 0 , x , y ); } else { code = sierp_pt2code ( bx , by , ( ax + cx ) / 2.0 , ( ay + cy ) / 2.0 , cx , cy , currentLevel , maxLevel , 2 * code + 1 , x , y ); } } код возврата ; }                                                                                         

Представление в виде системы Линденмайера

Кривую Серпинского можно выразить с помощью системы перезаписи ( L-системы ).

Алфавит : F, G, X

Константы : F, G, +, −

Аксиома : F--XF--F--XF

Правила производства :

X → XF+G+XF−−F−−XF+G+X

Угол : 45

Здесь и F , и G означают «движение вперед», + означает «поворот налево на 45°», а – означает «поворот направо на 45°» (см. рисунок черепахи ). Кривая обычно рисуется с разной длиной для F и G.

Квадрат Серпинского можно выразить аналогичным образом:

Алфавит : F, X

Константы : F, +, −

Аксиома : F+XF+F+XF

Правила производства :

X → XF−F+F−XF+F+XF−F+F−X

Угол : 90

Кривая стрелки

Кривая стрелки Серпинского представляет собой фрактальную кривую, похожую по внешнему виду и идентичную по пределу треугольнику Серпинского .

Эволюция кривой наконечника стрелки Серпинского

Кривая стрелки Серпинского рисует равносторонний треугольник с треугольными отверстиями через равные интервалы. Его можно описать двумя замещающими продукционными правилами: (A → BAB) и (B → A+B+A). A и B повторяются, а внизу делают то же самое — рисуют линию. Плюс и минус (+ и -) означают поворот на 60 градусов влево или вправо. Конечная точка кривой со стрелкой Серпинского всегда одна и та же, если вы повторяете ее четное количество раз и уменьшаете вдвое длину линии при каждой рекурсии. Если вы вернетесь на нечетную глубину (порядок нечетный), то в конечном итоге вы повернетесь на 60 градусов в другой точке треугольника.

Альтернативное сужение приведено в статье о кривой де Рама : используется тот же метод, что и кривые де Рама, но вместо использования двоичного разложения (по основанию 2) используется троичное разложение (по основанию 3).

Код

Учитывая функции рисования void draw_line(double distance);и void turn(int angle_in_degrees);, код рисования (приблизительной) кривой со стрелкой Серпинского выглядит следующим образом:

void sierpinski_arrowhead_curve ( unsigned order , double length ) { // Если порядок четный, мы можем просто нарисовать кривую. if ( 0 == ( порядок & 1 ) ) { кривая ( порядок , длина , + 60 ); } else /* порядок нечетный */ { Turn ( + 60 ); кривая ( порядок , длина , -60 ); } }                           

void кривая ( беззнаковый порядок , двойная длина , внутренний угол ) { if ( 0 == порядок ) { draw_line ( длина ); } else { кривая ( порядок - 1 , длина / 2 , - угол ); поворот ( угол ); кривая ( порядок - 1 , длина / 2 , угол ); поворот ( угол ); кривая ( порядок - 1 , длина / 2 , - угол ); } }                                         

Представление в виде системы Линденмайера

Как и многие двумерные фрактальные кривые, кривую со стрелкой Серпинского можно расширить до трех измерений.

Кривая стрелки Серпинского может быть выражена с помощью системы перезаписи ( L-системы ).

Алфавит : X, Y

Константы : F, +, −

Аксиома : XF

Правила производства :

Х → YF + XF + Y

Y → XF − YF − X

Здесь F означает «натянуть вперед», + означает «повернуть налево на 60°», а – означает «повернуть направо на 60°» (см. рисунок черепахи ).

Смотрите также

• Кривая Гильберта
• Снежинка Коха
• Граф Мура
• Полигон Мюррея
• Кривая Пеано
• Список фракталов по размерности Хаусдорфа
• Рекурсия (информатика)
• Треугольник Серпинского

Рекомендации

1. Вайсштейн, Эрик В. «Кривая Серпинского». Математический мир . Проверено 21 января 2019 г.
2. Диккау, Роберт М. (1996/7) «Двумерные L-системы», Математические фигуры Роберта . MathForum.org. Проверено 21 января 2019 г.
3. Платцман, Лорен К.; Бартольди, Джон Дж. III (1989). «Кривые заполнения пространства и плоская задача коммивояжера». Журнал Ассоциации вычислительной техники . 36 (4): 719–737. дои : 10.1145/76359.76361 .
4. Бартольди, Джон Дж. III. «Некоторые комбинаторные применения кривых заполнения пространства». Технологический институт Джорджии . Архивировано из оригинала 3 августа 2012 г.

дальнейшее чтение

• Пейтген, Х.-О.; Юргенс, Х.; Саупе, Д. (2013) [1992]. Хаос и фракталы: новые рубежи науки. Спрингер. ISBN 978-1-4757-4740-9.
• Стивенс, Роджер Т. (1989). Фрактальное программирование на C. Книги М&Т. ISBN 978-1-55851-037-1.