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

Криві Серпінського — це рекурсивно визначена послідовність неперервних замкнутих плоских фрактальних кривих, відкритих Вацлавом Серпінським.

Крива Серпінського
Названо на честь	Вацлав Серпінський
Підтримується Вікіпроєктом
Крива Серпінського у Вікісховищі

Загальний опис

Крива в границі при ${\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 і 2

Крива Серпінського, кроки від 1 до 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]
• Рекурсивна функція
• Трикутник Серпінського

Примітки

1. Platzman, Bartholdi, 1989.
2. Bartholdi.
3. Слюсар, В. (2007). (PDF). Электроника: наука, технология, бизнес. — 2007. — № 6. с. С. 82—89. Архів оригіналу (PDF) за 3 квітня 2018. Процитовано 18 грудня 2020. {{}}: |pages= має зайвий текст ()

Література

• 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 (16 червня). — С. 719—737.
• John J. Bartholdi III. Some combinatorial applications of spacefilling curves. — Georgia Institute of Technology. Архівовано з джерела 3 серпня 2012.