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

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

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

${\displaystyle S_{n}}$ равна ${\displaystyle l_{n}={2 \over 3}(1+{\sqrt {2}})2^{n}-{1 \over 3}(2-{\sqrt {2}}){1 \over 2^{n}}}$,

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

Использование кривой[править | править код]

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

На основе кривой Серпинского могут быть реализованы вибраторные либо печатные конструкции антенн^[3].

Построение кривой[править | править код]

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

Следующий апплет на языке Java рисует кривую Серпинского с помощью четырёх взаимно рекурсивных методов (методов, вызывающих друг друга):

import java.applet.Applet; import java.awt.Graphics; import java.awt.Image;  public class SierpinskyCurve extends Applet {      private SimpleGraphics sg = null;     private int dist0 = 128, dist;     private Image offscrBuf;     private Graphics offscrGfx;      public void init() {         sg = new SimpleGraphics(getGraphics());         dist0 = 100;         resize(4 * dist0, 4 * dist0);     }      public void update(Graphics g) {         paint(g);     }      public void paint(Graphics g) {          if (g == null)             throw new NullPointerException();          if (offscrBuf == null) {             offscrBuf = createImage(this.getWidth(), this.getHeight());             offscrGfx = offscrBuf.getGraphics();             sg.setGraphics(offscrGfx);         }          int level = 3;         dist = dist0;         for (int i = level; i > 0; i--)             dist /= 2;         sg.goToXY(2 * dist, dist);         sierpA(level); // start recursion         sg.lineRel('X', +dist, +dist);         sierpB(level); // start recursion         sg.lineRel('X', -dist, +dist);         sierpC(level); // start recursion         sg.lineRel('X', -dist, -dist);         sierpD(level); // start recursion         sg.lineRel('X', +dist, -dist);          g.drawImage(offscrBuf, 0, 0, this);      }      private void sierpA(int level) {         if (level > 0) {             sierpA(level - 1);             sg.lineRel('A', +dist, +dist);             sierpB(level - 1);             sg.lineRel('A', +2 * dist, 0);             sierpD(level - 1);             sg.lineRel('A', +dist, -dist);             sierpA(level - 1);         }     }      private void sierpB(int level) {         if (level > 0) {             sierpB(level - 1);             sg.lineRel('B', -dist, +dist);             sierpC(level - 1);             sg.lineRel('B', 0, +2 * dist);             sierpA(level - 1);             sg.lineRel('B', +dist, +dist);             sierpB(level - 1);         }     }      private void sierpC(int level) {         if (level > 0) {             sierpC(level - 1);             sg.lineRel('C', -dist, -dist);             sierpD(level - 1);             sg.lineRel('C', -2 * dist, 0);             sierpB(level - 1);             sg.lineRel('C', -dist, +dist);             sierpC(level - 1);         }     }      private void sierpD(int level) {         if (level > 0) {             sierpD(level - 1);             sg.lineRel('D', +dist, -dist);             sierpA(level - 1);             sg.lineRel('D', 0, -2 * dist);             sierpC(level - 1);             sg.lineRel('D', -dist, -dist);             sierpD(level - 1);         }     } }  class SimpleGraphics {     private Graphics g = null;     private int x = 0, y = 0;      public SimpleGraphics(Graphics g) {         setGraphics(g);     }      public void setGraphics(Graphics g) {         this.g = g;     }      public void goToXY(int x, int y) {         this.x = x;         this.y = y;     }      public void lineRel(char s, int deltaX, int deltaY) {         g.drawLine(x, y, x + deltaX, y + deltaY);         x += deltaX;         y += deltaY;     } } 

Следующая программа на языке Лого рисует кривую Серпинского с использованием рекурсии.

to half.sierpinski :size :level  if :level = 0 [forward :size stop]  half.sierpinski :size :level - 1  left 45  forward :size * sqrt 2   left 45  half.sierpinski :size :level - 1  right 90  forward :size   right 90  half.sierpinski :size :level - 1  left 45  forward :size * sqrt 2   left 45  half.sierpinski :size :level - 1 end 

to sierpinski :size :level  half.sierpinski :size :level  right 90  forward :size  right 90  half.sierpinski :size :level  right 90  forward :size  right 90 end 

См. также[править | править код]

• Кривая Гильберта
• Кривая Коха
• Кривая Мура
• Кривая Пеано
• Наконечник Серпинского^[en]
• Список фракталов по размерности Хаусдорфа^[en]
• Рекурсивная функция
• Треугольник Серпинского

Примечания[править | править код]

Литература[править | править код]

• Loren K. Platzman, John J. Bartholdi III. Spacefilling curves and the planar traveling salesman problem // Journal of the Association of Computing Machinery. — 1989. — Т. 36, вып. 4. — С. 719—737.
• John J. Bartholdi III. Some combinatorial applications of spacefilling curves. — Georgia Institute of Technology. Архивировано 3 августа 2012 года.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.