JPH02211584A - 図形情報処理方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） 本発明は図形情報処理方式、特に処理すべき図形情報を
座標上の属性に従って能率よく記憶部に記憶すると共に
記憶されけた図形対象物に高速にアクセスしうるように
した図形情報処理方式に関するものである。

（従来の技術） 大規模集積回路などのレイアウト、あるいは地図などの
図形対象物（図形情報）などを記憶装置に一旦記憶した
り、記憶した図形情報にアクセスしながら表示装置上で
、レイアウト結果を対話的に修正したり参照したりする
場合、位置座標によって決定される記憶領域の図形を高
速でアクセス可能なデータ構造が要求される。

実際上、数百ないし数千、致方に達づる図形情報を処理
するための各種の理論的研究がなされ、その技術的な開
発も行なわれている。これらの技術的成果は計ｃ９機幾
何学（Ｃ０１ｐＵｔａｔｊＯｎａｌ　　Ｑ　ｅＯｍｅｔ
ｒｙ　）と称する分野を形成している。その−例として
例えば、Ｔ、　Ａｓａｎｏ　　Ｍ、　５ａｔｏ　　Ｔ、
　０ｔｓｕｋｉ　＠　「Ｃｏｍｐｕｔｉｔｉｏｎａｌ　
　Ｑｅｏｌｌｌｅｔｒｙ　　、Ａ　Ｉｇｏｒｔｈｍｓ　
Ｊなる論文がＮ　ｏｒｔｈ　−Ｈｏｆ　１ａｎｄ社１９
８６年発行のＬ　ａｙｏｕｔ　　Ｄ　ｅｓｉａｎ　　ａ
ｎｄ　　Ｖ　ｅｒｉｆｉｃａｔ；ｏｎ　　ｐｐ２９５−
３４７あるいはり、　Ｔ、　１−ｅｅ。

１”　、　　Ｐ　、　　Ｐ　ｒｅｐａｒａｔａ著”　Ｃ
ｏｍｐｕｔａｔｉｏｎａｌ　　Ｑ　ｅｏｒａｅｔｒｙ−
△　３　ｕｒｖｅｙ″なる論文がＩＥＥＥ　　Ｔｒａｎ
ｓａｃｔｉｏｎ　　ｏｎ　　Ｃｏｍｐｕｔｅｒ　、　Ｖ
ｏｌ　　Ｃ−３３，Ｎｏ、１２．１９８４に掲載されて
いる。

図形情報を処理するに際し、記憶装置内に記憶された図
形対象物（図形構成要素）としてのデータを検索する場
合に、図形対象物の位置座標が主なキー情報として用い
られるが、図形情報を何ら整理、編集せずに逐次的に記
憶装置に記憶したのでは、目的の図形をサーチするのに
時間が多大にかかってしまう。

このための解決法としＣ図形情報を分類し、その大小関
係に応じて座標値を決めたり、２分が１探索法（バイナ
リ−サーチ）を利用してサーチの高速化を図っている。

しかしこれらの手法においては複数の分類キー情報の指
定ができるが、目的の図形情報に迅速かつ正確にアクセ
スすることはできない。

例えば第８図は、座標値に分類する従来の処理方式を示
すが、所定の大きさに分割された領域５２内に実際の図
形情報が５３で示した形で存在している場合には、１点
５１の座標値（ｘｉ、　ｙｉ）が与えられただけでは正
確な図形の処理はできない。

また図形情報を所定の規則によって分類してしまうと、
データの追加が必要となる場合には、ファイル自体を再
構成しなければならず処理に時間がかかってしまうもの
であった。

上記の問題を改善する手法として２分木方式あるいは平
衡２分木方式が提案されており（浅井。

