Позиционирующие квадраты по кругу с минимальным диаметром

Ответ 1

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

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

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

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

EDIT У меня есть лучшее решение:

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

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

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

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

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

ИЗМЕНИТЬ

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

• Предположим, что квадраты имеют размер 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;
  

ИЗМЕНИТЬ

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

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

plot '5.dat' with boxxyerrorbars

.5 в файле служит для размера полей... ленивого, но рабочего решения..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 не знал, что мне нужна пропорциональная компоновка. Представьте, что все работы сжаты в квадратную форму:))

Ответ 2

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

Мой результат вычислений:

Rmin <= X/(sqrt (2) * sin (180/N))

Где: X - длина квадратной стороны, а N - необходимое количество квадратов.

Я полагаю, что круги расположены так, что их центры падают на окружность большого круга.

- EDIT -

Используя идею Дэйва в комментарии ниже, мы также можем рассчитать хорошую нижнюю границу, рассматривая круги внутри квадратов (имея радиус X/2). Эта оценка:

Rmin >= X/(2 * sin (180/N))

Ответ 3

Как уже отмечалось, проблема позиционирования n точек, равномерно расположенных по окружности окружности, тривиальна. (Не ужасно) трудная часть проблемы состоит в том, чтобы определить радиус круга, необходимый для того, чтобы дать приятный макет квадратов. Я предлагаю вам следовать одному из других ответов и думать, что квадраты находятся внутри кругового "буфера", достаточно большого, чтобы содержать квадрат и достаточно места, чтобы удовлетворить ваши эстетические требования. Затем проверьте формулу для длины аккорда между центрами соседних квадратов. Теперь у вас есть угол в центре круга, подстроенный аккордом между квадратными центрами, и он может легко вычислить радиус круга из тригонометрии треугольника.

И что касается вашего последующего вопроса: я предлагаю вам решить проблему для квадратов длины стороны min(h,w) на круге, затем преобразовать квадраты в прямоугольники и круг в эллипс с эксцентриситетом h/w ( или w/h).

Ответ 4

Вы начинаете с произвольного круга (например, с диаметром (* n l)) и равномерно поместите квадраты по окружности. Затем вы проходите каждую пару соседних квадратов и:

• вычислить прямую линию, соединяющую их средние точки,

• вычислить пересечение этой линии с промежуточными квадратными сторонами (M1 и M2 - средние точки, S1 и S2 - соответствующие пересечения с квадратной стороной:

                  S2         S1
  M1--------------*----------*---------------M2
  
  ------------------------
  |                      |
  |                      |
  |                      |
  |                      |
  |          M1          |
  |           \          |
  |            \         |
  |      -------*------- +--------
  |      |       \       |       |
  |      |        \      |       |
  -------+---------*------       |
         |          \            |
         |           M2          |
         |                       |
         |                       |
         |                       |
         |                       |
         -------------------------
  

• вычислить масштабный коэффициент, который вам нужно будет сжать S1 и S2 (просто отношение суммы M1-S1 и S2-M2 к M1-M2) и

наконец, масштабируем круг по максимуму найденных масштабных коэффициентов.

Изменить: это точное решение. Однако небольшая мысль может оптимизировать это для скорости:

• Вам нужно сделать это только для квадратов, ближайших к 45 ° (если n равно) соответственно. 45 ° и 135 ° (если n нечетно, на самом деле вы можете доказать, что только один из них необходим).
• При больших n оптимальное расстояние квадратов на круге быстро приближается к длине диагонали квадрата. Таким образом, вы можете прекомпопировать коэффициенты масштабирования для нескольких небольших n (до десятка или около того), а затем иметь достаточно хорошее приближение с диагональю.

Ответ 5

Я бы решил это следующим образом:

Чтобы найти соотношение между радиусом r и длиной l, проанализируем безразмерное представление

• получить центры по окружности (x1, y1).. (xn, yn)
• из каждого центра получите нижний правый угол i-го квадрата и верхний левый угол я + 1-го квадрата.
• две точки должны иметь либо равные x, либо равные y, в зависимости от того, что меньше l Процедура
• должна повторяться для каждого центра, а последняя, ​​которая дает наименьшее значение l, является окончательным решением.

Это оптимальное решение и может быть решено его членами r = f (l). Решение можно адаптировать к прямоугольникам, отрегулировав формулу для xLR [i] и yUL [i + 1].

Попробует дать некоторый псевдокод.

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

Ответ 6

Предположим, что вы решили проблему для 3 или 4 квадратов.

Если у вас есть n >= 5 квадратов и расположите один квадрат в верхней части круга, вы получите еще одно квадратное падение в первый квадрант картезианской плоскости, концентрической с вашим кругом.

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

Координата x правой части верхнего круга равна x1 = L/2, где L - сторона квадрата. Координата x левой стороны круга рядом с верхней является x2 = r cos a - L/2, где r - радиус, a - угол между каждой парой квадратных центров (a = 360/n градусов).

Итак, нам нужно решить x1 <= x2, что приводит к

r >= L/cos a.

L и a известны, поэтому мы закончили: -)