前回まで大雑把に問題の概要を説明してきました。
そして最後に下２つの問題を課題として挙げたのでした。
- 長方形ではない残りの多角形に長方形を敷き詰める
- 詰めていく部品の順番
今回は主に多角形内に長方形を敷き詰めるアルゴリズムを説明していきたいと思います。
また、もともとは、素材となるプリプレグから長方形の部品を切り出すという問題でしたので、
素材であるプリプレグのことを、素材多角形 、または単に素材
部品である長方形を、部品長方形、または単に部品
と言うことがあるので注意してください。
多角形内への長方形の敷き詰め
とりあえず今回も、具体的な例で考えて行くことにします。
+-----------A'------------+ +----C----+
| | +---------+
| |
| +-----+
| |
+-------------------+
上の例は前回の説明から抜き出して来たものです。
私たちは今、素材である多角形A'に、部品である長方形Cを詰めようとしています。
さてどこに詰めましょうか？
.
.
.
例えば、下のように詰めることができます。
+-----------A'------------+
| |
| +----C----+
| +---+-----+
| |
+-------------------+
理由
ここではプリプレグはロール状になっており、数メートルから数十メートルあることを想定しています。
当然、このプリプレグから部品を切り出す際、端から部品を必要なだけ切り出していきます。
そのためプリプレグの途中から部品を切り出すということはしません。
このような事情で、できるだけ端から部品を詰めて切り出すために、上図のように部品Cを配置しました。
アルゴリズム
先の考えをもとに、長方形の部品を詰めていくアルゴリズムを考えてみます。
大まかな手順は下の通りです。
- 残りの部品長方形がなければ正常終了
- 素材の多角形の端（今回は最も右端）を見つけ、その座標を対象とする
- 対称座標へ詰めることが可能な部品長方形を選ぶ。
- 詰められるものがなければ終了
- 対象の座標へ選んだ部品を詰める
- 素材の多角形から詰めた部品を差し引いた多角形を、新たな素材多角形とする
- (1)へ戻る
多分、上の手順で雰囲気は伝えられたかと思います…。
残りは、上のアルゴリズムをより具体的にし、コードに落とし込むだけです。
詰めていく部品の順番
前述の通りアルゴリズムはそれほど難しくなさそうです。
しかし、実際にやってみると様々な問題が見えてきました。
その中の一つに、前回課題に挙げたような「詰めていく部品の順番」の問題があります。
この問題について考えてみます。
+-----------A-------------+ +--B--+ +----C----+
| | | | +---------+
| | +-----+
| |
| |
+-------------------------+
さて、これは前回の例から持ってきたものですが、Aには、BとCどちらの部品から詰めていけばよいでしょうか？
前回説明したように、B、Cどちらを先に詰めるかで、カット後の残りの素材の量、切り端の量が変わってくるでしょう。
しかし、正直なところB、Cどちらを詰めたらよいかという疑問に対して、正確に答えるのは難しいです。
とはいえ、正確でなくとも詰める順番を決めなくては詰めらないため、
ここではそれらを大雑把に計算してみたいと思います。
部品の評価
評価に使用する パラメータ と 評価方法 について簡単に紹介します。
パラメータ
第一に、評価に使えそうな値を探さなくてはなりません。
例えば、こんなのはどうでしょうか。
+-----------A-------------+ -
| | | y
| | |
| +--B--+ -
| | |
+-------------------+-----+
|-------------------|
x
x: 部品を詰めた後の、詰めた真横の残りの素材の横幅y: 部品を詰めた後の、詰めた真上の残りの素材の縦幅
上図のxとyは、残りの素材の量を示すのでパラメータに使えそうです。
評価方法
パラメータを決めたので、次に評価方法について考えてみます。
評価は次のような評価関数で行うことにします。
f(x, y) = ax + by
- a, b: 任意の定数
この評価関数の値が、小さいほど良いか大きいほどよいかは場合によりますが、今は 小さいほど良い ことにしておきましょう。
例えば、以下のように設定してみます。
-
a = -1, b = -1xとyの値が大きければ大きいほどよいため、小さな部品が優先して詰められそうです。 -
a = 0, b = 1yが小さいければよいため、縦方向の隙間が小さくなるように優先して部品を詰められそうです。
以上のようにして、詰めていく部品の順番を決定していくことになります。
最適化骨くんは実際にこのような評価方法を採用しています。
最適化骨くんのアルゴリズムについては、ざっと説明し終えました。
現状の問題としては、
- 何をパラメータとするか[1]
ax + byなんて単純な評価関数で良いのか、他に良い評価方法があるか[2]- 評価関数内の定数
a、bは手動で設定しなければならない[3] - あまりに隙間なく詰めすぎると、人間が切断作業を行うことが困難[4]
など、多くの問題がありますが、
幸い、人力飛行機の桁焼き程度なら実用的なレベルで使用できているようです。
(内心ほっとしています。)
まだ、多角形の最も端から長方形を詰めていく部分については、具体的に説明していないので、
次回はこの辺りを説明したいと思っています。
1: まだ詰めていない他の部品の情報もパラメータに含めるとか？
2: なかなか思いつかない、せいぜいf(x, y) = ax * byにするくらい
3: 自動決定するなら、a+b=1となるようにしaを0.0~1.1の範囲で適当な数点でサンプリングして最適な値を見つけるとか？
4: 自動切断機を作るか、ある大きさの格子で仕切ってあえて余白ができるようにするか
