Кривые Серпинского представляют собой рекурсивно определенную последовательность из непрерывную замкнутая плоскость фрактальные кривые, открытые Вацлавом Серпиньским, которые в пределе полностью заполняют единичный квадрат: таким образом, их предельная кривая, также называемая кривой Серпинского, является примером кривой заполнения пространства.
Поскольку кривая Серпинского заполняет пространство, ее Размерность Хаусдорфа (в пределе ) составляет .. евклидова длина итерационной кривой равно
т.е. он растет экспоненциально с вне всяких пределов, тогда как th e ограничение для области, заключенной в , равно квадрат (в евклидовой метрике).
Кривая Серпинского («квадратная снежинка Серпинского») первого порядка | Кривые Серпинского 1-го и 2-го порядков | Кривые Серпинского 1–3 порядков |
Кривая Серпинского полезна в нескольких практических приложениях, поскольку она более симметрична, чем другие обычно изучаемые кривые заполнения пространства. Например, он был использован в качестве основы для быстрого построения приближенного решения задачи коммивояжера (которая запрашивает кратчайшую последовательность из заданного набора точек): эвристика заключается в простом посещении точки в той же последовательности, в которой они появляются на кривой Серпинского. Для этого требуется два шага: сначала вычислить инверсию каждой точки, которую нужно посетить; затем отсортируйте значения. Эта идея была использована для создания систем маршрутизации для коммерческих автомобилей, основанных только на картах 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; }
Кривая Серпинского может быть выражена с помощью системы перезаписи (L-система ).
Здесь F и G означают «тянуть вперед», + означает «повернуть налево на 45 °», а - означает «повернуть направо на 45 °» (см. графика черепахи ). Кривая обычно строится с разной длиной для F и G.
Квадратная кривая Серпинского может быть выражена аналогичным образом:
Кривая стрелки Серпинского - фрактальная кривая, похожая по внешнему виду и идентичная в пределах треугольника Серпинского.
Эволюция кривой наконечника стрелки СерпинскогоКривая наконечника стрелки Серпинского рисует равносторонний треугольник с треугольными отверстиями через равные промежутки. Его можно описать двумя производственными правилами подстановки: (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-система ).
Здесь F означает «тянуть вперед», + означает «повернуть налево на 60 °», а - означает «повернуть направо на 60 °» (см. графика черепахи ).
Викискладе есть материалы, связанные с кривой Серпинского. |