Треугольник Серпинского — фрактал, математическое описание которого опубликовал польский математик Вацлав Серпинский в 1915 году.

В этом посте мы напишем рекурсивный алгоритм отрисовки данного известного фрактала в canvas с помощью JS

Какой кистью будем рисовать?

Основой всего будет HTML, в котором будет находиться дочерний элемент в виде canvas. Размером он будет в 1000x1000 пикселей, хотя также будет возможность увеличивать данное значение вплоть до 8к

В роли художника у нас выступает JavaScript. В нем мы напишем рекурсивный алгоритм, основывающийся на Игре Хаоса. Он будет размером всего-лишь чуть больше 20 строк.

Стили будут присутствовать, но разве что для красоты. Можно обойтись и без них.

Логика отрисовки:

У нас имеется белый холст в котором нужно обозначить три координаты — ABC (вершины треугольника)

Задаем начальную вершину. Допустим это будет C

Выбираем случайную вершину. Возьмем A

Проводим между ними линию и ставим точку по центру

Вновь выбираем случайную вершину. Пусть будет B

Проводим линию с предыдущей точки

Ставим новую точку по центру

Повторяем эти действия несколько сотен раз и мы получим первые отрисовки фрактала

Приступим к коду

Прописываем базовый HTML код, подключаем к нему .css и .js файл.

Задаем серый фон для body:

body {
    background-color: rgb(40, 40, 40); /* Чтоб красиво было :D */
}

Внутри body создаем элемент canvas, даем ему размеры 1000x1000 пикселей и белый фон:

<canvas width="1000" height="1000"></canvas>

canvas {
    background-color: white;
}

Чтоб мы знали нынешнюю итерацию и количество точек на экране, также пропишем следующее:

<span>Точек на экране: 0</span>

span {
    position: absolute; /* Прижимаем текст к левому-нижнему углу экрана */
    right: 0;
    bottom: 0;
    font-size: 30px; /* Задаем размер и цвет текста */
    color: white;
}

Пишем JS скрипт:

Для начала нужно получить сам canvas и его содержимое:

let canvas = document.querySelector('canvas') // Получаем canvas в виде DOM-элемента
let ctx = canvas.getContext('2d'); // Получаем его контекст (содержимое)

Обозначим вершины в виде матрицы (двумерного массива) с координатами:

Дабы не мучиться с координатами при изменении размера холста, лучше будем сами получать их с помощью .getBoundingClientRect()

let cornerCords = [ // Координаты в виде X = ширина, Y = высота
    [canvas.getBoundingClientRect().width / 2, 0], // Получаем ширину холста и делим ее на 2, тем самым находим центр (вершина А)
    [0, canvas.getBoundingClientRect().height], // Получаем только высоту холста и находим вершину B
    [canvas.getBoundingClientRect().width, canvas.getBoundingClientRect().height] // Получаем и высоту, и ширину холста, найдя вершину C
]

Если все переменные заменить на цифры, а холст будет размером в 1000х1000, то получитcя такой результат:

let cornerCords = [
    [500, 0], 
    [0, 1000], 
    [1000, 1000]
]

Теперь мы можем изменять размер холста как захотим, а треугольник несмотря на это, будет правильно отображаться

Переходим к рекурсии

Прописываем обычную функцию с именем RecursionDrawing:

function RecursionDrawing() {}

Как мы помним, перед началом нужно определиться с начальной вершиной, пусть будет A

Чтобы дать функции понять это, будем передавать параметр в виде массива, который достаем из матрицы координат:

function RecursionDrawing(previousDotCords) {
  // Функция теперь принимает координаты и обозначает их в виде переменной previousDotCords
} 

RecursionDrawing(cornerCords[0])

Внутрь функции прописываем setTimeout() (задержка), дабы не ловить ошибку:

function RecursionDrawing() {
  setTimeout(function () {}, 0) // Задержка 0мс, этого хватит
}

RecursionDrawing(cornerCords[0])

После обозначения начальной точки, нужно выбрать случайную вершину

Воспользуемся некоторыми манипуляциями со встроенной библиотекой Math:

function RecursionDrawing() {
  setTimeout(function () {
    let randomCorner = Math.floor(Math.random() * cornerCords.length)
    // Math.random() дает случайное дробное число (float) от 0 до 1
    // Умножая это значение на длину массива мы получаем случайное дробное число
    // Округляем с помощью Math.floor() и получаем случайное полное число (int)
    // Тем самым получаем случайное число (в нашем случае от 0 до 2, A-B-C)
    
  }, 0)
}

RecursionDrawing(cornerCords[0])

Начинаем работу с canvas:

function RecursionDrawing(previousDotCords) {
    setTimeout(function () {
        let randomCorner = Math.floor(Math.random() * cornerCords.length)

        ctx.beginPath() // Открываем путь 
        ctx.fillStyle = "black" // Цвет заполнения, в нашем случае черный (также поддерживает hsl, rgb, hex)
        
        ctx.closePath() // Закрываем путь
      }, 0)
  }

