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

Ответ 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.

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

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

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

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

Ответ 2

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

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

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

Ответ 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%

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

Ответ 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

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

Ответ 5

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