Перегляд вихідного коду сторінки Крива Серпінського

{{unibox}}'''Криві Серпінського'''&nbsp;— це рекурсивно визначена послідовність неперервних замкнутих плоских [[фрактал]]ьних [[Крива|кривих]], відкритих [[Вацлав Серпінський|Вацлавом Серпінським]].

==Загальний опис==
Крива в границі при <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> квадрата (в Евклідовій метриці).
{| border="0"
| valign="top" |
[[Файл:Sierpinski-Curve-1.png|міні|200x200пкс|Крива Серпінського, перший крок]]
| valign="top" |
[[Файл:Sierpinski-Curve-2.png|міні|200x200пкс| Крива Серпінського, кроки 1 і 2]]
| valign="top" |
[[Файл:Sierpinski-Curve-3.png|міні|200x200пкс| Крива Серпінського, кроки від 1 до 3]]
|-
|}

== Використання кривої ==
Крива Серпінського корисна для деяких практичних застосувань, оскільки вона симетричніша, ніж інші криві, що заповнюють простір, які зазвичай розглядають. Наприклад, її використано як базис для швидкої побудови наближеного розв'язку [[Задача комівояжера|задачі комівояжера]] (пошук найкоротшого обходу заданих точок)&nbsp;— евристичний розв'язок полягає у відвідуванні точок у тій послідовності, в якій вони зустрічаються на кривій Серпінського{{Sfn|Platzman, Bartholdi|1989}}. Для здійснення потрібно два кроки. Спочатку обчислюється обернена позиція кожної точки, потім значення сортуються. Цю ідею використано для системи маршрутизації комерційних машин, яка базувалася тільки на картках [[Rolodex]]{{Sfn|Bartholdi|}}.

На основі кривої Серпінського можна реалізувати вібраторні або друковані конструкції антен<ref name="slyusarantenna3">{{Cite web|last=Слюсар|first=В.|title=Фрактальные антенны. Принципиально новый тип «ломаных» антенн. Часть 2.|website=Электроника: наука, технология, бизнес. — 2007. — № 6.|date=2007|pages=С. 82—89.|url=http://www.electronics.ru/files/article_pdf/0/article_611_312.pdf|accessdate=18 грудня 2020|archive-date=3 квітня 2018|archive-url=https://web.archive.org/web/20180403104208/http://www.electronics.ru/files/article_pdf/0/article_611_312.pdf}}</ref>.

== Побудова кривої ==
Крива, що заповнює простір, є неперервним відображенням [[Одиничний інтервал|одиничного інтервалу]] в одиничний квадрат і (псевдо) оберненим відображенням одиничного квадрата в одиничний інтервал. Один зі способів побудови псевдооберненого відображення такий. Нехай нижній лівий кут (0,&nbsp;0) одиничного квадрата відповідає 0.0 (і 1.0). Тоді верхній лівий кут (0,&nbsp;1) має відповідати 0.25, правий верхній кут (1,&nbsp;1)&nbsp;— 0.50, а нижній правий кут (1,&nbsp;0)&nbsp;— 0.75. Прообраз [[Внутрішня точка|внутрішніх точок]] обчислюється з використанням рекурсивної структури кривої. Нижче наведено функцію на Java, яка обчислює відносне положення будь-якої точки кривої Серпінського (тобто, псевдообернене значення). Функція приймає координати точки (x, y) і кути охоплювального прямокутного рівнобедреного трикутника (ax, ay), (bx, by) і (cx, cy) (Зауважимо, що одиничний квадрат є об'єднанням двох таких трикутників). Інші параметри визначають рівень точності обчислень.
<source lang="java">
  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;  
  }
</source>
Наступний [[аплет]] на мові [[Java]] малює криву Серпінського за допомогою чотирьох [[Взаємна рекурсія|взаємно рекурсивних]] методів (методів, що викликають один одного):
<source lang="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;
    }
}
</source>
Наступна програма на мові [[Logo (мова програмування)|Лого]] малює криву Серпінського з використанням [[Рекурсія|рекурсії]].
 <code>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</code>

 <code>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</code>

== Див. також ==
* [[Крива Гільберта]]
* [[Крива Коха]]
* [[Крива Мура]]
* [[Крива Пеано]]
* {{Не перекладено|Наконечник Серпінського|||Sierpiński arrowhead curve}}<!-- Проблема вікіфікації: Сторінка [[:en:Sierpiński arrowhead curve]] (→ [[:en:Sierpiński curve#Arrowhead curve]]) перекладена як [[Крива Серпінського]], хоча хотіли [[Наконечник Серпінського]] (SashkoR0B0T)-->
* {{Не перекладено|Список фракталів за розмірністю Гаусдорфа|||List of fractals by Hausdorff dimension}}
* [[Рекурсія (програмування)|Рекурсивна функція]]
* [[Трикутник Серпінського]]

== Примітки ==
{{Reflist}}

== Література ==
* {{Стаття|author=Loren K. Platzman, John J. Bartholdi III|ref=Platzman, Bartholdi|date=1989|title=Spacefilling curves and the planar traveling salesman problem|видання=Journal of the Association of Computing Machinery|том=36|issue=4|pages=719—737}}
* {{Стаття|author=John J. Bartholdi III|ref=Bartholdi|url=http://www.isye.gatech.edu/~jjb/mow/mow.html|title=Some combinatorial applications of spacefilling curves|publisher=[[Технологічний інститут Джорджії|Georgia Institute of Technology]]|видання=|archiveurl=https://archive.today/20120803004338/http://www.isye.gatech.edu/~jjb/mow/mow.html|archivedate=2012-08-03}}

{{Перекласти|en|дата=липень 2022}}

{{Криві}}

[[Категорія:Наука в Польщі]]
[[Категорія:Фрактальні криві]]