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

Ранее я уже рассказывала, как создать такой макет круглой формы, теперь настало время разобраться с квадратной и прямоугольной, ведь такие букеты сейчас в моде, не правда ли?

Формулировка задачи. Ориентировочные решения.

Как вы успели заметить, макет состоит из внешней формы и внутренних круглых ячеек одинакового радиуса. В качестве внешней формы в этот раз рассмотрим угловатые фигуры, а именно квадрат и прямоугольник.

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

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

Итак, нам нужны только нечетные упаковки от 1 до 15, ведь у нас не принято дарить букеты из четного количества цветов.

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

При этом, важно отметить, что в условиях данной задачи стороны прямоугольника не могут быть равны, тем самым образуя квадрат. Было бы странно, если бы пользователь на первом этапе создания букета выбрал прямоугольную форму из 9 цветов, а на следующем шаге увидел бы квадрат 3×3, так как алгоритм посчитал такое соотношение сторон оптимальным. Поэтому будем чётко различать квадратную форму и прямоугольную.

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

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

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

Аналитические решения для таких условий достаточно просто прикинуть без расчётов:

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

Для выбрана уже другая упаковка, так как число 15 стало единственным, разложимым на множители

. Это позволило расположить круги проще всего — рядами. Такие упаковки для данных задач чаще всего используются во флористике.

Жадный алгоритм.

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

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

Будем действовать так же, как это делал бы жадный алгоритм — до каждой промежуточной точки, то есть локально, будем выбирать кратчайший путь. Тогда у нас получится путь А → В → Д → И → К, длина которого равна . Решило ли это глобальную задачу поиска кратчайшего пути? Давайте проверим. Существует путь, например, A → Б → Д → И → К, длина которого равна , что оказалось короче найденной алгоритмом длины. Вот такой вот шустрый, но недальновидный алгоритм.

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

Но что означает применение жадного алгоритма по отношению к задаче упаковки кругов? А именно то, что алгоритм будет выбирать позицию для нового круга, ориентируясь только на позиции ближайших кругов и не будет оценивать всю расстановку в целом. То есть код будет решать задачу оптимальности только на небольших независимых участках, что и означает решать задачу локально. Но как, даже локально, разместить круги максимально плотно? Что будет являться одним шагом для алгоритма? Максимально плотное размещение двух кругов — это касание. Но для двух кругов количество вариантов касаний бесконечно, тогда что насчёт трёх кругов? Как раз здесь это возможно: если известно расположение двух кругов, то третий круг будет касаться обоих одновременно только в двух случаях. Эту идею и реализуем далее после того, как разберёмся с вводными данными.

Разработка программ. Вводные данные.

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

Начнём с класса Point, который будет создавать точку с координатами .

class Point {
    constructor(x, y) {
        this.x = x;
        this.y = y;
    }
}

В отдельном классе Circle создадим круг, задав его радиус и центр с помощью точки класса Point. Будем считать, что радиус каждого круга фиксирован, в таком случае параметром для минимизации будет либо сторона квадрата, либо стороны прямоугольника.

class Circle {
    constructor(radius, center) {
        this.r = radius;
        this.c = center;
    }
}

Так, а зачем мы разделили создание круга на два класса? Дело в том, что класс Point создаёт точку не только как часть окружности, но и как самостоятельное звено, например, чтобы расположить круги в углах, нужно вычислить только координаты центров кругов, в то время как радиус не задействован в вычислениях и просто бы таскался вместе с точкой. Конечно, это не критично, но разделение классов позволит сделать код более читаемым, так как будет сразу видно, где вычисления относятся к точке, а где к кругу.

Класс Packer создаст массив this.circles, который будет хранить n радиусов единичных кругов. Параметр this.ratio зафиксирует соотношение сторон 1:1 для внешней квадратной формы. То есть для квадрата действительна формула . Также здесь будем вызывать метод минимизации площади solve. Минимизация будет обеспечиваться так: метод solve будет многократно вызывать метод compute, занимающийся первоначальной упаковкой кругов, далее solve выберет упаковку с наименьшей площадью и сохранит её в this.list, после чего при необходимости отсюда её возьмут другие методы, доводящие упаковку до финальной стадии.

class Packer {
    constructor(n_circles) {
        this.circles = Array(n_circles).fill(1);
        this.ratio = 1; // Квадратная форма
        this.list = this.solve(n_circles);
    }
}

