Полностью покрыть прямоугольник с минимальным количеством кругов фиксированного радиуса

Question

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

Проблема Ze *

Учитывая прямоугольник X от Y, найдитеминимальное количество кругов N с фиксированным заданным радиусом R, необходимое для полного покрытия каждой части прямоугольника.

---

Я думал о способах ее решения, но у меня нет ничего определенного.Если каждый круг определяет внутренний прямоугольник, то R^2 = Wi^2 + Hi^2, где Wi и Hi - это ширина и высота практической области, охватываемой каждым кругом i.Сначала я подумал, что должен сделать Wi равным Wj для любого i = j, то же самое для H.Таким образом, я мог бы упростить задачу, сделав соотношение ширины / высоты равным основному прямоугольнику (Wi/Hi = X/Y).Таким образом, N=X/Wi.Но это решение, безусловно, неверно в случае, если X значительно превышает Y или наоборот.
Вторая идея состояла в том, что Wi = Hi для любого заданного i.Таким образом, квадраты заполняют пространство наиболее эффективно.Однако, если остается очень узкая полоса, гораздо более оптимально использовать прямоугольники для ее заполнения или, что еще лучше, использовать прямоугольники для последней строки и до этого.
Тогда я понял, что ни одна из идей не является оптимальной, поскольку явсегда можно найти лучшие способы сделать это.Это всегда будет близко к финалу, но не к финалу.

Редактировать
В некоторых случаях (большой прямоугольник) объединение шестиугольников представляется лучшим решением, чем соединение квадратов.

Дальнейшее редактирование
Вот сравнение 2 методов: клевер против гексагональной.Гексагональный, очевидно, лучше для больших поверхностей.Однако я считаю, что когда прямоугольник достаточно мал, прямоугольный метод может быть более эффективным.Это догадка.Теперь на рисунке вы видите 14 кругов слева и 13 кругов справа.Хотя поверхность отличается намного больше (в два раза), чем один круг.Это потому, что слева они перекрываются меньше, тратя таким образом меньше поверхности.

Все еще остаются вопросы:

1. Оптимален ли сам шаблон правильного шестиугольника?Или необходимо внести определенные корректировки в части основного прямоугольника.
2. Есть ли причины не использовать правильные формы в качестве "окончательного решения"?
3. Есть ли на этот вопрос ответ?:)

Answer 1

Для X и Y, больших по сравнению с R, гексагональная (сотовая) структура близка к оптимальной.Расстояние между центрами окружностей в направлении X равно sqrt(3)*R.Расстояние между рядами в направлении Y равно 3*R/2, поэтому вам нужно примерно X*Y/R^2 * 2*/(3*sqrt(3)) окружностей.

Если вы используете квадратный шаблон, горизонтальное расстояние больше (2*R), но вертикальноерасстояние намного меньше (R), поэтому вам понадобится около X*Y/R^2 * 1/2 кругов.Начиная с 2/(3*sqrt(3) < 1/2, гексагональная модель - лучшее предложение.

Обратите внимание, что это только приблизительное значение.Обычно можно немного подергивать обычный шаблон, чтобы что-то подходило там, где стандартный шаблон не подходит.Это особенно верно, если X и Y малы по сравнению с R.

С точки зрения ваших конкретных вопросов:

1. Гексагональная структура - оптимальное покрытие всей плоскости,Если бы X и Y были конечными, я думаю, что часто можно получить лучший результат.Тривиальный пример - это когда высота меньше радиуса.В этом случае вы можете перемещать окружности на один ряд дальше друг от друга, пока расстояние между точками пересечения каждой пары окружностей не станет равным Y.

2. Наличие регулярного шаблона накладывает дополнительные ограничения нарешение, и поэтому оптимальное решение при этих ограничениях может быть неоптимальным при снятии этих ограничений.В целом, некоторые неправильные шаблоны могут быть лучше (см. Страницу, на которую ссылается mbeckish).

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

Answer 2

Этот сайт атакует проблему под несколько иным углом: учитывая n кругов юнитов, какой самый большой квадрат они могут покрыть?

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

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

Answer 3

Шестиугольник лучше алмаза. Рассмотрим процентную площадь круга юнитов, покрытого каждым:

#!/usr/bin/env ruby

include Math

def diamond
  # The distance from the center to a corner is the radius.
  # On a unit circle, that is 1.
  radius = 1

  # The edge of the nested diamond is the hypotenuse of a
  # right triangle whose legs are both radii.
  edge = sqrt(radius ** 2 + radius ** 2)

  # The area of the diamond is the square of the edge
  edge ** 2
end

def hexagon
  # The hexagon is composed of 6 equilateral triangles.
  # Since the inner edges go from the center to a hexagon
  # corner, their length is the radius (1).
  radius = 1

  # The base and height of an equilateral triangle whose
  # edge is 'radius'.
  base = radius
  height = sin(PI / 3) * radius

  # The area of said triangle
  triangle_area = 0.5 * base * height

  # The area of the hexagon is 6 such triangles
  triangle_area * 6
end

def circle
  radius = 1
  PI * radius ** 2
end

puts "diamond == #{sprintf "%2.2f", (100 * diamond / circle)}%"
puts "hexagon == #{sprintf "%2.2f", (100 * hexagon / circle)}%"

И

$ ./geometrons.rb 
diamond == 63.66%
hexagon == 82.70%

Далее, правильные шестиугольники - это многоугольники с высшими вершинами, которые образуют правильную тесселяцию плоскости .

Answer 4

Согласно моим расчетам правильный ответ:

D=2*R; X >= 2*D, Y >= 2*D,
N = ceil(X/D) + ceil(Y/D) + 2*ceil(X/D)*ceil(Y/D)

В частном случае, если остаток для X / D и Y / D равен 0, тогда

N = (X + Y + X*Y/R)/D

Case 1: R = 1, X = 2, Y = 2, then  N = 4

Case 2: R = 1, X = 4, Y = 6, then  N = 17

Case 3: R = 1, X = 5, Y = 7, then  N = 31

Надеюсь, это поможет.

Answer 5

Когда круги расположены как клевер с четырьмя листьями с пятым кругом посередине, круг охватит область, равную R * 2 * R. При таком расположении возникает вопрос: сколько кругов, которые охватывают область R * 2 * R, будут покрывать область W * H? или N * R * 2 * R = W * H. Так что N = W * H / R * 2 * R.