Создание интерактивного макета. Задача упаковки кругов в круг. Метод отжига / forpes.ru

Главная
Создание интерактивного макета. Задача упаковки кругов в круг. Метод отжига

Создание интерактивного макета. Задача упаковки кругов в круг. Метод отжига +13

10.09.2025 22:12

AnnaLafleur 0 677 Источник

Я начала разработку интерактивного интерфейса для своего проекта «Florist». Центральным элементом сайта должен был стать интерактивный макет — с его помощью пользователь мог бы визуализировать различные цветочные дизайны, располагая в ячейках макета цветы из каталога. Я создала прототип, внедрила его в сайт и доработала окончательный дизайн до такой картинки:

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

Рассмотрим, как автоматически создаётся такой симпатичный макет круглой формы для любого выбранного числа. Сам макет состоит из внешней формы — большого круга и размещённых внутри него кругов-ячеек одинакового радиуса. Такие ячейки необходимо упаковать в форму наиболее плотным образом, избегая пересечений и пустот. Решение будет устремлено к оптимальному, при этом сохранит визуально приятное размещение, то есть, например, симметричное или зеркальное.

Постановка задачи. Аналитическое решение.

Подобная задача в математике носит название «Упаковка кругов в круг». Её целью является упаковка единичных кругов в как можно меньший круг. Ряд математиков доказали оптимальность или выдвинули гипотезы о ней для упаковок, содержащих вплоть до 20 внутренних кругов, что для меня исчерпывающе, так как я собираюсь ограничиться макетами из нечётного количества от 1 до 15 внутренних кругов. Ознакомимся с предложенными математиками решениями. Если они будут подходить под мои скромные желаемые параметры, то есть они будут симметричны, например, то эти решения станут ориентировочными для будущего кода — такие решения код должен будет выдать.

Приведу необходимый фрагмент таблицы из Рувики.

Все приведённые в таблице диаграммы удовлетворяют моим скромным запросам, а значит, все эти решения — потенциальные. Будем ориентироваться на них при доработке результатов кода, постараемся достичь именно такого вывода.

Cреднее значение плотности упаковки от 3 до 15 кругов примерно равно $71,1\%$ . Данные вычисления понадобятся для формирования ориентировочного понимания, какой примерно ответ код должен будет выдать.

Сформулируем условие задачи, решение которой будем искать с помощью алгоритма.

Известно, что существует n кругов одинакового радиуса r. Также существует круг — «контейнер», радиус которого равен R. Необходимо вписать n кругов внутри контейнера так, чтобы радиус контейнера был минимальным. Найти минимальный радиус контейнера и вычислить координаты оптимального размещения n внутренних кругов для $n = \{1,3,5,7,9,11,13,15\}$ . Построить диаграммы.

Перейдём к реализации алгоритма такой упаковки на JavaScript. Напишем код общим методом, который будет самостоятельно выстраивать нужные конфигурации для любого n.

Метод отжига.

Используем вероятностный метод отжига, решающий задачу оптимизации упаковки с помощью симуляции одноимённого физического процесса. Условные «частицы» внутри заданной области движутся быстро и хаотично наподобие атомов нагретого металла, на данном этапе они обладают огромным количеством энергии, после чего металл постепенно медленно охлаждают, движение частиц замедляется, и они занимают устойчивую позицию кристаллической решётки, то есть находят глобальный минимум энергии. Такой метод работает итеративно, то есть постепенно улучшая решение.

Для задачи упаковки такой метод значительно эффективен, так как при подборе решения возникает огромное количество локальных минимумов. Локальный минимум — это такое решение, которое алгоритм воспринимает как оптимальное, но делает это преждевременно. Алгоритм находит такую точку, в которой все решения вокруг менее оптимальны, чем в данной точке, и воспринимает эту позицию как итоговое решение, хотя на самом деле это некая «яма», за пределами которой есть глобальный минимум — самое оптимальное решение из существующих.

Применимо к нашей задаче, локальный минимум — это позиция круга, при которой общая упаковка вмещается в контейнер, казалось бы, «минимального» радиуса R, так как все решения в ближайшей местности приводят к увеличению радиуса R. Но на самом деле, если изучить больше пространства вокруг, то окажется, что оптимальная упаковка находится дальше и вмещается в действительно минимальный радиус R.

