拆分一个矩形分成N个相同大小的矩形 [英] Split a rectangle into n equally sized rectangles

问题描述

我在寻找一种算法来分割矩形（假设1000x800）为n（或以上，但由于一些额外的矩形越好）的矩形内同样大小的矩形，因此，所有的空间使用。小矩形也应尽可能地做到接近原始宽高比越好。

I'm looking for an algorithm to split a rectangle (let's say 1000x800) into n (or more, but as few extra rectangles as possible) equally sized rectangles within that rectangle, so all the space is used. The small rectangles should also try to be as close to the original aspect ratio as possible.

例如：

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

拆分为N = 2：

Split for n = 2:

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

拆分为N = 3

Split for n = 3

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

等

有没有这样的算法？理想情况下，我想拥有它在Python，但实际上任何语言是好的，因为我应该能够把它翻译...

Is there such an algorithm? Ideally I'd like to have it in Python, but really any language is fine since I should be able to translate it...

编辑：

这是一些额外的相关信息：

A few extra infos:

目标面将是一个浏览器窗口，所以表面会有的大致的4：3或16：9或另一种流行的尺寸。矩形是由像素。纵横比是不的保证是一个整数。

The target surface will be a browser window, so the surface will be roughly 4:3 or 16:9 or another popular dimension. The rectangle is made of pixels. The aspect ratio is not guaranteed to be an integer.

减去多余的矩形稍有preferable比纵横比限制。

Less excess rectangles is slightly preferable over the aspect ratio constraint.

推荐答案

（我假设，也许是错误的，你的矩形是无限可分的，而不是由独立的像素。）

(I'm assuming, perhaps wrongly, that your rectangles are infinitely divisible rather than being made up of discrete pixels.)

您可以随时获得完全正确的纵横比，在一定的成本浪费矩形，通过让M = CEIL（开方（N）），并使用m个每边。

You can always get exactly the correct aspect ratios, at some cost in wasted rectangles, by letting m = ceil(sqrt(n)) and using m pieces on each side.

否则，您正在寻找P，Q接近的sqrt（N），使得PQ> = n和p，q是彼此接近。当然，P的最佳选择，Q将取决于你怎么舍得对不准确的权衡浪费。这似乎并不可能，你会永远想利用P，Q从开方（N）很远，因为这样做会给你一个很大的错误的形状。所以我想你想是这样的：

Otherwise, you're looking for p,q close to sqrt(n) such that pq >= n and p,q are close to one another. The best choice of p,q will of course depend on how willing you are to trade off waste against inaccuracy. It doesn't seem likely that you'll ever want to take p,q very far from sqrt(n), because doing so would give you a large error in shape. So I think you want something like this:

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

和希望是非常错误的形状是非常糟糕的事实将意味着你从来没有真正不得不采取循环的迭代。

and hopefully the fact that very wrong shapes are very bad will mean that you never actually have to take many iterations of the loop.

下面， merit_function 应该体现你的preferences交易性降形状反对浪费。

Here, merit_function is supposed to embody your preferences for trading off shape against waste.

这篇关于拆分一个矩形分成N个相同大小的矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！