在一個可變大小的平面上隨機地分佈各種尺寸的矩形（考慮密度）

Question

我正在尋找一種算法，該算法隨機地在容器內分佈多個矩形（由其寬度和高度定義）長方形。後者不是由大小來定義的，而是由寬高比決定的。 必須有另外一個變量決定結果的密度，換句話說：兩個矩形的平均距離。 所有的矩形都將被放置，這是可能的，因爲容器的大小沒有限制。任何矩形都不能重疊。

最終結果應該是每個矩形的確定位置以及所用平面本身的尺寸。

不幸的是，我找不到一個這樣做的算法，或者到目前爲止它的一部分。我會很感激任何建議，意見或參考！事實證明，主要問題是跟蹤「空閒空間」列表，並在相應的放置後更新。

在真實的情況下，我需要這個，給定的矩形不是完全隨機的形狀。它們的高度幾乎相同，並且往往比高的寬廣得多：它們只是從文本中提取的文字，應該作爲「雲」分佈在飛機上。

Answer 1

下面是關於如何設計一個算法的一些想法：

• 由於實際矩形具有相似的尺寸，你也許可以將其整合到行和堆疊多個行，以獲得最終的佈局
• 使用事實上，rowCount * colCount == totalCount和colCount/rowCount == aspectRatio可以近似每行和每列中的矩形數
• 要確定放置矩形後剩餘的空閒空間，計算所有矩形的邊界框的面積，並減去各個矩形區域的總和。這是可行的，因爲矩形不重疊。
• 也許totalFreeSpace與boundingBoxArea的比率可以給出所需的密度。如果不是，那麼O(n^2)算法應該幫助計算每個問題描述的密度（假設總矩形數不是太大）。
• 一旦你有了上面的工作，你可以調整一些東西來改善雲的形狀。例如，對每行進行排序，使其中心最大的矩形。

Answer 2

我認爲你正在尋找一些像基於強制佈局的圖形可視化。如果你可以在你的單詞之間建立一個關係，那麼這個力就是你需要的參數。