解説

最適化骨くんのアルゴリズム解説(1)

先日、Twitterの方で紹介しました、最適化骨くんについての解説したいと思います。

最適化骨くんとは、プリプレグから桁焼きのために必要な部品を切り出すための図面を生成するプログラムです。

今回は最適化骨くんを作った理由から簡単に説明していこうと思います。

経緯

Craftpalでは、プリプレグから桁巻の部品を切り出すために、一度CADを使って切り出し図面を生成しています。

この図面作成は、だいたい下の手順で行います。

  1. 残っているプリプレグの寸法を図る
  2. 図った寸法からプリプレグの図面をCADで生成
  3. CADの図面に部品を書き入れる
  4. プリプレグの切れ端が少なくなるよう調整/再配置する

このなかでも、プリプレグの切れ端ができるだけ少なくなるようにする作業が、厄介な問題です。

実際の図面が上図になります。
緑線が余っているプリプレグ、赤線が切り出す部品を表しています。

従来はCADソフトを用いて手動で作成していました。

そこで、なんとかこの作業を自動化できないか考えることにしました。
試行錯誤の末、完成したプログラムが最適化骨くんです。


さて、本題であるアルゴリズムの解説をしていきます。

手法自体は単純です。

今回は、基本的な問題から考えて行こうと思います。

長方形の中に長方形を入れる

長方形の形をしたプリプレグに、長方形の部品を入れられるか? という問題を考えます。

つまり、長方形の中に長方形を入れられるか、という問題です。

また、ここでは"親"長方形の中に"子"長方形を入れる、ということにします。

これは非常に簡単に解けそうです。実際、以下の様にCで書けます。[1]

int main() { struct rect { int x; int y; }; struct rect parent = { x = 200, y = 10 }; struct rect child = { x = 10, y = 1 }; if (child.x <= parent.x && child.y <= parent.y) { // OK } else { // NG } }

上記のように親長方形の中に子長方形を入れる問題が解けることがわかりました。

しかし、これは非常に限定的な問題なので、次は、この問題を拡張した問題を説いていくことにします。

現実的には、

  • 長方形のプリプレグに複数の長方形を敷き詰める
  • もともと長方形ではない残りのプリプレグに長方形を敷き詰める

という問題が頻繁に起こります。

次に、親長方形に複数の子長方形を敷き詰める問題について考えて行こうと思いますが、今回は、このあたりで筆を置くことにします。


1: どうやって説明するか悩みましたが、私が一番説明し易い、Cで説明することにします。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

正しい答えでコメントできます *