Теперь рисуем саму точку:

X = (X-случайной вершины + X-предыдущей точки) / 2

Y = (Y-случайной вершины + Y-предыдущей точки) / 2

Также укажем размеры точки: (1, 1)

// В JS будет выглядеть так
(cornerCords[randomCorner][0] + previousDotCords[0]) / 2, (cornerCords[randomCorner][1] + previousDotCords[1]) / 2, 1, 1)

Вставляем это в основной код:

function RecursionDrawing(previousDotCords) {
    setTimeout(function () {
        let randomCorner = Math.floor(Math.random() * cornerCords.length)

        ctx.beginPath()
        ctx.fillStyle = "black"
      
        // ctx.fillRect() — Заполняет указанную область принимая: (x, y, width, height)
        ctx.fillRect((cornerCords[randomCorner][0] + previousDotCords[0]) / 2, (cornerCords[randomCorner][1] + previousDotCords[1]) / 2, 1, 1)
      
        ctx.closePath()
      }, 0)
  }

Запускаем рекурсию, указывая в конце кода саму функцию и передавая координаты новой точки:

function RecursionDrawing(previousDotCords) {
    setTimeout(function () {
        let randomCorner = Math.floor(Math.random() * cornerCords.length)

        ctx.beginPath()
        ctx.fillStyle = "black"
        ctx.fillRect((cornerCords[randomCorner][0] + previousDotCords[0]) / 2, (cornerCords[randomCorner][1] + previousDotCords[1]) / 2, 1, 1)
        ctx.closePath()

        // Передаем тоже самое, что и в ctx.fillRect(), но без width и height (1, 1)
        RecursionDrawing([(cornerCords[randomCorner][0] + previousDotCords[0]) / 2, (cornerCords[randomCorner][1] + previousDotCords[1]) / 2])
      }, 0)
  }

Осталось лишь посчитать кол-во точек

Вне функции объявляем переменную iteration:

let iteration = 0

Теперь до вызова рекурсии мы должны прописать следующее:

let iteration = 0
function RecursionDrawing(previousDotCords) {
    setTimeout(function () {
        let randomCorner = Math.floor(Math.random() * cornerCords.length)

        ctx.beginPath()
        ctx.fillStyle = "black"
        ctx.fillRect((cornerCords[randomCorner][0] + previousDotCords[0]) / 2, (cornerCords[randomCorner][1] + previousDotCords[1]) / 2, 1, 1)
        ctx.closePath()

        iteration++ // К iteration прибавляем +1
        // Получаем наш span и заменяем его содержимое
        document.querySelector('span').innerText = `Точек на экране: ${iteration}` 
      
        RecursionDrawing([(cornerCords[randomCorner][0] + previousDotCords[0]) / 2, (cornerCords[randomCorner][1] + previousDotCords[1]) / 2])
      }, 0)
  }

Чтож, осталось лишь собрать все вместе

Весь код:

HTML:

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <link rel="stylesheet" href="style.css">
</head>
<body>
    <canvas width="1000" height="1000"></canvas>
    <span>Точек на экране: 0</span>

    <script src="script.js"></script>
</body>
</html>

CSS:

body {
    background-color: rgb(40, 40, 40);
}
canvas {
    background-color: white;
}
span {
    position: absolute; 
    right: 0;
    bottom: 0;
    font-size: 30px;
    color: rgb(255, 255, 255);    
}

JS:

let canvas = document.querySelector('canvas')
let ctx = canvas.getContext('2d');

let cornerCords = [
    [canvas.getBoundingClientRect().width / 2, 0], 
    [0, canvas.getBoundingClientRect().height], 
    [canvas.getBoundingClientRect().width, canvas.getBoundingClientRect().height]
]

let iteration = 0
function RecursionDrawing(previousDotCords) {
    setTimeout(function () {
        let randomCorner = Math.floor(Math.random() * cornerCords.length)

        ctx.beginPath()
        ctx.fillStyle = "black"
        ctx.fillRect((cornerCords[randomCorner][0] + previousDotCords[0]) / 2, (cornerCords[randomCorner][1] + previousDotCords[1]) / 2, 1, 1)
        ctx.closePath()

        iteration++
        document.querySelector('span').innerText = `Точек на экране: ${iteration}`

        RecursionDrawing([(cornerCords[randomCorner][0] + previousDotCords[0]) / 2, (cornerCords[randomCorner][1] + previousDotCords[1]) / 2])
    }, 0)
}

RecursionDrawing(cornerCords[0])

Спасибо за прочтение данного поста.

CodePen: https://codepen.io/Saman2789/pen/vYQEGNV

Буду благодарен, если посетите мой телеграм канал: https://t.me/blg_projects