Расположение квадратов на круге с минимальным диаметром

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

Я бы поместил эти квадраты на круг размером 1 единицу (слишком маленький, я знаю, несите меня), распределенный на нем поровну. Это достаточно просто, просто разделите (разделите) ваши 360 градусов на количество квадратов. Затем просто проверьте все свои квадраты на перекрытие со своими соседями; если они перекрываются, увеличьте радиус.

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

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

РЕДАКТИРОВАТЬ У меня есть решение получше:

Я думал о том, что сказать вам, если вы спросите: «Как я узнаю, перекрываются ли квадраты?» Это дало мне представление о том, как точно рассчитать размер круга за один шаг:

Поместите квадраты на слишком маленький круг. Вы знаете, как: вычислите точки на окружности, в которых ваши углы 360 / n пересекают ее, и поместите туда центр квадрата. На самом деле, вам пока не нужно размещать квадраты, для следующих шагов нужны только средние точки.

Чтобы вычислить минимальное расстояние квадрата до его соседа: Вычислите разность по X и разность по Y средних точек и возьмите их минимум. X и Y на самом деле просто косинусы и синусы на окружности.

Вам понадобится минимум любой квадрат против своего соседа (скажем, по часовой стрелке). Поэтому вам нужно обойти круг, чтобы найти самый маленький.

Минимальное (X или Y) расстояние между квадратами должно быть 1,0. Так что просто возьмите величину, обратную минимальному расстоянию, и умножьте на это размер круга. Престо, твой круг правильного размера.

РЕДАКТИРОВАТЬ

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

• Предположим, что квадраты имеют размер 1, т.е. каждая сторона имеет длину 1 единицу. В конце концов, ваши коробки наверняка будут больше 1 пикселя, но это всего лишь вопрос масштабирования.

• Избавьтесь от крайних случаев:

   if (n <2) throw new IllegalArgumentException ();
  если (n == 2) вернуть 0,5; // 2 квадрата точно уместятся на окружности радиуса 0.5
  

• Начните с круга размером r 0,5, который наверняка будет слишком маленьким для любого количества квадратов> 2.

   r = 0,5;
  dmin = 1,0; // начинаем предполагать, что минимальное расстояние в порядке
  a = 2 * PI / n;
  for (p1 = 0.0; p1 <= PI; p1 + = a) {// начиная с угла 0, пробуем все точки до середины
   // (да, мы начинаем восток, а не север. не имеет значения)
  р2 = р1 + а; // следующая точка на окружности
  dx = abs (r * cos (p2) - r * cos (p1))
  dy = abs (r * sin (p2) - r * sin (p1))
  dmin = min (dmin, dx, dy)
  }
  r = r / dmin;
  

РЕДАКТИРОВАТЬ

Я превратил это в настоящий Java-код и получил для запуска нечто очень похожее на это. Код и результаты здесь: http://ideone.com/r9aiu

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

plot '5.dat' with boxxyerrorbars

.5 в файле serve размер ящиков ... ленивое, но рабочее решение. 0,5 применяется к обеим сторонам от центра, поэтому коробки в конечном итоге имеют размер 1,0.

Увы, мой алгоритм не работает . Это делает радиусы слишком большими, поэтому коробки располагаются намного дальше друг от друга, чем необходимо. Даже уменьшение в 2 раза (в некоторых местах могло быть ошибкой использование 0,5) не помогло.

Простите, я сдаюсь. Может быть, мой подход можно спасти, но он работает не так, как я, хотя мог бы. : (

РЕДАКТИРОВАТЬ

Ненавижу сдаваться.Я собирался оставить свой компьютер, когда подумал о способе спасти свой алгоритм:

Алгоритм регулировал меньшее расстояний X или Y, чтобы оно было не менее 1. Это легко продемонстрировать. просто глупо.Когда у вас много ящиков, то на восточном и западном краях круга у вас есть ящики, уложенные почти прямо друг на друга, причем их X очень близко друг к другу, но они защищены от соприкосновения за счет наличия достаточного расстояния Y между их.

Итак ... чтобы выполнить эту работу, вы должны масштабировать максимум dx и dy так, чтобы (для всех случаев) как минимум радиус (или это был двойной радиус?).

Исправленный код находится здесь: http://ideone.com/EQ03g http://ideone.com/VRyyo

Повторно протестирован в GnuPlot, он создает красивые маленькие кружочки прямоугольников, где иногда просто 1 или 2 коробки ровно соприкасаются. Проблема решена! :)

(Эти изображения шире, чем высокие, потому что GnuPlot не знал, что мне нужен пропорциональный макет. Только представьте, что все работы сжаты в квадратную форму :))