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

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

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

{\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}}

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

Кривая Серпинского («квадратная снежинка Серпинского»). ^[1]) первого порядка

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

Кривая Серпинского полезна в нескольких практических приложениях, поскольку она более симметрична, чем другие обычно изучаемые кривые, заполняющие пространство. Например, он использовался в качестве основы для быстрого построения приближенного решения задачи коммивояжера (которая требует кратчайшей последовательности заданного набора точек): Эвристика заключается в простом посещении точек в одной и той же последовательности. так, как они выглядят на кривой Серпинского. ^[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, long code, 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 * code + 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 );
            }
        }
        return code;    
    }

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

Кривую Серпинского можно выразить с помощью системы перезаписи ( 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 order is even we can just draw the curve.
    if ( 0 == (order & 1) ) {
        curve(order, length, +60);
    }
    else /* order is odd */ {
        turn( +60);
        curve(order, length, -60);
    }
}

void curve(unsigned order, double length, int angle)
{
    if ( 0 == order ) {
        draw_line(length);
    } else {
        curve(order - 1, length / 2, -angle);
        turn(angle);
        curve(order - 1, length / 2, angle);
        turn(angle);
        curve(order - 1, length / 2, -angle);
    }
}

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

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

Алфавит : X, Y

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

Аксиома : XF

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

Х → YF + XF + Y

Y → XF − YF − X

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

См. также

Ссылки

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

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

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

[1] Вайсштейн, Эрик В. «Кривая Серпинского» . Математический мир . Проверено 21 января 2019 г.

[2] Диккау, Роберт М. (1996/7) « Двумерные L-системы », Математические фигуры Роберта . MathForum.org. Проверено 21 января 2019 г.

[Platzman89-3] Платцман, Лорен К.; Бартольди, Джон Дж. III (1989). «Кривые заполнения пространства и плоская задача коммивояжера» . Журнал Ассоциации вычислительной техники . 36 (4): 719–737. дои : 10.1145/76359.76361 .

[BartholdiURL-4] Бартольди, Джон Дж. III. «Некоторые комбинаторные применения кривых заполнения пространства» . Технологический институт Джорджии . Архивировано из оригинала 3 августа 2012 г.

[1]

[2]

[3]

[4]

v т и Фракталы
Характеристики	Фрактальные измерения Ассуад Подсчет коробок Хигучи Корреляция Хаусдорф Упаковка Топологический Рекурсия Самоподобие
Итерированная функция система	Папоротник Барнсли Канторовский набор Снежинка Коха Моя губка Ковер Серпинского Треугольник Серпинского Аполлоническая прокладка Слово Фибоначчи Кривая заполнения пространства Кривая Бланманже Кривая Де Рама Минковский Кривая дракона Кривая Гильберта кривая Коха Кривая Леви C Кривая Мура Кривые Пеано Кривая Серпинского Кривая Z-порядка Нить Т-образный н-хлопья Фрактальные шутки шестихлопьевидный Кривая Госпера Дерево Пифагора Функция Вейерштрасса
Странный аттрактор	Мультифрактальная система
L-система	Фрактальный навес Кривая заполнения пространства H-дерево
Время побега фракталы	Фрактал горящего корабля Джулия сет Заполненный Ньютон фрактал Кролик Дуади Ляпунов фрактал Набор Мандельброта точка Мисюревича Набор Мультиброт Ньютон фрактал Треуголка Мандельбокс Мандельбулба
рендеринга Методы	Буддадброт Орбитальная ловушка Пиковерный стебель
Случайные фракталы	Броуновское движение Броуновское дерево Броуновский двигатель Фрактальный пейзаж полет Леви Теория перколяции Самоизбегающая прогулка
Люди	Майкл Барнсли Георг Кантор Билл Госпер Феликс Хаусдорф Десмонд Пол Генри Гастон Джулия Хельге фон Кох Пол Леви Aleksandr Lyapunov Бенуа Мандельброт Хамид Надери Йегане Льюис Фрай Ричардсон Вацлав Серпиньский
Другой	« Какова длина побережья Британии? » Парадокс береговой линии Фрактальное искусство Список фракталов по размерности Хаусдорфа Фрактальная геометрия природы (книга 1982 г.) Красота фракталов (книга 1986 г.) Хаос: создание новой науки (книга 1987 г.) Калейдоскоп Теория хаоса