Может быть математически умный способ сделать это, но я бы не знал.
Я думаю, что это немного усложняется тем фактом, что геометрия различна для каждого различного числа квадратов; для 4 - ромб, для 5 - пятиугольник и т. д.
Что бы я сделал, это поместил бы эти квадраты в круг из 1 единицы (слишком маленький, я знаю, терпите меня), равномерно распределенный на нем. Это достаточно просто, просто сложите (разделите) свои 360 градусов на количество квадратов. Затем просто проверьте все свои квадраты на совпадение со своими соседями; если они перекрываются, увеличьте радиус.
Вы можете сделать эту процедуру менее глупой, чем кажется, используя интеллектуальный алгоритм, чтобы приблизиться к нужному размеру. Я думаю о чем-то вроде алгоритма Ньютона: учитывая две последовательные догадки, одна из которых слишком мала, а другая слишком велика, ваше следующее предположение должно быть средним из этих двух.
Вы можете перемещаться вниз с любой точностью, которая вам нравится. Остановитесь, когда расстояние между догадками будет меньше произвольного небольшого запаса погрешности.
РЕДАКТИРОВАТЬ У меня есть лучшее решение:
Я думал о том, что сказать вам, если вы спросите: "Как я узнаю, что квадраты перекрываются?" Это дало мне представление о том, как точно рассчитать размер круга за один шаг:
Поместите свои квадраты в слишком маленький круг. Вы знаете, как: вычислить точки на окружности, где ваши углы 360 / n пересекают его, и поместить центр квадрата туда. На самом деле вам пока не нужно размещать квадраты, для следующих шагов требуются только середины.
Чтобы вычислить минимальное расстояние квадрата до его соседа: вычислите разницу в X и разницу в Y средних точек и возьмите их минимум. X и Y на самом деле являются просто косинусами и синусами на круге.
Вам понадобится минимум любого квадрата против соседа (скажем, по часовой стрелке). Так что вам нужно обойти круг, чтобы найти самый маленький.
Минимальное (X или Y) расстояние между квадратами должно стать 1,0. Так что просто возьмите обратную величину минимального расстояния и умножьте на это размер круга. Престо, твой круг подходящего размера.
EDIT
Не теряя общности, я думаю, что можно немного прибавить моё решение, так что оно близко к кодированию. Вот уточнение:
- Предположим, квадраты имеют размер 1, т.е. каждая сторона имеет длину 1 единицу. В конце концов ваши поля наверняка будут больше 1 пикселя, но это только вопрос масштабирования.
Избавьтесь от угловых чехлов:
if (n < 2) throw new IllegalArgumentException();
if (n == 2) return 0.5; // 2 squares will fit exactly on a circle of radius 0.5
Начните с размера круга r, равного 0,5, что, безусловно, будет слишком маленьким для любого числа квадратов> 2.
r = 0.5;
dmin = 1.0; // start assuming minimum distance is fine
a = 2 * PI / n;
for (p1 = 0.0; p1 <= PI; p1+=a) { // starting with angle 0, try all points till halfway around
// (yeah, we're starting east, not north. doesn't matter)
p2 = p1 + a; // next point on the circle
dx = abs(r * cos(p2) - r * cos(p1))
dy = abs(r * sin(p2) - r * sin(p1))
dmin = min(dmin, dx, dy)
}
r = r / dmin;
EDIT
Я превратил это в настоящий код Java и получил что-то похожее на это для запуска. Код и результаты здесь: http://ideone.com/r9aiu
Я создал графический вывод, используя GnuPlot. Мне удалось создать простые диаграммы блоков, расположенных по кругу, вырезав и вставив наборы точек из выходных данных в файл данных, а затем запустив
plot '5.dat' with boxxyerrorbars
* * * * * * .5 в файле служат для определения размера блоков ... ленивое, но рабочее решение. .5 применяется к обеим сторонам от центра, поэтому размеры ящиков равны 1,0.
Увы, мой алгоритм не работает . Это делает радиусы слишком большими, таким образом помещая коробки намного дальше, чем необходимо. Даже уменьшение в 2 раза (возможно, было ошибкой использовать 0,5 в некоторых местах) не помогло.
Извините, я сдаюсь. Может быть, мой подход может быть спасен, но он не работает так, как я это сделал. (
EDIT
Я ненавижу сдаваться. Я собирался покинуть свой компьютер, когда думал о способе спасти свой алгоритм:
Алгоритм корректировал меньшие расстояний X или Y, чтобы они были как минимум 1. Легко показать, что это просто глупо.Если у вас много ящиков, то на восточном и западном краях круга у вас есть ящики, сложенные почти прямо друг на друге, с их X очень близко друг к другу, но они защищены от прикосновения, имея достаточное расстояние Y междуих.
Итак ... чтобы сделать эту работу, вы должны масштабировать максимум dx и dy, чтобы (во всех случаях) быть как минимум радиусом (или он был в два раза больше радиуса)??)коробки точно соприкасаются. Проблема решена! :)
Хостинг imgur.comХостинг imgur.com
(Эти изображения шире, чем они высокие, потому что GnuPlot не знал, что я хотел пропорционального расположения. Просто представьте, что все работы сжаты в квадратную форму :))