Внутри класса Packer реализуем основной метод упаковки compute c помощью вышеупомянутого жадного алгоритма. Но к жадному алгоритму перейдём не сразу, а начнем с того, что опишем математически нашу рабочую область, то есть внешний квадрат или прямоугольник. Чтобы вычислить сторону w квадрата или прямоугольника нам необходимо первоначальное значение площади surface — оно определяется в методе solve, к которому мы перейдём позднее. С помощью значения площади вычислим сторону квадрата или прямоугольника с помощью обобщённой формулы:

let w = this.w = Math.sqrt(surface * this.ratio);
let h = this.h = w; // Квадратная область
let h = this.h = w / ratio; // Прямоугольная область

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

let bounding_r = Math.sqrt(surface) * 100;

Дуги этих кругов благодаря огромному масштабу будут приближены к прямой линии границы квадрата. Такое явление называется аппроксимацией — замена сложной функции более простой, близкой к исходной.

Запишем в массив placed координаты каждой границы. Например, правая граница — это отрезок от до , тогда в массив для неё запишем значения , соответствующие координатам .

let placed = [];
placed = [
    bounding_circle(w/2, h/2, w/2, -h/2), // правая граница
    bounding_circle(w/2, -h/2, -w/2, -h/2), // нижняя граница
    bounding_circle(-w/2, -h/2, -w/2, h/2), // левая граница
    bounding_circle(-w/2, h/2, w/2, h/2) // верхняя граница
];

С помощью данного массива в функции bounding_circle вычислим координаты больших кругов, выполняющих роль границ. Центр такого круга должен быть смещён на bounding_r от центра границы. Середина границы находится в точке , а смещение по y необходимо, если середина границы находится в точке с и наоборот. То есть если , то при положительном смещение будет вправо, а при отрицательном влево, и наоборот.

function bounding_circle(x0, y0, x1, y1) {  
    let cX = (x0 + x1) / 2 + (x0 === x1 ? (x0 > 0 ? bounding_r : -bounding_r) : 0);
    let cY = (y0 + y1) / 2 + (y0 === y1 ? (y0 > 0 ? bounding_r : -bounding_r) : 0);
    return new Circle(bounding_r, new Point(cX, cY)); 
}

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

Размещение кругов в области.

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

function in_rect(radius, center) { 
	if (center.x - radius < -w / 2) return false; 
	if (center.x + radius > w / 2) return false; 
	if (center.y - radius < -h / 2) return false; 
	if (center.y + radius > h / 2) return false; 
	return true; 
}

А прямоугольник расположим в положительной координатной четверти, но учтём, что ось y будет направлена вниз, как это принято в компьютерной графике. В дальнейшем при отрисовке это упростит расчёты.

function in_rect(radius, center) { 
	if (center.x - radius < 0) return false;
	if (center.x + radius > w) return false; 
	if (center.y - radius < 0) return false; 
	if (center.y + radius > h) return false; 
	return true;
}

Далее в функции corner определим размещение нового круга относительно двух других размещённых ранее — с1 и с2. Чтобы новый круг касался c1, нужно чтобы расстояние между их центрами было равно сумме их радиусов. Аналогично и с c2. Тогда чтобы новый круг касался их обоих, нужно, чтобы выполнялись сразу оба условия:

Тогда задача сводится к поиску пересечения между двумя увеличенными окружностями радиусом и . Заметим, что таких пересечений два с обеих сторон, а одно необходимое будет выбирать следующий метод compute.

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

Найдём расстояние между центрами c1 и c2, которое будет являться локальной осью y. На ней расположим точку, через которую построим перпендикуляр — ось x. И на этой оси на нужном расстоянии отметим центр новой окружности. Это расстояние запросто посчитаем из прямоугольного треугольника по теореме Пифагора.

Итак, вычислим для начала расстояние A между c1 и c2. Для этого найдём длину вектора u, направленного от центра круга c1 к центру c2. Формулы вынесем в класс Point, чтобы не прописывать их каждый раз, а просто вызывать vect() для создания вектора и norm() для вычисления его длины:

vect(p) { return new Point(p.x - this.x, p.y - this.y); }
norm() { return Math.sqrt(this.x * this.x + this.y * this.y); }

И используем их в corner:

