JPH0328974A - 印刷配線板自動配線設計装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は印刷配線板上に配線の導体模様を設計する自動
配線設計装置に関する。

［従来の技術］ 従来の自動配線設計装置は印刷配線板平面に存在すべき
配線の導体模様を印刷配線板上の主格子，副格子上に集
中させ．配線の導体模様を線分情報として管理しながら
．先に配線した導体模様を動かさずに．新配線経路を探
索するという静的な配線経路探索手段を有していた。

また，これを改良したリップアップリルート法を用いた
自動配線設計装置がある。これは新配線の配線経路を妨
害する既導体模様を除去し，新配線の導体模様を確定し
てから除去した配線を再配置する方法である。

〔発明が解決しようとするａｌｌｆｌ］上述した従来の
自動配線設計装置は，１度配線の導体模様を確定してし
まうと．後に別の配線を配置する際に配線経路を妨害す
ることがある。これを第１２図を用いて説明する。

第１２図の例は部品端子間に２本まで配線の導体模様を
配置できる設計例（主格子間２本設計）を示している。

今，印刷配線板２１の配線禁止領域１１−１によって囲
まれた範囲で，始点端子１６−１と終点端子１６−２を
新導体模様により接続することを考える。この時，端子
１６−１．１６−２と配線禁止領域１１−１との間隔が
小さいため．その間に配線パターンは通せないものとす
る。端子１６−１と１６−２を接続する経路は既導体模
様１０−１が配線経路を塞いでいるため配線不可能とな
る。

このように既導体模様１０−１が新配線の配線経路を妨
害する状況が度々発生し，自動結線率を低下させるとい
う欠点があった。

これを改良した従来のリップアップリルート法は既導体
模様を再配置することによりこの欠点を除去しようとし
たのであるが，その再配置するべき経路を探索する際に
，更に他の既導体模様１〇一１により妨害されるので，
その繰りの返しに多大な計算時間を要する課題があった
。更に，文献エレクトロニクス（Ｅｌｅｃｔｒｏｎｉｃ
ｓ）　１　９　７　８年１月１９日Ｐ．１０２と日経エ
レクトロニクス１９７８年６月２６８Ｐ．１３２で．既
導体模様１０−１間に迷路法で新配線の経路を探索して
既導体模様１０−１を押し分けて配線する方法が提案さ
れているが．この方法は探索した経路の回りの既導体槙
様１０−１を押し分けられるか否かの判断方法が不明で
ある。また．押し分ける方法が不明であり，実現性に乏
しい課題があった。

本発明は従来装置のこのような課題を解決しようとする
もので，短かい計算処理時間で高結線率を実現できる印
刷配線板自動配線設計装置を提供することにある。

［課題を解決するための手段］ 本発明によると，第１に，印刷配線板の導体模様の画像
記憶部と，該画像記憶部に記憶した配線の導体模様を移
動させて新配線の導体模様を挿入する押し分け手段を持
つ制御部を有することを特徴とする印刷配線板自動配線
設計装置が得られる．第２に，前記第１の装置において
，前記画像記憶部が，導体素片と境界辺と節と間隔領域
を構造体として記憶する手段を有し，前記制御部が，前
記画像記憶部に記憶した間隔領域を通る経路を探索する
経路探索手段と，間隔領域に新しい導体素片を挿入し，
境界辺にスルホールを挿入して既スルホールを押し分け
る押し分け手段と，境界辺ごとにスルホール設定可能性
と配線導体の挿入可能性を調らべ，障害がある場合にそ
れらを表示し，操作卓からの指示により部品を移動する
経路障害検出手段を有することを特徴とする印刷配線板
自動配線設計装置が得られる。

第３に，前述の第１の装置であって，画像記憶部が，導
体素片と．境界辺と，節と，間隔領域と，スルホール予
約点とを構造体として記憶する手段を有し．前記制御部
が，前記画像記憶部に記憶した間隔領域を通る経路を探
索する経路探索手段と，新しい導体素片およびスルホー
ルを挿入し，それに伴い既スルホールを押し分ける押し
分け手段と，間隔領域毎にスルホール予約点を調らべ，
境界辺毎に配線導体の挿入可能性を調らべ，障害がある
場合にそれらを表示し，操作卓からの指示により部品を
移動する経路障害検出手段とを有することを特徴とする
印刷配線板自動配線設計装置が得られる。

第４に，前述の第１の装置であって．前記画像記憶部が
配線の導体模様を画素に分解して記憶する手段を有し，
前記制御部が，前記画像記憶部に記憶した既配線の導体
模様の間隙に新配線の仮経路を探索する経路探索手段と
，該仮経路と既配線の導体模様との間に１画素以上の間
隔をあけるように既配線の導体模様を移動しながら新配
線の導体模様を挿入する押し分け手段と，スルホール設
定可能な領域を調べる処理および固定部品の間の配線容
量を調べる処理を行なう経路障害検出手段とを有するこ
とを特徴とする自動設計装置が得られる。

第５に，前記押し分け手段がスルホールの移動も行なう
ことを特徴とする自動配線設計装置であってもよい。

第６に，前述の第４の装置であって，前記画像記憶部の
１つの画素が，導体の有無を示すビ・ントと，導体の固
定指定を書き込むビットと，探索波紋を書き込むビット
と，探索の障壁を書き込むビットと，スルホール使用可
能ビット以外に，移動するスルホールの識別ビットと，
移動するスルホールに結線している導体の識別ビットと
を有し，前記押し分け手段および経路障害検出手段を用
いて．結線に障害となる該画像記憶部に記憶された固定
指定のスルホールおよびそのスルホールに結線している
導体模様を移動させて，新たな導体模様を挿入するスル
ホール移動手段を有することを特徴とする自動配線設計
装置が得られる。

第７に．前述の第４の装置であって，経路探索手段が，
前記画像記憶部の記憶容量に対して．画像記憶部に記憶
された導体模様と固定指定の画素の占める割合を算出し
て係数化し，その係数の示す値により経路探索領域を求
め，経路探索領域内を経路探索することを特徴とする自
動配線設計装置が得られる。

［実施例］ 実施例１ 次に，本発明について，図面を参照して説明する。第１
図（１），（２）は本発明の一実施例のブロック図とそ
の各手段間の処理の関係を示すブロック図である。印刷
配線板の各層面に対応させたｎｘｎ×１６ビットの画像
記憶部１と１画像記憶部１の記憶を読み出し，書き込む
機能を有する制御部２を持つ。制御部２は部形状入力手
段２−０と，結線点入力手段２−１と，経路探索手段２
−２と，押し分け手段２−３と，経路障害検出手段２−
４とから成る。他に，画像表示部３，操作卓４，印刷部
５，通信部６，制御用記憶部７及び磁気記録部８を持つ
。

第２図は第１の実施例の画像記憶部１の１画素９に対す
るビット構成１−１を示す。１６ビットから成る画素９
をｎＸｎ個で２次元的な広がりを持つ画像群を構戊する
。この１つ１つの画素は以下のビットを有する。

（１）導体模様１０ （２）固定指定１１（禁止領域１１−１，スルホール１
１−２．部品端子１１−３） （３）スルホール使用可能フラグｌ２ （４〉経路障害フラグ１３ （５〉経路探索レベル１４ （６）仮経路１５ これらのビットは平面状に並らべて１つの模様となる種
類の違う模様の１要素である。

第３図はこの第１の実施例の手順を示す流れ図，第４図
（１），　（２）．　（３）は導体模様の例を示す図，
第５図（１）〜（６）はこの第１の実施例の手順を示す
流れ図，第６図はこの第１の実施例の予約木構造のデー
タ構造を示すブロック図，第７図（１）〜（４）は導体
模様と予約木構造との例を示す図，第８図（ｚ）．　（
２）はこの第１の実施例の押し分け手段の手順を示す流
れ図である。

第１図（２），第２図，第３図〜第８図により，制御部
２の動作手順を説明する。

■　全体の動作手順 第３図は全体の手順を示す流れ図である。部品形状入力
手段２−０が第１図（１）の部品座標表７−３から部品
の位置と形状を入力し１画像記憶部１の禁止領域１１−
１，部品端子１１−３のビットに書き込む。

次に．書き込んだ全部の固定指定１１を起点として，経
路障害検出手段２−４を動作させる。

経路障害検出手段２−４はスルホール使用可能検出処理
２−４−１，経路障害検出処理２−４−４を行なう。ス
ルホール使用可能検出処理２−４−１は画像記憶部１で
，他の導体模様１０，固定指定１１との間にスルホール
径と必要導体間隔との余裕を取った画素９にスルホール
１１−２を設定できると判断し，その画素９のスルホー
ル使用可能フラグ１２を立てる。

また，経路障害検出処理２−４−４には固定指定１１の
間の配線容量を調べる機能を持たせる。

すなわち，後述する押し分け手段２−３を用いても配線
チャネルの確保が不可能な箇所を配線経路を探索する際
に必ず障害になるという意味で経路障害と名付け，画像
記憶部１の経路障害フラグ１３をたてる。

経路障害検出処理２−４−４の詳細な動作については，
後述する。

次に結線点入力手段２−１が結線すべき端子対の座標す
なわち第４図に示す新配線パターンの始点端子１６−１
，終点端子１６−２を第１図（１）の結線網表７−２か
ら人力し，更に経路探索手段２−２が仮経路１５を求め
画像記憶部１に書き，押し分け手段２−３が新配線の新
導体模様１０−２を確定する。

また，固定障害検出処理２−４−２は新導体模様１０−
２を起点として，押し分けの障害となる固定指定１１を
探索する。更に，その固定指定１１を起点として経路障
害検出手段２−４を動作させる。以下，この手順を繰り
返す。

次に，結線点入力手段２−１，経路探索手段２−２，押
し分け手段２−３，経路障害手段２−４について更に詳
細に説明する。

■　結線点入力手段２−１の動作手順 結線点人力手段２−１は結線すべき始点端子１６−１及
び終点端子１６−２を座標で人力する機能，あるいは部
品番号とその部品の端子番号から成る結線網表７−２を
人力して部品座標表７−３と合わせて端子の座標を計算
して求める機能とを持ち，用途により使い分ける。

■　線路探索手段２−２の動作手順 ■−１　迷路法２−２−１ 経路探索手段２−２は，画素単位で経路探索法の１つで
ある迷路法２−２−１を適用して配線経路を発見する。

第４図（１）に示すように配線経路の発見のために，画
像記憶部１において始点端子１６−１から近傍の画素に
対して，経路探索レベル１４の２ビットで数値０，１．
２を表わし，既導体模様１〇一１や経路障害フラグ１３
の立っている画素を避けながら，数値を周期的に展開し
ていく。スルホール使用可能フラグ１２が立っている画
素に至った場合，スルホールを介して他の面へも数値展
開する。また，この数値を書き込んだ領域が終点端子１
６−２に到達したかどうかの判定を行ない，到達してい
れば経路が存在するとして，バックトレース処理２−２
−２を行なう。経路探索レベル１４が終点端子１６−２
まで到達していなければ．更に数値を展開することが可
能かどうか判定する。

数値展開が不可能であれば，配線経路は存在しないため
経路探索手段２−２を中断する。

■−２　バックトレース処理２−２−２バックトレース
処理２−２−２では迷路法２−２−１で画像記憶部１に
書き込まれた数値をもとに，終点端子１６−２から始点
端子１６−１まで，第４図（２）に示すように数値の周
期を逆にして，２，１．０の順で経路探索レベル１４の
領域を逆もどりして仮経路１５を求める。更に仮経路１
５に対して固定指定１１との間隔あるいは既導体模様１
０−１との間隔を保つために，押し分け手段２−３を用
いて，既導体模様１０−１や仮経路１５自身を移動させ
ながら新導体模様１０−２を第４図（３〉のように確定
していく。この押し分け手段２−３については後述する
。

次に，第５図（１）．（２），（３）　，第６図，第７
図（１），　（２）　．　（３）を参照し，固定障害検
出処理２−４＝２と経路障害検出手段２−４のうちの経
路障害検出処理２−４−４を詳細に説明する。

■　固定障害検出処理２−４−２の手順■−１　押し分
け方向の設定処理 第５図（１）は固定障害検出処理２−４−２の手順を示
した流れ図である。押し分け手段２−３により設定した
第４図（３〉の様な新導体模様１０−２に対して，その
一画素αを起点とし，その前後の画素εとβの位置に応
じて，第５図（１）に示す表に基づき，αからの押し分
け方向１８（第６図）を求め，画素αの座標１７−５　
（第６図）とともに，第６図に示すデータ構造の要素よ
り成る第５図（２）に示す予約本構造１７の要素Ｙに登
録する。

■−２　押し分け予約処理２−４−３の手順押し分け予
約処理２−４−３は．第５図（２）および第５図（３）
の（ａ）　．　（ｂ）に示す手順で，予約木構造１７の
要素Ｙに対し，画素αの押し分け方向１８に存在する画
素に対応した要素を付加し，第７図（１）に示すように
予約本構造１７を枝分かれさせて生長させていく。この
過程で固定指定１１を障害点として検出する。また，画
素αの導体模様１０を押し分け方向１８に分岐する要素
の導体データ１７−６へ記憶することにより導体の押し
分けによる移動を予約する。なお第５図（３）において
，Ａ，Ｂは導体模様１０の有（１）と無（○）を示す。

また図を回転したり，鏡像を取った場合も有効である。

■　経路障害検出処理２−４−４の手順第５図（４）　
．　（５）は経路障害検出処理２−４−４の手順を示す
流れ図である。前記固定障害検出処理２−４−２で障害
点とした画像記憶部１における固定指定１１を起点とし
て押し分け予約処理２−４−３を動作させ，第７図（２
）に示すごとく予約木構造１７を形成する。この時，障
害点があるならば，起点とした固定指定１１と障害点と
の間に新導体模様１０−２を挿入することが不可能であ
る。障害点がない時は，更に第２押し分け予約処理２−
４−５を第７図（３〉のように行なう。この時障害点が
ないならば，新導体模様１０−２とその間隔との２画素
を挿入することが可能である。

そうでないならば，新導体模様１０−２を挿入して既導
体模様１０−１との間に十分な間隔を取ることができな
い。障害点がある場合，第５図（６〉に示す障害フラグ
設定処理２−４−６により，第７図（４）に示すごとく
，両固定指定１１をつないで経路障害フラグ１３を立て
る。

■　押し分け手段２−３の動作手順 次に，第４図（２），（３）と，第８図（１）　，　（
２）を参照し，押し分け手段２−３を詳細に説明する。

初に，始点端子１６−１から終点端子１６−２までの仮
経路１５上の各画素に対応する要素を連結した鎖構造２
０を作る。この鎖構造２０の各要素には画素座標と接続
方向を登録する。以後この鎖構造２０をたどりながら第
８図（２〉に示す押し分け方向調査処理２−３−１を行
ない押し分け方向１８を求める。それにより，既導体槙
様１０−１を１画素押し分けるか，２画素押し分けるか
をを選んで押し分ける。

押し分け方向調査処理２−３−１の手順を第８図（２）
の流れ図により説明する。

押し分け方向調査処理２−３−１は．鎖構造２０の各要
素ごとにその要素が指定する画素αを起点として押し分
け予約処理２−４−３を行ない，押し分け障害を調べる
。押し分け障害がある場合は，その反対方向に２回押し
分けるために．第１．第２の移動方向をそろえて鎖構造
２０の各要素に順に記憶していく。

押し分け手段２−３は，１回押し分けるためには，押し
分け予約処理２−４−３を行った後に予約木構造１７の
導体データ１７−６で画像記憶部１の導体模様１０を更
新する。２回押し分けるためには，更に第２押し分け処
理２−４−５を行った後に第２の予約本構造１７の導体
データ１７一６で導体模様１０を更新する。

このようにして，押し分け手段２−３が仮経路１５自身
と既導体模様１０−１を移動して相互に必要な間隔を確
保して新配線の新導体模様１０−２を確定する。そして
，その後に再び結線点入力手段２−１から前述の手順を
くりかえして連続的に自動配線していく。

実施例２ 本発明の第２の実施例について説明する。

第９図（１）〜（４）は本発明の第２の実施例の動作手
順を示す流れ図，第１０図はこの第２の実施例の予約木
構造のデータ構造を示すブロック図，第１１図（１）．
（２）はこの第２の実施例の導体模様の例を示す図であ
る。

この第２の実施例においては．第１の実施例における押
し分け予約処理２−４−３を第９図（ｌ），〈２〉に示
す手順で行なう。

■　押し分け予約処理２−４−３の手順第９図（１）に
おいては，画素９にスルホール１１−２が指定されてい
る場合の処理が第１の実施例と異なる。それは，スルホ
ール１１−２を移動するためである。また，第２図に示
した画像記憶部１の画素９の経路探索レベル１４の２ビ
ットを用い，片方を十用に，他方を一用に割当てる。そ
して，押し分け予約の際スルホール１１−２に衝突する
場合，そのスルホール１１−２領域の境界にスルホール
１１−２の増（＋）減（−）記号を書く。そして．スル
ホール１１−２がある要素Ｙに対応する予約本構造１７
の要素から各十一記号を書いた各画素に対応する要素を
分岐させる。スルホール１１−２を十記号の書かれた画
素に書き，一記号の書かれた画素で消去するとスルホー
ル１１−２が移動する。第１０図に示す予約本構造１７
の要素を用い，十一記号の画素のスルホールデータ１７
−７を“有り”／“無し″とすることによりスルホール
１１−２の押し分けを予約する。

スルホールデータ１７−７を“有り゜とした予約木構造
１７の要素からは．基板の表面・裏面ともに予約木構造
１７を分岐させていく。

この様に予約木構造１７の分岐数が多くなるので．その
データ構造は第１０図に示すように可変長にする。

第２押し分け予約処理２−４−５と押し分け手段２−３
も第９図（３）　．　（４）の様にスルホールデータ１
７−７の追加に対応する。

押し分け予約処理２−４−３をこのようにした結果．経
路障害検出処理２−４−４は，スルホール１１−２を押
し分けることを前程にしても配線を挿入できない障害を
検出する。

■　押し分け手段２−３の手順 また，押し分け手段２−３は，第９図（４〉のように押
し分け予約処理２−４−３により既導体模様１０−１と
スルホール１１−２とを押し分けた予約木構造１７の導
体データ１７−６とスルホールデータ１７−７で導体模
様１０とスルホール１１−２を書き直すことにより導体
模様１０とスルホール１１−２を移動させる。

第１１図（１）の様に仮経路１５に対して押し分け手段
２−３を用いて既導体模様１０−１やスルホール１１−
２や仮経路１５自身を移動させながら新導体模様１０−
２を第１１図（２）のように確定していく。

なお，本発明における画像記憶手段１は印刷配線板の全
面を含まないでもよい。その場合，必要に応じて部品座
標表７−３を読んで．必要な領域の導体模様を画像記憶
部１に書き込んで処理する。

実施例３ 第１４図は，第３の実施例の画像記憶部１の構成ビット
１−１を示す。画素９をｎｘｎ個で２次元的な広がりを
もつ画素群を構成する。この画素９は１６ビットで構成
され，以下のビットを有することを特徴とする。

（１）導体模様１０ （２）固定指定１１（Ｍ止領域１・１−１，スルホール
１１−２，部品端子１１−３を示す）（３）スルホール
使用可能フラグ１２ （４）移動するスルホールフ．ラグ２２（５）経路障害
フラグ１３ （６）経路探索レベル１４ （７）移動するスルホールに結線している導体フラグ２
３ （８）仮経路１５ この第３の実施例は前記第１の実施例で説明した経路探
索手段２−２によって得られた仮経路１５に接するスル
ホール１１−２を移動し，さらに移動したスルホール１
１−２に結線していた導体模様１０を結線し直すスルホ
ール移動手段２−５（第１５図参照）を有し，スルホー
ル１１−２が移動したのち，第１の実施例と同じ押し分
け手段２−３によって新配線を挿入する。

第１６図（１）〜第２０図（４〉よりスルホール移動手
段２−５の手順を説明する。

第１６図（１〉〜（３）は．スルホール移動手段２一５
の手順を示すフローチャート，第１７図はスルホール鎖
構造及びスルホール位置条件フラグを示す図，第１８図
は導体鎖構造を示す図，第１９図はスルホール移動方向
種類及び現在のスルホール位置と移動位置から移動方向
を求める図．第２０図は第３の実施例の動作説明図であ
る。

第１７図〜第２０図（１）〜（４）を参照しながら，第
１６図（１）〜（３）について説明する。

まず，移動するスルホールの鎖構造２４を作る。

第１７図で示すようにスルホールの鎖構造２４にはスル
ホール位ｉｆ！２７，スルホール位置条件フラグ２８．
画像記憶部１上をスルホール位置２７を中心に３×３行
列読んだ画素群２９をメンバーとする。スルホール位置
条件フラグ２８は移動するスルホールの中心に位置する
スルホール画素３０を０，内側に位置するスルホール画
素３１を１，外側に位置するスルホール画素３２を２，
コーナーに位置するスルホール画素３３を３としたフラ
グを持つ。スルホールの鎖構造２４を作りながら移動す
るスルホールフラグ２２を第１６図（１）の手順に従っ
て画像記憶部１に書きこむ。

次に，移動するスルホールに結線する導体の鎖構造２５
を作る。第１８図で示すように，導体の鎖構造２５には
，導体配置層コード３５と導体位置３６をメンバーとす
る。導体の８１構造２５を作りながら，移動するスルホ
ールに結線している導体フラグ２３を第１６図（１）の
手順に従って画像記憶部１に書きこむ 次に．スルホールの移動方向を調査する。第１９図で示
すように，スルホール移動方向の種類３７を→ｔ−＋の
４方向とし．現在のスルホール位置（Ｘｓ，ｙｓ）と，
移動したい位置（ｘ．，ｙ．）より求める移動方向と増
分３８により，スルホールの移動方向３９と，ｘ＋Ｙの
増分４ｏを求める。

次に，第１６図（２〉の手順に従ってスルホールの鎖構
造２４を読み，第１７図で示す如くメンバーであるスル
ホール位置条件フラグ２８が３及び２，すなわち，移動
するスルホールのコーナーに位置するスルホール画素３
３及び外側に位置するスルホール画素３２で，移動方向
３つに面するスルホール位置２７を読んだ時，第１の実
施例と同じ押し分け手段２−３によって導体の鎖構造２
５以外の導体模様を押し分ける。

そして，第１６図（２）で示すすべてのスルホールの鎖
構造２４のメンバーであるスルホール位置２７に増分４
０を加え，更に加えた位置の画像記憶部１にスルホール
１１−２を書きこむ。このように，１回スルホールの鎖
構造２４の最後まで処理されると，移動方向３つに１画
素分進む。これを　第１７図で示す鎖構造２４のメンバ
ーであるスルホール位置条件フラグ２８が０すなわち移
動するスルホールの中心に位置するスルホール画素３０
が，移動位置に達するまで，スルホール１１一２を移動
する。

次に，第２０図（１）〜（４）に示すように移動したス
ルホールに結線していた導体画素４２の移動を行なう。

まず第２０図（１）で示すように，移動したスルホール
に結線していた導体画素４２から４周近傍に，経路探索
レベル１４の２ビットで数値０，１．２を表わし．移動
したスルホールに結線していた導体画素４２の数値を周
期的に展開して，レベルが移動してきたスルホールの中
心画素４１に達したらレベル展開をやめる。

次に，第２０図（２）　，　（３）で示すように，移動
してきたスルホールの中心画素４１からレベルの周期を
逆にして２，１．０の順で経路探索レベル１４を逆戻り
しながら移動したスルホールに結線していた導体画素４
２との交点位置４３まで，移動してきたスルホールに結
線する新たな導体画素４４を第６図（３）の手順に従っ
て，画像記憶部１に書きこむ。さらに第２０図（４）で
示すように，導体の鎖構造２５（第１８図参照）の始点
位置３４から交点位置４３まで移動したスルホールに結
線していた導体画素４２を第１６図（３）の手順に従っ
て，画像記憶部１より消す。

次に，移動するスルホールフラグ２２と，移動するスル
ホールに結線している導体フラグ２３を第６図（３）の
手順に従って画像記憶部１より消す。

これらを第１６図（３）の手順に従って表裏面に対して
行なう。

このように，スルホール移動手段２−５を行なった後に
．第１５図で示すように第１の実施例と同じ押し分け手
段２−３によって新配線（第２０図（４）を参照）を挿
入する。

この′７３３の実施例は画像記憶部に移動するスルホー
ルの識別ビットと，移動するスルホールに結線している
導体の識別ビットをもち，導体の固定指定であるスルホ
ール画素を移動させ，さらに移動位置と，移動したスル
ホールに結線していた導体模様の間に，新たな導体模様
を書きこむことにより，結線の障害となるスルホールを
移動することができる。

実施例４ 本実施例は，第１の実施例と同じビット構成１−１（第
２図参照）を有し，同じ動作ブロック図（第１図（１）
　，　（２））に従って動作する。本実施例は，第１の
実施例と同じ経路探索手段２−２を用いるが，経路探索
の領域を限定していることが特徴である。本実施例を第
２１図〜第２４図を参照してその手順を示す。

第２１図は本実施例の手順を示すフローチャートである
。第１の実施例と同じ結線点入力手段２＝１の後，画像
記憶部ｌのある面積中の画素記憶容量に対する，導体模
様１０と固定指定１１の合計が占める割合を示す係数値
を算出する導体占有率算出処理４６を行ない，第１の実
施例と同じ結線突入手段２−１で得られた結線すべき始
点端子及び終点端子間を，疑似結線ネットワーク処理４
７によって算出された導体占有率算出処理４６による係
数値を評価し，係数値が低いすなわち，画像記憶部１の
ある面積中の画素記憶容量に対する導体模様１０と固定
指定１１の合計が占める割合が低く，故に．画素記憶密
度が低い経路探索領域を与える疑似結線網表４７−１を
形成する。疑似結線網表４７−１より得られた経路探索
領域をもとに画像記憶部１の領域に対して第１の実施例
と同じ経路探索手段２−２を用いて経路を発見する。

経路が見つからなければ，さらに疑似結線網表４７−１
より画素記憶密度が次に低い経路探索領域を得て，画像
記憶部１の領域に対して，実施例１と同じ経路探索手段
２−２を用いることをくり返して経路を発見する。

第２２図〜第２４図をもとに，第２１図で示す導体占有
率算出処理４６と疑似結線ネットワーク処理４７につい
て説明する。

■　導体占有率算出処理４６の手順 第２２図は画像記憶部１のｎＸｎ画素で囲まれる領域中
の，画素記憶容量に対する導体模様１０と固定指定１１
の合計が占める割合を導体占有率係数値５１とし，導体
占有率係数値５１を，導体占有率係数配列４９の１つの
要素５２とし．導体占有率係数配列４つと同じ配列構成
を．疑似配線空間配列５０を持ち，さらに導体占有率係
数配列４つと疑似配線空間配列５０は，表面５３，裏面
５４単位にあることを示している。

第２３図は画素記憶部１のｎＸｎ画素で囲まれる領域の
表面導体模様５７，裏面導体模様５８，固定指定１１さ
らに空き画素５つ（データピットがたっていない画素）
を示している。

第２２図で示す導体占有率係数値５１は第２３図で示す
画像記憶部１のｎＸｎ画素で囲まれる領域の画素記憶容
量を１００とした時，表面導体模様５７と固定指定１１
，裏面導体模様５８と固定指定１１の合計が占める比率
である。これを画像記憶部１の全領域にわたって表面５
３，裏面５４行ない，結果を導体占有率係数配列４９に
入れる。

■　疑似結果ネットワーク処理４７の手順第１の実施例
と同じ，第１図（１）の手順より結線入力手段２−１で
得られた結線網表７−２に従って，結線すべき始点端子
と終点端子の座標から，第２２図で示すように導体占有
率係数配列４９における始点端子が存在する始点要素５
５と終点端子が存在する終点要素５６を知る。さらに，
導体占有率係数配列４つと同じ配列構成をもつ疑似配線
空間配列５０において，始点端子が存在する始点要素５
５と終点端子が存在する終点要素５６間の疑似結線網４
８を形成する。第２２図及び第２４図で示すように疑似
結線網４８から，始点要素５５と終点要素５６の間を疑
似結線網４８にそって，導体占有率係数配列４９の導体
占有率係数値５１の総計をとり，その値の低いすなわち
画素記憶密度の低い疑似結線網４８を，疑似配線空間配
列５０上で求められた１つの経路探索領域６０として順
に画素記憶密度の高い疑似結線網４８を記憶する第２１
で示す疑似結線網表４７−１を形成する。この経路探索
領域６０をもとに，画像記憶部１に対し，第１の実施例
と同じ経路探索手段２−２を用いて経路を発見する。

経路が発見できなければ，疑似結線網表４７−１より次
に画素密度の低い疑似結線網４８を得，同じように経路
探索領域６０を求め，第１の実施例と同じ経路探索手段
２−２より経路を発見する。

このように新たに配線経路を求める時，画素密度の低い
領域内を第１の実施例と同じ経路探索手段２−２を用い
て経路を発見し，第３の実施例と同じスルホール移動手
段２−５，第１の実施例と同じ押し分け手段２−３を用
いて新配線を挿入する。

この第４の実施例は画像記憶部の記憶容量に対して，画
像記憶部に記憶された導体模様と固定指定の合計が占め
る割合を係数化し，その係数値の示す値により，画素密
度の低い経路探索領域から経路探索することができる。

実施例５ 本発明の第５の実施例について，第２５図〜第２８図を
参照して説明する。

第２５図は本発明の第５の実施例のブロック図，第２６
図（１）〜（４〉はこの第５の実施例の画像記録部の各
画素のデータ構造を示す図，第２７図（１）〜（６）は
この第５の実施例の手順を示す流れ図，第２８図（１）
〜（ｌ１）はこの第５の実施例の画像記録部の各要素の
印刷配線板上の位置を示す図である。

第２５図において印刷配線板の画像記憶部１に第２６図
（１）（ａ）に示す導体素片６２−１を記憶する。これ
は第２６図（１）　（ｂ）にデータ構造を示す禁止領域
６２−１−２．スルホール６２−１−３，部品端子６２
−１−４と，第２６図（２）　（ｂ）にデータ構造を示
す配線導体６２−１−１，同（ａ）に示すデータ構造の
境界辺６２−２と，第２６図（３）にデータ構造を示す
節６２−３と，第２６図（４）にデータ構造を示す間隔
領域６２−４を記憶する。

これらは，各データの種類欄に分類番号を書いて区別す
る。

導体素片６２−１の履歴欄の構造を以下に示す。

履歴欄は以下のフラグを有することを特徴とする。

（１）始点フラグ （２〉終点フラグ （３）消去指定 （４）新素片指定 （５）移動可否指定 境界辺６２−２の履歴欄の構造を以下に示す。

（１）層間メイズ方向フラグ （２）層面内メイズ方向フラグ （３）スルホール障害フラグ （４〉配線障害フラグ 制御部２の動作手順は第１の実施例の第１図（１）及び
（２）に示した通りであり，部品形状入力手段２−０が
部品座標表７−３から部品の位置と形状を入力し．それ
により，部品端子６２−１−４及び禁止領域６２−１−
２を第２８図（１）に示すように画像記憶部１へ記憶す
る。その後，経路障害検出手段２−４を動作させる。

そして，結線点人力手段２−１が結線すべき端子対を結
線網表７−２から読み出し，その都度経路探索手段２−
２が経路６３を探索し，その結果をバックトレース配列
６４へ書き込む。更に押し分け手段２−３が画像記憶部
１に配線導体２−１−１とスルホール６２−１−３を書
き込む。そして再び経路障害検出手段２−４を動作させ
た後に結線点入力手段２−１が次に結線すべき端子対を
読み出し，これらの手順を繰り返す。

以下に，第２７図（１）〜（６〉により制御部２の詳細
な動作手順を説明する。

■　部品形状入力手段２−０の動作手順始めに第２７図
（１）により部品形状入力手段２−０の動作手順を説明
する。

部品形状入力手段２−０は部品座標表７−３を読み，第
２８図（１）に示すように，部品端子６２一１−４及び
禁止領域６２−１−２を画像記憶部１へ記憶する。次に
，第２８図（２〉に示すように，それらを複数の層面に
共通な線分６５で接続する。

線分６５は以下の条件で作る。いずれかの層面に部品端
子６２−１−４及び禁止領域６２−１−２がある時それ
を線分の端部とする。その端部を中心とする正八角形の
同じ辺に２つ以上の線分があり得る時，一番短い線分を
残し他の線分を除く。

その結果，線分６５を得る。

層面ごとに，線分６５の端点及び交点を複数の層面に共
通なｉｉ６２−３とし，第２６図（３）に示すデータ構
造で記憶する。層面ごとに線分６５を節６２−３により
分割して境界辺６２−２とし．第２６図（２〉に示すデ
ータ構造で記憶する。層面ごとに，これらの境界辺６２
−２−１と導体素片６２−１とで囲まれる領域を間隔領
域６２−４として記憶する。以上で部品形状入力手段２
−０の説明を終了する。

層面ごとに，その層面に存在する部品端子６２−１−４
あるいは禁止領域６２−１−２を端部とする線分６５を
連結し，両端ともにその層面の部品端子６２−１−４あ
るいは禁止領域６２−１−２である線分を作り，線分６
５−１と呼ぶ。線分６５−１に対し．経路障害検出手段
２−４を動作させる。この詳細は後述する。

すべての線分６５−１に対して経路障害検出手段２−４
を動作させ，スルホール障害フラグあるいは配線障害フ
ラグを立てる。

■　経路探索手段２−２の動作手順 次に，第２７図（２）を参照して経路探索手段２−２の
動作手順を説明する。経路探索手段２−２は結線点入力
手段２−１が読み出した端子対の指定する始点端子１６
−１と終点端子１６−２に始点フラグ及び終点フラグを
立てる。

次に，第２８図（３〉に示すように，始点端子１６−１
に接する間隔領域６２−４を読む。これを経路として前
線配列へ記憶する。その間隔領域６２−４に接する導体
素片６２−１が終点端１６一２でなければ間隔領域６２
−４に接する境界辺６２−２を読み出す。

境界辺２２−２に配線障害フラグあるいはノイズ方向フ
ラグが設定されていなければ．その境界辺６２−２を経
路６３とし，それに層面内メイズ方向フラグを設定し，
前線配列６７へ記憶する。

境界辺６２−２にスルホール障害フラグが設定されてい
なければ第２８図（４〉に示すように他層面を接続する
経路を求める。境界辺６２−２を第１層面境界辺６２−
２−１と呼ぶ（ａ）。始めに，第１層面境界辺６２−２
−１を端とする線分を求める。

すなわち，第１層面境界辺６８−２−１の存在する層面
において，部品端子６２−１−４．禁止領域６２−１−
２，あるいはスルホール６２−１−３を端部とする境界
辺６２−２と第１層面境界辺６２−２−１を，中介する
境界辺６２−２で接続した線分を求め，第１層面線分６
５−２と呼ぶ（ａ）　Ｏ 第１層面線分６５−２の配線束太さ６６を以下の様にし
て求める。第１層面線分６５−２と交わる導体素片６２
−１を求める。この導体素片６２−１の幅と必要間隔を
加えた長さを第１層面線分６５−２の配線東太さ６６と
する。配線束太さ６６は，第１層面線分６５−２が間に
配線導体６２一１−１を挾んで短縮できる最小距離であ
る。

次に，以下の様にして他の層面で，第１層面線分６５−
２と重なる線分を求め，第２層面線分６５−３と呼ぶ（
ｂ）。第１層面線分６５−２の端部がスルホール６２−
１−３であれば，他の層面おいて，それから，第１層面
境界辺６２−２−１の方向へ境界辺６２−２で接続し，
第１層面線分６５−２と同じ配線束太さの線分を第２層
面線分６５−３とする（ｂ）。第２層面線分６５−３の
，第１層面境界辺６２−２−１の側の端部に接続する境
界辺を第２層面境界辺６２−２−２と呼ぶ。更に，第１
層面境界辺６２−２−１に対し，他の第１層面線分６５
−２及び第２層面線分６５−３，及び第２層面境界辺６
２−２−２を求める。新旧の第２層面境界辺６２−２−
２を境界辺６２−２で結び，それらを境界辺６２−・２
−４と呼ぶ。境界辺６２−２−４の他層面境界辺欄に第
１層面境界辺６２−２−１の番号を記憶する。境界辺６
２−２−４にスルホール間メイズ方向フラグを設定する
。境界辺６２−２−４を経路６３とし，前線配列６７へ
記憶する。

第１層面線分６５−２の端部がスルホール６２−１−３
でない場合は，第１層面線分６５−２の端部の節６２−
３が第２層面にも共通であるのを利用して，第２層面線
分６５〒３は第２層面で節６２−３を介して接続する部
品端子６２−１−４，禁止領域６２−１−２あるいはス
ルホール６２一１−３を端部とする。第２層面線分６５
−３は端部からそのｉ６２−３までの配線東太さ６６と
第１層面線６５−２の配線束太さとを加えた値の配線東
太さ６６となる他端の第２層面境界辺６２−２−２を定
め，同様に処理する。

次に．前線配列６７の要素を順に読み出して，第２８図
（５）に示すようにそれらに接する間隔領域６２−４に
関して同様の処理を行なう。前線配列６７の全要素を処
理し終って．終点端子１６−２に達さなかったときは配
線不可能と記憶する。

また，間隔領域６２−４に接する導体素片が終点端子１
６−２であれば，バックトレース処理２−２−２を行な
う。

■−１　バックトレース処理２−２−２の手順バックト
レース処理２−２−２を第２７図（３）を参照して詳細
に説明する。バックトレース処理２−２−２は終点端子
１６−２に接する間隔領域６２−４を読み出す。間隔領
域６２−４に接する導体素片６２−１に始点フラグが設
定されていなければ．間隔領域６２−４に接する境界辺
６２−２を読み出す。そのメイズ方向フラグがその間隔
領域６２−４へ向いている境界辺６２−２を選び，更に
，それと接続する間隔領域６２−４を経路６８−１とし
てバックトレース配列６８へ記憶する。

次に，その間隔領域６２−４に対して以上の処理を繰り
返す。

間隔領域６２−４に接する導体素片６２−１に始点フラ
グが設定されていたならば，バックトレース処理２−２
−２を終了する。このようにしてバックトレース配列６
８を作る。配列６８の経路６８−１を第２８図（６〉に
示す。

■　押し分け手段２−３の動作手順 次に，第２７図（４）により押し分け手段２−３の動作
手順を説明する。

押し分け千段２−３は，バックトレース配列６８に記憶
した経路６８−１を順次読み出す。その経路６８−１が
同一層面をつなぐ経路であるならば，経路６８−１の境
界辺６２−２の間に配線導体６２−１−１を挿入し，そ
こを新しい節６２一３とし２つの新しい境界辺６２−２
へ分割する。

次に，従来の間隔領域６２−４を新しい境界辺６２−２
に合わせて２つの間隔領域６２−４へ分割する。この間
隔領域６２−４へ接する従来の境界辺６２−２．及び導
体素片６８−１について，それらが記憶している間隔領
域６２−４の番号を新しい番号へ更新する。また，新し
い配線導体６２−１−１に，新しい間隔領域６２−４の
番号と節２−２−３６の番号とを記憶する。

また，経路６８−１が他層面をつなぐ経路であるならば
，第２８図（７〉に示すように，経路６８−１の第１層
面境界辺６２−２−１と第２層面の境界辺６２−２−４
をそれぞれ新しい境界辺６２一２へ２分割して，それら
の分割点を両層面に共通の新しい節６２−３とする。そ
の節２−２−３上に新しいスルホール６２−１−３を置
く。

次に，従来の境界辺６２−５．６２−６を含む線分６５
−１を求め，更に，その端と接続する線分６５−１を求
め，そのもう一端と新しいスルホール６２−１−３とを
結び，両層面に共通な新しい線分６５とする。そして新
しい線分６５は，層面ごとに，それを横切る従来の配線
導体６２−１−１により分割して新しい境界辺６２−２
を作る。

分割点を新しい節６２−３とする。新しい節６２−３に
より，従来の配線導体６２−１−１を新しい配線導体６
２−１−１へ２分割する。

このようにして生まれた新しい間隔領域６２−４に接す
る従来の境界辺６２−２及び導体素片６２−１について
，それらが記憶している要素番号を新しい番号へ更新す
る。

次に，新しい境界辺６２−２を含み，その層面に存在す
る，部品端子６２−１−４．禁止領域６２−１−４ある
いはスルホール６２−１−３を両端とする線分６５−１
を求める。新しい境界辺６２−２ごとに線分６５−１を
求めて挿入する導体を０として障害線検出処理２−４−
６を行なう。

この処理によりスルホール６７−１−３を適切な位置へ
移動する。障害線検出処理２−４−６については後述す
る。

次に，線分６５−１の端部から節６２−３までの配線束
太さ６６を求め，その線分６５−１上に存在するすべて
の配線導体６２−１−１の節６２−３に対して，それら
が互いに配線導体の幅，あるいはスルホール６２−１−
３の半径と必要間隔を加えた長さ以上に離れるように節
６２−３の位置を定める。この節６２−３の間を結ぶ配
線導体６２−１−１は第２８図（８）に示すように５ス
ルホール６２−１−３や部品端子６２−１−４から必要
な間隔を取って位置を確定する。

■　経路障害検出手段２−４の動作手順次に経路障害検
出手段２−４を説明する。経路障害検出手段２−４は．
スルホール障害及び配線障害を検出し，画像表示部３へ
表示する。更に，部品の移動指令を入力することにより
，配線導体６２−１−１とスルホール６２−１−３と他
の部品を移動させながら部品の位置をずらす処理である
。

■−１　スルホール障害の検出の手順 以下に経路障害検出手段２−４でスルホール障害を検出
する手順を詳細に説明する。線分６５−１と挿入を考え
るスルホール６２−１−３の直径を指定して障害線検出
処理２−４−６を働かせる。

障害線検出処理２−４−６は，スルホール６２−１−３
を移動可能とした上で，周囲の部品端子６２−１−４あ
るいは禁止領域６２−１−２がスルホール６２−１−３
の移動を制限する結果障害を解消できない障害を求める
。

■−１−１　障害線検出処理２−４−６の動作手順 障害線検出処理２−４−６の動作手順を第２７図（５）
を参照し詳細に説明する。

障害線検出処理２−４−６は線分６５−１の端部にスル
ホール６２−１−３がある場合に，その端部を移動し，
１１分６５−１の長さを配線束太さ６６と挿入を考える
導体の幅と必要間隔を加えた長さに伸ばす。この際に部
品端子６２−１−４，禁止領域６２−１−２につながる
端部は動かさない。スルホール６２−１−３につながる
端部はスルホール６２−１−３とともに動かす。そのス
ルホール６２−１−３を起点としてスルホール押し分け
処理２−７を行ない，障害の有無を調べる。

■−１−１−１　　スルホール押し分け処理２−７の手
順 スルホール押し分け処理２−７の手順を第２７図（６）
を参照して詳細に説明する。スルホール押し分け処理２
−７は２つの条件のもとにスルホール６２−１−３に接
近するスルホール６２−１−３を押し分ける。第１の条
件は新スルホール６２−１−３と接近するスルホール６
２−１−３との距離が，その間の配線束太さ６６より短
かくなった場合に接近するスルホールを押し分けること
である。第２の条件は新スルホール６２−１−３を中心
とする半径が５　ｍｍ程度の正八角形の中心からその上
下左右の辺までの扇形の範囲にある被押し分けスルホー
ル６２−１−３を押し分けることである。

この条件は，スルホールの配線妨害を最小限にするため
の施策である。スルホール６２−１−３を斜めに並べて
，配線導体６２−１−１を縦横方向に走行させてスルホ
ール６２−１−３間を斜めに通過させればスルホール６
２−１−３の配線妨害が少なくなるからである。

この２つの条件のもとにスルホール６２−１−３を押し
分けていく。押し分けられたスルホール６２−１−３の
逆押し分け欄に，それを押し分けたスルホール６２−１
−３の番号を記憶する。

スルホール６２−１−３が押し分けられて，部品端子６
２−１−４や禁止領域６２−１−２との間の距離が，そ
れらとの間の配線東太さ６６より短かくなった場合は，
障害が有るとし，スルホール押し分け処理２−７を停止
する。

■−１−１′　障害線の検出処理２−４−６の手順の説
明の続き 次に，第２７図（５〉に戻り，障害線検出処理２−４−
６の手順の説明を続ける。スルホール押し分け処理２−
７により障害がある場合は，障害からスルホール６２−
１−３の逆押し分け欄の指定するスルホール６２−１−
３を押し戻していき．起点としたスルホール６２−１−
３を押し戻す。

その押し戻された位置から．押し戻された方向に垂直な
線を境界とするスルホール移動禁止領域を作る。スルホ
ール６２−１−３をスルホール移動禁止領域以外の位置
へ再移動し．線分６５−１を配線東太さ６６に挿入を考
える。

導体の直径と必要間隔を加えた長さに伸ばす。

そして，そのスルホール６２−１−３の移動した位置を
起点として再度スルホール押し分け処理２−７と逆押し
分けとを繰り返す。

線分６５−１の長さを必要な長さへ伸ばせなかった場合
は，障害有りと記憶する。

■′　経路障害検出手順２−４の動作手順の説明の続き 次に，経路障害検出手段２−４の動作手順の説明を続け
る。経路障害検出手段２−４は，障害線検出処理２−４
−６を行った後に，障害の有無のみを記憶し，この処理
において移動したスルホール６２−１−３はもとの位置
に復帰させる。障害があった場合は，その線分６５−１
の境界辺６２−２−１にスルホール陣害フラグを立てる
。このスルホール障害６つ−１を第２８図（９〉に示す
ように画像表示部３へ表示する。

■−２　配線障害検出処理の手順 次に，配線障害を検出する手順を説明する。線分６５−
１と挿入を考える配線導体６２−１−１の回路幅を指定
して，障害線検出処理２−４−６を働かせる。この際に
，障害の有無のみを記憶し，この処理で移動したスルホ
ール６２−１−３はもとの位置に復帰させる。障害があ
った場合は，その線分６５−１の境界辺６２−２−１に
配線障害フラグを立てる。この配線障害６つ−２を第２
８図（ｌＯ）に示すように画像表示部３へ表示する。

■−３　部品位置移動処理の手順 次に，経路障害検出手段２−４で，部品の位置を移動す
る処理の手順を説明する。操作卓４から操作者が部品移
動を指令すると，第２８図（１１）に示すように，移動
する指令を与えられた第１の部品７０−１の全部の部品
端子６２−１−４を移動する。そして，これらの部品端
子６２−１−４を起点とし，スルホール押し分け処理２
−７を行なう。別の部品端子６２−１−４を障害として
スルホール押し分け処理２−７が停止したならば，その
部品端子６２−１−４を含む第２の部品３〇一２をすべ
て移動する。

すなわち，第２の部品７０−２の部品端子６２−１−４
をすべて平行移動し，その部品端子６２−１−４を起点
に加え，スルホール押し分け処理２−７を続行する。ス
ルホール押し分け処理２−７が禁止領域６２−１−２で
停止したならば，障害となった禁止領域６２−１−２を
表示して処理を終了する。

以上で経路障害検出手段２−４を説明終了する。

経路障害検出手段２−４の動作を再び結線点入力手段２
−１から繰り返す。

実施例６ 本発明の第６の実施例について，第２９図〜第３２図を
参照して説明する。

第２９図は本発明の第６の実施例のブロック図である。

印刷配線板の画像記憶部１に導体素片７２−１を記憶す
る。これは第３０図（１）にデータ構造を示す（ａ）。

スルホール７２−１−３と部品端子７２−１−４を含む
（ｂ）。

また，第３０図（２）にデータ構造を示す境界辺７２−
２と（ａ），！３０図（３）にデータ構造を示す節７２
−３と，第３０図（４）にデータ構造を示す間隔領域７
２−４と，さらに，第３０図（５）にデータ構造を示す
スルホール予約点７２−５を記憶する。これらは，各要
素の種類欄に分類番号を書いて区別する。各要素は，第
３０図（６〉に示すように，互にポインタで結合する。

間隔領域７２−４はポインタで境界辺７２−２とスルホ
ール予約点７２−５を指し，境界辺７２−２は逆に間隔
領域７２−４を指し，他に節７２−３を指す。節７２−
３は逆に境界辺７２−２を指し，他に導体素片７２−１
を指す。導体素片７２−１は逆に節を指す。

間隔領域７２−４は禁止領域７２−１−２を含み，境界
辺７２−２は配線導体７２−１−１を含む。導体素片７
２−１と境界７２−２のうち配線導体７２−１−１はネ
ット番号を有し，導体素片７２−１のうち部品端子７２
−１−４は部品番号を有す。節７２−３及びスルホール
予約点７２−５は位置座標を有する。境界辺７２−２，
間隔領域７２−４．スルホール予約点７２−５は経路探
索レベル１４を有する。

制御部２の動作手順の概要は実施例１の第１図（２〉と
同じであり，第３１図（１）により手順を説明する。部
品形状入力手段２−０が部品座標表７−３から部品の位
置と形状を入力し．それによりｉ１３２図（１）に示す
印刷配線板２１の部品端子７２−１−４及び禁止領域７
２−１−２を画像記憶部１へ記憶する。その後．経路障
害検出手段２−４を動作させる。

そして，結線点入力手段２−１が結線すべき端子対を結
線網表７−２から読み出し．その都度経路探索手段２−
２が経路を探索し，その結果をバックトレース配列７４
へ書き込む。さらに押し分け手段２−３が画像記憶部１
に配線導体２−１−１とスルホール７２−１−３を書き
込む。そして再び経路障害検出手段２−４を動作させた
後に結線点入力手段２−１が次に結線すべき端子対を読
み出し，これらの手順を繰り返す。

以下に，第３０図，第３１図（１）〜（９），第３２図
により制御部２の詳細な動作手順について説明する。

■　部品形状入力手段の動作手順 初めに第３０図（７）と第３１図（２）．（３）により
部品形状入力手段２−０の動作手順を述べる。部品形状
入力手段２−０は部品座標表７−３を読み，第３０図（
１）に示すように，部品端子？２−１−４及び禁止領域
７２−１−２を画像記憶部１へ記憶する。次に，第３１
図（３）に示す線分作戊処理２−０−１により．禁止領
域７２−１−２の境界辺７２−２に定距離ごとに節７２
−３を置き，部品端子７２−１−４のｊｍ７２−３と合
わせ．それらが縦横方向（４５度以内のずれを許す）で
最近接するものを線分７５で結び第３０図（７〉に示す
構造体で記憶する。線分７５を配線導体７２−１−１で
分割して，境界辺７２−２として第３０図（２）に示す
構造体で記憶する。層面ごとに，これらの境界辺７２−
２と配線導体７２−１−１とで囲まれる領域を間隔領域
７２−４として第３０図（４）に示す構造体で記憶する
。

■　経路障害検出手段２−４の動作手順次に、第３１図
（４〉〜（Ｂ〉，第３２図（２）〜（５）を参照して経
路障害検出手段２−４を説明する。

経路障害検出手段２−４は．スルホール使用可能検出処
理２−４−１と経路障害検出処理２−４−４と部品移動
処理２−４−７を行なう。

■−１　スルホール使用可能検出処理２−４−１の手順 スルホール使用可能検出処理２−４−１は後述する押し
分け手段２−．３を用いて間隔領域７２一４に設置する
ことが可能なスルホール７２−１−３をスルホール予約
点７２−５として求め，間隔領域７２−４へポインタで
結合する。以下に第３１図（４）〜（６），第３２図（
２）　．　（３）によりスルホール使用可能検出処理２
−４−１を説明する。

スルホール使用可能検出処理２−４−１は第３２図（３
）に示すような間隔領域７２−４の範囲内及びその近傍
の定ピッチの格子点上のスルホール予約点７２−５に対
して以下の処理を行う。第３２図（２）に示すように間
隔領域７２−４と境界辺７２−２に対して，それを含み
両端を部品端子７２−１−４，禁止領域７２−１−２又
はスルホール７２−１−３とする線分７５を読み出す。

第３２図（３〉のように線分７５の端の節７２−３とス
ルホール予約点７２−５を結んでスルホール補助線７５
−２として第３０図（７）の構造体で記憶する。その長
さをｇとする。次に，第３２図（２）で線分７５上にお
いて間隔領域７２−４の境界辺７２−２から節７２−３
までの間で線分７５に交わるスルホール２２−１−３等
の導体素片７２−１及び配線導体７２−１−１を求める
。これらの幅とそれらの間に必要な間隔を加えた長さを
配線東太さ７６と呼ぶ。配線束太さ７６は，間隔領域７
２−４と節７２−３が配線導体７２−１−１，導体素片
７２−１の間の間隔を満足しながら接近できる最小距離
である。スルホール補助線７５−２の長さｇが配線束太
さ７６以上であるならば，スルホール予約点７２−５と
間隔領域７２−４を互にポインタで結合する。

長さｐが足りない場合，既スルホール７２−１−３を押
しのけて新スルホール７２−１−３を挿入する。これが
可能か調べるためにスルホール補助線７５−２に対し，
新スルホール７２−１−３の直径を指定して障害線検出
処理２−４−６を行なう。

■−１−１　障害線検出処理２−４−６の手段障害線検
出処理２−４−６は，スルホール７２−１−３を移動可
能とし，周囲の部品端子７２−１−４あるいは禁止領域
７２−１−２を移動禁止した上で，線分７５への新配線
導体７２−１−１と導体素片７２−１の挿入可否を調べ
る処理である。

この障害線検出処理２−４−６の手順を第３１図（５）
を参照し詳細に説明する。

障害線検出処理２−４−６は，線分７５の端部にスルホ
ール７２−１−３がある場合に，そのスルホール７２−
１−３を移動し，線分７１の長さを配線太さ７６と挿入
を考える導体の幅と必要間隔を加えた長さに伸ばす。こ
の際に部品端子７２−１−４と禁止領域７２−１−２は
移動させない。

スルホール７２−１−３につながる節７２−３はスルホ
ール７２−１−３と共に移動させる。そのスルホール７
２−１−３を起点としてスルホール押し分け処理２−７
を行ない．障害の有無を調べる。

■−１−１−１　　スルホール押し分け処理２−７の手
順 スルホール押し分け処理２−７の手順を第３１図（６）
を参照して詳細に説明する。スルホール押し分け処理２
−７は起点スルホール７２−１−３の周囲のスルホール
７２−１−３を検出する。起点スルホール７２−１−３
と周囲のスルホール７２−１−３の節７２−３が線分７
５で直結していない場合，スルホール補助線７５−２を
作り，各各の節７２−３とポインタで結合する。

そして，以下の２つの条件のもとに，そのスルホール７
２−１−３を押し分ける。第１の条件は．接近するスル
ホール間の距離が５その間の配線束太さ７６より短かく
なった場合に，スルホール７２−１−３を配線東太さ７
６の位置まで移動することである。第２の条件は．新ス
ルホール７２一１−３から半径５■曹以内で縦横方向か
ら２２．５度以内にあるスルホール７２−１−３をその
条件以外の位置へ移動することである。

第２の条件は，スルホールの配線妨害を最小限にするた
めの施策である。配線導体７２−１−１を縦横方向に走
行させてスルホール７２−１−３を斜めに並べればスル
ホール７２−１−３の配線妨害が少なくなるからである
。

この２つの条件のもとにスルホール７２−１−３を押し
分けていく。押し分けられたスルホール７２−１−３の
節７２−３の逆押し分け欄に，それを押し分けた起点ス
ルホール７２−１−３の番号を記憶し，押し分けられれ
たスルホール７２−１−３を次の起点スルホール７２−
１−３として次々と押し分けていく。

起点スルホール７２−１−３と部品端子７２−１−４や
禁止領域？２−１−２との間の距離が，それらとの間の
配線東太さ７６より短かくなった場合，あるいは，起点
スルホール７２−１−３の押し分けるスルホール７２−
１−３に移動禁止領域があり移動できないとき，障害が
有るとし，スルホール押し分け処理２−７を停止する。

■−１−１′　障害線検出処理２−４−６の手順の続き 次に，第３１図（５〉に戻り，障害線検出処理２−４−
６の手順の説明を続ける。スルホール押し分け処理２−
７により障害がある場合は，障害の節７２−３の逆押し
分け欄に記憶した起点スルホール７２−１−３を押し戻
す。そして，障害の節７２−３と起点スルホール７２−
１−３とを結ぶ線分７５（あるいはスルホール補助線７
５−２）の移動禁止領域ベクトル欄に障害の座標を記憶
し．さらに，起点スルホール７２−１−３の押し戻され
た位置と障害の位置座を結ぶ方向ベクトルを記憶する。

起点スルホール７２−１−３には．このベクトルに垂直
な線を境界として移動禁止領域を定義する。起点スルホ
ール７２−１−３から押し分け順を逆にたどって，さら
にその起点となるスルホール７２−１−３を起点とし，
再度スルホール押し分け処理２−７を繰り返す。

移動禁止領域に囲まれて．線分７５を必要な長さへ伸ば
せなかった場合は，障害有りと記憶する。

以上が障害線検出処理２−４−６である。

■−１′　スルホール使用可能検出処理２−４−１の手
順の続き 次に，スルホール使用可能検出処理２−４−１の手順の
説明を続ける。

これは，障害線検出処理２−４−６を行った後に，障害
の有無のみを記憶し，この処理において移動したスルホ
ール７２−１−３はもとの位置に復帰させる。

障害がある場合は，間隔領域７２−４にスルホ−ル陣害
フラグ７７を立てる。スルホール障害フラグ７７をスル
ホール陣害７９−１として，第３２図（４）に示すよう
に画像表示部３へ表示する。

障害がない場合は起点としたスルホール予約点７２−５
を間隔領域７２−４へポインタで結合する。

障害線検出処理２−４−６でスルホール予約点７２−５
が移動する場合は，そのスルホール予約点７２−５を定
ピッチの格子上の他のスルホール予約点７２−５の位置
へ移動して障害が無ければそのスルホール予約点７２−
５と間隔領域７２−４を互にポインタで結合する。もし
，定ピッチの格子上の他のスルホール予約点７２−５の
位置では障害があり，それ以外の位置で障害がなければ
，その位置に新しいスルホール予約点７２−５を定義し
て，間隔領域７２−４とポンイタで結合する。

そして，新しいスルホール予約点７２−５に対してスル
ホール使用可能検出処理２−４−１を行ないそれと結合
する間隔領域７２−４とポインタで結合する。

■−２　経路障害検出処理２−４−４の手順次に．経路
障害検出処理２−４−４を説明する。

これは，線分７５に対し，挿入する新配線導体７２−１
−１の回路幅を指定して障害線検出処理２−４−６を行
なう。この際に，障害の有無のみを記憶し，この処理で
移動したスルホール７２−１−３はもとの位置に復帰さ
せる。障害がある場合は，障害とつながる全線分７５に
経路障害フラグｌ３を立てる。この線分７５を配線障害
７９−２として，第３２図（５）に示すように画像表示
部３へ表示する。

■−３　部品移動処理２−４−７ 次に、部品移動処理２−４−７の手順を説明する。

部品移動処理２−４−７はスルホール障害７つ−１と配
線障害７９−２を第３２図（４）．（５）のように画像
表示部３へ表示し，操作者が部品の移動指令を入力する
ことにより配線導体７２−１−１とスルホール７２−１
−３と部品を互いの必要間隔を保ちながら移動する。

つまり，操作卓４から操作者が部品移動を指令すると，
第３２図（６〉に示すように，移動する指令を与えられ
た第１の部品８０−１の全部の部品端子７２−１−４を
移動する。そして，これらの部品端子７２−１−４を起
点とし，スルホール押し分け処理２−７を行なう。別の
部品端子７２−１−４を障害としてスルホール押し分け
処理２−７が停止したなばら，その部品端子７２−１−
４を含む第２の部品８０−２を移動する。

つまり，第２の部品８０−２の部品端子７２−１−４を
すべて平行移動し，その部品端子７２一１−４を起点に
加え，スルホール押し分け処理２−７を続行する。スル
ホール押し分け処理２−７が禁止領域７２−１−２で停
止したならば，障害となった禁止領域７２−１−２を表
示して処理を終了する。

以上で経路障害検出手段２−４を説明終了する。

■　経路探索手段２−２の動作手順 次に，第３１図（７），（８）及び第３２図〈７〉を参
照して経路探索手段２−２の手順を説明する。

経路探索手段２−２は結線点入力手段２−１が読み出し
た端子対の指定する始点端子１６−１と終点端子１６−
２に，始点フラグ及び終点フラグを立てる。

一筆書き配線を行なうときは，端子の節７２−３に結合
する境界辺７２−２に始点フラグ終点フラグを立てる。

配線ネットの任意位置間を配線するときは，同一ネット
の配線導体７２−１−１．導体素片７２−１に始点フラ
グ終点フラグを立ててそれらに結合する境界辺７２−２
に始点フラグ終点フラグを立てる。

次に，間隔領域７２−４．境界辺７２−２，スルホール
予約点７２−５を単位として迷路法２−２−１を適用し
て配線経路を発見する。つまり，第３２図（３）に示す
ように始点端子１６−１に接する間隔領域７２−４の経
路探索レベル１４に数値Ｏを書き込む。その間隔領域７
２−４を前線配列へ記憶し，次に起点とする。それに接
する境界辺７２−２に経路探索レベル１４が書き込まれ
ていないで境界辺７２−２の示す線分７５に経路障害フ
ラグ１３が立っていなければ，その境界辺７２−２を前
線配列へ記憶し，その経路探索レベル１４に数値１を書
き込む。また，起点間隔領域７２−４に結合するスルホ
ール予約点７２−５に経路探索レベル１４が書き込まれ
ていなければ，そのスルホール予約点７２−５を前線配
列７７へ記憶するとともに，その経路探索レベル１４に
数値１を書き込む。

次に，前線配列７７に記憶した境界辺７２−２，スルホ
ール予約点７２−５のうち，記憶した順番に各要素を起
点とする。それに接する間隔領域７２−４を前線配線７
７へ記憶するとともに，その間隔領域７２−４の経路探
索レベル１４に起点の数値の次の数値２を書き込む。こ
のようにして経路探索レベル１４に数値を０．１．２の
順で周期的に展開していく。

また，この数値を書き込んだ間隔領域７２−４が終点端
子１６７２に接すれば数値展開を停止し，バックトレー
ス処理２−２−２を行なう。終点端子１６〜２に達しな
いうちに数値展開が不可能になれば．配線経路は存在し
ないため経路探索手段２−２を中断する。

■−１　バックトレース処理２−２−２の手順バックト
レース処理２−２−２を第３１図（８）を参照して説明
する。バックトレース処理２−２−２では迷路法２−２
−１で間隔領域７２−４．境界辺７２−２．スルホール
予約点７２−５の経路探索レベル１４に書き込んだ数値
をもとに，終点端子１６−２から始点端子１６−１まで
数値の周期を逆にして，２，１，Ｏの順で経路探索レベ
ル１４の領域を逆戻りして，それらのバックトレース要
素７８−１をバックトレース配列７８へ記憶する。

以上でバックトレース処理２−２−２と経路探索手段２
−２の動作手順を説明する。

■　押し分け手段２−３の動作手順 次に．第３１図（９）及び第３２図（８）．（９）によ
り押し分け手段２−３の動作手順を述べる。押し分け手
段２−３は，バックトレース配列７８に記憶したバック
トレース要素７８−１を順次読み出す。そのバックトレ
ース要素７８−１が境界辺７２−２であるならば，境界
辺７２−２を含む線分７５に対して配線導体７２−１−
１の回路幅を指定して障害線検出処理２−４−６を行な
う。この処理によりスルホール７２−１−３を押し分け
て新配線を挿入する間隔をあける。その後に，第３２図
（８）に示すように境界辺７２−２の間に新配線導体７
２−１−１を挿入し，そこを新しい節７２−３とし２つ
の新しい境界辺７２−２へ分割する。

次に，従来の間隔領域７２−４を新しい境界辺７２−２
に合わせて２つの間隔領域７２−４へ分割する。

従来の間隔領域７２−４へ接する従来の境界辺７２−２
及び配線導体７２−１−１を新しい間隔領域７２−４及
び新しい節７２−３へポインタで接合し直す。

第３２図（９）に示すようにバックトレース要素７８−
１がスルホール予約点７２−５であるならば．スルホー
ル予約点７２−５のスルホール補助線７５−２に対し．
スルホール予約点７２−５の位置を移動禁止して，新ス
ルホール７２−１−３の直径を指定して障害線検出処理
２−４−６を行なう。この処理により既スルホール７２
−１−３を押し分けて新スルホール７２−１−３を挿入
する間隔を設ける。そしてスルホール予約点７２−５の
位置に新スルホール７２−１−３を作る。スルホール補
助線７５−２を新線分７５とし，新線分７５を既配線導
体７２−１−１で分割して新境界辺７２−２として記憶
する。また．線分７５で既境界辺７２−２と既間隔領域
７２−４を分割して記憶する。このように，バックトレ
ース配列７８のバックトレース要素７８−１を順次読み
出して新配線を挿入していく。

■　固定障害検出処理２−４−２の手順固定障害検出処
理２−４−２は，押し分け手段２−３により更新した線
分７５の移動禁止領域ベクトル欄の内容で，その端の節
７２−３の移動禁止領域を定義する。その節７２−３に
接続する他の線分７５については移動禁止領域ベクトル
欄を更新する。これを繰り返して関連する全線分７５の
移動禁止領域ベクトル欄を更新する。

移動禁止領域ベクトル欄を更新された線分７５を，次の
経路障害検出処理２−４−４の対象として記憶する。そ
れら線分７５に接する間隔領域７２−４を，次のスルホ
ール使用可能検出処理２−４−１の対象として記憶する
。

以上で固定障害検出処理２−４−２を終了し，次に，経
路障害検出手段２−４を行なう。処理対象とする間隔領
域７２−４及び線分７５は固定障害検出処理２−４−２
で指定したものとする。このようにして，以上の全処理
を繰り返す。

第１３図は本発明および従来のものの結線時間と結線率
の関係図を示し，（ａ）は本発明，（ｂ）は従来のもの
の特性曲線を示す。

第１３図に示したように，従来のリップアップリルート
法と比較して短い計算処理時間で高結線率を実現するこ
とが可能になる。これは従来技術が再配線すべき既配線
を捜し出すのに試行錯誤的に行なう手法を用いているの
に対し，本発明は直接再配線すべき配線パターン，すな
わち移動して配線容量を確保できる既配線パターンを検
出できることにある。

［発明の効果］ 以上説明したように本発明は短かい計算処理時間で高結
線率を実現することが可能となる効果がある。

【図面の簡単な説明】

第１図（１）は本発明の第１の実施例の構成を示すブロ
ック図，第１図（２）は本発明の処理手段間の関係を示
すブロック図，第２図は本発明の第１の実施例の画像記
憶部の画素に対するビット構成を示す図，第３図は，本
発明の第１の実施例の手順を示す流れ図．第４図（１）
．（２）．（３）は導体模様の例を示す図，第５図（１
）〜（６〉は本発明の第１の実施例の手順を示す流れ図
．第６図は本発明の第１の実施例の予約木構造のデータ
構造を示すブロック図，第７図（１）〜（４）は導体模
様と予約木構造との例を示す図，第８図（１）．（２）
は本発明の第１の実施例の押し分け手段の手順を示す流
れ図，第９図（１）〜（４）は本発明の第２の実施例の
手順を示す流れ図，第１０図は本発明の第２の実施例の
予約木構造のデータ構造を示すブロック図，第１１図（
１）．（２）は第２の実施例における導体模様の例を示
す図，第１２図は，導体模様の例を示す図，第１３図は
結線時間を示ずグラフをあらわす図，第１４図は第３の
実施例における画像記憶部のデータ構造を示す図，第１
５図は第３の実施例におけるブロックフローチャートを
示す図．第１６図（ｌ）〜（３〉は第３の実施例におけ
るスルホール移動手段を示すフローチャート図，第１７
図は第３の実施例におけるスルホール鎖構造及びスルホ
ール位置条件フラグを示す図，第１８図は第３の実施例
における導体鎖構造を示す図．第１９図は第３の実施例
におけるスルホール移動方向種類及び現在のスルホール
位置と移動位置から移動方向を求める図，第２０図（１
）は第３の実施例におけるネット波紋のひろがりを示す
図，第２　０　（２）図は第３の実施例におけるレベル
をバックトレースして，移動したスルホールに結線して
いた導体模様上の交点位置及び経路を求める図，第２０
図（３〉は第３の実施例におけるバックトレースされた
経路に従って新たな導体を書き込んだ図，第２０図（４
）は第３の実施例における導体鎖構造の始点から交点位
置までの導体を消した図，第２１図は第４の実施例のブ
ロックフローチャートを示す図．第２２図は第４の実施
例の導体占有率係数配列と疑似配線空間配列を示す図．
第２３図は第４の実施例の画像記憶部に記憶された導体
模様と固定指定及び空き画素を示す図，第２４図は第４
の実施例の疑似結線網より得られた経路探索領域を示す
図．第２５図は本発明の第５の実施例の構成を示すブロ
ック図，第２６図（１）〜（４）は，本発明の第５の実
施例の画像記憶部の各要素のデータ構造を示す図，第２
７図（１）〜（６）は本発明の第５の実施例の手順を示
す流れ図．第２８図（１）〜（ｌ１）は本発明の第５の
実施例の画像記憶部の各要素の印刷配線板上の位置を示
す図，第２９図は本発明の第６の実施例の構成を示すブ
ロック図，第３０図（１）〜（７）は，本発明の第６の
実施例の画像記憶部の各要素の構造体を示すブロック図
，第３１図（１）〜（９）は本発明の第６の実施例の手
順を示す流れ図，第３２図（１）〜（９）は本発明の第
６の実施例の画像記憶部の各要素の印刷配線板上の位置
を示す図である。 記号の説明：１・・・画像記憶部，２・・・制御部，２
一〇・・・部品形状人力手段，２−１・・・結線点入力
手段，２−２・・・経路探索手段，２−３・・・押し分
け手段，２−４・・・経路障害検出手段，２−５・・・
スルホール移動手段，３・・・画像表示部，４・・・操
作卓，５・・・印刷部，６・・・通信部，７・・・制御
用記憶部，７−１・・・制御手順記憶，７−２・・・結
線網表，７−３・・・部品座標表，７−４・・・配線座
標表，７−５・・・作業用領域，８・・・磁気記録部，
９・・・画素，１０・・・導体画素，１０−１・・・既
導体模様．１０−２・・・新導体模様，１１・・・固定
指定，１１−１・・・禁止領域，１１−２・・・スルホ
ール，１１−３・・・部品端子，１３・・・経路障害フ
ラグ，１４・・・経路探索レベル，１５・・・仮経路，
１６−１・・・始点端子，１６−２・・・終点端子，１
７・・・予約本構造，２１・・・印刷配線板，６２−１
・・・導体素片，６２−１−１・・・配線導体，６２−
１−２・・・禁止領域，６２−１−３・・・スルホール
，６２−１−４・・・部品端子，６２−２・・・境界辺
，６２−３・・・節，６２−４・・・間隔領域，６５・
・・線分，７２−１・・・導体素片，７２−１−１・・
・配線導体，７２−１−２・・・禁止領域，７２−１−
３・・・スルホール，７２−１−４・・・部品端子，７
２−２・・・境界辺，７２−３・・・節，７２−４・・
・間隔領域，７２一５・・・スルホール予約点をそれぞ
れあらわす。 第 １ 図（２） ”−２：利渭邪 図（１） 第２図 １：３Ｉ像記憶部 第３図 第 ４図 （２） １６−１：姑点端子 第４図 （１） １６−２：終！Ｍ．端子 〆 第４図（３） 第５ 図（１） 第５図（３） 第 ５図（２） 第 ５ 図（４） 第５屈（５） 第６図 第５図 （６） 第 ７図（１） 第 ８ 第 ７図（３） 第７図（４） 図（２） 第 ９ 図（１） 第 ９ 図（２） 箪 ９図（ａ） 第９図（３） 第１０図 第１１ 図（１） 第１２図 第１１図（２） 第１３図 結線時間（Ｈ） 第１５図 第１６図（１） 第１６図（３） （２）３８ 第１９図 第２０図（１） 第２０図（３） 第２０図（２） １５．仮経路 ４２゜移動したスルーホールに昂璋しＴ−ｋｌん碑挿閣
系第２０図（４） ３４：　ｉｌ体の須楕遭の始点位置 （１） （２） ５０ 第２２図 第２４図 第２６図（１） 導体素片６２−１ （ｂ） ６２−＋−２：蒙止ｉ篭． ６２−１−３：スルホール，　６２−１−４．部品増子
第２６図（２） ６２−１ ＩＩ２綿導体 第２６図（４） ６２−４ 間隔領域 第２６図（３） Ａ ○ 第２７図（１） 第２７図（２） 第２７図（４） 第２７図（３） 第２７図（５） 第２７図（６） 第２８図 （１） 印刷１２線板 第２８図（３） 第２８図（５） 第２８図（４） 第２８図（６） Ｖ ６２−２　境界辺 （ｂ） 第２８図（７） 〈挿入前〕 く挿入盪冫 第２８図（９） 第２８図（８） 第２８図（１０） ６９−Ｚ　配螺陽ｉ 第２８図（１１） 第３０図（１） 導体素片７２−１ （ｂ） ７２−１−３ スルホール ７２−１−４：部品靖子 第２９図 第３０図（２） 第３０図（３） ７２−３：　ｉｉ５ 第３０図（５） ７２−５：スルホール予約点 第３０図（４） ７２−４：間隔鵠域， （７２−１−２ 禁止り域） 第３０図（６） （ｂ） 第３０図（７） 第３１図（２） Ｍ３１図（１） 第３１図（６） 第３１図（７） 第３１図（８） 第３１図（９） 第３２図（２） 部品靖子７２−１−４ 第３２図（１） 印１１１２場板２１ 第３２図（３） 第３２図（４） 第３２図（６） 第３２図（５） 配１１ＪＲ畜 ７９−２ 第３２図（７） 第３２図（８） ７２−１−１　：　（新）配＃１導体 第３２図（９） ７２−４：（新）間隔領域 ７２−５：スルホール予約点 ７２−１−３：　（新）スルホール

Claims (7)

【特許請求の範囲】
1. １．印刷配設板の導体模様の画像記憶部と，該画像記憶
   部に記憶した配線の導体模様を移動させて新配線の導体
   模様を挿入する押し分け手段を持つ制御部を有すること
   を特徴とする印刷配線板自動配線設計装置。
2. ２．前記画像記憶部が導体素片と境界辺と節と間隔領域
   を構造体として記憶する手段を有し，前記制御部が，前
   記画像記憶部に記憶した間隔領域を通る経路を探索する
   経路探索手段と，間隔領域に新しい導体素片を挿入し，
   境界辺にスルホールを挿入して既スルホールを押し分け
   る押し分け手段と，境界辺ごとにスルホール設定可能性
   と配線導体の挿入可能性を調らべ，障害がある場合にそ
   れらを表示し，操作卓からの指示により部品を移動する
   経路障害検出手段を有することを特徴とする特許請求の
   範囲第１項記載の印刷配線板自動配線設計装置。
3. ３．前記画像記憶部が，導体素片と，境界辺と，節と，
   間隔領域と，スルホール予約点とを構造体として記憶す
   る手段を有し，前記制御部が，前記画像記憶部に記憶し
   た間隔領域を通る経路を探索する経路探索手段と，新し
   い導体素片およびスルホールを挿入し，それに伴い既ス
   ルホールを押し分ける押し分け手段と，間隔領域毎にス
   ルホール予約点を調らべ，境界辺毎に配線導体の挿入可
   能性を調らべ，障害がある場合にそれらを表示し，操作
   卓からの指示により部品を移動する経路障害検出手段と
   を有することを特徴とする，特許請求の範囲第１項記載
   の印刷配線板自動配線設計装置。
4. ４．前記画像記憶部が配線の導体模様を画素に分解して
   記憶する手段を有し，前記制御部が，前記画像記憶部に
   記憶した既配線の導体模様の間隙に新配線の仮経路を探
   索する経路探索手段と，該仮経路と既配線の導体模様と
   の間に１画素以上の間隔をあけるように既配線の導体模
   様を移動しながら新配線の導体模様を挿入する押し分け
   手段と，スルホール設定可能な領域を調べる処理および
   固定部品の間の配線容量を調べる処理を行なう経路障害
   検出手段とを有することを特徴とする，特許請求の範囲
   第１項記載の印刷配線板自動設計装置。
5. ５．前記押し分け手段がスルホールの移動も行なうこと
   を特徴とする特許請求の範囲第４項記載の印刷配線板自
   動配線設計装置。
6. ６．前記画像記憶部の１つの画素が，導体の有無を示す
   ビットと，導体の固定指定を書き込むビットと，探索波
   紋を書き込むビットと，探索の障壁を書き込むビットと
   ，スルホール使用可能ビット以外に，移動するスルホー
   ルの識別ビットと，移動するスルホールに結線している
   導体の識別ビットとを有し，前記押し分け手段および経
   路障害検出手段を用いて，結線に障害となる該画像記憶
   部に記憶された固定指定のスルホールおよびそのスルホ
   ールに結線している導体模様を移動させて，新たな導体
   模様を挿入するスルホール移動手段を有することを特徴
   とする，特許請求の範囲第４項記載の印刷配線板自動配
   線設計装置。
7. ７．前記経路探索手段が，前記画像記憶部の記憶容量に
   対して，画像記憶部に記憶された導体模様と固定指定の
   画素の占める割合を算出して係数化し，その係数の示す
   値により経路探索領域を求め，経路探索領域内を経路探
   索することを特徴とする特許請求の範囲第４項記載の印
   刷配線板自動配線設計装置。