(57)【特許請求の範囲】
【請求項１】
指定された始点から終点までの経路を形成する経路形成装置において、
迂回路の位置情報を格納する経路格納手段と、
始点と終点間を結ぶ直線を演算する直線演算手段と、
該直線演算手段にて演算された直線を上下左右に所定のクリアランス値分、拡張した範囲と重なる障害物を検出する障害物検出手段と、
該検出された障害物のオフセット外形線を求め、前記直線と前記オフセット外形線が交差する第一の交点と第二の交点を求め、前記第一の点から前記オフセット外形線を経て前記第二の交点に至る迂回路を求め、決定した迂回路の前記第一の交点と前記第二の交点と前記迂回路上の点を前記経路格納手段に格納する迂回路決定手段と、
前記経路格納手段に格納された全ての点について、１点ずつ点を特定し、該特定点と接続可能な他の点を特定し、短絡経路が形成できるか判定し、短絡経路を形成できると判定した場合、前記経路格納手段から形成される短絡経路から外れる点を削除し、前記特定点と他の点を前記短絡経路の始点と終点として、前記直線演算手段と前記障害物検出手段と前記迂回路決定手段により、始点と終点間を結ぶ直線を演算し、障害物を検出し、迂回路を求め、格納する処理を実行する短絡経路決定手段と、
前記直線と前記決定された迂回路とを用いて始点から終点に至る経路を形成する手段とを含む経路形成装置。
【請求項２】
請求項１記載の経路形成システムにおいて、更に、前記経路格納手段に格納されている、前記第一の交点から前記第二の交点まで前記障害物の周りを右回り及び左回りで辿る経路のうち短い方を迂回路として決める手段を有する経路形成装置。
【請求項３】
請求項１または２記載の経路形成装置において、
更に、
経路を表示装置に表示する表示手段と、
前記表示装置において経路の始点と終点の指示を入力する入力手段とを有し、
前記迂回路決定手段は、更に、決定した迂回路を表示装置に表示する表示手段を有する経路形成装置。
【請求項４】
請求項１乃至３のいずれか一項記載の経路形成装置において、
更に、前記入力手段にて前記表示装置の画面上で指定される点を終点として所定周期でサンプリングする終点サンプリング手段と、
前記終点サンプリング手段にて終点がサンプリングされる毎に、前記始点から前記終点に至る経路が形成されるように前記終点を前記直線演算手段に提供する制御手段とを有し、
サンプリングされる終点の変化に応じて前記表示装置の画面上に形成される経路が順次変化するようにした経路形成装置。
【請求項５】
指定された始点から終点までの経路を、直線演算手段、障害物検出手段、障害物検出手段、迂回路決定手段、短絡経路決定手段及び経路形成手段を有するコンピュータにより形成する経路形成方法において、
前記直線演算手段で、始点と終点間を結ぶ直線を演算するステップと、
迂回路の位置情報を経路格納手段に記憶するステップと、
障害物検出手段で、前記演算された直線を上下左右の所定のクリアランス分拡張した範囲と重なる障害物を検出するステップと、
迂回路決定手段で、前記検出された障害物のオフセット外形線を求め、前記直線と前記オフセット外形線が交差する第一の交点と第二の交点を求め、前記第一の交点から前記オフセット外形線を経て前記第二の交点に至る迂回路を求めるステップと、
前記短絡経路決定手段で、前記経路格納手段に格納された全ての点について、１点ずつ点を特定し、該特定点と接続可能な他の点を特定し、短絡経路が形成できるか判定し、短絡経路を形成できると判定した場合、前記経路格納手段から形成される短絡経路から外れる点を削除し、前記特定点と前記他の点を前記短絡経路の始点と終点として、前記直線演算手段と前記障害物検出手段と前記迂回路決定手段により始点と終点間を結ぶ直線を演算するステップと障害物を検出するステップと迂回路を求めるステップとを実行するステップと、
前記経路形成手段で、前記直線と前記決定された迂回路とを用いて始点から終点に至る経路を形成するステップと、
前記第一の交点と前記第二の交点と前記迂回路の点を前記経路格納手段に格納するステップとを含む経路形成方法。
【請求項６】
コンピュータに、
始点と終点間を結ぶ直線を演算するステップと、
迂回路の位置情報を記憶するステップと、
前記演算された直線を上下左右の所定のクリアランス分拡張した範囲と重なる障害物を検出するステップと、
前記検出された障害物のオフセット外形線を求め、前記直線と前記オフセット外形線が交差する第一の交点と第二の交点を求め、前記第一の交点から前記オフセット外形線を経て前記第二の交点に至る迂回路を求めるステップと、
前記迂回路記憶ステップで記憶された全ての点について、１点ずつ点を特定し、該特定点と接続可能な他の点を特定し、短絡経路が形成できるか判定し、短絡経路を形成できると判定した場合、前記迂回路記憶ステップから形成される短絡経路から外れる点を削除し、前記特定点と前記他の点を前記短絡経路の始点と終点として、前記直線演算手段と前記障害物検出手段と前記迂回路決定手段を実行するステップと、
前記直線と前記迂回路とを用いて始点から終点に至る経路を形成するステップと、
前記第一の交点と前記第二の交点と前記迂回路の点を記憶するステップとを実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、プリント基板の設計を行うＣＡＤ（Computer Aided Design ）システム等に適用され、プリント配線パターン等の経路を形成するためのシステム及び方法及びコンピュータに経路形成の処理を行なわせるためのプログラムを格納した記録媒体に関する。
【０００２】
【従来の技術】
従来、プリント基板の設計を行なうＣＡＤシステムにおいて、プリント基板上の２点間にプリント配線パターンが形成されるべき経路を決める場合、例えば、次のような処理が行なわれている。
プリント基板面を細かい矩形領域（メッシュ）に分割する。始点と終点（２点）が指定されると、該始点から障害物（例えば、電子部品、既に形成されたプリント配線パターン、スルーホール等）のない矩形領域を辿って終点に至る経路が探索される。即ち、経路の探索の過程で選択された各矩形領域において、隣接する８方向の矩形領域に障害物が存在するか否かが調べられ、障害物が存在しない隣接矩形領域のうちから所定のアルゴリズムに従って経路が通るべき１つの矩形領域が選ばれる。このように矩形領域が選択される毎に同様の処理を繰り返すことによって、始点から障害物のない矩形領域を辿って終点に至る経路が決定される。
【０００３】
【発明が解決しようとする課題】
上記のような従来の経路の決定手法では、常に、経路が通るべき矩形領域と判断された矩形領域に隣接する全ての矩形領域について障害物の有無を更に判定しなければならず、その処理の対象となる領域が広くなる。その結果、処理量が多くなって、処理時間が長くなってしまう。
【０００４】
また、選択されるべき矩形領域により経路が進む方向（８方向）が大きく変わってしまうため、決定された経路の長さは、不要に長くなる可能性がある。
そこで、本発明の第一の課題は、障害物を迂回して２点間を結ぶ経路を短時間にて決定できるような経路形成システム及び方法及を提供することである。
また、本発明の第二の課題は、障害物を迂回して２点間を結ぶより短い経路を決定できるような経路形成システム及び方法を提供することである。
【０００５】
更にまた、本発明の第三の課題は、上記のように２点間を結ぶ経路形成の処理をコンピュータに行なわせるためのプログラムを格納した記録媒体を提供することである。
【０００６】
【課題を解決するための手段】
本発明は、指定された始点から終点までの経路を形成する経路形成装置において、迂回路の位置情報を格納する経路格納手段と、始点と終点間を結ぶ直線を演算する直線演算手段と、該直線演算手段にて演算された直線を上下左右に所定のクリアランス値分、拡張した範囲と重なる障害物を検出する障害物検出手段と、該検出された障害物のオフセット外形線を求め、前記直線と前記オフセット外形線が交差する第一の交点と第二の交点を求め、前記第一の点から前記オフセット外形線を経て前記第二の交点に至る迂回路を求め、決定した迂回路の前記第一の交点と前記第二の交点と前記迂回路上の点を前記経路格納手段に格納する迂回路決定手段と、前記経路格納手段に格納された全ての点について、１点ずつ点を特定し、該特定点と接続可能な他の点を特定し、短絡経路が形成できるか判定し、短絡経路を形成できると判定した場合、前記経路格納手段から形成される短絡経路から外れる点を削除し、前記特定点と前記他の点を前記短絡経路の始点と終点として、前記直線演算手段と前記障害物検出手段と前記迂回路決定手段を制御する短絡経路決定手段と、前記直線と前記決定された迂回路とを用いて始点から終点に至る経路を形成する手段とを含むことを特徴とする。
【０００７】
上記のような、経路形成システム及び方法では、指定された始点と終点間を結ぶ直線が基本的な経路として選ばれる。そして、その基本的な経路である直線と既に表示画面上に存在する障害物と交差する場合に、その障害物を迂回する迂回路が求められる。そして、この直線と迂回路に基づいて始点から終点に至る最終的な経路が形成される。
【０００８】
上記経路形成システム及び方法では、始点から終点を結ぶ直線（最短距離）に添って、迂回路の決定のための処理が行なわれるので、処理の対象となる領域が必要以上に広くならない。そして、形成される経路は、始点から終点を結ぶ直線に可能な限り近いものとなる。
例えば、本発明をプリント基板設計におけるプリント配線パターンの形成に適用する場合、形成すべきプリント配線パターンは、障害物（回路素子等）から所定の距離だけ離さなければならない。このような場合において、始点から終点に至る直線に近すぎる障害物は、該直線と交差するものと見なすようにするという観点から、上記経路形成システム及び方法において、演算された直線を含む所定の検索領域を生成し（検索領域設定手段）、該検索領域と重なる表示画面上の障害物を検索する（検索手段）ことにより、障害物を検出する（障害物検出手段）ようにできる。
【０００９】
また、前記迂回路決定手段は、更に、第一の交点から第二の交点まで障害物の周りの迂回路上の点と点の間を結ぶ直線に対して、短絡する経路を形成できるかを判定し、短絡経路を形成できると判定した場合、前記経路格納手段から前記短絡経路により不要となる点を削除する短絡経路決定手段と、前記第一の交点から前記第二の交点まで前記障害物の周りを右回り及び左回りで辿る経路のうち短い方を迂回路として決める手段を有することを特徴とする。
【００１０】
このような経路形成システム及び方法では、障害物の周りを右回り及び左回りで辿る経路のうち短い方が迂回路として決定され、始点から終点に至るより短い経路を形成することができる。
また、検出された障害物の迂回路が容易に決定できるという観点から、該直線と交わる障害物の周りを囲むオフセット外形線を求め、該オフセット外形線と上記直線との交点を演算し（交点演算手段）、演算された交点の一方を第一の点、他方を第二の点とし、この第一の点から第二の点までオフセット外形線を右回り及び左回りで辿る経路のうち短い方を選択し、この選択された経路を迂回路として決める（迂回路決定手段）ようにできる。
【００１１】
このような、経路形成システム及び方法では、障害物を囲むオフセット外形線を辿る経路の一部が当該障害物の迂回路として決定される。更に、そのオフセット外形線を辿る経路のうちより短い経路が迂回路となる。従って、より短い迂回路が決定される。
上記のように、オフセット外形線に基づいて迂回路を決定する経路形成システム及び方法において、該オフセット外形線を容易に決定できるという観点から、上記オフセット外形線は矩形を形成するようできる。即ち、障害物の迂回路は、この障害物を囲む矩形の一部となる。
【００１２】
このような経路形成システム及び方法では、この障害物を内部に含む矩形を設定することで迂回路を決定することができる。この矩形と内部の障害物との関係（障害物の外形線と矩形（オフセット外形線）との距離）は、形成すべき経路を障害物からどれだけ離すべきかに基づいて定められる。
上述したようなシステム及び方法にて決定される経路を更に短縮できるようにするという観点から、上述した経路形成システム及び方法において、更に、直線と迂回路から決まる始点から終点に至る経路上のある点から他の点に至る短絡経路を決め（短絡経路決定手段）、上記直線と迂回路から決まる始点から終点に至る経路を決定された短絡経路にて補正する（経路補正手段）ようにできる。
【００１３】
上記経路形成システム及び方法では、上記直線と迂回路から決まる始点から終点に至る経路上のある点と他の点との間の部分が、それらの点間に形成される短絡経路にて補正される。従って、上記直線と迂回路から決まる始点から終点に至る経路が短縮される。
また、上記のようにして短絡経路を形成する場合、対象となる２点間の最短距離となる直線にて短絡経路を形成することが望ましい。この場合、２点間を結ぶ直線上に他の障害物が存在する可能性がある。このように、該２点間を結ぶ直線上に障害物があったとしても、形成される短絡経路ができるだけ２点間を結ぶ直線に近くなるようにするという観点から、上記直線と迂回路から決まる始点から終点に至る経路上のある点から他の点に至る短絡直線を演算し、演算された短絡直線に交差する既に表示画面に表示された障害物を検索し、検索された障害物の周りを迂回する短絡迂回路を決定し、上記短絡直線及び短絡迂回路に基づいて短絡経路を決定する（短絡経路決定手段）ようにできる。
【００１４】
上記経路形成システム及び方法では、既に得られている始点から終点に至る経路上の２点間を結ぶ直線（短絡直線）が基本的に短絡経路として選択される。そして、その直線が障害物と交差する場合に、その障害物を迂回する短絡迂回路が決定され、上記短絡直線と短絡迂回路とに基づいて短絡経路が決定される。従って、短絡経路は、該２点間を結ぶ直線（最短距離）により近いものとなる。
【００１５】
特に、経路の終点がマウス等のポインティングデバイスにて指定できる場合、その指定位置を移動する時に、その終点の移動に伴って表示画面上に形成される経路が変化すると（ラバーバンディング）、ユーザにとって便利である。このような、画面表示を実現する観点から、更に、本発明は、経路を表示装置に表示する表示手段と、前記表示装置において経路の始点と終点の指示を入力する入力手段とを有し、前記迂回路決定手段は、更に、決定した迂回路を表示装置に表示する表示手段を有することを特徴とする。
【００１６】
本発明は、更に、前記入力手段にて前記表示装置の画面上で指定される点を終点として所定周期でサンプリングする終点サンプリング手段と、前記終点サンプリング手段にて終点がサンプリングされる毎に、前記始点から前記終点に至る経路が形成されるように前記終点を前記直線演算手段に提供する制御手段とを有し、サンプリングされる終点の変化に応じて前記表示装置の画面上に形成される経路が順次変化するようにしたことを特徴とする。
【００１７】
本発明は、指定された始点から終点までの経路を、直線演算手段、障害物検出手段、障害物検出手段、迂回路決定手段、短絡経路決定手段及び経路形成手段を有するコンピュータにより形成する経路形成方法において、前記直線演算手段で、始点と終点間を結ぶ直線を演算するステップと、迂回路の位置情報を経路格納手段に記憶するステップと、障害物検出手段で、前記演算された直線を上下左右の所定のクリアランス分拡張した範囲と重なる障害物を検出するステップと、迂回路決定手段で、前記検出された障害物のオフセット外形線を求め、前記直線と前記オフセット外形線が交差する第一の交点と第二の交点を求め、前記第一の交点から前記オフセット外形線を経て前記第二の交点に至る迂回路を求めるステップと、前記短絡経路決定手段で、前記経路格納手段に格納された全ての点について、１点ずつ点を特定し、該特定点と接続可能な他の点を特定し、短絡経路が形成できるか判定し、短絡経路を形成できると判定した場合、前記経路格納手段から形成される短絡経路から外れる点を削除し、前記特定点と前記他の点を前記短絡経路の始点と終点として、前記直線演算手段と前記障害物検出手段と前記迂回路決定手段を制御するステップと、前記経路形成手段で、前記直線と前記決定された迂回路とを用いて始点から終点に至る経路を形成するステップと、前記第一の交点と前記第二の交点と前記迂回路の点を前記経路格納手段に格納するステップとを含むことを特徴とする。
【００１９】
本発明は、始点と終点間を結ぶ直線を演算するステップと、迂回路の位置情報を記憶するステップと、前記演算された直線を上下左右の所定のクリアランス分拡張した範囲と重なる障害物を検出するステップと、前記検出された障害物のオフセット外形線を求め、前記直線と前記オフセット外形線が交差する第一の交点と第二の交点を求め、前記第一の交点から前記オフセット外形線を経て前記第二の交点に至る迂回路を求めるステップと、前記迂回路記憶ステップで記憶された全ての点について、１点ずつ点を特定し、該特定点と接続可能な他の点を特定し、短絡経路が形成できるか判定し、短絡経路を形成できると判定した場合、前記迂回路記憶ステップから形成される短絡経路から外れる点を削除し、前記特定点と前記他の点を前記短絡経路の始点と終点として、前記直線演算手段と前記障害物検出手段と前記迂回路決定手段を実行するステップと、前記直線と前記迂回路とを用いて始点から終点に至る経路を形成するステップと、前記第一の交点と前記第二の交点と前記迂回路の点を記憶するステップとをコンピュータに実行させることを特徴とする。
【００２０】
なお、更に上述した各経路形成システムでの（及び方法に従った）処理をコンピュータに行なわせるため、対応する機能をコンピュータに実現させるプログラムが格納された記録媒体が提供される。
【００２１】
【発明の実施の形態】
以下、本発明の実施の一形態を図面に基づいて説明する。
本発明に係る経路形成システム及び方法は、例えば、プリント基板を設計する際にプリント配線パターン（配線経路）を表示画面上に形成するシステム（ＣＡＤ）に適用できる。このようなシステムのハードウエアは、例えば、図１に示すように構成される。
【００２２】
図１において、このシステムは、ＣＰＵ（中央処理演算ユニット）１０、メモリユニット２０、入力制御ユニット３０、表示制御ユニット４０、ＣＤ−ＲＯＭドライバ５０およびハードディスクユニット６０を有している。これら各ユニット１０、２０、３０、４０、６０及びＣＤ−ＲＯＭドライバ５０は、バス７０を介して接続されている。また、システムは、更に、情報入力デバイスとしてのキーボード３１、ポインティングデバイスとしてのマウス３２、および表示ユニット４２を有している。キーボード３１およびマウス３２からの情報は、入力制御ユニット３０およびバス７０を介してＣＰＵ１０に提供される。
【００２３】
メモリユニット２０は、ＲＡＭ、ＲＯＭ等のメモリデバイスを含み、プログラムおよび各種の情報を記憶する。ハードディスクユニット６０は、ファイル、データベース、プログラム等の情報を格納している。プリント基板設計に関するプログラムはＣＤ−ＲＯＭ１００に格納され、このＣＤ−ＲＯＭ１００により該プリント基板設計に関するプログラムが当該システムに提供される。ＣＤ−ＲＯＭ１００はＣＤ−ＲＯＭドライバ５０にセットされ、ＣＤ−ＲＯＭドライバ５０によってＣＤ−ＲＯＭ１００から読みだされた該プログラムは、バス７０を介してハードディスクユニット６０に格納される。そして、ハードディスクユニット６０から必要に応じて読みだされたプログラムは、メモリユニット２０（ＲＡＭ）に格納される。ＣＰＵ１０は、このメモリユニット２０に格納されたプログラムに従ってプリント配線パターンの形成処理（経路形成の処理）を含むプリント基板設計に関する処理を実行する。
【００２４】
上記ＣＤ−ＲＯＭ１００は、本発明に係るコンピュータに経路形成の処理を行わせるためのプログラムを格納した記録媒体に相当する。この記憶媒体は、ＣＤ−ＲＯＭ１００のほか、システムの構成に応じて、磁気ディスク（フロッピーディスク）、ＤＶＤ等の他の光ディスク、光磁気ディスク（ＭＯ）、磁気テープ、その他半導体メモリカード（ＰＣカード）等で構成することができる。
【００２５】
ＣＰＵ１０によるプリント基板設計に関する処理の実行の結果、設計されたプリント基板上のプリント配線パターンが表示ユニット４２に表示される。オペレータは、例えば、表示ユニット４２に表示されるプリント配線パターンを見ながらキーボード３１、マウス３２を操作して設計に必要な情報を入力する。
表示ユニット４２の画面上にプリント配線パターンを形成するため、ＣＰＵ１０は、例えば、図２および図３に示すプログラムの手順に従って処理を実行する。
【００２６】
図２において、まず、ＣＰＵ１０は、入力された配線経路の始点（ｄ１）、終点（ｄ２）および配線経路と障害物とのクリアランス値δを内部のレジスタにセットする（Ｓ１）。この配線経路の始点（ｄ１）、終点（ｄ２）および配線経路と障害物とのクリアランス値δは、別に設計された電子回路を記述する回路情報に基づいて自動的に当該システムに提供されるものでも、また、ユーザがキーボード３１およびマウス３２を用いて当該システムに提供するものであってもよい。そして、ＣＰＵ１０は、セットされた始点（ｄ１）および終点（ｄ２）を結ぶ直線を演算する（Ｓ２）。この始点（ｄ１）から終点（ｄ２）に至る直線Ｌは、例えば、図７（１）に示すように、既に、表示ユニット４２の画面上に表示された電子部品Ａ、Ｂ（障害物Ａ、Ｂ）と、交差すると仮定する。
【００２７】
その後、ＣＰＵ１０は、演算した直線Ｌを内部に含む検索範囲Ｅｏを、図７（２）に示すように設定する（Ｓ３）。この検索範囲Ｅｏは、直線Ｌを上下、左右方向にセットしたクリアランス値δだけ拡張した範囲である。そして、ＣＰＵ１０は、検索範囲Ｅｏと重なる画面上の障害物を検索する（Ｓ４）。その検索の結果、障害物Ａ、Ｂが得られると（Ｓ５）、そのうちの１つ、例えば、障害物Ａが処理の対象として特定される（Ｓ６）。
【００２８】
ＣＰＵ１０は、特定した障害物Ａの周りを囲むオフセット外形線ＡＯを求める（Ｓ７）。このオフセット外形線ＡＯは、例えば、図７（３）に示すように、障害物Ａの外形線からクリアランス値δだけ離れた位置に設定される線である。オフセット外形線ＡＯは矩形を形成する。その後、ＣＰＵ１０は、上記直線Ｌと障害物Ａの周りに設定したオフセット外形線ＡＯとの交点を演算するＳ（８）。この場合、図７（３）に示すように、交点ｄ３およびｄ４が得られる。
【００２９】
このように、直線Ｌとオフセット外形線ＡＯとの交点ｄ３およびｄ４が得られると、ＣＰＵ１０は、交点ｄ３から右回りにオフセット外形線ＡＯを辿って交点ｄ４に至る経路と、交点ｄ３から左周りにオフセット外形線ＡＯを辿って交点ｄ４に至る経路のうち短い経路を迂回路として決定する（Ｓ９）。この場合、交点ｄ３から左回りにオフセット外形線ＡＯを辿って交点ｄ４に至る経路が、図７（４）に示すように、迂回路ＬＡとして決定される。その後、ＣＰＵ１０は、上記のように演算して求めた交点ｄ３およびｄ４と迂回路ＬＡの折曲点ｄ７およびｄ８を求めるべき経路上の点としてメモリユニット２０（ＲＡＭ）に格納する（Ｓ１０）。そして、ＣＰＵ１０は、検索された全ての障害物についての処理が終了したかどうかを判定し（Ｓ１１）、終了していなければ、次の障害物Ｂを特定して（Ｓ６）、上記と同様の処理（Ｓ７、Ｓ８、Ｓ９、Ｓ１０）を実行する。その結果、図７（３）に示すように障害物Ｂの周りを囲むオフセット外形線ＢＯと直線Ｌとの交点ｄ５およびｄ６に基づいて、図７（４）に示すような迂回路ＬＢが決定される。そして、この交点ｄ５およびｄ６と迂回路ＬＢの折曲点ｄ９およびｄ１０が更に、求めるべき経路上の点としてメモリユニット２０に格納される。
【００３０】
上記のような処理を検索された障害物全てについて終了すると（Ｓ１１）、ＣＰＵ１０は、図３に示す手順での処理を始める。
図３において、ＣＰＵ１０は、上記のようにメモリユニット２０に格納された各点（ｄ３、ｄ４、ｄ５、ｄ６、ｄ７、ｄ８、ｄ９、ｄ１０）から１点ｄｉを特定する（Ｓ２１）。また、ＣＰＵ１０は、この特定した点ｄｉと接続可能な他の点（以下対応点ｄｊという）を特定する（Ｓ２２）。そして、ＣＰＵ１０は、該点ｄｉと対応点ｄｊとの間に短絡経路が形成できるか否かを判定する（Ｓ２３）。例えば、点ｄ３（ｄｉ）は点ｄ８（ｄｊ）と接続可能であるが、障害物Ａのために、点ｄ３と点ｄ８との間には短絡経路を形成することができない。また、図８（１）に示すように、点ｄ８（ｄｉ）は点ｄ９（ｄｊ）と接続可能であり、更に、点ｄ８と点ｄ９との間には短絡経路Ｌｓを形成することができる。このように、２点間に短絡経路を形成することができると判定されると、ＣＰＵ１０は、その短絡経路によって不要になる経路上の点をメモリユニット２０に格納した点から削除する（Ｓ２４）。上記のように、点ｄ８と点ｄ９との間に短絡経路Ｌｓが形成できる場合、図８（２）に示すように、その短絡経路Ｌｓによって不要となる点ｄ４およびｄ５がメモリユニット２０から削除される。
【００３１】
ＣＰＵ１０は、上記のような処理を形成すべき経路上の点としてメモリユニット２０に格納された全ての点（ｄ３、ｄ４、ｄ５、ｄ６、ｄ７、ｄ８、ｄ９、ｄ１０）について実行する（Ｓ２５、Ｓ２６）。そして、全ての点についての当該処理が終了すると、ＣＰＵ１０は、その時点でメモリユニット２０に経路上の点として格納されている点を用いて、プリントパターン配線の表示処理を実行する（Ｓ２７）。この処理では、始点（ｄ１）から上記メモリユニット２０に格納された点（ｄ３、ｄ７、ｄ８、ｄ９、ｄ１０、ｄ６）を順次辿って終点（ｄ２）に至る経路の配線パターンイメージがメモリユニット２０の画像メモリ上に展開され、そのイメージ情報がメモリユニット２０から表示制御ユニット４０を介して表示ユニット４２に提供される。その結果、図９に示すように、始点（ｄ１）から障害物ＡおよびＢを迂回して終点（ｄ２）に至る配線パターンＰＬ１が表示ユニット４２の画面上に形成される。
【００３２】
なお、直線Ｌを演算した後、その直線Ｌを含む検索範囲に重なる障害物が無い場合（Ｓ５）、始点（ｄ１）から終点（ｄ２）に至る直線の配線パターンＰＬが表示画面上に形成される（Ｓ５→Ｓ２７）。
上記のようにして表示ユニット４２の画面上に形成された配線パターンＰＬ１は、始点（ｄ１）と終点（ｄ２）を結ぶ直線により近いものとなり、より短い配線パターンとなる。また、処理の過程で、短絡経路を形成するようにしているので、更に短い配線パターンＰＬ１を形成することが可能となる。
【００３３】
なお、上述した処理における各ステップと請求項記載の要件との対応関係は、次のようになる。図２に示すステップＳ２が直線演算手段（演算プログラム手段）に、ステップＳ３が検索領域設定手段（検索領域設定プログラム手段）に、ステップＳ４が検索手段（検索プログラム手段）に、ステップＳ７がオフセット外形線を求める手段（プログラム手段）に、ステップＳ８が交点演算手段（交点演算プログラム手段）に、ステップＳ９がオフセット外形線を右回りおよび左回りで辿る経路のうち短い方を迂回路として決める手段（プログラム手段）に、それぞれ対応する。また、図３に示すステップＳ２３が短絡経路決定手段（短絡経路決定プログラム手段）に、ステップＳ２４が経路補正手段（経路補正プログラム手段）に、それぞれ対応する。
【００３４】
例えば、図１０（１）に示すように、始点（ｄ１）から終点（ｄ２）に至る直線Ｌと交差する障害物ＡおよびＢの間に、該直線Ｌとは、交差しない他の障害物Ｃが存在する場合を仮定する。この場合、前述したように図２および図３に示す手順に従ってなされる処理の過程で、点ｄ８と点ｄ９間に短絡経路Ｌｓを形成すると、その短絡経路Ｌｓが図１０（２）に示すように障害物Ｃと交差してしまう。そこで、形成しようとする短絡経路Ｌｓが他の障害物と交差することを防止するため、図３に示す手順に代えて、例えば、図４に示す手順に従って、ＣＰＵ１０は処理を行なう。なお、図４において、図３と同じステップ番号は同じ処理を表しており、詳しい説明は省く。
【００３５】
図４において、上述したのと同様に、経路上の点であるとしてメモリユニット２０に格納された各２点ｄｉ、ｄｊ間に短絡経路が形成できるかどうかが判定される（Ｓ２１、Ｓ２２、Ｓ２３）。そして、短絡経路が形成することができる場合、上記と同様に、短絡経路により不要となった経路上の点がメモリユニット２０から削除される（Ｓ２４）。従って、例えば、図１０（１）、（２）に示すように、２点ｄ８、ｄ９間に形成される短絡経路Ｌｓによって不要となった点ｄ４、ｄ５がメモリユニット２０から削除される。
【００３６】
その後、ＣＰＵ１０は、現在処理の対象となる点ｄｉを始点とし、選択された対応点ｄｊを終点としてそれぞれ内部のレジスタにセットする（Ｓ３１）。そして、ＣＰＵ１０は、この始点（ｄｉ）から終点（ｄｊ）に至る直線を演算する（Ｓ３２）。この演算される直線（短絡直線）は、短絡経路Ｌｓを表している。そして、その短絡経路Ｌｓ（直線）の周りに、図２に示す処理と同様に、検索範囲を設定し（Ｓ３３）、その検索範囲と重なる障害物が検索される（Ｓ３４）。そして、そのような障害物が存在する場合（Ｓ３５）、ＣＰＵ１０は、図２に示すステップＳ６、Ｓ７、Ｓ８、Ｓ９での処理に相当する迂回路決定処理Ｐ１００を実行する。その結果、例えば、始点（ｄ８＝ｄｉ）から終点（ｄ９＝ｄｊ）に至る短絡経路Ｌｓ内に、図１０（３）に示すような迂回路（短絡迂回路ｄ１１→ｄ１２→ｄ１３→ｄ１４）が決められる。
【００３７】
そして、ＣＰＵ１０は、この短絡迂回路を特定する点ｄ１１、ｄ１２、ｄ１３、ｄ１４をメモリユニット２０内に格納された形成すべき経路上の点に追加する（Ｓ３６）。上記のような処理を、図２に示す処理にて得られた全ての点について実行する（Ｓ２５、Ｓ２６）。全ての点についての処理が終了すると、ＣＰＵ１０は、最終的にメモリユニット２０に格納された点（ｄ３、ｄ６、ｄ７、ｄ８、ｄ９、ｄ１０、ｄ１１、ｄ１２、ｄ１３、ｄ１４）に基づいて、上記始点（ｄ１）から順次各点を辿って終点（ｄ２）に至る配線パターンの表示処理を実行する。その結果、例えば、図１１に示すように、始点（ｄ１）から各障害物Ａ、Ｂ、Ｃを迂回して終点（ｄ２）に至る配線パターンＰＬ２が表示ユニット４２の画面上に形成される。
【００３８】
なお、上記図４に示す手順に従った処理における各ステップと請求項記載の要件との関係は次のようになる。ステップＳ３２がある点から他の点に至る短絡直線を演算する手段（プログラム手段）に、ステップＳ３３とＳ３４が短絡直線と交差する障害物を検索する手段（プログラム手段）に、処理Ｐ１００が迂回路を決定する手段（プログラム手段）に、それぞれ対応している。
【００３９】
形成すべき配線パターンの始点および終点がマウス３２等のポインティングデバイスにて指定できる場合、始点を指定した後に、終点の指定位置を移動に伴って表示画面上に形成される経路が変化すると（ラバーバンディング）、プリント基板を設計するユーザにとって便利である。このような機能を実現するため、例えば、図５に示すような手順のプログラムがシステムに提供される。このようなプログラム手順に従って、ＣＰＵ１０は次のように処理を実行する。
【００４０】
ＣＰＵ１０は、最初、始点入力の待ち状態にある（Ｓ４１）。ここで、ユーザがマウス３２によって表示画面上のマウスポインタを所望の位置に合わせてマウスボタンを押すと、ＣＰＵ１０は、そのポインタ位置を始点（ｄ１）として内部のレジスタにセットする  （Ｓ４２）。その後、ＣＰＵ１０は、図示しない内部のタイマＴを起動し（Ｓ４３）、そのタイマＴが所定時間Ｔｏ（例えば、３０ミリ秒乃至５０ミリ秒）に達したか否かを判定する（Ｓ４４）。
【００４１】
ユーザは、始点位置を入力するためにマウス３４のマウスボタンを押した後に、その状態でマウス３４を移動（ドラッグ）している間、更に以下の処理が実行される。
タイマＴが所定時間Ｔｏに達したことを判定すると（Ｓ４４）、ＣＰＵ１０は、その時点でマウス３４によって指示されるマウスポインタの位置をサンプリングする（Ｓ４５）。そして、ＣＰＵ１０は、そのサンプリングした位置を終点として内部のレジスタにセットする（Ｓ４６）。このように、始点および終点がセットされると、ＣＰＵ１０は、前述した、例えば、図２および図４（又は図３）に示す手順の処理Ｐ１０１を実行して、始点から終点に至る配線パターンを表示ユニット４２の画面上に形成する。その後、ＣＰＵ１０は、タイマＴをリセットし（Ｓ４７）、終点の指示操作、即ち、マウス３２のドラッグ操作が終了したかどうかを判定する（Ｓ４８）。そして、マウス３２のドラッグ操作が終了していなければ、ＣＰＵ１０は、タイマＴを再度起動して（Ｓ４３）、上記と同様の処理を繰り返す。
【００４２】
上記処理は、ユーザによるマウス３２のドラッグ操作が終了するまで、繰り返される。従って、マウス３２のドラッグ操作が行なわれている間、例えば、図１２（１）に示すように、ポインタ位置ｄ２がサンプリングされると、始点ｄ１から各障害物（電子部品）Ａ、Ｂ、Ｃを迂回してポインタ位置ｄ２に至る配線パターンＰＬ２０が表示画面上に形成され、更に、図１２（２）に示すように、ポインタ位置ｄ３がサンプリングされると、始点ｄ１から障害物Ａを迂回してポインタ位置ｄ３に至る配線パターンＰＬ２１が表示画面上に形成され、更に、図１２（３）に示すように、ポインタ位置ｄ４がサンプリングされると、始点ｄ１から障害物Ａを迂回してポインタ位置ｄ４に至る配線パターンＰＬ２２が表示画面上に連続的に表示される。
【００４３】
上記のように、マウス３２をドラッグしている間、始点（ｄ１）からポインタ位置に延びる配線パターンが、ポインタ位置の変化に応じて、表示ユニット４２の画面上にラバーバンディング表示される。そして、ユーザが最適であると判断した配線パターンが画面上に形成された時に、マウス３２のマウスボタンの押すのをやめる（ドラッグ操作をやめる）と、ＣＰＵ１０は、終点の指示操作が終了したと判定し（Ｓ４８）、処理を終了する。そして、その時点で、表示ユニット４２の画面上に形成された配線パターンがそのまま維持される。
【００４４】
なお、図５に示す手順に従った処理の各ステップと請求項記載の要件との関係は次のようになる。ステップＳ４３、Ｓ４４、Ｓ４５が終点サンプリング手段（終点サンプリングプログラム手段）に、ステップＳ４６が制御手段（プログラム手段）に、それぞれ対応し、処理Ｐ１０１が直線演算手段の機能を含む。
また更に、マウス３２の操作だけで画面に形成される配線パターンが延びてゆくようにすると、プリント基板設計者である、ユーザにとって便利である。このような機能を実現するため、例えば、図６に示すような手順のプログラムがシステムに提供される。このようなプログラム手順に従って、ＣＰＵ１０は次のように処理を実行する。
【００４５】
ＣＰＵ１０は、最初、始点入力の待ち状態にある（Ｓ５１）。ここで、ユーザがマウス３２によって表示画面上のマウスポインタを所望の位置に合わせてマウスボタンを素早く押して離す操作を連続して２度を押すと（ダブルクリック）、ＣＰＵ１０は、そのポインタ位置を始点（ｄ１）として内部のレジスタにセットする（Ｓ５２）。その後、ＣＰＵ１０は、終点入力の待ち状態となる（Ｓ５３）。ここで、ＣＰＵ１０がマウス３２の操作により終点の入力操作がなされたと判定すると、更に、その操作が最終操作であるか否かを判定する（Ｓ５４）。この例の場合、終点を入力する操作として、最終操作であるマウス３２のダブルクリック操作と、最終操作でないマウス３２の単なるクリック操作とが許容される。
【００４６】
ユーザが終点の位置にマウスポインタを合わせてマウス３２をダブルクリックすると、ＣＰＵ１０は、最終操作であると判定し（Ｓ５４）、内部のフラグをセットする（Ｓ５５）。そして、ＣＰＵ１０は、そのポインタ位置を終点として内部のレジスタにセットする（Ｓ５６）。
このように、始点および終点がセットされると、ＣＰＵ１０は、前述した、例えば、図２および図４（又は図３）に示す手順の処理Ｐ１０１を実行して、始点から終点に至る配線パターンを表示ユニット４２の画面上に形成する。そして、ＣＰＵ１０は、上述したフラグがセットされているかを判定する（Ｓ５７）。この場合、フラグがセットされているので、ＣＰＵ１０は、上記のように終点としてセットした位置を始点に変更して再度セットし（Ｓ５８）、終点入力の待ち状態となる（Ｓ５３）。
【００４７】
上記の処理に従えば、例えば、図１３（１）に示すように、始点（ｄ１）が入力された後に、ポインタ位置ｄ２でマウス３２のダブルクリック操作がなされると、始点（ｄ１）から障害物Ａを迂回してポインタ位置ｄ２に至る配線パターンＰＬ３０が表示ユニット４２の画面上に形成される。このとき、ポインタ位置ｄ２が新たな始点としてセットされる。
【００４８】
上記のように、ＣＰＵ１０が終点入力の待ち状態となるときに、ユーザがマウス３２を操作してマウスポインタを所望の位置に合わせ、マウス３２の単なるクリック操作を行なうと、ＣＰＵ１０は、最終操作でない終点の入力操作がなされたと判定する（Ｓ５３、Ｓ５４）。そして、その入力されたポインタ位置を終点として内部のレジスタにセットする。その後、ＣＰＵ１０は、上記のように新たに始点として設定された前回の終点から今回新たにセットされた終点に至る配線パターンを形成するための処理Ｐ１０１を実行する。そして、ＣＰＵ１０は、上述したフラグがセットされていないことを確認した後（Ｓ５７）、終点入力の待ち状態となる。
【００４９】
上記処理の結果、表示ユニット４２の画面上において、前回終点とされた位置から更に、今回終点として指定された位置まで配線パターンが延びる。例えば、図１３（１）に示すように、点ｄ１からｄ２に至る配線パターンが表示画面上に形成されている状態で、図１３（２）に示すように、ポインタ位置ｄ３でマウス３２のクリック操作がなされると、点ｄ２から更にポインタ位置ｄ３まで延びる配線パターンＰＬ３１が表示画面上に形成される。
【００５０】
以後、同様に、ユーザがマウス３２の操作にてマウスポインタの位置を移動し、クリック操作を行なう毎に、上記のように新たに設定された始点から終点に至る配線パターンが表示画面上から消去され、上記のように新たに設定された始点から今回クリック操作にて指定された位置に延びる新たな配線パターンが表示画面上に形成される。例えば、図１３（２）に示すように、点ｄ１、ｄ２を経由して点ｄ３に至る配線パターンＰＬ３０、ＰＬ３１が表示画面に形成されている状態で、図１３（３）に示すように、ポインタ位置ｄ４にてマウス３２のクリック操作が行なわれる。すると、点ｄ２から点ｄ３に至る配線パターンＰＬ３１が表示画面から消去されて、新たに点ｄ２から今回指定した点ｄ４に至る配線パターンＰＬ３２が表示画面上に形成される。
【００５１】
このようなシステムでは、ユーザは、例えば、マウス３２のクリック操作を繰り返すことによって種々の配線パターンを表示画面に切り換え形成し、最適と思われるパターンが形成されたときにその終点にマウスポインタを合わせてマウス３２をダブルクリックする。このような操作により、表示画面に形成された配線パターンが固定され、その配線パターンの終点が新たな始点として設定される。このような操作を繰り返す過程で、マウス３２をダブルクリックする毎に、表示ユニット４２の画面に形成される配線パターンは、延びてゆく。
【００５２】
なお、図６に示す手順に従って実行される処理の各ステップと請求項記載の要件との関係は次のようになる。ステップＳ５６が第一の制御手段（第一のプログラム手段）に、ステップＳ５８が第二の制御手段（第二のプログラム手段）にそれぞれ対応し、処理Ｐ１０１に直線演算手段の機能が含まれる。
上述した各実施の形態の例では、障害物を囲むオフセット外形線は、障害物の形状にかかわらず矩形を形成したが、本発明は、これに限定されることなく、任意の形状を形成することができる。例えば、オフセット外形線を障害物の外形線に忠実に添った形状にしてもよい（クリアランスが一定）。
【００５３】
また、障害物の種類に応じてことなるクリアランスのオフセット外形線を形成することができる。
【００５４】
【発明の効果】
以上説明してきたように、本発明によれば、始点から終点に至る直線を基本にして該始点から終点に至る経路を形成するので、該始点から終点に至る比較的短い経路を、比較的少ない処理量にて表示画面上に形成することができる。即ち、２点間を結ぶより短い経路が短時間で形成することができる。
【図面の簡単な説明】
【図１】本発明に係る経路形成システムのハードウエア構成の例を示すブロック図である。
【図２】本発明に係る経路形成システムでの処理例を示すフローチャートである。
【図３】本発明に係る経路形成システムでの処理例を示すフローチャートである。
【図４】本発明に係る経路形成システムでの処理例を示すフローチャートである。
【図５】本発明に係る経路形成システムでの処理例を示すフローチャートである。
【図６】本発明に係る経路形成システムでの処理例を示すフローチャートである。
【図７】基本的な経路形成の過程を示す図である。
【図８】短絡経路を形成する過程を示す図である。
【図９】表示画面に形成される配線パターンの例を示す図である。
【図１０】短絡経路が障害物と交差する場合の処理過程を示す図である。
【図１１】表示画面に形成される配線パターンの他の例を示す図である。
【図１２】マウスの操作に基づいた配線パターンの変化の状態の例を示す図である。
【図１３】マウスの操作に基づいた配線パターンの変化の状態の他の例を示す図である。
【符号の説明】
１０  ＣＰＵ
２０  メモリユニット
３０  入力制御ユニット
３１  キーボード
３２  マウス
４０  表示制御ユニット
４２  表示ユニット
５０  ＣＤ−ＲＯＭドライバ
６０  ハードディスクユニット
７０  バス
１００  ＣＤ−ＲＯＭ
【図１】
0004044642.tif 000002
【図２】
0004044642.tif 000003
【図３】
0004044642.tif 000004
【図４】
0004044642.tif 000005
【図５】
0004044642.tif 000006
【図６】
0004044642.tif 000007
【図７】
0004044642.tif 000008
【図８】
0004044642.tif 000009
【図９】
0004044642.tif 000010
【図１０】
0004044642.tif 000011
【図１１】
0004044642.tif 000012
【図１２】
0004044642.tif 000013
【図１３】
0004044642.tif 000014