將矩形均勻分佈在另一個矩形內所需的算法

我正在尋找一種算法，可以幫助在較大的矩形內分佈不同大小的矩形，同時最小化重疊。將矩形均勻分佈在另一個矩形內所需的算法

我已經看過bin包裝算法，但他們似乎最大限度地減少矩形之間的空間量（在我的情況下，所有正在打包的項目將是正方形）。

我想我想要最大化所有方塊和外部矩形邊框之間的距離。

這裏是什麼，我試圖做一個例子：

Example of what I am saying

2011-12-12 howardr

「最小化重疊」，這意味着它們可以重疊？ – Nanne

我想你想最大化矩形和外部矩形的邊界之間的最小*距離。 – vitaut

@Nanne我不是很擔心，如果有一些重疊。我認爲可能有一個算法可以工作，但不能處理可變大小的正方形。在這種情況下，我會優化中位數或平均數。 – howardr

-2

這似乎是Knapsack Problem的推廣。

動態規劃將在接近多項式時間的情況下求解它。

2011-12-12 22:01:45 javanix

我在發佈之前查看了揹包問題，並且我認爲一些與解決此問題有關的算法會起作用。我想我不知道什麼變量要優化我的主要要求，即均勻分佈在外矩形內的平方（我在描述我的問題時表達歉意）。 – howardr

如果你使用the one described here這樣的算法儘可能緊湊地打包它們，然後均勻擴展以匹配目標包圍矩形，該怎麼辦？

例如，假設您可以將上面的3個矩形打包到3x2框中，並且您的外框爲7x5。然後從方框中心到中心的矢量到每個矩形，然後將x分量乘以(7/3)，將y分量乘以(5/2），然後給出新的中心。

2011-12-13 17:59:25 AShelly

回答