Упаковка прямоугольников фиксированного размера внутри круга с наибольшим «зумом» - PullRequest
Новая
       13

Упаковка прямоугольников фиксированного размера внутри круга с наибольшим «зумом»

0 голосов
/ 09 сентября 2011

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

1 Ответ

2 голосов
/ 09 сентября 2011

Если бы я сделал это, я, вероятно, сделал бы это с помощью бинарного поиска с использованием функции, проверяющей, разрешима ли проблема для заданных значений N, R и rectangle_scale.

Функция теста, вероятно, должна выглядеть примерно так:

testfunction (R, rectangle_scale)

  1. Установите как можно больше прямоугольников по диаметру
  2. Установите как можно больше над диаметром, примыкающим к прямоугольнику сверхудиаметра (например, 2 * R / rectangle_scale * side) или что-то в этом роде)
  3. Повтор (размещение над прямоугольниками, которые вы только что поместили. Делайте это до тех пор, пока больше не будет соответствовать прямоугольникам
  4. returnколичество прямоугольников, которые соответствуют

Тогда бинарный поиск будет стандартным: 

while(upperbound-lowerbound > limit) {
   new_bound = (upperbound+lowerbound) / 2;
   num_fit = testfunction(N, R, new_bound);
   if(num_fit > N) {
      upperbound = new_bound;
   } else {
      lowerbound = new_bound;
   }
}

В идеале вы, конечно, захотите сделать это математически. Если для вас подходит приближение, вы могли бы сделать это через области. Приближение было бы (rectangle_area * scale * N = pi * R ^ 2) => scale = scale = pi * R ^ 2 / N / rectangle_area.

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

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

...