1. 首頁
  2. 問答
  3. 包裝矩形算法

包裝矩形算法

2011-09-28 71 views
5

我需要解決以下問題： 我有多個矩形的大小：寬度高度，寬度/ 2高度/ 2，寬度/ 4高度/ 4，寬度/ 8高度/ 8 ...等包裝矩形算法

我需要將這些矩形放在一個大小爲x * width y * height的大矩形中，這樣沒有矩形重疊，矩形隨機分佈在包裝中，任何矩形至少應該碰到另一個矩形。我嘗試了一個相當基本的貪婪算法，但它失敗了。

你能給我一些關於如何解決問題的建議嗎？

謝謝！

編輯：你可以在每個大小

這不是功課不止一個矩形。我試圖創建一個效果類似於ted.com

通過隨機我的意思是可能存在滿足約束的矩形的多個包裝。該算法不應在每次運行時產生相同的包裝。

來源

2011-09-28 silviupop

+1

作業...... – jmpcm

+0

這是功課嗎？如果這樣做標記爲家庭作業。 –

+1

你需要提供更多細節。你是否有每一個矩形尺寸（例如單元邊的1個，0.5個單元邊的1個等等），或者你有多少個可以隨意使用的矩形？另外，隨機定義.. –

回答

2

您可以使用空間索引或四叉樹細分2d平面。這個想法是將2d問題簡化爲1d問題。一旦獲得了空間索引（或空間填充曲線），並且可以將2d離散化爲1d，則可以使用1d來搜索相似度，或者按照從低到高的順序進行排序，或者按照長度進行排序。如果你得到這個訂單，你可以計算這個索引回到第二個代表，並以最有效的方式將它們打包在你的容器中。有很多方法可以創建空間索引。希爾伯特曲線是一些最好但很難做出的。另一個是z曲線或morton曲線。它與zizag曲線不同，因爲它將平面細分爲4個正方形（不是矩形）。

編輯：這裏是一個鏈接，一個jQuery的插件：http://www.fbtools.com/jquery/treemap/ 這裏有世界poplulation：http://www.fbtools.com/jquery/treemap/population.html

編輯：http://people.csail.mit.edu/konak/papers/socg_2008-circular_partitions_with_applications_to_visualization_and_embeddings.html

編輯：http://lip.sourceforge.net/ctreemap.html

來源

2011-09-28 21:43:09 Bytemain

+0

感謝您的鏈接。很有幫助。 – silviupop

0

假設您只有一個每個尺寸的矩形，您可以嘗試複製紙張尺寸的排列。按大小排列矩形，從最大到最小，然後

  1. 取第一個矩形並將其放置在目標平面的拐角處。
  2. 拍攝下一張長方形（斷言它比以前的長方形小）
  3. 旋轉約90度
  4. 的地方，以便
    • 它的尺寸較短的鄰近最後的大國鄰居的尺寸較長的
    • 和其較長的一側與目標平面的邊緣相鄰或相鄰的邊緣相同 尺寸
  5. 重複2 - 4

我認識的描述可能是不清楚，所以這裏的畫面呈現解決方案 - 它應有助於掌握它：

enter image description here

來源

2011-09-28 09:21:04 mloskot

+0

在你的例子中，你在每個步驟（A1，A2 ...）上將表面分爲2，但是在期望的算法中它是4 ...因此有些事情是錯誤的這裏 –

+0

A系列紙張的工作原理是邊緣長度比爲1：sqrt（2），其他紙張尺寸不以這種方式包裝。 （我經常想知道爲什麼A系列在國際上不是更普遍......） – spraff

+0

@Ricky Bobby好點，我在閱讀這個問題時錯過了那些細節。 – mloskot

1

在每一步你把你的新的表面rectange by 4。

SUM（1/4用於n [0，INF）= 4/3 **

所以你能做的最好是適合你的矩形表面 4/3的矩形（高度×寬）

（這是一個下界）

@mloskot算法給出了一個可能的解決方案，這將是在表面的矩形3/2 *（高度*寬度）：在這裏，是示：

enter image description here

我看不出你怎麼做得更好。

來源

2011-09-28 09:31:43

4

這聽起來像一個rectangle packing problem。有一個鏈接到algorithm。該代碼儘可能緊密地包裝矩形。你說你想要矩形分佈隨機，我猜這意味着並不是所有矩形都是相鄰的一個大小，所有的矩形都分佈在大矩形中。也許上面鏈接的代碼將是獲得一些想法的好起點。

來源

2011-09-28 21:12:48 JohnPS

相關問題

 相關問題