Частица не может знать, в каком минимуме она находится. Преимущество метода отжига заключается в том, что он позволяет частице продолжать поиск после нахождения локального минимума, что часто приводит к истинному решению, но не гарантирует его. Такое поведение обусловлено тем, что в первой фазе цикла частица двигается с огромной скоростью, проходя большую часть местности, и может ориентировочно выяснить обстановку. Входя во вторую фазу, где она уже двигается более медленно, она ищет окончательное решение и останавливается в глобальном минимуме.

Создание прототипа. Переменные и константы.

Для реализации метода необходимо задать следующие начальные значения:

Радиус r внутренних кругов.

unitRadius = 30

Значение 30 выбрано как среднее удобное. При значении 1, к примеру, вычисления алгоритма будут слишком малы, так как маленькие круги проходили бы маленькое расстояние и затрудняли бы подсчёты. Аналогично неудобно брать слишком большие значения, увеличивая тем самым вычислительную нагрузку для алгоритма.

Начальный радиус R внешнего контейнера.

containerRadius = unitRadius * Math.sqrt(n / 0.9)

Такая формула элементарно выводится, основываясь на плотности упаковки кругов. Площадь внутреннего круга равна $\pi r^2$ , площадь n таких кругов — $n \pi r^2$ . Для контейнера аналогично — $\pi R^2$ . Плотность упаковки вычисляется как отношение общей площади единичных кругов к площади контейнера:

$ρ = \frac{n \pi r^2}{\pi R^2} = n (\frac{r}{R})^2 ≈ 0.9$ $\frac{r}{R} ≈ \sqrt\frac{0.9}{n}$ $R ≈ r \sqrt\frac{n}{0.9}$

Я взяла заведомо слишком высокую плотность упаковки $90\%$ как начальную — это значит, что изначально все круги не смогут поместиться в контейнер и алгоритм будет постепенно увеличивать его радиус до оптимального.

Пустой массив для хранения минимального найденного значения R. Он будет сравнивать найденные R и оставлять каждый раз наименьшее значение, последнее будет считаться оптимальным.

bestContainerRadius = Infinity

Начальная температура — с неё начинается постепенное охлаждение.

let temperature = 2.0;

Значение температуры будет влиять на изначальную интенсивность перемещений частиц.

Коэффициент охлаждения, который определяет, как быстро будет уменьшаться температура с каждой итерацией. Такое значение принято брать чуть меньше 1. Чем ближе значение к 1, тем медленнее идёт охлаждение.

coolingRate = 0.9997

Потолок для количества итераций. Код не будет выполнять более 5000 итераций, что предостережёт алгоритм от перегрузки и торможения. Если код не справится за это время для некоторых n, то вместо того, чтобы увеличить максимальное количество итераций, более целесообразно будет усовершенствовать конкретную часть алгоритма, дать ему больше наводок, помогая достичь нужного результата. Тогда код не будет лишний раз проводить итерации для тех n, которым достаточно 5000.

maxIterations = 5000

За 5000 итераций температура от 2.0 спадёт до $2.0 \times 0.9997^{5000} \approx 0.446$ — такое значение оптимально низкое, чтобы система могла стабилизироваться на конечном этапе отжига. Значение, более приближенное к 0, не будет значительно изменять итоговую конфигурацию, так как изменения на низких температурах минимальны, и нет смысла доводить температуру вплотную до 0.

Наделение частицы физическими свойствами.

В роли частицы, наделённой физическими параметрами, будет выступать круг. Класс Ball задаст физические параметры для частицы: её координаты, радиус и начальную скорость velocity, равную 0.

constructor(x, y, radius) {
  this.r = radius;
  this.velocity = { x: 0, y: 0 };
  this.position = { x: x, y: y };
}

Стабилизируем скорость движения частицы, чтобы держать симуляцию под контролем. Скорость частицы определяется длиной вектора force. Длина вектора определяется по небезызвестной формуле Пифагора. Если результирующая скорость превышает 1, она нормализуется.

