(57)【要約】【課題】素材の配置構造の複雑さを制御しながらすべての区画分けを系統立てて探すことができる、素材の配置方法および切出し方法を提供すること。【解決手段】核グラフを構成する第１工程、核グラフを変更する第２工程、グラフから分割線分構成を行う第３工程、水平関係枝対応付けを行う第４工程、垂直関係枝対応付けを行う第５工程、各区画内に素材割り当てを行う第６工程、素材の縦横寸法に応じて各区画を水平圧縮する第７工程、および素材の縦横寸法に応じて各区画を垂直圧縮する第８工程からなる。【選択図】    図１
2004148475.tif 000002
【特許請求の範囲】
【請求項１】
複数箇の任意の大きさの素材を、基材上に配置構造の複雑さを規定しながら配置する素材の配置及び切出し方法であって、下記ａ．乃至ｇ．の条件下で核グラフを構成する第１工程と、
ａ．点は、１本の直線上に存在する。
ｂ．枝は、有向枝で全て左から右への向きである。
ｃ．枝は、水平関係枝と垂直関係枝の２種類である。
ｄ．点から出力する枝は、最右の点を除いて、水平関係枝だけが１本以上か垂直関係枝が１本以上である。最右の点から出力する枝は存在しない。
ｅ．点に入力する枝は、水平関係枝が高々１本と垂直関係枝が高々１本である。
ｆ．水平関係枝の始点と終点の間に存在する点には水平関係枝が入力する。
ｇ．垂直関係枝の始点と終点の間に存在する点には垂直関係枝が入力する。
点数が素材数と同数又はそれ以上になるまで、核グラフから始めて順次下記ａ．乃至ｆ．の方法から一の方法を選択し、グラフを変更する第２工程と、
ａ．点に対し、その点を水平関係枝で結ばれた２点で置き換える。その点に水平関係枝が入力していたときは、その入力枝の先を置き換えた点のうちの左の点に変更する。その点に垂直関係枝が入力していたときはその入力枝を除去し、その入力枝の元から置き換えた点の両点に向けて２本の垂直関係枝を追加する。その点に出力枝が存在するときは、その点の全ての出力枝の元を置き換えた点のうちの右の点に変更する。
ｂ．点に対し、その点を垂直関係枝で結ばれた２点で置き換える。その点に水平関係枝が入力していたときは、その入力枝を除去し、その入力枝の元から置き換えた点の両点に向けて２本の水平関係枝を追加する。その点に垂直関係枝が入力していたときは、その入力枝の先を置き換えた点のうちの左の点に変更する。その点に出力枝が存在するときは、その点の全ての出力枝の元を置き換えた点のうちの右の点に変更する。
ｃ．最左の点の左に１点を追加する。最左の点を含む水平関係枝が入力されていない点を１点以上左から順に選び、それらの点に追加した点から水平関係枝を追加する。
ｄ．最左の点の左に１点を追加する。最左の点を含む垂直関係枝が入力されていない点を１点以上左から順に選び、それらの点に追加した点から垂直関係枝を追加する。
ｅ．最右の点の右に１点を追加し、最右の点からその点へ水平関係枝を追加する。
ｆ．最右の点の右に１点を追加し、最右の点からその点へ垂直関係枝を追加する。
前記第２工程で得られたグラフを基に、点から出力している枝を基材の区画分けにおける区画と区画の間にある分割線分に対応させる第３工程と、
前記第２工程で得られたグラフを基に、水平関係枝が出力している点に対応している区画はその枝が入力している点に対応している区画よりも左に位置すると定義づける第４工程と、
前記第２工程で得られたグラフを基に、垂直関係枝が出力している点に対応している区画はその枝が入力している点に対応している区画よりも上に位置すると定義づける第５工程と、
切り分けられた区画に、基材上に配置すべき素材を高々１箇割当てる第６工程と、
上記第４工程乃至第６工程の定義に基づく関係と各区画に割当てられた素材の幅を保持しながら垂直線分を資源として想定している基材の左辺に近づける第７工程と、
上記第４工程乃至第６工程の定義に基づく関係と各区画に割当てられた素材の高さを保持しながら水平線分を資源として想定している基材の上辺に近づける第８工程とを有することを特徴とする配置構造の複雑さを制御可能な素材の配置及び切出し方法。
【請求項２】
請求項１に記載の第１工程における核グラフの構成、第２工程におけるグラフの拡張、および第５工程における素材の割当てを変更して、再び請求項１に記載の各工程を繰り返すことを特徴とする配置構造の複雑さを制御可能な素材の配置及び切出し方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数の素材の配置構造の複雑さを制御して、基材上に素材を配置する方法及び基材から複数の素材を切り出す方法に関する。
【０００２】
【従来の技術】
平面基材上に素材を配置する半導体集積回路やプリント基板の配置設計或は布地などの平面基材から各種サイズの複数の素材を切り出すに際しては、素材の配置設計（フロアプラン）が重要である。基材上への素材の配置又は基材からの素材の切り出しにおいては、可及的に小さな面積の基材を用いることができれば製造コストを低減せしめ得る。
【０００３】
しかしながら、半導体集積回路の配置設計等においては、素材（部品）の面積は決定しているが、幅（横寸法）および高さ（縦寸法）が未定である素材を配置する必要がある場合がある。従来、図７に示すような、水平又は垂直の分割線によって素材の配置領域を再帰的に分割することができる配置構造即ちスライス構造を用いて幅と高さが未定の部品の配置設計がなされていた。この配置構造によるときは、素材の幅（横寸法）および高さ（縦寸法）が任意であれば、全素材の面積の総和と同じ面積の基材上での素材の配置が高速に実現できる。また、素材の幅や高さに制限がある場合も、基材の面積が最小となるような素材の幅と高さを容易に計算できる。
【０００４】
しかしながら、図８に示すような素材の配置構造の場合、前記スライス構造では実現できない。発明者らのうちの１人が先に提案した特開平９−１０８９３３号公報および特開平９−１０８９３４号公報に開示されている素材の配置方法によれば、図８に示すような配置構造を実現できる。しかし、図８に示す配置構造および図９に示す配置構造の複雑さの違いに着目して、区画分けを系統立てて列挙することができない問題がある。
【０００５】
【発明が解決しようとする課題】
図９に示す素材の配置構造の複雑さは、基材の面積が最小となるような素材（部品）の幅および高さの計算の容易さに関係しているため、配置構造の複雑さを制御して素材の配置をすることはきわめて重要である。
【０００６】
本発明は、素材の配置構造の複雑さを制御しながらすべての区画分けを系統立てて探すことができる素材の配置方法及び切り出し方法を提供することを目的とする。
【０００７】
【課題を解決するための手段】
上記課題を解決するための請求項１に記載の発明は、複数箇の任意の大きさの素材を、基材上に配置構造の複雑さを規定しながら配置する素材の配置及び切出し方法であって、下記ａ．乃至ｇ．の条件下で核グラフを構成する第１工程と、
ａ．点は、１本の直線上に存在する。
ｂ．枝は、有向枝で全て左から右への向きである。
ｃ．枝は、水平関係枝と垂直関係枝の２種類である。
ｄ．点から出力する枝は、最右の点を除いて、水平関係枝だけが１本以上か垂直関係枝が１本以上である。最右の点から出力する枝は存在しない。
ｅ．点に入力する枝は、水平関係枝が高々１本と垂直関係枝が高々１本である。
ｆ．水平関係枝の始点と終点の間に存在する点には水平関係枝が入力する。
ｇ．垂直関係枝の始点と終点の間に存在する点には垂直関係枝が入力する。
点数が素材数と同数又はそれ以上になるまで、核グラフから始めて順次下記ａ．乃至ｆ．の方法から一の方法を選択し、グラフを変更する第２工程と、
ａ．点に対し、その点を水平関係枝で結ばれた２点で置き換える。その点に水平関係枝が入力していたときは、その入力枝の先を置き換えた点のうちの左の点に変更する。その点に垂直関係枝が入力していたときはその入力枝を除去し、その入力枝の元から置き換えた点の両点に向けて２本の垂直関係枝を追加する。その点に出力枝が存在するときは、その点の全ての出力枝の元を置き換えた点のうちの右の点に変更する。
ｂ．点に対し、その点を垂直関係枝で結ばれた２点で置き換える。その点に水平関係枝が入力していたときは、その入力枝を除去し、その入力枝の元から置き換えた点の両点に向けて２本の水平関係枝を追加する。その点に垂直関係枝が入力していたときは、その入力枝の先を置き換えた点のうちの左の点に変更する。その点に出力枝が存在するときは、その点の全ての出力枝の元を置き換えた点のうちの右の点に変更する。
ｃ．最左の点の左に１点を追加する。最左の点を含む水平関係枝が入力されていない点を１点以上左から順に選び、それらの点に追加した点から水平関係枝を追加する。
ｄ．最左の点の左に１点を追加する。最左の点を含む垂直関係枝が入力されていない点を１点以上左から順に選び、それらの点に追加した点から垂直関係枝を追加する。
ｅ．最右の点の右に１点を追加し、最右の点からその点へ水平関係枝を追加する。
ｆ．最右の点の右に１点を追加し、最右の点からその点へ垂直関係枝を追加する。
前記第２工程で得られたグラフを基に、点から出力している枝を基材の区画分けにおける区画と区画の間にある分割線分に対応させる第３工程と、
前記第２工程で得られたグラフを基に、水平関係枝が出力している点に対応している区画はその枝が入力している点に対応している区画よりも左に位置すると定義づける第４工程と、
前記第２工程で得られたグラフを基に、垂直関係枝が出力している点に対応している区画はその枝が入力している点に対応している区画よりも上に位置すると定義づける第５工程と、
切り分けられた区画に、基材上に配置すべき素材を高々１箇割当てる第６工程と、
上記第４工程乃至第６工程の定義に基づく関係と各区画に割当てられた素材の幅を保持しながら垂直線分を資源として想定している基板の左辺に近づける第７工程と、
上記第４工程乃至第６工程の定義に基づく関係と各区画に割当てられた素材の高さを保持しながら水平線分を資源として想定している基材の上辺に近づける第８工程とを有することを特徴とする配置構造の複雑さを制御可能な素材の配置及び切出し方法である。
【０００８】
請求項２に記載の発明は、請求項１に記載の第１工程における核グラフの構成、第２工程におけるグラフの拡張、および第５工程における素材の割当てを変更して、再び請求項１に記載の各工程を繰り返すことを特徴とする配置構造の複雑さを制御可能な素材の配置及び切出し方法である。
【０００９】
【発明の実施の形態】
以下、本発明をその好ましい実施形態に則して説明する。
【００１０】
先ず、下記条件の下で核グラフを構成する（第１工程）。
ａ．点は、１本の直線上に存在する。
ｂ．枝は、有向枝で全て左から右への向きである。
ｃ．枝は、水平関係枝と垂直関係枝の２種類である。
ｄ．点から出力する枝は、最右の点を除いて、水平関係枝だけが１本以上か垂直関係枝だけが１本以上である。最右の点から出力する枝は存在しない。
ｅ．点に入力する枝は、水平関係枝が高々１本と垂直関係枝が高々１本である。
ｆ．水平関係枝の始点と終点の間に存在する点には水平関係枝が必ず入力する。
ｇ．垂直関係枝の始点と終点の間に存在する点には垂直関係枝が必ず入力する。
図１に、点数を５とし、水平関係枝を実線で、垂直関係枝を点線で表した核グラフの一例を示す。
【００１１】
次に、点数が素材数と同数又はそれ以上になるまで、核グラフから始めて順次下記方法から一の方法を選択し、グラフを変更する（第２工程）。
ａ．点に対し、その点を水平関係枝で結ばれた２点で置き換える。その点に水平関係枝が入力していたときは、その入力枝の先を置き換えた点のうちの左の点に変更する。その点に垂直関係枝が入力していたときはその入力枝を除去し、その入力枝の元から置き換えた点の両点に向けて２本の垂直関係枝を追加する。その点に出力枝が存在するときは、その点の全ての出力枝の元を置き換えた点のうちの右の点に変更する。
ｂ．点に対し、その点を垂直関係枝で結ばれた２点で置き換える。その点に水平関係枝が入力していたときは、その入力枝を除去し、その入力枝の元から置き換えた点の両点に向けて２本の水平関係枝を追加する。その点に垂直関係枝が入力していたときは、その入力枝の先を置き換えた点のうちの左の点に変更する。その点に出力枝が存在するときは、その点の全ての出力枝の元を置き換えた点のうちの右の点に変更する。
ｃ．最左の点の左に１点を追加する。最左の点を含む水平関係枝が入力されていない点を１点以上左から順に選び、それらの点に追加した点から水平関係枝を追加する。
ｄ．最左の点の左に１点を追加する。最左の点を含む垂直関係枝が入力されていない点を１点以上左から順に選び、それらの点に追加した点から垂直関係枝を追加する。
ｅ．最右の点の右に１点を追加し、最右の点からその点へ水平関係枝を追加する。
ｆ．最右の点の右に１点を追加し、最右の点からその点へ垂直関係枝を追加する。
図２に、上記核グラフの、点ｂを水平関係枝で結ばれた点ｂ１、ｂ２に置き換え、点ｅを垂直関係枝で結ばれた点ｅ１、ｅ２に置き換え、最左点ａの左に点ｆを追加し、その点から点ａに垂直関係枝を追加した結果を示す。
【００１２】
図２に示すグラフの各点から出力している枝を、基材の区画分けにおける区画と区画の間にある分割線に対応させる（第３工程）。
【００１３】
そして、点ａから出力している水平関係枝（ａ，ｂ１）、（ａ，ｃ）に対して、水平関係枝（ａ，ｂ１）が入力している点ｂ１に対応する区画ならびに水平関係枝（ａ，ｃ）が入力している点ｃに対応する区画は、水平関係枝（ａ，ｂ１）、（ａ，ｃ）に対応する線分の右に位置すると定義づける（第４工程）。
【００１４】
同様に、点ｂ２から出力している垂直関係枝（ｂ２，ｃ）、（ｂ２，ｅ１）に対して、垂直関係枝（ｂ２，ｃ）が入力している点ｃに対応する区画ならびに、垂直関係枝（ｂ２，ｅ１）が入力しているｅ１に対応する区画は、垂直関係枝（ｂ２，ｃ）、（ｂ２，ｅ１）に対応する線分の下に位置すると定義づける（第５工程）。
【００１５】
これらの作業によって、任意の線分と任意の区画の位置関係が定義づけられ、図３に示すような区画分けが得られる。
【００１６】
図３に示す区画ｆ，ａ，ｂ１，ｂ２，ｃ，ｄ，ｅ１，ｅ２に、配置すべき素材（部品）を割当てる（第６工程）。このとき、１箇の区画が収納する素材は、高々１箇である。図４に、図３に示す区画に７箇の素材を割当てた様子を示す。
【００１７】
図４に示す区画分けにおいて、左右何れかの辺を垂直基線側と定める。
たとえば、左側を垂直基線側と定める。区画の左側垂直線分の位置が決定されている区画に対して、区画の右側垂直線分を、各区画に割当てられた素材の幅以上の範囲内で、可及的に左側垂直線分に近くなるように位置させる（第７工程）。
図５に、区画ａの右側垂直線分１を、区画ａに割当てられた素材の幅だけ左側垂直線分から離して位置させた例を示す。
【００１８】
同様に、素材の上下何れかの辺を水平基線側と定める。たとえば、上側を水平基線側と定める。区画の上側水平線分の位置が決定されている区画に対して、区画の下側水平線分を、各区画に割当てられた素材の高さ（縦寸法）以上の範囲内で、可及的に上側水平線分に近づけて位置させる（第８工程）。
【００１９】
こうして、水平線分と垂直線分を移動させ、図６に示す素材配置後の区画を得る。その結果、全ての素材（部品）を配置するのに必要な面の大きさが判明するので、この面の大きさを下回らない基材を用意して、基材上に素材を配置したり、基材たとえば布地から素材を切り出すことができる。なお、基材から素材を切り出す場合には、基材上に切り出しパターンが配置され、この切り出しパターンに基づいて素材を切り出す。
【００２０】
処で、得られた基材の面の大きさに不満で、基材の面をさらに小さくしたい場合には、核グラフを変更するか、グラフの変更方法の選択を変更するか、グラフによって定義された区画への素材の割当てを変更すればよい。
【００２１】
また、本発明の素材の配置方法及び切り出し方法は、核グラフによって定められた配置構造の複雑さを保持しているので、所望の配置構造の複雑さをもった核グラフから開始すれば、配置構造の複雑さを制御することが可能である。
【００２２】
さらに、あらゆる区画分けを系統立てて列挙することができるので、時間さえあれば全ての配置を検討することも可能である。これらの変更は無作為に行うことも可能であるし、変更後と変更前とを比較して改善できそうな核グラフやグラフの変更方法の選択や素材の割当てを推定して行うことも可能である。
【００２３】
以上、本発明の実施の形態を詳しく述べたが、本発明は前記実施の形態に限定されるものではなく、特許請求の範囲の項に記載された本発明の要旨の範囲内で、様々な変更を施すことが可能である。本発明の実施形態の変更例を下記する。（１）上記実施の形態においては、素材数は７、区画数は８であるが、基材上に配置しようとする素材数および区画数は、区画数が素材数以上である限り当然変更可能であり、たとえば、素材数：１６、区画数：６４でも可能である。
（２）上記実施の形態においては、素材の幅と高さを変更していないが、素材の幅と高さを変更することも可能である。
（３）本発明において対象とする基材や素材は特に限定されるものではない。しかし、回路素子を素材とし、回路基板を基材とする半導体集積回路やプリント基板配置設計が本発明の適用分野として最適である。
また、本発明は、布地などの平面基材から各種大きさの素材を切り出したりする場合にも適している。
（４）グラフなどは、紙などに現実に形成する必要はなく、電子計算機などが作り出す仮想空間上に形成することも可能である。
（５）各工程は、必ずしも記載された順番に行う必要はない。第４工程から第５工程、第７工程から第８工程は、その順序を逆に行うこともまた、同時に行うことも可能である。
（６）上記実施の形態においては、素材は方形であるが、素材配置のために確保する区画が方形であれば、素材自体は必ずしも方形である必要はない。
（７）上記実施の形態においては、水平関係枝、垂直関係枝をそれぞれ実線と点線で表現したが、これらの枝を他の形態に変更してもよいこと勿論であり、電子計算機上のメモリ空間における状態に変更可能である。
（８）上記実施の形態においては、区画名を英字アルファベットで記したが、それ以外の数字、文字、マーク、電子計算機上のメモリ空間における状態等に変更可能である。
（９）上記実施の形態においては、核グラフから変更を施してグラフを得ているが、下記条件を満足する範囲内で、点の追加や除去、枝の追加や除去を行うことも可能である。
ａ．点は、１本の直線上に存在する。
ｂ．枝は、有向枝で全て左から右への向きである。
ｃ．枝は、水平関係枝と垂直関係枝の２種類である。
ｄ．点から出力する枝は、最右の点を除いて、水平関係枝だけが１本以上か垂直関係枝が１本以上である。最右の点から出力する枝は存在しない。
ｅ．点に入力する枝は、水平関係枝が高々１本と垂直関係枝が高々１本である。
ｆ．水平関係枝の始点と終点の間に存在する点には水平関係枝が入力する。
ｇ．垂直関係枝の始点と終点の間に存在する点には垂直関係枝が入力する。
【００２４】
【発明の効果】
本発明によれば、区画に対応した点と水平関係枝と垂直関係枝の２種類の枝からなり、ある条件を満たす核グラフを用意し、この核グラフを選択的に変更し、そのグラフを基に線分と区画の位置関係を定義し、区画に高々１箇の素材を配置し、定義された関係に違反しない範囲かつ区画に素材が収納できる範囲で区画を圧縮することが容易にできる。
【００２５】
また、得られた配置に満足できない場合には、核グラフ変更、グラフの変更方法の選択の変更、グラフによって定義された区画への素材の割当ての変更で容易に対応することができる。変更後のグラフの種類は、区画数をＭとすると、多くとも２Ｍ・（Ｍ−１）！しかないので、素材の配置の管理が容易である。
【００２６】
さらに、核グラフの配置構造の複雑さを保持してグラフの変更を行うので、配置構造の複雑さを制御することも容易である。
そして、素材の代わりに切り出しパターンを配置した場合には、この切り出しパターンに基づいて素材を切り出すことができる。
【図面の簡単な説明】
【図１】点数を５とし、水平関係枝を実線で、垂直関係枝を点線で表した核グラフの一例を示すグラフ
【図２】図１に示す核グラフを変更したグラフの一例を示すグラフ
【図３】図２に示すグラフを基に、本発明の第３工程乃至第５工程によって得られる区画分けの結果を示す平面図
【図４】図３に示す区画に、素材を割当てた一例を示す平面図
【図５】図４に示す区画ａの右側線分１を、区画ａに割当てられた素材の幅だけ左側垂直線分から離して位置させた状態を示す平面図
【図６】本発明の第７工程乃至第８工程によって、水平線分と垂直線分を移動させた結果を示す平面図
【図７】素材の配置構造におけるスライス構造の一例を示す平面図
【図８】スライス構造では実現できない配置構造の一例を示す平面図
【図９】図８に示す配置構造よりも複雑な配置構造を示す平面図
【図１】
2004148475.tif 000003
【図２】
2004148475.tif 000004
【図３】
2004148475.tif 000005
【図４】
2004148475.tif 000006
【図５】
2004148475.tif 000007
【図６】
2004148475.tif 000008
【図７】
2004148475.tif 000009
【図８】
2004148475.tif 000010
【図９】
2004148475.tif 000011