今井著［計算とアルゴリズム」オーム社１９８６年出版
）、その他、冒頭に示した論文においてセグメント・ツ
リー法、プライオリティ・サーチ・ツリー法またファラ
ドツリ−（Ｑｕａｄ　−Ｔｒｅｅ　）法およびｋ　−ｄ
　”／り一法がＪ　、　３　、　Ｒｏｓｅｎｂｅｒｇの
論文“Ｇ　ｃｏｇｒａｐｈｉｃａｌ　　Ｄ　ａｔａ　　
Ｓ　ｔｒｃｔｕｒｅｓ　　Ｃｏ１ｐａｒｅｄ　：Ａ　　
５ｔｕｄｙ　　ｏｆ　　（）ａｔａ　　３ｔｒｕｃｔｕ
ｒｅｓ　　３　ｕｐｐｏｒｔｉｎｇ　　Ｒｅｇｔｏｎ　
　ｃ）　ｕｅｒｉｅｓ”、ＩＥＥＥ　　Ｔｒａｎｓ、ｏ
ｎ　　ＣＡＤ　　Ｖｏｌ、　　ＣＡＤ−４゜Ｎｏ、１　
、　Ｊａｎ、　１９８５．　ＤＩ）、　５３〜６３など
に紹介されている。

第９図（ａ）、（ｂ）はプライオリティ・サーチ・ツリ
ー（優先捜索樹状）方式の概要を示す。

すなわち、第９図（ａ）ｘｙ座標上で斜線で表われた図
形をもつある領域の点の集合に対して最小のｙ座標をも
つ点を通る直線で平面を分割し、これを第９図（１））
のノードＰ＋　に対応させる。次に上記最小Ｖ座標より
上にある領域内の点数が等しくなるような縦半直線ｘ＝
５で分割し、ノードＰ２、Ｐ３を対応させながら順次分
割してゆぎ、各部分領域に点が存在しない処に達したら
操作を終える。

上記プライオリティ・サーチ・ツリ一方式は、確かにデ
ータ構造においてデータの追加および削除がダイナミッ
クに行なえる利点、座標上の点とノードの対応が１対１
の関係にある、空間内の座標値の情報が有効に使えるな
どの利点がある。

そして確かに２分木、平衡２分木方式における処理技術
の不足点、あるいはセグメント・ツリー方式における区
間データとツリー点の対応の複雑さ、アクセス効率の低
さなども改良されている。

またファラドツリー法においてもｂｉｓｅｃｔｏｒ　　
＋ｔｓｔなる技法を利用する事によって点などだけでな
く大きさを持つ図形情報を取扱えるように改良がなされ
、ｋ−ｄツリー法では複数の座標値を分類のキーとする
事によって大きさを持つ図形情報を効率良く取扱うため
の改良が行なわれた。

（発明が解決しようとする課題） しかしながら、プライオリティ・サーチ・ツリ一方式に
おいても図形情報が原則的に「点」あるいは「線Ｊの存
在として処理されているために取扱上の精度に問題があ
り、所定区間内に含まれる点をサーチするのでサーチに
おける片寄りの問題があり、その他、目的のデータへの
アクセス時間も十分迅速であるとは言えなかった。

すなわち、複数のノードに係わる大きな図形対象物の場
合は、「点」あるいは「線」に分割して記憶することと
なるため、分割された図形データをアクセスして元の図
形対象物を再現するために、処理上の効率が良くなかっ
た。

またクオツドツリー法はパイセクタ・リストの導入によ
ってアクセス時間を短くし、かつ大きさを持つ図形を取
扱う事を可能としたが２本の直線の交差と古う決った方
法で平面を四分割するため図形の平面上での分布の粗密
に対して木の生成をダイナミックに適応していく事がむ
ずかしい。

一方に−ｄツリー法では図形の座標を多重の分類キーに
対応させる事によって大きさを持つ図形を取扱う事を可
能とし、かつ高速のデータアクセスを可能としたが多重
の分類キーを利用しているため記憶装置上でのデータの
格納位置の近接関係とデータ相互間の近接関係の関連が
少なくなり、一般に利用される仮想記憶やデータベース
管理システムのバッファ管理のような二階層以上の記憶
ＷＡ層を持つ記憶装置ではデータアクセス速度が十分に
速くならない事があった。

本発明は上記の問題点を解決するもので、図形を構成す
る構成要素を正確かつ確実に分析して図形データとして
記憶装置に記憶し、このように記憶した図形データをと
り出して図形処理する際に目的の図形データに迅速にア
クセスし、正確に取り出すことができるようにした図形
情報処理方式を提供することを目的としている。

［発明の構成］ （課題を解決するための手段） 本発明による図形情報処理方式においては、２分木の各
ノードに対応して各バケット記憶領域を記憶装置内に設
けておいて処理すべき図形をＸ方向またはＹ方向に第１
の分割線で２分割し、該第１の分割線と当接する全ての
部分図形情報を第１ノード（根ノード）に属する図形デ
ータとして第１のバケット記憶領域に記憶し、次いで２
分割したいずれの一方の図形を順次細かく２分割してゆ
ぎ、各分割線に当接する図形情報は対応する各ノードに
所属するバケット記憶領域に記憶してゆき、当接する図
形情報がない場合には分割された特定図形領域内に含ま
れる図形情報の存在、不存在にしたがって下部の２分木
のノードに分岐しながら下って、所定の条件を満す最小
区分域に達した際に、上記最小区分域に完全に含まれる
図形情報を各終端バケット記憶領域に記憶し、片半分の
図形の処理が終了したら他の半分も同様に分割し、各分
割線に対応する各ノードに関連したバケット記憶領域お
よび終端バケット記憶領域に各図形情報を記憶してゆく
ようにしてデータベースを構築している。

（作用） このようにして構築されたデータベースから目的とする
図形情報を検索（サーチ）する場合には、サーチすべき
特定の記憶領域の座標を指定し、第１のノードに所属し
たバケット記憶領域の内容を調べ次に下部方向へと各２
分木を辿ってゆけば迅速に所望のバケットに到達するこ
とができる。

すなわち、本発明による図形情報処理方式においては、
各分ｖ１線に当接する図形情報は、小さなものから大き
なものまで対応する各ノードのバケット記憶領域にブロ
ック的に−かたまり（クラスタ）に記憶されておりさら
に他のノードの図形情報と重複しないので能率のよいサ
ーチが迅速に行なえる。

また本発明による図形処理方式においては、複数の分割
線によって定義される矩形領域の寸法により大きい図形
対象物はその分割線に対応する二分木のノードより下位
のノードに対応するバケツト内には存在しないと言う性
質を有するため図形対象物を大きさによって分類した事
になっている。

口のため図形対象物を大きざによって容易に検索できる
。

また実行する２分割は他の２分割とは独立に実施される
ため図形データの粗密に対応して最適な比率での２分割
が可能となり効率的記憶装置利用が可能となる。

（実施例） 第１図は本発明による図形を構成している各構成要素を
含む図形を分割線で分割する方法を示し、第２図は第１
図において分割された各領域から取り出された図形情報
が各ノードに関連した各バケット記憶領域（以下これを
簡単のために単にバケットと称する）に記憶してゆく２
分木構成を示丈。

第１図において、Ｃｈ　、　０２　、０３　、・・・・
・・０８は図形を構成する図形対象物（コンポーネント
）を示し、これらは、例えばブロック、線、島状区域１
点（×印）などであるとする。

まず、第１分割線■により図形を２分割する。

そして該第１分割線■を第２図の第１ノードに対応させ
、前記分割線上に当接して存在する図形対象物０５の図
形情報を、第１ノードに関連したバケット１にすべて格
納する。

次に上記のように２分割された上半分の図形を第２分割
線■で２分割する。この第２分割線■を第２図の第２ノ
ードに対応させる。この場合、第２分割線■上には０５
の一部が存在するが、この図形情報はすでに第１ノード
のバケット１に格納しであるので、バケット２には何も
格納されない。

さて、第２分割線■で２分された左半分は、第２図で第
２ノードを左側の２分木に下ってゆくことを意味し、右
半分は右側の２分木を下ってゆくことを示す。次いで第
６分割線■により上記左半分を更に２分割し、該第６分
割線■上に図形対象物が存在すれば、それらの図形情報
を総て第６ノードのバケット６に格納するが、この場合
には存在しないのでバケット６には何ら図形情報は格納
されない。

第６分割線■で分割された上半分の最小区分域Ｂ７には
図形対象物０１，０２があるので終端バケットＢ７にそ
れらの図形情報を格納する。一方、分割された下半分の
最小区分１４　Ｂ　５には、０５の一部が存在するが、
この図形情報はすでに第１ノードのバケット１にまとめ
て格納されているので終端バケットＢ５には何も格納さ
れない。

先の第２分割線■で分割された右半分に対しても第７分
割１線ので２分割して各図形情報を格納してゆけば第７
ノードのバケット７に０３の図形情報が格納され、最小
区分域Ｂ８に対応する終端バケット８Ｂには何も格納さ
れず、最小区分域Ｂ６に対応する終端バケットＢ８には
０４の図形情報が最終的に格納される。

第１分割線■で分割された下半分についても同様に第３
．第４．第５分割線（■、■、■）で分割しながら図形
情報を格納してゆくことによって第２図の第３ノード以
下の２分木データベースが構築されるので、全体として
第２図の２分木データベースを構築することができる。

この例では第２．第３の分割線（■、■）は同一のＸ座
標を共有しているが必ずしも同一である必要はなく図形
の粗密に合せて最適な位置で分割を行う事が可能である
。

次に第２図のように構築されたデータベースから所望の
図形情報を検索（サーチ）する方法を説明する。

図示しないグラフィック装置付属のマウスなどにより、
最小区分域Ｂｅ内の図形対象物０４に対応する図形情報
をサーチしたいとする。まず、Ｂｅ内の座標を指定し、
名分が１線の座標にしたがって第１ノード、第２ノード
、第７ノードについて２分木を下って（下方に探索して
）ゆけば終端バケットＢａ内の図形対象物０４に迅速に
アクセスできる。

次に、データベースを構築する処理手順の実例を示す。

第３図は本発明のデータ構造を生成する一実施例の処理
手順を示すフローチャートである。図形対象物の存在す
る領域を指定領域とする。またバケラトに対応する領域
について所定最小区分域の条件を定義する。例えば、１
パケツトの情報量と格納するメモリの記憶領域が対応す
るように設定する。これらの準備が終ると、ステップ２
０１において、入口からデータ構造を領域の分割と対応
させて生成する処理が始まる。ステップ２０２ではデー
タ構造生成の対象となる指定領域を「対象領域」とし、
処理の対象領域が宣言される。ステップ２０３では「対
象領域」が所定の条件を満足する大きさ以下になってい
るか調べ、もし小さければこれ以上の２分木の発生を行
わずステップ２０７で最終部分領域に対応する終端バケ
ットを作すノードにつなげて、ステップ２０日に進み、
手続の呼び出しを終了する。もしまだ領域が大きければ
２分水発生のための分割線の座標を決めるステップ２０
４に進む。ステップ２０４での座標値決定法はあらかじ
め決められた−様な大きさのバケットを生成するように
決定する。決定した座標に対してノードを作成し２分木
に接続するとともにバケットを接続する作業をステップ
２０５で行う。以下同様の処理を２０３の条件を満足す
るまで再帰的に続けて２分木を完成する。

第４図は生成されたデータ構成に対してデータを格納お
よび追加する手順を示している。ステップ３０１で開始
した処理はステップ３０２で図形対象物データの入力、
２分木の根へのポインタの移動などの初期化を行う。ス
テップ３０３では対象となっているノードの領域が更に
分割されているか調べもし分割されていなければステッ
プ３０４によって部分領域に対応する終端バケットに格
納してステップ３０５で終了する。もし対象となってい
るノードの領域が更に分割されているならばステップ３
０６で図形対象物と対象ノードの分割線との関係を調べ
、その結果に従ってステップ３０７．３０８．３０９の
処理を行う。ただしステップ３０８の場合は終了なので
ステップ３１０を行う。

第５図は指定された座標点に関係の有る可能性の有る図
形対象物を列挙する方法についてのフローチャートであ
る。この方法は基本的に２分探索を行い目標となる座標
点を含むバケットをとり出す。この２分探索において通
過したノードに関連付けられたバケットと座標点を含む
一分領域に対応する終端バケットに含まれる図形対象物
が目標座標点に関係のある可能性がある。ステップ４０
１で開始される処理はステップ４０２で初期化の手順を
終る。ステップ４０３の対象ノードが更に分割されるか
の検査を行い、もし分割されない場合はステップ４０４
において部分領域に対応するバケットを検索対象（関係
の可能性の有り）としてもどす。もし更に分割されてい
る場合はステップ４０５に進み分割線に対応するバケッ
トを探索対象（関係の可能性が有り）としてもどしステ
ップ４０６に行き次に探索すべきノードを決める。

もし目標点が分割点に対して左側または上側にある時は
ステップ４０７に進む。他の時はステップ４０８に進み
探索を進める。

本発明の他の実施例として第３図のステップにおいてツ
リーの左右の部分木において図形情報として格納される
べき図形対象物の数がバランスしていた方が探索の効率
が良くなる性質を利用して図形対象物の位置の分布を分
析して各部分領域に含まれる図形対象物の数がなるべく
等しくなるように分ＩＪ［ｌを引（事が可能となる。こ
のように決めた分割線ケ利用すれば高速アクセスが可能
となる。

またデータ構造へのデータ追加とデータ構造の生成を同
時にデータの性質によって適応的に行う効率の良い手法
も可能である。

さらに別の実施例としてはバケット内部でのデータ構造
に新しい工夫を加え高速化を図る事ができる様にしたも
のがある。すなわち、特に分割線に対応するバケットは
第１図の分割線■のように領域全体を横断する場合も有
るため多数の図形対象物がバケットに入る可能性がある
。このような場合は図形対象物の性質によっては効率の
よい分類配列が可能となる。図形対象物が点の場合は完
全に分類整列させておく事ができる。また線分の場合も
分割線に垂直の場合は分類整列が可能となる。

別な分類法としては第１０図に示したように着目した分
割線に対して図形対象物を射像し分割線と平行な線分を
分割線を分ける点との関係で本提案の手法を利用し二分
木上に分類する事もできる。

このような図形対象物固有の性質を活用して効率化を図
るためこれらの図形対象物の性質たとえば分割線に垂直
な線分、点などによって分類してその同一性質のグルー
プ内で分類してバケットに格納する方法がある。分割線
に接する図形の数が多く１つのバケットに入れるデータ
としては値が多重ぎる場合はさらに二分木等のデータ構
造とこれらの手法を組合せる事ができる。この実７１！
！沫も高速化に寄与する。

更に別の実施例としては三次元空間内において、平面を
分割線の代わりに利用する事によって空間の図形対象物
をバケットに分類していく方式が実現できる。

更に別の実施例においては部分領域にまたがる図形対象
物のある種の物は考えられている処理の内容によっては
分割線との交点で切断して部分領域のバケットに格納す
る事が可能である。この手法によれば分υ１線に対応す
るバケットに対応する図形対象物があまりに増加する事
を妨げる。

別の実施例としては本データ構造をネットワーク型のデ
ータベースで作成した場合、第６図（ａ　）に示すよう
に階層展開を２セツト７１で行ないレコード７２に格納
し、第６図（ｂ　）では自己セット７３で表現し、間接
的にツリーの階層構造を表現する事ができる。

次に、本発明の具体的応用例として、ＶＬＳＩ設計用グ
ラフィックエディタについて説明する。

このＶＬＳ　ｌｆｆ１計用グラフイツクエデイタにおい
ては、グラフィックエディタのデータベースないしはデ
ータ構造内に、論理回路の接続を表現するセルの接続関
係データとその接続関係と対応したレイアウト図形を表
現した図形データを格納するものである。この場合、図
形データとしては配線を表示する線分、配線線分間の接
続を表すＶＩＡ１複数のトランジスタから構成されるあ
らかじめ設計されたマクロセル、その他の多角形などが
ある。接続関係の表現と図形データは第７図に示したよ
うにデータベース上に相互関係を表現していなければな
らない。第７図は接続関係と図形データの対応が破線で
表現されている。

一般にグラフィックエディタとして要求される特性はグ
ラフィックデイスプレィなどの図形表示装置に対して指
定された領域の図形データをできる限り高速に供給Ｊる
事である。また図形表示装置に表示された図形をマウス
等の座標指示装置で指定された座標値に関係する図形を
できる限り高速に識別確定１′る事である。更に図形デ
ータと接続データに矛盾が４工いか、つまり図形上での
誤った接続がないか、図形データがＬＳＩレイアウトと
しての幾何学的設計基準を満足しているなどを高速に検
査する事である。

上記要求を満足する上で障害となる点、つまり解決すべ
き問題点は領域の指定、座標的の指定などに対して高速
に関連するデータを検索する事である。このためには図
形データ情報の高速アクセス可能な最適な格納が要求さ
れる。そこで、本発明で提案したデータ構造およびアク
セス手法によれば図形データである配線線分、ＶＩＡ、
マクロセルなどはデータ構造ないしは同様の構造を表現
したデータベースに図形情報（図形対象）として分類さ
れて格納される。このデータに対して指定領域のデータ
を高速アクセスするには、前述した如くに木を値から指
定領域を示す座標値と木の各ノードの分υ１線のＸ！標
、ｙ座標との大小比較を行い領域内を検索するようにす
れば高速アクセスが可能となる。指定された座標点に関
連する図形を検索する場合も同様の木の検索制御を行え
ば可能となる。更に接続の検査、幾何学的設計基準の検
査においても座標的に近傍の図形データを高速にアクセ
スする事が重要であり同様のデータ構造に対するアクセ
ス手法が効率化につながるものである。

［発明の効果］ 以上、本発明の実施例について述べてきたが、本発明に
よる図形情報処理方式においては、図形を分割してゆく
際に、各分割線上およびその近傍にある図形対象物はま
とめで当該分割線に対応するノードのバケットに格納さ
れるようにしたので、先行する分割線と後続の分割線上
、あるいは分割された領域にまたがる同一の図形対象物
が、当該各ノードのバケットにそれぞれ分散格納される
ことはなく、したがって所望の図形情報へのアクセスを
迅速かつ能率よく行なうことができる。

【図面の簡単な説明】

第１図は本発明による図形分割方式を示す図、第２図は
第１図の分割方式に対応して図形情報を記憶し検索しう
る２分木データベース構成図、第３図は本発明によるデ
ータベースを構築する処理のフローチャートを示す図、
第４図は２分木データベース構成に図形情報に格納する
手順を示したフローチャートを示づ図、第５図は指定さ
れた座標に関係する可能性のある図形情報を取り出し処
理を行なうフローチャートを示す図、第６図は２分水デ
ータ構造をネットワーク型の階層表現とした場合を示す
図、第７図は、本発明の具体的応用例を示す図、第８図
、第９図は従来技術による図形情報処理方式を示す図、
第１０図は分割線に関連する図形を二分木データへ格納
する方式を示す図である。 １・・・第１ノード（根ノード）に所属するバケット、 ２．３．４．５．６・・・第２．第３．第４．第５゜第
６．第７ノードにそれぞれ所属するバケット、Ｂ＋乃至
Ｂ８・・・分割された各最小区分域に存在する図形情報
を格納する終端バケット。

Claims (4)

【特許請求の範囲】
1. （１）処理すべき図形を第１の分割線で２分割し、該分
   割線上に存在する部分を有する図形対象物の図形情報を
   前記第１の分割線に対応する第１のバケットにまとめて
   格納し、次いで前記２分割された図形領域を更に第２、
   第３の分割線で分割し各分割線上に存在する部分を有す
   る図形対象物の図形情報を各分割線に対応する第２、第
   ３のバケットに格納し、所定の最小区分域に達した際に
   、前記最小区分域に完全に含まれる図形対象物を前記最
   小区分域に関連して設けられた各終端バケットに格納し
   て図形情報のデータベースを構築することを特徴とする
   図形情報処理方式。
2. （２）前記各分割線で２分割された両半分の領域の位置
   関係は２分木の各枝路に対応することを特徴とする請求
   項１に記載の図形情報処理方式。
3. （３）先行する所定の分割線および後続の所定の分割線
   上にまたがる図形対象物は、前記先行する分割線に対応
   する所定のバケットにまとめて格納され、前記図形対象
   物の分散格納はしないことを特徴とする請求項１に記載
   の図形情報処理方式。
4. （４）前記各分割線に対応するバケットおよび終端バケ
   ットに格納された所望の図形対象物を検索する際には、
   分割された所定の最小区分域の座標を指定し、上位のノ
   ードから下位のノードへと２分木の枝路を最短距離で下
   つて所定のバケット内の図形情報を検索してゆくことを
   特徴とする請求項１に記載の図形情報処理方式。