Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Из Википедии — свободной энциклопедии

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

Поскольку кривая Серпинского заполняет пространство, её размерность Хаусдорфа (в пределе при ) равна .
Евклидова длина кривой

равна ,

т. е. она растёт экспоненциально по , а предел при площади области, заключённой кривой , составляет квадрата (в евклидовой метрике).

Кривая Серпинского, первый шаг
Кривая Серпинского, шаги 1 и 2
Кривая Серпинского, шаги с 1 по 3

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

Кривая Серпинского полезна для некоторых практических приложений, поскольку она более симметрична по сравнению с другими обычно рассматриваемыми заполняющими пространство кривыми. Например, она использовалась в качестве базиса для быстрого построения приближённого решения задачи коммивояжёра (которая ищет кратчайший обход заданных точек) — эвристическое решение заключается в посещении точек в той последовательности, в какой они встречаются на кривой Серпинского[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

См. также

Примечания

  1. Platzman, Bartholdi, 1989.
  2. Bartholdi.
  3. Слюсар, В. Фрактальные антенны. Принципиально новый тип «ломаных» антенн. Часть 2. Электроника: наука, технология, бизнес. — 2007. — № 6. С. 82—89. (2007). Дата обращения: 22 апреля 2020. Архивировано 3 апреля 2018 года.

Литература

Эта страница в последний раз была отредактирована 15 сентября 2023 в 17:42.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).