長方形を指定された領域の近距離に分割します

Question

私は一連のセットを持っています n 正の数、および寸法の長方形 バツ と y 私が分割する必要があること n 次のような小さな長方形

• 各小さな長方形の表面積は、指定されたセットの対応する数に比例します
• 大きな長方形のすべてのスペースが占有されており、小さな長方形の間に残りのスペースはありません
• それぞれの小さな長方形は、実現可能であると正方形に近いように形作る必要があります
• 実行時間はかなり小さくなければなりません

これについての道順が必要です。 Webで説明されているこのようなアルゴリズムを知っていますか？アイデアはありますか（擬似コードは問題ありません）？

ありがとう。

Answer 1

あなたが説明するものはaのように聞こえます Treemap:

Treemapsは、ネストされた長方形のセットとして階層（ツリー構造）データを表示します。ツリーの各枝には長方形が与えられ、その後、サブブランチを表す小さな長方形でタイル張りになります。リーフノードの長方形には、データの指定された次元に比例した面積があります。

そのウィキペディアページはリンクします ベン・シュナイダーマンによるページ, 、素晴らしい概要とJavaの実装へのリンクを提供します。

それから教員のラウンジでこれについて困惑している間、私はAHAを持っていました！レベルを横断するときに、水平方向と垂直方向を交互に繰り返して、画面を長方形に分割した経験。この再帰アルゴリズムは魅力的に思えましたが、それが常に機能し、6行のアルゴリズムを書くのに自分自身を納得させるのに数日かかりました。

ウィキペディアも Mark Bruls、Kees Huizing、Jarke J. Van Wijkによる「Squarified Treemaps」 （PDF）1つの可能なアルゴリズムを提示する：

長方形を再帰的に長方形にテッセレーションすることができます。そのため、それらのアスペクト比（最大（高さ/幅、幅/高さ））アプローチ1にできるだけ近くに近づくにはどうすればよいですか？考えられるすべてのテッセレーションの数は非常に多いです。この問題は、NPハードの問題のカテゴリにあります。ただし、アプリケーションには最適なソリューションは必要ありません。短時間で計算できる優れたソリューションが必要です。

質問の再帰については言及していないので、あなたの状況はTreemapの1つのレベルにすぎない可能性があります。しかし、アルゴリズムは一度に1つのレベルで動作するため、これは問題ないはずです。

Answer 2

私は似たようなことに取り組んできました。私は、可能な限り同様のアスペクト比を取得することよりも単純さを優先しています。これは（理論的に）機能するはずです。 1〜10のnの一部の値を紙でテストしました。

n =作成する長方の総数、q = max（幅、高さ） / min（幅、高さ）、r = n / q

q> n/2の場合、n部位の長方を最長の側に分割します。 Q <= n/2の場合、最短側に沿ってr（丸いINT）パーツの逆を分割します。次に、最短側に沿ってn/r（丸められたint）パーツのサブレクトを分割します。次のサブレクツ部門の結果から、丸みを帯びた値を減算します。すべてのサブレクトを繰り返し、または必要な数の長方が作成されるまで繰り返します。