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

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

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

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

Крива в границі при $n\rightarrow \infty$ повністю заповнює одиничний квадрат, так що гранична крива, також звана кривою Серпінського, є прикладом кривих, що заповнюють простір.

Оскільки крива Серпінського заповнює простір, її розмірність Гаусдорфа (в границі при $n\rightarrow \infty$) дорівнює $2$. Евклідова довжина кривої

$S_{n}$ дорівнює $l_{n}={2 \over 3}(1+{\sqrt {2}})2^{n}-{1 \over 3}(2-{\sqrt {2}}){1 \over 2^{n}}$,

т. е. вона зростає екпоненційно за $n$, а границя при $n\rightarrow \infty$ площі області, охопленої кривою $S_{n}$, становить $5/12$ квадрата (в Евклідовій метриці).

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

Крива Серпінського, кроки 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;  
  }

Наступний аплет на мові 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

Див. також

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

Література

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