ある矩形の中に複数の矩形が入りきるかを判定したい

質問

こんにちは、いつも拝見させてもらっています。

ある大きさの矩形の中に、違った大きさの複数矩形が収まりきるかを判定するアルゴリズムをご存知でしょうか？

具体的に言うと、複数のビットマップ画像を色々と並び替えて、一定の大きさの矩形（例えば1024*1024ドット）に収まりきるかを判定したいのです。

条件としては、
１．収めたい矩形のサイズは決まっている
２．張り合わせたい矩形は複数で、それぞれサイズはバラバラ
３．張り合わせたい矩形を回転させてはいけない（縦横のサイズは変更できない）

簡単だと思ったのですが、意外とうまく行きません。
数学にも疎いので、どういう方面を参考にして良いやらわかりません。
みなさん、お知恵をお越しください。
それではよろしくお願いします。

回答No.1

Willyt · ベストアンサー

この問題は『板取り』と称し、厄介な問題を抱えた命題なのです。鋼板から構造物の材料を切り出すとき、矩形を含めたさまざまな形のものを効率よく並べることができれば、コスト削減に繋がるので大変注目されて来ました。しかし、これをどんな場合にでも適用できるアルゴリズムは現在のところ発見されておらず、どのソフトでもトライアルで求めることでお茶を濁しているのが現状です。私も昭和４０年代の後半からこの問題を含めた製造システムに携わって来たのですが、頭の痛い問題でした。
　従ってこれの普遍的なアルゴリズムを完成できれば巨額の利益が上がられる筈ですが、ちょっとやそっとでは行かないということです。どうぞ頑張って下さい。

お礼

有難うございます。大変勉強になりました。
なんという問題に手を出してしまったのでしょう！
簡単なのでは？と思った自分が恥ずかしいです。
ご教授、有難うございました。