最終回になります。
これまで、アルゴリズムの概要の説明と、詰めていく部品の評価を行ってきました。
そして前回、下のアルゴリズムを示しました。
- 残りの部品長方形がなければ正常終了
- 素材の多角形の端（今回は最も右端）を見つけ、その座標を対象とする
- 対称座標へ詰めることが可能な部品長方形を選ぶ。
- 詰められるものがなければ終了
- 対象の座標へ選んだ部品を詰める
- 素材の多角形から詰めた部品を差し引いた多角形を、新たな素材多角形とする
- (1)へ戻る
前回の部品の評価は、上の手順の３番目で必要なことでしたが、
今回は手順2の、多角形の右端から詰めていく作業に注目します。
つまり、以下が今回のテーマとなります。
- 多角形の右端から部品を詰める方法
- 長方形を詰める位置をどのように探索するか
多角形に長方形を詰める
いつも通り、下の例で考えていきます。
+-----------A-------------+ +--B--+ +----C----+
| | | | +---------+
| | +-----+
| |
| |
+-------------------------+
上のように 長方形 Aの中に、右端から、別の 長方形 を詰めて行くのは容易にできます。
今は、長方形Bを詰めるとしましょう。
+-----------A'------------+ +----C----+
| | +---------+
| |
| +-----+
| |
+-------------------+
すると上のように、長方形Aは、 多角形 A'となります。
今私たちは、多角形A'の右端に長方形Cを詰めようとしています。
これは、例えば、下のようにできます。
+-----------A'------------+
| |
| +----C----+
| +---+-----+
| |
+-------------------+
アルゴリズム
先のことをアルゴリズムに起こしてみます。
まず、多角形A'を長方形に分割します。
(この問題では、切り出しの都合上、素材多角形は長方形を縦に並べたもので表すことができます。)
+-----------A'------------+
| |
| |
+-------------------+-----+
| |
+-------------------+
この長方形の中で、最も横方向の幅が大きいものを選択します。上図ではA'の上方の長方形になります。
次にその長方形に部品長方形Cを詰めます。これは容易にできるのでした。
結果、下のようになります。
+-----------A'------------+
| |
| +----C----+
+---------------+---+-----+
| |
+-------------------+
以上から、アルゴリズムはこのようになります:
- 素材多角形を長方形に分割する
- 分割した長方形の中で最も右に長いものを選ぶ
- 選んだ長方形の右端に部品長方形を詰める
このアルゴリズムであれば問題を、単純な長方形に長方形を詰める問題をもとに、解くことができます。
切れ端、領域の統合
さて、次に下の例について考えてみます。
+-----------D-------------+ +-G-+
| | | |
+-------E-------+---------+ | |
| | +---+
+---------F-----+---+
| |
+-------------------+
先程の例とことなるのは、長方形Gがどの長方形(D,E,F)にも入らないということです。
この場合は、長方形を統合して、新たな長方形にできれば解決できそうです。
.
まずは、アルゴリズムに沿って考えてみましょう。
はじめに長方形の中で最も横幅が大きいものを選びます、今回はDとなります。
そこにGを詰めようとしますが、DにGは入らないため失敗します。
.
.
.
ここで、Dの隣りにあるEをDと統合してみたらどうでしょうか？
+-------H-------+.......... +-G-+
| | . | |
| |.......... | |
| | +---+
+---------F-----+---+
| |
+-------------------+
- 点線: 切れ端部分
長方形D, Eを統合してみると、新たに長方形Hができました。
Hには、Gが詰められそうです。では詰めてみましょう。
+-------H-------+..........
| +-G-+ .
| | |..........
| | |
+---------F-+---+---+
| |
+-------------------+
最終的にできた、多角形に長方形を１つ詰めるアルゴリズムは下の通りです:
- 素材多角形を 長方形に分割する
- 分割した長方形の中で 最も幅が長いものを選ぶ
- 選んだ長方形に部品長方形が詰められれば４へ、そうでなければ５へ
- 選んだ長方形の右端に部品長方形を詰める、終了
- 選んだ長方形と次に横幅が長い長方形を 統合する
- 統合が成功すれば２へ、これ以上統合できないなら終了
このアルゴリズムを用いて自動生成した図面を上図に示しました。
余分な切れ端が少なく、同じ形の部品が集まって配置されていることがわかります。
課題
上記のように詰めることができました。
この調子でいけば、実用上のほとんどの問題は解けそうです。
しかし、課題もあります。
このアルゴリズム上では、点線で示した部分が切れ橋になります。
切れ端はどの部品も詰めることができない領域です。
このアルゴリズムでは、この切れ端をいかに少なくするかが重要な課題のひとつになります。
例えば、先程はD, Eを統合しましたが、E, Fを統合していたら？
結果的には、E, Fを統合したほうが切れ端が少なくて済んだでしょう。
例えば以下のような課題があります:
- 分割したどの長方形から長方形を詰めていくか
- どのように長方形の領域を統合していくか
- 長方形の右上から詰めるか右下からつめるか
余談
できれば、問題は楽にときたいと思います。
そのためには、問題の見方を変えたり、分割したり、簡単な問題にどうにか帰着する必要があります。
今回はたまたま、このように、長方形に長方形を詰める問題を単位として解くことができ幸運でした。
ただし、このアルゴリズムよって最適解が得られるかというのは別の問題のため注意が必要です。
最後に
プリプレグは高価な素材です、そのためCraftPalでは出来る限り、無駄な端材を出さないように努力を行っております。
その一環で「最適化骨くん」も開発されました。
これまでの記事で、最適化骨くんが何を解決しようとしているか、その解決方法、課題について大まかに紹介できたかと思います。
今回、紹介しきれなかったこともありますが、これについては機会があればまた何処かで…[1] [2]
ソースコードはこちらで公開しています。
1: 最適化骨くんはDXF形式の図面生成、レイヤーわけ、座標計算、なども行っています。
2: コア実装は"普通の"C++で行いましたので、クロスプラットフォームへの移植も可能です。
