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

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

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

<math> S_n </math> равна <math> l_n = {2 \over 3} (1+\sqrt 2) 2^n - {1 \over 3} (2-\sqrt 2) {1 \over 2^n} </math>,

т. е. она растёт экпоненциально по <math> n </math>, а предел при <math>n \rightarrow \infty </math> площади области, заключённой кривой <math> S_n </math>, составляет <math> 5/12 </math> квадрата (в Евклидовой метрике).

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

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

Заполняющая пространство кривая является непрерывным отображением единичного интервала в единичный квадрат и (псевдо) обратным отображением единичного квадрата в единичный интервал. Один из способов построения псевдообратного отображения следующий. Пусть нижний левый угол (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 рисует кривую Серпинского с помощью четырёх взаимно рекурсивных^[en] методов (методов, вызывающих друг друга):

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

См. также

Напишите отзыв о статье "Кривая Серпинского"

Примечания

↑ Platzman, Bartholdi, 1989.
↑ Bartholdi.

Литература

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 [www.isye.gatech.edu/~jjb/mow/mow.html Some combinatorial applications of spacefilling curves]. — Georgia Institute of Technology.

[Platzman.2C_Bartholdi.E2.80.941989.E2.80.94.E2.80.94-1] Platzman, Bartholdi, 1989.

[Bartholdi.E2.80.94.E2.80.94.E2.80.94-2] Bartholdi.

[1]

[2]

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

Содержание

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

Рисование кривой

См. также

Напишите отзыв о статье "Кривая Серпинского"

Примечания

Литература

Отрывок, характеризующий Кривая Серпинского

Навигация

Персональные инструменты

Поиск

Навигация

Инструменты

На других языках