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

редактировать

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

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

ln = 2 3 ( 1 + 2) 2 n - 1 3 (2 - 2) 1 2 n, {\ displaystyle l_ {n} = {2 \ over 3} (1 + {\ sqrt {2}}) 2 ^ {n} - { 1 \ over 3} (2 - {\ sqrt {2}}) {1 \ over 2 ^ {n}},}{\ displaystyle l_ {n} = {2 \ over 3} (1 + {\ sqrt { 2}}) 2 ^ {n} - {1 \ over 3} (2 - {\ sqrt {2}}) {1 \ over 2 ^ {n}},}

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

Кривая Серпинского («квадратная снежинка Серпинского») первого порядка Кривые Серпинского 1-го и 2-го порядков Кривые Серпинского 1–3 порядков
«Квадратная кривая» Серпинского 2-4 порядков

Содержание

  • 1 Использование кривой
  • 2 Представление в виде системы Линденмайера
  • 3 Кривая со стрелкой
    • 3.1 Код
    • 3.2 Представление в виде системы Линденмайера
  • 4 См. Также
  • 5 Ссылки
  • 6 Дополнительная литература

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

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

Кривая заполнения пространства представляет собой непрерывную карту единичного интервала на единичный квадрат и, следовательно, (псевдо) обратные карты единичный квадрат к единичному интервалу. Один из способов построения псевдообращения следующий. Пусть нижний левый угол (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; }

Представление как Lindenmayer система

Кривая Серпинского может быть выражена с помощью системы перезаписи (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 + FX
Угол : 90

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

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

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

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

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

Код

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

void sierpinski_arrowhead_curve (беззнаковый порядок, двойная длина) {// Если порядок четный, мы можем просто нарисовать кривую. if (0 == (порядок 1)) {кривая (порядок, длина, +60); } else / * порядок нечетный * / {turn (+60); кривая (порядок, длина, -60); }}
пустая кривая (беззнаковый порядок, двойная длина, целочисленный угол) {if (0 == порядок) {draw_line (length); } else {кривая (порядок - 1, длина / 2, -угол); поворот (угол); кривая (порядок - 1, длина / 2, угол); поворот (угол); кривая (порядок - 1, длина / 2, -угол); }}

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

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

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

Алфавит : X, Y
Константы : F, +, -
Аксиома : XF
Правила производства :
X → YF + XF + Y
Y → XF - YF - X

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

См. Также

Викискладе есть материалы, связанные с кривой Серпинского.

Ссылки

Дополнительная литература

Последняя правка сделана 2021-06-08 08:18:20
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте