(57)【要約】【課題】所定の条件を満たすまで、図形の頂点数を削減するように対象図形を変換することである。【解決手段】対象図形に対し外接する凸多角形であるフレームを生成し、フレームと図形の差分図形を算出し、差分図形を分割する。更に、この分割図形の頂点数が所定の条件を満たすまで、上記プロセスを繰り返す方法、及びこのための装置。【選択図】図７
2007299107.tif 000002
【特許請求の範囲】
【請求項１】
図形データ変換方法において、
変換プロセスが、
―取込まれた対象図形について、当該図形に外接する凸多角形のフレームを生成するステップと、
―前記フレームと前記図形との差分を計算し、差分図形を生成するステップと、
―当該差分図形を所定の規則に基づいて分割図形に分割するステップと、
―前記分割図形の頂点数をカウントするステップと、
―前記分割図形の頂点数が所定の条件を満たすかを判別するステップと、
からなるプロセスであって、前記プロセスにおける前記分割図形の頂点の数が所定の条件を満たすまで、当該プロセスを繰り返すことにより図形を変換する図形データ変換方法。
【請求項２】
前記フレームが凸包により生成されることを特徴とする請求項１記載の図形データ変換方法。
【請求項３】
前記フレームを生成するステップにおいて、前記フレームが長方形または三角形を含む、一般凸多角形であることを特徴とする請求項１記載の図形データ変換方法。
【請求項４】
前記フレームを生成するステップにはフレームの各頂点の座標を記憶手段に記憶するステップが含まれることを特徴とする請求項１記載図形データ変換方法。
【請求項５】
請求項４に基づいて変換された図形データを、前記記憶されたフレームの頂点座標を使い、前記変換と逆の変換を実行して元の図形データを復元する図形データ復元方法。
【請求項６】
図形データ変換装置が、
―対象図形について、当該図形に外接する凸多角形のフレームを生成するフレーム生成手段と、
―前記フレームの頂点の座標を記憶する記憶手段と
―前記フレームと前記図形との差分を計算し、差分図形を求める差分図形生成手段と、
―当該差分図形を所定の規則に基づいて分割する分割手段と、
―前記分割された図形の頂点数をカウントするカウント手段と
―前記図形の頂点数が所定の条件を満たすかを判別する判別手段と
を有する図形データ変換装置。
【請求項７】
請求項６において変換された図形データを前記記憶されたフレームの頂点座標を用いて、元の図形データを復元する図形データ復元装置。
【請求項８】
請求項１記載の図形データ変換方法を図形データの圧縮に使用する図形データ圧縮方法。
【請求項９】
請求項５の図形データ復元方法を図形データの伸張として使用する図形データ伸張方法。
【請求項１０】
請求項６記載の図形データ変換装置を図形データの圧縮に使う図形データ圧縮装置。
【請求項１１】
請求項７の図形データ復元装置を図形データの伸張に使用する図形データ伸張装置。
【請求項１２】
コンピュータに、取込まれた対象図形について、当該図形に外接する凸多角形のフレームを生成するステップと、
―前記フレームと前記図形との差分を計算し、差分図形を生成するステップと、
―当該差分図形を所定の規則に基づいて分割図形に分割するステップと、
―前記分割図形の頂点数をカウントするステップと、
―前記分割図形の頂点数が所定の条件を満たすかを判別するステップと、
からなるプロセスであって、
前記プロセスにおける前記分割図形の頂点の数が所定の条件を満たすまで、当該プロセスを繰り返すことにより図形の変換を実行させるためのプログラム。
【請求項１３】
前記フレームを生成するステップにはフレームの各頂点の座標を記憶手段に記憶するステップが含まれることを特徴とする請求項１２記載の図形データ変換方法。
【請求項１４】
請求項１３のプログラムを使って変換された図形データを、前記記憶されたフレームの頂点座標を使い、前記変換と逆の変換を実行して元の図形データを復元させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、必要な図形を表現するための図形データの変換方法、及び装置に関する。特に、プリント配線回路を設計するために使われる図形データ変換方法および装置に関する。
【背景技術】
【０００２】
近年、図形データ処理の分野においては技術が目覚しく進歩しており、プロセッサの高速化・高機能化により図形データ処理技術も飛躍的な進歩を遂げている。
【０００３】
この図形データ処理の技術の進歩は、他の技術にも大きな影響を与えている。例えば、プリント基板製造の分野ではＣＡＤで作成したデータに基づいてプリント基板を作成している。ＣＡＤでは、ガーバー(Gerber)フォーマットのデータ（非特許文献１）を含め図形データを表現するためのデータ・フォーマットが複数存在する。プリント配線のためのアプリケーション・ソフトはこうしたデータ・フォーマットに準拠しながら個別に作成されている。
【０００４】
ここで、ガーバーフォーマットはフォトプロッタメーカのガーバー社（Gerber Scientific Instrument Company）が考案したＣＡＤ用データ形式であるが、同フォーマットにおいてはプリント基板の作成を自動化するための情報（穴の位置、大きさ、配線の太さ等）を数値化して表現されているので、プリント配線設計における１つの標準的なフォーマットとなっている。又、別の代表的なフォーマットとしてCadence社のＧＤＳフォーマット(非特許文献２、非特許文献３)があり、このフォーマットもプリント配線技術分野で多用されている。ユーザはこれらデータ・フォーマットの何れかを選択して図形データを作成している。
【０００５】
これらフォーマットに基づいてアプリケーションソフトを作成する際に留意すべきことは、利用上の制約である。例えば、図形の頂点数について制約があることである。前記ガーバーフォーマットでは図形の頂点数を無制限に使えるが、ＧＤＳフォーマットでは図形の頂点数には制限があり、例えば８０００個以下にしなければならないという制約がある。従って、ＧＤＳフォーマットの図形データ作成においては、図形が前記制限を越えている場合は、頂点数を所定数以下にしなければ図形データを作成することは出来ない。
【０００６】
頂点数を所定数以下にするための方法として図形を分割して表現するという方法が当業者にとって技術常識であった。図形を分割するに際し、設計者は図形の辺の自己交差により図形の形状が変わらないように各頂点の位置関係をチェックしながら分割線を決めていた。
【０００７】
以下、この点について具体的に説明する。
図３はアプリケーションソフトで処理を行う対象の図形Ａである。この図形はＧＤＳフォーマットで表現できる数ｎ以上の頂点数ｍ（ｍ≫ｎ）をもつ多角形であるとする。この多角形をＧＤＳフォーマットで表現できるように分割するための方法として、２つの方法が知られている。
【０００８】
図９は第１の方法を示す図である。この方法は開始点から頂点の最大値ｎに向かって分割線を引くというものである。この方法では分割処理時間は短縮されるが図形と分割線が交差する（自己交差という）可能性があり望ましくない。図１０は第２の方法を示す図である。この方法は、開始点から各頂点に順番に自己交差しないか否か確認しながら分割線を引くものである。この方法では自己交差しないが、分割処理時間が長くなるという問題がある。また、一般的に対象図形の頂点数が増加するに比例して処理時間が長くなるという問題がある。
【０００９】
【非特許文献１】http://www.interq.or.jp/japan/se-inoue/eagle44.htm
【非特許文献２】EBハンドリングデータフォーマット GDSII. NEO Version1.2、(株)半導体先端テクノロジーズ
【非特許文献３】http://www.filcon.co.jp/mcr/pm_s.html
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上記の通り、従来の方法によると対象図形の頂点数の増加に比例して処理時間が長くなるという問題があったが、本発明はこの問題点を解決するためになされたもので、その目的は従来の方法とは全く異なる、新規なやり方で簡単に効果的に図形データを変換する方法と装置を提供することである。
【課題を解決するための手段】
【００１１】
本発明の第１の態様は、図形データ変換方法において、変換プロセスが、取込まれた対象図形について、当該図形に外接する凸多角形のフレームを生成するステップと、前記フレームと前記図形との差分を計算し、差分図形を生成するステップと、当該差分図形を所定の規則に基づいて分割図形に分割するステップと、前記分割図形の頂点数をカウントするステップと、前記分割図形の頂点数が所定の条件を満たすかを判別するステップとからなるプロセスであって、前記プロセスにおける前記分割図形の頂点の数が所定の条件になるまで、当該プロセスを繰り返すことにより図形を変換する図形データ変換方法、及び、前記変換された図形データを前記変換と逆の変換を実行して元の図形データを復元する図形データ復元方法である。
【００１２】
第３の態様は、図形データ変換装置が、対象図形について、当該図形に外接する凸多角形のフレームを生成するフレーム生成手段と、前記フレームの頂点の座標を記憶する記憶手段と、前記フレームと前記図形との差分を計算し、差分図形を求める差分図形生成手段と、当該差分図形を所定の規則に基づいて分割する分割手段と、前記分割された図形の頂点数をカウントするカウント手段と、前記分割図形の頂点数が所定の条件を満たすかを判別する判別手段と、を有する図形データ変換装置、及び、前記変換された図形データから元の図形データを復元する図形データ復元装置である。
【００１３】
第４の態様は、前記図形データ変換方法を図形データの圧縮に使用する図形データ圧縮方法及び装置、並びに前記圧縮データを伸張する伸張方法及び装置である。
【００１４】
第５の態様は、前記第１の態様の変換方法を実行させるため、及び、変換された図形データを復元させるためのプログラムである。
【発明の効果】
【００１５】
本発明によれば、どのような図形、例えば、不規則な形状の図形、多数の頂点を持つ多角形を凸多角形になるまで分割できる。又、対象図形の外側に分割する線を決定するので、確実に、安全に分割することができ、従来技術において問題であった自己交差の問題を解決することができる。また、図形を囲む外枠（フレームという）の形状を長方形とすることで、頂点数が多くなってもフレームを簡単に見つけることができ、処理時間を短縮することができる。
【００１６】
また、本発明によれば、数回の変換により図形はシンプルな図形に変換されるので、本発明は図形データを圧縮するのに極めて有効な方法・装置である。
【発明を実施するための最良の形態】
【００１７】
本発明の実施例
以下、本発明の一実施例について図面を参照しながら説明する。
図１は本発明の図形変換装置の構成を示すブロック図である。図中、１は図形を取り込む手段、例えば、スキャナー、ＣＡＤ等の他の装置で生成され転送される図形データを取り込む手段である。２は本発明の図形変換装置であり、コンピュータにより構成され、３のメモリと共に、取り込まれた図形について図形データの変換を実行する。
【００１８】
本図形変換装置は、対象図形について、当該図形に外接する凸多角形のフレームを生成するフレーム生成手段と、前記フレームの頂点の座標を記憶する記憶手段と、前記フレームと前記図形との差分を計算し、差分図形を求める差分図形生成手段と、当該差分図形を所定の規則に基づいて分割する分割手段と、前記分割された図形の頂点数をカウントするカウント手段とを有する。
その変換については後記の変換方法で詳述する。４は図形変換装置２で生成された変換データを別の装置に出力する出力手段である。
【００１９】
以下本発明について詳述するが、その前に理解のために本発明の概要を説明する。
本発明の概要
本発明は、変換の対象となる図形（以下単に図形とも言う）Ａを取囲み、外接する凸形状の多角形（以下「フレーム」又は「凸包」という）Ｆを生成し、このフレームを使って、同フレームＦと前記図形Ａの差分図形Ｂ（＝Ｆ−Ａ）を算出し、この差分図形を分割するという方法である。
【００２０】
同差分図形Ｂを複数の図形Ｂ１〜Ｂｎに分割し、各々の分割された図形Ｂｉに対し図形ＢｉのフレームＦ（Ｂｉ）を生成し、同フレームＦ〔Ｂｉ〕と前記図形Ｂｉの差分図形Ｃｉ（＝Ｆ〔Ｂｉ〕−Ｂｉ）を算出するプロセスを実行する。このプロセスは頂点数が所定の条件を満たすまで繰り返される。変換対象図形Ａはこのプロセスを経るに従い、より小さな図形に変換される。これが対象図形Ａを変換する本発明の変換方法である。
【００２１】
本発明では、フレームとして凸多角形を使う。これは、図形の形状に左右されることなく分割することができるからである。フレームは単純な形状が好ましく、３角形、長方形が望ましい。本発明による数回のプロセス後に作成される図形の頂点数が大幅に変換されることは以下の説明から理解される。
【００２２】
復元方法について
こうして得られた変換後データは、変換と逆の手順により、元の図形データに復元される。以下に復元について述べる。
各ステップでフレームを生成すると、フレームの頂点の座標が記憶される。即ち、フレームの頂点の座標が記憶手段に記憶される。最終段階の変換された図形データは、その直前のフレームとの差分を求めることにより、その直前の図形に復元される。更に、上記の変換プロセスと逆のプロセスを順次実行することにより、元の図形が復元される。
【００２３】
次に図面に基づいて本発明の変換方法の実施例を説明する。
図２は本発明の図形変換のフローチャートである、図３は本発明の方法により変換する対象の図形Ａ（斜線で示す図形）であり、その形状は略Ｓ字状である。なお発明の理解のために単純な図形を選択したが、現実の設計における図形は複雑であることを付言する。
【００２４】
初めに変換する対象となる図形Ａ(図３に示す)をスキャナー等を用いて図形データを取り込む。この取り込みは前記の通り、ＣＡＤ等の装置で生成され転送される図形データを取り込む手段であってもよい。（ステップＳ１）
【００２５】
次に、前記図形Ａに対し外接する凸形状の多角形であるフレームを生成する（ステップＳ２）。フレームとして長方形、三角形を使うことが好ましい。しかし、これに限定されるものではない。図形Ａに対し長方形、三角形形状のフレームを生成する方法は、計算幾何学で凸包の作成法として周知であるから、説明を省略する（「計算幾何学入門」森北出版、譚、平田共著、２００１年１０月「第３章  凸包の計算」）。図４は上記の方法で生成されたフレームＦ（破線で示した）を表す。この時、フレームの各頂点の座標はメモリ３に記憶される。
【００２６】
（差分図形生成）
フレーム図形Ｆを生成した後、フレーム図形Ｆから対象図形Ａを引算して図形Ｂ（＝Ｆ−Ａ）が生成される（ステップＳ３）。図５は図４の図形の色を反転したものであり、斜線部分が差分図形Ｂである。
【００２７】
（図形の分割）
図５の差分図形Ｂの生成後に、前記差分図形Ｂから複数の多角形を分割する（ステップＳ４）。分割は次のようにして実行される。即ち、図５において、前記フレームＦの辺に沿ってフレームＦと前記図形Ａとの図形分割可能な接点（ｔ１〜ｔ５）を見つけ、隣接する２つの接点の組、即ち、ｔ１とｔ２の組、ｔ２とｔ３の組、ｔ３とｔ４の組、ｔ４とｔ５の組、ｔ５とｔ１の組で図形を分割する。図６は図５の差分図形Ｂを分割した図形Ｂ１〜Ｂ５を示す（第１回目の分割）。
【００２８】
この時の図６で示す分割図形Ｂ１ないしＢ５は、元の図形から分割されたものであるから、それぞれの図形の頂点数は元の図形の頂点数より小さくなっていることは明らかである。
【００２９】
前記分割図形Ｂ１ないしＢ５に対し、各図形の頂点数を検出する(ステップＳ５)。その数が所定数ｎ以下であると処理を終了させてよい（ＥＮＤ）。しかし前記頂点数が所定数より大きい場合、当該プロセスが繰り返される(ステップＳ２に戻る)。なお、この実施例では処理の終了条件を所定数ｎ以下としたが、これは一例であって、他の適切な条件で終了することを排除するものではない。
【００３０】
最初の分割で頂点数が所定数ｎ以下にならない場合、再びフレームを生成することとなる。分割図形Ｂ１〜Ｂ５の各々に対して、前記の凸包形成法によりフレーム生成を行う(ステップＳ２)。フレームが生成されると、フレームの各頂点の座標が記憶手段に記憶される。この段階で種々の図形が生成されるので具体的なフレーム生成例を説明する。
【００３１】
図７は前記分割図形Ｂ１〜Ｂ５に対するフレームを表す。分割図形Ｂ１〜Ｂ５を取囲む破線Ｆ１〜Ｆ５がフレームである。一般に、変換効率と処理のしやすさから、フレームとして長方形、三角形を使うことが好ましい。以下、これら分割図形Ｂ１〜Ｂ５のそれぞれのフレームの生成の仕方について説明する。
【００３２】
図７の左上に分割図形Ｂ１を示す。周知の凸包の形成方法により、図形Ｂ１を含む三角形がフレームとなる。破線Ｆ１がフレームである。
【００３３】
次に、図７の左中段に分割図形Ｂ２を示す。
同様に、分割図形Ｂ２に対し、周知の凸包の作成法により、フレームとして、例えば長方形Ｆ２を形成することができる。破線Ｆ２がフレームである。
【００３４】
以下同様に、図７の左下段に分割図形Ｂ３を示す。
分割図形Ｂ３に対し、周知の凸包の作成法により、フレームとして、例えば長方形Ｆ３を形成することができる。
【００３５】
図７の右下段に分割図形Ｂ４を示す。
分割図形Ｂ４は三角形そのものであるから、周知の凸包の作成法により、フレームとして前記分割図形Ｂ４と同一の三角形が生成される。このため差分図形は生成されず、更に図形を分割することはできない。この場合、変換プロセスはこの段階で終了する。
【００３６】
図７の右上段に分割図形Ｂ５を示す。
分割図形Ｂ５に対し、周知の凸包の作成法により、フレームとして、例えば長方形Ｆ５を生成することができる。
【００３７】
以上第１分割について説明した。
本発明の理解を深めるために、更に上記プロセスを繰り返し、分割図形がどのように変換されるかを説明する。
【００３８】
図８は前記分割図形群Ｂ（Ｂ１〜Ｂ５）が複数の分割プロセスでどのような図形データに変化していくかを示す図である。図８の左端の図形が前記分割図形群Ｂである。
【００３９】
左から２番目の図形群は第２分割により生成される分割図形群Ｃであり、破線は分割図形に対し生成されたフレームである。左から３番目の図形は第３分割により生成される分割図形群Ｄであり、破線は分割図形に対し生成されたフレームである。右端の図形は第４分割により生成される分割図形群Ｅである。
【００４０】
分割図形群Ｂから差分図形群Ｃ(Ｃ１，Ｃ２，Ｃ３、Ｃ５)を生成するステップについては、既に説明したステップと同様である。図８は、Ｂ１からＣ１が生成され、Ｂ２からはＣ２が生成される。更にＢ３からはＣ３が生成され、Ｂ５からはＣ５が生成されることを示す。
【００４１】
（第２分割）
次に上記の通り生成された差分図形群Ｃを分割する分割処理について述べる。
差分図形Ｃ１の分割については、図形分割可能な接点が存在しないので分割はない。
【００４２】
差分図形Ｃ２については、図形分割可能な接点ｔ１１が存在し、Ｃ２１とＣ２２に分割される。同様に、差分図形Ｃ３についても図形分割可能な接点ｔ１２が存在し、Ｃ３１とＣ３２に分割され、差分図形Ｃ５についても図形分割可能な接点ｔ１３が存在し、Ｃ５１とＣ５２に分割される。
【００４３】
次に、前記差分図形Ｃ１及び分割図形Ｃ２１，Ｃ２２、Ｃ３１、Ｃ３２、Ｃ５１、Ｃ５２に対しフレームを生成する。前記プロセスと同様に凸包生成方法によりフレームを生成する。特に図形Ｃ２１、Ｃ２２のように図形を構成する２辺が直線の場合は、フレームとして長方形を用いると処理効率が落ちるので、台形又は凸４角形Ｆ２１，Ｆ２２となる。
【００４４】
以上のプロセスにおいて、図形Ｃ３２がこれ以上分割できない。
分割図形群Ｃ（Ｃ１、Ｃ２１，Ｃ２２、Ｃ３１、Ｃ５１、Ｃ５２）とそれに対応するフレームから第３回目の差分図形群Ｄ（Ｄ１、Ｄ２、Ｄ３、Ｄ５）が生成される。
【００４５】
（第３分割）
上記の通り生成された差分図形群Ｄに対して、上記と同様に分割処理が行われる。この段階では図形が極めて複雑な図形になるので詳細な説明を省略するが、プロセスは上記の説明の通りである。
【００４６】
前記分割図形群Ｄ１、Ｄ２、Ｄ３、Ｄ５とそれに対応するフレームから第４回目の差分図形群Ｅ（Ｅ１、Ｅ２、Ｅ３、Ｅ５）が生成される。これらプロセスは上記のプロセスと同様であるから説明を省略する。
【００４７】
以下同様に処理は、前記のように差分図形の頂点の数が所定数以下になるまで、又は所定の条件になるまで、当該プロセスが繰り返される。これら差分図形Ｅ１、Ｅ２、Ｅ３、Ｅ５は、元の図形Ａに比してその頂点数が削減されていることが明らかである。
【００４８】
本発明の他の技術分野への応用
本発明の構成、方法は、図形データ圧縮の分野に応用できる。図８において処理が進むにつれて上記説明したように図形が縮減され、従って図形データとしても大幅に削減されていることが分かる。圧縮された図形データは、前記メモリに記憶された頂点座標を用いながら、圧縮の手順とは逆の手順により元の図形に伸張されることも明らかである。
【産業上の利用可能性】
【００４９】
上記の通り、プリント配線設計においてＧＤＳフォーマットのソフトを用いる場合に、本発明の方法は極めて有効である。加えて、本発明の方法によると図形データが削減されるのであるから、図形データ圧縮方法として用いることができる。
【図面の簡単な説明】
【００５０】
【図１】図１は、本発明の構成を示すブロック図である。
【図２】図２は、本発明の手順を示すフローチャートである。
【図３】図３は、変換の対象となる図形である。
【図４】図４は、変換対象の図形に対し生成されたフレームを示す図である。
【図５】図５は、図２の図形を反転表示した図である。
【図６】図６は、図３の黒色図形を分割した図形である。
【図７】図７は、分割図形に対し生成されたフレームを示す図である。
【図８】図８は、第１分割図形ないし第４分割図形を示す図である。
【図９】図９は、従来の第１の分割手法を示す図である。
【図１０】図10は、従来の第２の分割手法を示す図である。
【図１】
2007299107.tif 000003
【図２】
2007299107.tif 000004
【図３】
2007299107.tif 000005
【図４】
2007299107.tif 000006
【図５】
2007299107.tif 000007
【図６】
2007299107.tif 000008
【図７】
2007299107.tif 000009
【図８】
2007299107.tif 000010
【図９】
2007299107.tif 000011
【図１０】
2007299107.tif 000012