function corner(radius, c1, c2) {
    let u = c1.c.vect(c2.c);
    let A = u.norm();

Далее нам необходимо вычислить расстояние x, которое мы отложим от точки c1, чтобы провести ось x. Рассмотрим треугольник, вершинами которого являются центры кругов, он обозначен на рисунке выше. Обозначим , и y — высота. Тогда по теореме Пифагора:

Вычтем из первого уравнения второе и выразим искомое x:

И не забудем о том, что круги c1 и c2 не должны быть слишком далеко друг от друга. То есть расстояние между ними не должно быть больше — случая, когда три круга расположены в ряд.

if (A > B + C) return [];

Итак, мы нашли расстояние x, теперь отложим его на отрезке А и поставим на этом месте точку base. Для этого уменьшим вектор u до единичного размера, а затем масштабируем до длины x. Тогда он будет указывать на точку base.

Чтобы уменьшить вектор u длиной А до единицы, нужно поделить его на А соответственно. Вынесем стандартный метод масштабирования вектора mult() в класс Point, а чтобы переместить точку на вектор добавим метод add().

mult(a) { return new Point(this.x * a, this.y * a); }
add(p) { return new Point(this.x + p.x, this.y + p.y); }

Так как метод mult() предусматривает только умножение, то заменим деление на А умножением на .

u = u.mult(1 / A);
let base = c1.c.add(u.mult(x));

Теперь из точки base в перпендикулярном направлении отложим точки p1 и p2 на расстоянии , исключая его возможные отрицательные значения. Теперь можно создать круги в этих центрах и добавить их в список res при условии, что они не выходят за границы, конечно.

let y = Math.sqrt(Math.max(0, B * B - x * x));
let p1 = new Point(base.x - u.y * y, base.y + u.x * y);
let p2 = new Point(base.x + u.y * y, base.y - u.x * y);
let res = [];
if (in_rect(radius, p1)) res.push(new Circle(radius, p1));
if (in_rect(radius, p2)) res.push(new Circle(radius, p2));
return res;

Вспомним, что для прямоугольника у нас нет границ, созданных из больших кругов и границы обозначены классическими прямыми. Это означает, что для начала упаковки кругов в прямоугольнике нет стартового капитала, ведь для работы вышеупомянутого алгоритма необходимо иметь изначально минимум два круга. В таком случае вместо того, чтобы изобретать новые функции, просто воспользуемся аналитическим условием, которое я упоминала ранее:

Круги в углах — первые 4 круга изначально будут расположены в углах прямоугольника, что станет отправной точкой для алгоритма.

if (this.n_circles >= 5) {
    placed = [
        new Circle(r, new Point(r, r)), // Левый верхний
        new Circle(r, new Point(w - r, r)), // Правый верхний  
        new Circle(r, new Point(r, h - r)), // Левый нижний
        new Circle(r, new Point(w - r, h - r)) // Правый нижний
    ];
}

Выбор оптимального размещения.

Сейчас мы рассмотрели размещение одного нового круга относительно двух уже размещённых, но что, если у нас размещено уже три круга? Тогда относительно двух каких размещать четвертый? Эту задачу и должен решать жадный алгоритм.

Для начала нам нужен массив unplaced, в котором будут храниться все неразмещённые круги. Этот массив будет простой копией исходного массива this.circles, из которого будут постепенно удаляться значения, пока их количество не достигнет 0. Создадим также множества, в которых будут сохраняться индекс каждого круга и координаты его лучшей позиции.

let unplaced = this.circles.slice(0);
while (unplaced.length > 0) {
    let lambda = {};
    let circle = {};	

Будем перебирать каждый элемент массива, то есть каждый неразмещённый круг, и попутно обозначим первоначальный минимум lambda_min для расстояния между кругами. Это значение зададим космически огромным и будем использовать его в качестве точки отсчёта. Первое вычисленное расстояние будет гарантированно меньше lambda_min, заменит его и так далее после многократных сравнений проявится реальный минимум. Аналогично и для lambda, где будет храниться максимальное значение плотности.

    for (let i = 0; i < unplaced.length; i++) {
        let lambda_min = 1e10;
        lambda[i] = -1e10;

Для каждого неразмещённого круга будем перебирать все возможные пары двух уже размещённых кругов из placed. Для этих двух кругов вычислим ближайшее положение текущего неразмещённого круга с помощью разобранной нами ранее функции corner. Так как таких положений может быть до двух, запишем их в массив corners и проверим каждое на валидность. То есть проверим, не будет ли новый круг пересекать уже существующие, вычислив для этого расстояние между границами кругов. Это можно сделать, воспользовавшись формулой , вынесенной в класс Circle.

        for (let j = 0; j < placed.length; j++) {
	        for (let k = j + 1; k < placed.length; k++) {
		        let corners = corner(unplaced[i], placed[j], placed[k]);
		        for (let c = 0; c < corners.length; c++) {
                    let d_min = 1e10;
                    let valid = true;
                    for (let l = 0; l < placed.length; l++) {
				        if (l == j || l == k) continue;
				        let d = placed[l].distance(corners[c]);
				        if (d < 0) {
				            valid = false;
				            break;
				        }
				        if (d < d_min) d_min = d;
				    }

Если валидных позиций всё ещё несколько, то выберем наиболее плотную из них по формуле . Эта формула отражает, насколько расстояние d меньше радиуса. Чем меньше d, тем меньше доля , однако нам интересна не доля , а плотность размещения. А плотность становится больше, если доля меньше — чтобы это выразить мы берём обратное значение , где 1 — это . Тогда чем меньше будет d, тем больше будет значение плотности λ.

				    if (valid && d_min < lambda_min) {
				        lambda_min = d_min;
				        lambda[i] = 1 - d_min / unplaced[i];
				        circle[i] = corners[c];
				    }

После перебора выберем из получившегося массива круг с наиболее оптимальной позицией, то есть с наиболее высоким показателем плотности lambda. Добавим его в placed и удалим из unplaced.

let lambda_max = -1e10;
let i_max = -1;
for (let i = 0; i < unplaced.length; i++) {
    if (lambda[i] > lambda_max) {
        lambda_max = lambda[i];
        i_max = i;
    }
}
placed.push(circle[i_max]);
unplaced.splice(i_max, 1);

Равномерное распределение.

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

Получив доступ к текущему расположению круга, метод centerFreeCircles() выбирает потенциальные варианты смещения его позиции, анализируя ближайшую область вокруг него. Потенциальные варианты смещения в коде обозначены как candidates. Метод рассматривает кандидатов для каждого круга в восьми направлениях angleStep вокруг текущего положения круга, то есть в направлении (вправо), (вверх) и тд. На каждом направлении обозначается по 3 кандидата на расстоянии и от текущей позиции круга.

centerFreeCircles() {  
    let circles = this.list;  
    let numCircles = this.circles.length;  
    let w = this.w;
    for (let i = 0; i < circles.length; i++) {  
        let circle = circles[i];  
        let candidates = [];  
  
        let steps = 8;  
        let radiusStep = circle.r * 0.5;  
        let angleStep = Math.PI * 2 / steps;  

Чтобы не потерять возможность сохранить текущую позицию круга без изменений, сохраним её в список кандидатов:

candidates.push(new Circle(circle.r, circle.c));  

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

В нашем случае ρ — это и , а φ — это и тд. Эти значения будут перебираться в цикле с определённым шагом angleStep для φ и radiusStep для ρ.

        for (let r = 1; r <= 3; r++) {  
            for (let a = 0; a < steps; a++) {  
                let x = circle.c.x + r * radiusStep * Math.cos(a * angleStep);  
                let y = circle.c.y + r * radiusStep * Math.sin(a * angleStep);  
                candidates.push(new Circle(circle.r, new Point(x, y)));  
            }  
        }  

Теперь среди набранных кандидатов надо выбрать наилучшего. Наилучший будет соответствовать нескольким критериям: конечно, он не будет пересекать другие круги или границы области, но при этом он должен находится как можно дальше от ближайшего препятствия, за что отвечает расстояние minDistance. Обозначим расстояние до других кругов как d, и перебирая расстояние до каждого круга, исключим случаи пересечения, обозначив для них valid = false. Если же пересечения нет, запишем d как minDistance и будем сравнивать все minDistance, пока не найдём максимальный.

        let bestCandidate = null;  
        let maxMinDistance = -1;  
  
        for (let c = 0; c < candidates.length; c++) {  
            let candidate = candidates[c];  
            let valid = true;  
  
            if (candidate.c.x - candidate.r <= -w/2 ||  
                candidate.c.x + candidate.r >= w/2 ||  
                candidate.c.y - candidate.r <= -w/2 ||  
                candidate.c.y + candidate.r >= w/2) {  
                continue;  
            }  
  
            let minDistance = Infinity;  
            for (let j = 0; j < circles.length; j++) {  
                if (i == j) continue;  
                let d = candidate.distance(circles[j]);  
                if (d <= 0) {  
                    valid = false;  
                    break;  
                }  
                if (d < minDistance) minDistance = d;  
            }  

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

            let boundaryDist = Math.min(  
			    candidate.c.x + w/2 - candidate.r, // левая граница
			    w/2 - candidate.c.x - candidate.r, // правая граница
			    candidate.c.y + h/2 - candidate.r, // нижняя граница
			    h/2 - candidate.c.y - candidate.r // верхняя граница
            );  

Теперь можем обновить minDistance, если расстояние до границы окажется меньше расстояния до ближайшего круга. Тогда ведь ближайшим препятствием будет граница, а не круг.

minDistance = Math.min(minDistance, boundaryDist); 

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

            if (valid && minDistance > maxMinDistance) {  
                maxMinDistance = minDistance;  
                bestCandidate = candidate;  
            }  
        }  
  
        if (bestCandidate && maxMinDistance > circle.r * 0.05) {  
            circles[i] = bestCandidate;  
        }  

Оптимизация площади.

Помимо непосредственного размещения кругов, необходимо по ходу пьесы минимизировать площадь самой рабочей области. Реализуем это в методе solve(). Начиная с площади , будем проводить размещение кругов и уменьшать или увеличивать площадь в зависимости от результата размещения в compute. Алгоритм распределил круги в первоначальной площади surface и мог выдать результат, в котором размещены либо все круги, либо не все. Если не удалось разместить все круги, то алгоритм увеличивает площадь, а если удалось — уменьшает в 2 раза за итерацию, после чего заново размещает круги.

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

solve(numCircles) {  
    let surface = this.circles.length * Math.PI;  
    let limit = surface / 1000;  
    let step = surface / 2;  
    let res = [];  
    while (step > limit) {  
        let placement = this.compute(surface, numCircles);  
        if (placement.length !== this.circles.length) {  
            surface += step;  
        } else {  
            res = placement;  
            this.bounds = this.tmp_bounds;  
            surface -= step;  
        }  
        step /= 2;  
    }   
    return res;  
}

Пора взглянуть, что получилось.

Мне подходят упаковки для . В случаях при необходимо эстетически усовершенствовать упаковки, что можно сделать, добавив для них условие симметрии.

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

let ratio_min = 1.0;
let ratio_max = 2.0;
let ratio_step = 0.01;

for (let ratio = ratio_min; ratio <= ratio_max; ratio += ratio_step) {
    ratios.push(ratio);
}

Симметрия в квадратной упаковке. Доработка результатов.

Первым делом проверим наличие уже симметрично размещённых кругов с помощью функции checkSymmetry(). Объявим константу tolerance с крайне малым значением и будем использовать её для учёта погрешности позиций после округлений. Также создадим массив, в котором будем отмечать обработанные круги и пустой массив для хранения кругов без симметричной пары.

let circles = this.list;
let tolerance = 1e-6;
let used = new Array(circles.length).fill(false);
let unpaired = [];

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

for (let i = 0; i < circles.length; i++) {
    if (used[i]) continue;
    let cx = circles[i].c.x;
    let cy = circles[i].c.y;
    let foundMatch = false;
    for (let j = 0; j < circles.length; j++) {
        if (i === j || used[j]) continue;
        let cxj = circles[j].c.x;
        let cyj = circles[j].c.y;
        if (Math.abs(cx + cxj) < tolerance && Math.abs(cy + cyj) < tolerance) {
            used[i] = true;
            used[j] = true;
            foundMatch = true;
            break;
        }
    }

В случае, если симметричная пара для круга не найдена, необходимо выяснить, является этот круг центральным, а если нет, то добавить его в список непарных кругов.

if (!foundMatch) {
    if (Math.abs(cx) < tolerance && Math.abs(cy) < tolerance && unpaired.length === 0) {
        used[i] = true;
    } else {
        unpaired.push(i);
    }
}

Если во всей упаковке не оказалось непарных кругов, то есть она полностью симметрична, то есть список непарных кругов пуст, то обозначим такую упаковку флагом true.

return unpaired.length === 0;

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

Будем перебирать все круги и вычислять симметричную координату с помощью mirroredPos методом mirror(), вынесенным в класс Point.

optimizeSymmetry(circles) {
    let symmetric = [];
    let used = new Array(circles.length).fill(false);
    for (let i = 0; i < circles.length; i++) {
        if (used[i]) continue;

        let mirroredPos = circles[i].c.mirror();
        let closest = -1;
        let minDist = Infinity;

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

        for (let j = 0; j < circles.length; j++) {
            if (i == j || used[j]) continue;
            let d = circles[j].c.dist(mirroredPos);
            if (d < minDist) {
                minDist = d;
                closest = j;
            }
        }

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

        if (closest != -1 && minDist < 1.0) {
            let avgX = (circles[i].c.x + circles[closest].c.y) / 2;
            let avgY = (circles[i].c.y + circles[closest].c.x) / 2;

            symmetric.push(new Circle(circles[i].r, new Point(avgX, avgY)));
            symmetric.push(new Circle(circles[i].r, new Point(avgY, avgX)));
            used[i] = true;
            used[closest] = true;
        } else {
            symmetric.push(circles[i]);
            used[i] = true;
        }

Проверим, что новые позиции не вышли за границы.

    let valid = true;
    for (let i = 0; i < symmetric.length; i++) {
        if (symmetric[i].c.x - symmetric[i].r < -this.w/2 ||
            symmetric[i].c.x + symmetric[i].r > this.w/2 ||
            symmetric[i].c.y - symmetric[i].r < -this.h/2 ||
            symmetric[i].c.y + symmetric[i].r > this.h/2) {
            valid = false;
            break;
        }

        for (let j = i + 1; j < symmetric.length; j++) {
            if (symmetric[i].intersects(symmetric[j])) {
                valid = false;
                break;
            }
        }
        if (!valid) break;
    }
    return valid ? symmetric : circles;
}

Итак, финальное размещение:

Симметрия упаковки в прямоугольнике.

А что насчёт симметрии в прямоугольнике? Помнится, я планировала условие симметрии, но не по диагонали, как в квадрате, а по вертикали или горизонтали.

Горизонтальная и/или вертикальная симметрия — обеспечит однозначность упаковки и значительно уменьшит количество потенциально верных результатов.

Да, и заметим ключевое различие с квадратной областью: в квадрате симметрия используется на финальной стадии алгоритма для доработки имеющихся результатов, а в прямоугольнике условие симметрии — это флаг, который выбрать именно эту упаковку из множества предложенных. Поэтому добавим функцию hasSymmetry в завершении процесса упаковки. Зададим оси симметрии centerX, centerY и погрешность tolerance, а также временно перебазируем область, задав её центр в с помощью normalized для упрощения расчётов на данном этапе.

hasSymmetry(placement) {
    if (!placement || placement.length === 0) return false;
    if (this.n_circles === 13 || this.n_circles === 1 || this.n_circles === 3) return true;

    let w = this.w;
    let h = this.h;
    let centerX = w / 2;
    let centerY = h / 2;
    let tolerance = 0.2;

    let normalized = placement.map(c => new Point(c.c.x - centerX, c.c.y - centerY));

Начнём с горизонтальной симметрии. Будем перебирать круги в текущей упаковке и вычислять для каждого круга координаты симметричной пары. Если они окажутся симметричными по горизонтали, то эта упаковка нам подходит.

    let horizontalSymmetry = true;
    for (let i = 0; i < normalized.length; i++) {
        let c = normalized[i];
        let mirrored = new Point(c.x, -c.y); 
        let found = false;

        for (let j = 0; j < normalized.length; j++) {
            if (Math.abs(normalized[j].x - mirrored.x) < tolerance &&
                Math.abs(normalized[j].y - mirrored.y) < tolerance) {
                found = true;
                break;
            }
        }
        if (!found) {
            horizontalSymmetry = false;
            break;
        }
    }

С вертикальной симметрией аналогично. После чего в методе solve, мы выбираем именно среди симметричных упаковок, если таковых окажется несколько, самую плотную, что и было описано ранее.

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

Отрисовка.

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

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