applyForce(force) {
    this.velocity.x += force.x;
    this.velocity.y += force.y;
    const speed = Math.sqrt(this.velocity.x * this.velocity.x + this.velocity.y * this.velocity.y);
    if (speed > 1.0) {
        this.velocity.x = (this.velocity.x / speed) * 1.0;
        this.velocity.y = (this.velocity.y / speed) * 1.0;
    }
}

Добавим обновление позиций кругов. Функция deterministicRandom будет генерировать случайный шум noise и добавлять его к скорости. Шум даёт небольшую волю кругам в движении, изъясняясь фигурально. Так круги избегают застревания в локальных минимумах.
Прибавим к позиции скорость и таким образом обновим позицию. Стоп, сложить позицию и скорость? Однако ошибки всё-таки здесь нет. В физике чтобы найти новую позицию, мы бы действовали по условной формуле:

$\text{x}_{t+1} = \text{x}_t + \text{$v$} \cdot \Delta t$

то есть сложили бы координату прошлой позиции и расстояние, на которое сдвинулась частица за промежуток времени $\Delta t$ , cократив тем самым мешающие секунды. Однако в данном случае интервал времени между шагами симуляции $\Delta t$ слишком мал и условно принят за 1, что упрощает итоговую формулу и позволяет таки сложить позицию и скорость.

update(seed, iter) {
    const noiseX = (deterministicRandom(seed, this.position.x * 1000 + iter) - 0.5) * 1.2;
	const noiseY = (deterministicRandom(seed, this.position.y * 1000 + iter + 1000) - 0.5) * 1.2;
    this.velocity.x += noiseX;
    this.velocity.y += noiseY;
    this.position.x += this.velocity.x;
    this.position.y += this.velocity.y;
    this.velocity.x *= 0.98;
    this.velocity.y *= 0.98;
}

1.2 — это масштаб шума, который определяет интенсивность случайных перемещений.
0.98 — коэффициент стабилизации, уменьшающий скорость на каждой итерации.

Симуляция физики.

С классом Ball разобрались, перейдём к классу Packer, то есть к тому самому методу отжига. Здесь генерируется значение шума, о котором я говорила ранее. Для его генерации добавим константу — начальное значение seed — оно будет псевдослучайным, что позволит нам контролировать каждое созданное случайное число, а соответственно, это значит, что код всегда будет выводить один и тот же результат, не подвергаясь неконтролируемой случайности.

seed = 12345 * n_circles

Генерировать шум будем в пределах 0 и 1, для этого удобно воспользоваться синусом как ограничителем.

deterministicRandom(seed, index) {
    const x = Math.sin(seed + index * 1000) * 10000;
    return x - Math.floor(x);
}

Принципиально важно внести в код проверку на отсутствие пересечений кругов. При физической симуляции такая проверка обеспечивает продолжение движения после столкновения частиц. Наличие пересечений легко проверить математически, сравнивая расстояние между центрами кругов с суммой их радиусов. При соприкосновении кругов минимальное значение равно двум радиусам. Такие вычисления необходимо провернуть в декартовой системе координат и воспользоваться снова небезызвестной формулой.

hasOverlaps(balls) {
    for (let i = 0; i < balls.length; i++) {
        for (let j = i + 1; j < balls.length; j++) {
            const dx = balls[i].position.x - balls[j].position.x;
            const dy = balls[i].position.y - balls[j].position.y;
            const d = Math.sqrt(dx * dx + dy * dy);
            if (d < balls[i].r + balls[j].r && d > 0) {
                return true;
            }
        }
    }
    return false;
}

Первая итерация.

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

this.iter++;

Добавим флаг, отслеживающий столкновения кругов. Если они всё-таки были, то флаг покажет true.

this.hasCollisions = false

Сбросим максимальную скорость до 0 как начальную.

this.maxVelocity = 0

Интегрируем в движение частиц шум noise, который будет добавляться к текущей позиции частицы на первых 2000 итерациях, то есть на начальной стадии отжига. Для большей уникальности воздействия шума зададим различные случайные значения смещения deterministicRandom по осям x и y.

if (this.iter < 2000) {
    for (let ball of this.balls) {
        const noiseX = (this.deterministicRandom(this.seed, ball.position.x * 1000 + this.iter) - 0.5) * 0.6;
        const noiseY = (this.deterministicRandom(this.seed, ball.position.y * 1000 + this.iter + 1000) - 0.5) * 0.6;
        ball.position.x += noiseX;
        ball.position.y += noiseY;
    }
}

