オーバーラップを最小限に抑えながら、異なるサイズの長方形をより大きな長方形内に分散させるのに役立つアルゴリズムを探しています。
ビン パッキング アルゴリズムを見てきましたが、長方形の間のスペースの量を最小限に抑えるようです (私の場合、パックされるすべてのアイテムは正方形になります)。
すべての正方形と外側の長方形の境界線との間の距離を最大にしたいと思います。
これが私がやろうとしていることの例です:
1674 次
2 に答える
1
ここ で説明されているようなアルゴリズムを使用して、それらをできるだけ密にパックし、ターゲットを囲む四角形に一致するように均等に拡張するとどうなるでしょうか?
たとえば、上の 3 つの長方形を 1 つの3x2箱に詰めることができ、外側の箱が7x5. 次に、ボックスの中心から各長方形の中心までのベクトルを取り、x 成分に を掛け、(7/3)y 成分に(5/2) を掛けると、新しい中心が得られます。
于 2011-12-13T17:59:25.403 に答える
-2
これは、ナップザック問題の一般化のようです。
動的計画法は、多項式時間に近い時間で解決します。
于 2011-12-12T22:01:45.603 に答える