Разделите прямоугольник на n прямоугольников одинакового размера

Question

Я ищу алгоритм для разбиения прямоугольника (скажем, 1000x800) на n (или больше, но как можно меньше дополнительных прямоугольников) прямоугольников одинакового размера внутри этого прямоугольника, чтобы использовалось все пространство. Маленькие прямоугольники также должны стараться быть как можно ближе к исходному соотношению сторон.

Например:

+---------------+
|               |
|               |
|               |
+---------------+

Разделить для n = 2:

+---------------+
|               |
+---------------+
|               |
+---------------+

Разделить для n = 3

+-------+-------+
|       |       |
+-------+-------+
|       |       |
+---------------+

1012 * Etc. *

Есть ли такой алгоритм? В идеале я хотел бы, чтобы это было на Python, но на самом деле любой язык хорош, так как я мог бы его перевести ...

EDIT:

Несколько дополнительных сведений:

Целевая поверхность будет окном браузера, поэтому поверхность будет примерно 4: 3 или 16: 9 или другим популярным измерением. Прямоугольник состоит из пикселей. Соотношение сторон не гарантированно будет целым числом.

Меньше лишних прямоугольников немного предпочтительнее ограничения соотношения сторон.

Answer 1

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

Вы всегда можете получить точно правильные соотношения сторон, по какой-то цене в потраченных впустую прямоугольниках, приняв m = ceil (sqrt (n)) и используя m частей с каждой стороны.

В противном случае, вы ищете p, q близко к sqrt (n), так что pq> = n и p, q близки друг к другу. Лучший выбор p, q, конечно, будет зависеть от того, насколько вы готовы обменять отходы на неточность. Маловероятно, что вы когда-нибудь захотите взять p, q очень далеко от sqrt (n), потому что это даст вам большую ошибку в форме. Поэтому я думаю, что вы хотите что-то вроде этого:

p = ceiling(sqrt(n))
best_merit_yet = merit_function(p,p,0)
best_configuration_yet = (p,p)
for p from floor(sqrt(n)) downward:
  # we need pq >= n and q as near to p as possible, which means (since p is too small) as small as possible
  q = ceiling(n/p)
  if max(merit_function(n/p,n/q,0), merit_function(n/q,n/p,0)) < best_merit_yet:
    break
  n_wasted = p*q-n
  merit1 = merit_function(n/p,n/q,n_wasted)
  merit2 = merit_function(n/q,n/p,n_wasted)
  if max(merit1,merit2) > best_merit_yet:
    if merit1 > merit2:
      best_configuration_yet = (p,q)
      best_merit_yet = merit1
    else:
      best_configuration_yet = (q,p)
      best_merit_yet = merit2

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

Здесь merit_function должен воплощать ваши предпочтения в обмене формы на отходы.

Answer 2

Используйте эту функцию, чтобы получить 2 числа в виде списка:

def divide_equally(n):
    if (n<3):
        return [n, 1]
    result = list()
    for i in range(1, int(n ** 0.5) + 1):
       div, mod = divmod(n, i)
       #ignore 1 and n itself as factors
       if mod == 0 and i != 1 and div != n:
           result.append(div)
           result.append(i)
    if len(result)==0: # if no factors then add 1
        return divide_equally(n+1)
    return result[len(result)-2:]

Например:

print divide_equally(1)
print divide_equally(50)
print divide_equally(99)
print divide_equally(23)
print divide_equally(50)

даст

[1, 1]
[10, 5]
[11, 9]
[6, 4]  # use the next even number (24)
[10, 5] # not [25, 2] use the 2 closest numbers 

Answer 3

Редактировать: вторая идея:

var countHor = Math.Floor(Math.Sqrt(n));
var countVer = Math.Ceil(n / countHor);
var widthDivided = widthTotal / countVer;
var heightDivided = heightTotal / countHor;

Хотя результат зависит от того, что вы предпочитаете: соотношение прямоугольников или количество дополнительных прямоугольников (например, для n = 14, оно должно быть 2x7 или 3x5, для n = 7, если оно будет 3x3 или 2x4)

Первая идея неверна из-за некоторых затрат:

Если вы хотите получить минимальное количество равных прямоугольников, вам следует использовать операцию sqrt. Например, если n = 9, то это будет 3x3 прямоугольника (2 линии по вертикали и 2 линии по горизонтали). Если n = 10, это будет 3x4 прямоугольника в качестве этажа (sqrt (10)) x ceil (sqrt (10)) => 3x4 (2 строки по вертикали и 3 линии по горизонтали или по-другому).

Это просто общая идея алгоритма, в зависимости от ваших требований вы должны построить правильный алгоритм.

Размеры новых прямоугольников будут следующими:

var widthDivided = widthTotal / Math.Floor(Math.Sqrt(count));
var heightDivided = heightTotal / Math.Ceil(Math.Sqrt(count));

Вот аналогичная задача, но она не будет возвращать минимальное значение: Алгоритм разбиения прямоугольника на n меньших прямоугольников и вычисления каждого центра