Ограничения границ.

Добавим проверку выхода частицы за границы контейнера. Расстояние d от центра круга до текущей позиции вычислим так же с помощью небезызвестной формулы. Сумма расстояния до частицы d и её радиуса r не должна быть больше радиуса контейнера R.

Если частица выходит за пределы контейнера, нормализуем её вектор. Сделаем это с помощью объекта norm с нормализованными координатами центра. Эти координаты вычисляются путём деления текущей позиции частицы на d.

const d = Math.sqrt(ball.position.x * ball.position.x + ball.position.y * ball.position.y);

`
Деление на число не меняет направление вектора, поэтому такой вектор будет аналогично иметь направление от центра координат до положения частицы, однако его длина всегда будет равна 1:

$\sqrt{(\frac{x}{d})^2 + (\frac{y}{d})^2} = \sqrt{\frac{x^2}{d^2} + \frac{y^2}{d^2}} = \sqrt{\frac{x^2 + y^2}{d^2}} = \sqrt{\frac{d^2}{d^2}} = \sqrt{1} = 1$

Если , то есть частица находится в центре контейнера, то создадим альтернативу деления на 0.01, убирая потенциальное деление на 0. Вы можете со мной поспорить, утверждая, что «частица, находясь в центре контейнера, никак не сможет зайти за его пределы, потому что её радиус определённо меньше радиуса контейнера». С этим трудно не согласиться, однако проверка — это всего лишь подстраховка, потому что алгоритм, гипотетически оказавшись в такой ситуации, просто-напросто остановит симуляцию, а этого допустить нельзя.

Итак, как будет работать нормализующий вектор? Перемножим координаты вектора norm на с небольшой погрешностью 0.01. Так единичный вектор увеличится до длины , после чего умножение такого вектора на текущую координату переместит частицу на границу окружности радиусом .

Между вектором позиции ball.position и вектором скорости ball.velocity есть принципиальная разница. Вектор позиции направлен из центра координат, то есть центра контейнера, до текущей позиции частицы и имеет соответствующую длину $d=\sqrt{x^2+y^2}$ . С помощью вектора norm мы меняем длину ball.positon до нужной нам длины и, таким образом, частица перемещается на внутреннюю границу контейнера. Вектор скорости, в отличие от вектора позиции, исходит из центра самой частицы. Его длина равна текущей скорости частицы, а направление вектора соответствует направлению её движения.

Итак, перемещая саму частицу, также необходимо изменить направление её движения. Это можно сделать, умножив вектор скорости на отрицательное число, что задаст противоположное направление движения. Возьмём коэффициент -0.8, то есть зададим новую скорость, равную $80\%$ текущей и, тем самым, немного замедлим движение частицы.

Такое поведение математически имитирует столкновение частицы с границей контейнера.

if (d > this.containerRadius - ball.r) {
    const norm = {
        x: ball.position.x / (d || 0.01),
        y: ball.position.y / (d || 0.01)
    };
    ball.position.x = norm.x * (this.containerRadius - ball.r - 0.01);
    ball.position.y = norm.y * (this.containerRadius - ball.r - 0.01);
    ball.velocity.x *= -0.8;
    ball.velocity.y *= -0.8;
    this.hasCollisions = true;
}

Столкновение частиц.

От симуляции столкновения частиц с границей плавно перейдем к их столкновению между собой. Начнем с циклов — будем перебирать все пары частиц, каждую с каждой. Во внешнем цикле будем проверять каждую частицу под номером i. Чтобы избежать проверки частицы с самой собой, начнём вложенный цикл со смещением j на 1 от i. Это также поможет избежать проверки одной и той же пары из номеров, например, 1-2 и 2-1.

Выберем частицы i и j, вычислим расстояние между ними по аналогичной формуле:
$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$

for (let i = 0; i < this.balls.length; i++) {
    for (let j = i + 1; j < this.balls.length; j++) {
        const ball1 = this.balls[i];
        const ball2 = this.balls[j];
        const dx = ball1.position.x - ball2.position.x;
        const dy = ball1.position.y - ball2.position.y;
        const d = Math.sqrt(dx * dx + dy * dy);

Сравним его с суммой радиусов частиц и выясним факт пересечения. При этом добавим условие

, исключая потенциальное деление на 0 в будущем.

Создадим нормализующий вектор force, задающий направление отталкивания частиц. По аналогии с вектором norm, длина force всегда будет равна 1, что позволит масштабировать его до желаемой длины.

$\sqrt{(\frac{x_1-x_2}{d})^2 + (\frac{y_1-y_2}{d})^2} = \sqrt{\frac{(x_1 - x_2)^2+(y_1-y_2)^2}{d^2}} = \sqrt{\frac{d^2}{d^2}} = \sqrt{1} = 1$

В данном случае вектор исходит от первой частицы и направлен ко второй. Необходимо с помощью force сдвинуть обе частицы в противоположные стороны друг от друга. Одну частицу сдвинем с помощью force, а другую — с помощью отрицания force.

Расстояние, на которое круги заходят друг на друга, обозначим overlap. На расстояние overlap будем раздвигать круги, но не до момента касания, а чуть больше. Ровное устранение пересечения за одну итерацию приводит к нестабильности симуляции: частицы отодвигаются ровно до момента касания, что физически будет выглядеть как резкий скачок в конкретную точку касания, нам же необходимо сохранить плавность и постепенность симуляции.

const minDist = ball1.r + ball2.r;
if (d < minDist && d > 0) {
    this.hasCollisions = true;
    const overlap = minDist - d;
    const force = {
        x: dx / (d || 0.01),
        y: dy / (d || 0.01)
    };
    ball1.position.x += force.x * overlap * 0.8;
    ball1.position.y += force.y * overlap * 0.8;
    ball2.position.x -= force.x * overlap * 0.8;
    ball2.position.y -= force.y * overlap * 0.8;

Рассчитаем силу отталкивания forceMagnitude. Она должна различаться в зависимости от того, насколько сильно круги наложились друг на друга, то есть от overlap, а также от текущей температуры — это не связано напрямую, но работает косвенно: чем выше температура, тем больше частицы носятся по контейнеру, исследуя его. В таком случае сила отталкивания помогает частицам дальше отлететь после столкновения и, таким образом, изучить больше пространства. Эмпирически зададим коэффициент для прямо пропорциональной зависимости:

const forceMagnitude = overlap * 5.0 * (1.0 + temperature);
ball1.applyForce({
    x: force.x * forceMagnitude,
    y: force.y * forceMagnitude
});
ball2.applyForce({
    x: -force.x * forceMagnitude,
    y: -force.y * forceMagnitude
});

Завершаем цикл, немного охлаждая температуру и обновляя счётчик итераций. Так заканчивается первая итерация.

for (let ball of this.balls) {
    ball.update(this.seed + this.iter, this.iter);
}
temperature *= coolingRate;

Корректировки.

Метод finalizePositions() — это последний этап оптимизации расположения частиц, то есть окончательное устранение пересечений.

Введём счётчик итераций корректировки.

let adjustments = 0;

Начальный шаг, определяющий, как сильно будут перемещаться частицы после обнаружения пересечения. Изначально на половину overlap.

let step = 0.5;

Ограничим число итераций.

const maxAdjustments = 3000;

Продублируем логику столкновения частиц между собой и с границей контейнера. При этом будем уменьшать шаг корректировки на 0.999 на каждой итерации с шагом 0.1, пока пересечение не будет устранено.

if (!hasOverlap) break;
    adjustments++;
    step = Math.max(0.1, step * 0.999);

Финальная отладка.

Итак запустим наш прототип, пока что без финальной отрисовки.

Как мы можем видеть, большинство упаковок достигли оптимальности, однако остались проблемы с конфигурациями для и , вероятно, магнитные бури.
Для явно зададим круг в центре, а остальные круги расположим на окружности радиусом , согласно данным из Рувики.

Полная окружность контейнера описывает , то есть $2\pi$ радиан, тогда при размещении на ней 8-ми кругов с одинаковым интервалом угол между соседними кругами будет равен $\frac{2\pi}{8}=\frac{\pi}{4}$ , а каждый i-ый круг будет расположен под углом $\frac{\pi i}{4}$ . Чтобы описать положение частицы с помощью угла и радиуса, нужно перейти из декартовой в полярную систему координат с помощью такой формулы:

$\begin{cases}x = r⋅cosφ\\y = r⋅sinφ\end{cases}$

В данном случае r — это обозначение расстояния от точки до полюса, в нашем контексте это не r, а . Тогда координаты кругов будут равны:

$\begin{cases}x = 2.613r⋅cos\frac{\pi i}{4} \\ y = 2.613r⋅sin\frac{\pi i}{4}\end{cases}$

createSpecialConfiguration(n) {
    if (n === 9) {
        let newBalls = [];
        newBalls.push(new Ball(0, 0, unitRadius));
        const outerRadius = unitRadius * 2.613;
        for (let i = 0; i < 8; i++) {
            const angle = (i * Math.PI) / 4;
            const x = Math.cos(angle) * outerRadius;
            const y = Math.sin(angle) * outerRadius;
            newBalls.push(new Ball(x, y, unitRadius));
        }
        return newBalls;
    } 
}

Для нужно создать похожую конфигурацию: 3 круга в центре, а остальные на окружности радиусом . Центры 3-х кругов образуют равносторонний треугольник, а на окружности, которая его описывает, мы как раз и расположим 3 наших круга. Радиус такой окружности вычисляется по формуле $R = \frac{a}{\sqrt3}$ , где a — это сторона треугольника, то есть 2r. Тогда $R = \frac{2r}{\sqrt3}=1.1547r$ . Добавим также смещение на $\frac{\pi}{6}$ .

else if (n === 13) {
    const outerCount = n - 3;
    const innerCount = 3;
    const outerRadius = unitRadius * 3.236;
    const innerRadius = unitRadius * 1.1547;
    let newBalls = [];
    for (let i = 0; i < outerCount; i++) {
        const angle = (i * 2 * Math.PI) / outerCount;
        const x = Math.cos(angle) * outerRadius;
        const y = Math.sin(angle) * outerRadius;
        newBalls.push(new Ball(x, y, unitRadius));
    }
    for (let i = 0; i < innerCount; i++) {
        const angle = (i * 2 * Math.PI) / innerCount + Math.PI/6;
        const x = Math.cos(angle) * innerRadius;
        const y = Math.sin(angle) * innerRadius;
        newBalls.push(new Ball(x, y, unitRadius));
    }
    return newBalls;
}
return [];

Сравним результаты теперь.

Всё совпало, значит алгоритм готов, осталось довести до ума финальную отрисовку.

Отрисовка.

Функция drawFlowers(n) берёт результаты работы Packer, то есть список координат внутренних кругов, и рисует их в векторном формате .svg, включая сам контейнер, само собой. Если пользователем выбрана форма «круг», то в пустой контейнер рисуем найденную в Packer упаковку кругов.

svg.innerHTML = '';
if (currentShapeIndex !== 0) return;
const packer = new Packer(n);

Ширина и высота контейнера известны как 2bestContainerRadius. В настройках позиционирования добавим ширину контейнера, ограниченную $70\%$ ширины экрана, а высоту — $80\%$ с учетом отступов margin. Адаптивность определим с помощью zoom, обозначив сохранение пропорций так, чтобы максимальная ширина и высота были пропорциональны текущим. Соответственно, область видимости с учётом всего будет равна w * zoom + margin * 2 по ширине и высоте аналогично. С помощью border зададим параметры внешнего круга-контейнера: центр в начале координат, ширину и радиус. Декоративные эффекты в виде толщины обводки тоже добавим.

const w = bestContainerRadius * 2;
const h = w;
const margin = 20;
const maxWidth = window.innerWidth * 0.7 - margin * 2;
const maxHeight = window.innerHeight * 0.8 - margin * 2;
const zoom = Math.min(maxWidth / w, maxHeight / h);
const strokeWidth = 4;
const border = {
    x: 0,
    y: 0,
    width: w,
    height: h,
    cx: w / 2,
    cy: h / 2,
    r: w / 2
};
const viewBoxWidth = w * zoom + margin * 2;
const viewBoxHeight = h * zoom + margin * 2;

С помощью setAttribute установим ту самую область видимости в масштабируемых единицах. А также зададим preserveAspectRatio и xMidYMid meet для сохранения пропорций и центрирования при масштабировании страницы.

svg.setAttribute('viewBox', `0 0 ${viewBoxWidth} ${viewBoxHeight}`);
svg.setAttribute('preserveAspectRatio', 'xMidYMid meet');
const contentGroup = document.createElementNS("http://www.w3.org/2000/svg", "g");

URL http://www.w3.org/2000/svg не ведёт на реальную страницу в интернете, напротив, это стандартный атрибут, указывающий на то, что мы работаем именно с пространством имён svg-элементов.

Приступим к самой отрисовке. Воспользуемся параметрами из border, чтобы создать область, где будет изображение, её центр совпадёт с центром внешнего круга «контейнера», который, в свою очередь, очертим только контуром stroke цвета #fedfd7 без заливки fill .

const borderCircle = document.createElementNS("http://www.w3.org/2000/svg", "circle");
borderCircle.setAttribute("cx", (border.cx * zoom + margin).toString());
borderCircle.setAttribute("cy", (border.cy * zoom + margin).toString());
borderCircle.setAttribute("r", (border.r * zoom).toString());
borderCircle.setAttribute("fill", "none");
borderCircle.setAttribute("stroke", "#fedfd7");
borderCircle.setAttribute("stroke-width", strokeWidth.toString());
borderCircle.setAttribute("pointer-events", "none");
contentGroup.appendChild(borderCircle);

Внутренние круги нарисуем чуть более детально. Из packer.list возьмём полученные алгоритмом координаты центров внутренних кругов и масштабируем с учётом отступов, итоговые координаты обозначим . Для них необходимо добавить смещение, чтобы таким образом из системы координат Packer перейти в систему координат svg. В Packer центр координат находится в центре контейнера, относительно этой точки ориентированы координаты каждого круга, а в svg стандартно центр находится в верхнем левом углу, из которого ось x уходит вправо, а ось y — вниз.

Каждый круг будет иметь контур того же цвета, что и у контейнера, а также заливку цвета #fd8264.

packer.list.forEach((circle) => {
    const cx = (circle.c.x + w / 2) * zoom + margin;
    const cy = (circle.c.y + h / 2) * zoom + margin;
    const radius = circle.r * zoom;
    const circleEl = document.createElementNS("http://www.w3.org/2000/svg", "circle");
    circleEl.setAttribute("cx", cx.toString());
    circleEl.setAttribute("cy", cy.toString());
    circleEl.setAttribute("r", radius.toString());
    circleEl.setAttribute("fill", "#fd8264");
    circleEl.setAttribute("stroke", "#fedfd7");
    circleEl.setAttribute("stroke-width", strokeWidth.toString());
    contentGroup.appendChild(circleEl);
});

В центре каждого круга будет расположен знак «+», призывающий к нажатию. Соответственно, нужно нарисовать две перпендикулярные линии: горизонтальную line1 и вертикальную line2 от до . Длина линий будет равна .

const plusSize = radius * 0.4;
const line1 = document.createElementNS("http://www.w3.org/2000/svg", "line");
line1.setAttribute("x1", (cx - plusSize / 2).toString());
line1.setAttribute("y1", cy.toString());
line1.setAttribute("x2", (cx + plusSize / 2).toString());
line1.setAttribute("y2", cy.toString());
line1.setAttribute("stroke", "#fedfd7");
line1.setAttribute("stroke-width", strokeWidth.toString());
line1.setAttribute("stroke-linecap", "round");
line1.setAttribute("pointer-events", "none");
contentGroup.appendChild(line1);

const line2 = document.createElementNS("http://www.w3.org/2000/svg", "line");
line2.setAttribute("x1", cx.toString());
line2.setAttribute("y1", (cy - plusSize / 2).toString());
line2.setAttribute("x2", cx.toString());
line2.setAttribute("y2", (cy + plusSize / 2).toString());
line2.setAttribute("stroke", "#fedfd7");
line2.setAttribute("stroke-width", strokeWidth.toString());
line2.setAttribute("stroke-linecap", "round");
line2.setAttribute("pointer-events", "none");
contentGroup.appendChild(line2);

Теперь посмотрим, что получилось.

Демонстрационная страница: PackingCircles
Код страницы: PackingCircles.html
Больше о проекте в тг: LafleurDesignProjects