(57)【要約】【課題】  図形データの管理を簡便に行え、メモリの使用効率、検索効率の向上、検索の高速化を図る。【解決手段】  図形の存在領域をＸ，Ｙ方向にそれぞれ分割してセルに区分し、セル単位で存在する図形データの分類情報を含む図形情報と、図形データファイルの図形データ格納場所を示す格納情報と、同一セル内に複数の図形が存在する場合の他の制御コードとの間の継続情報とを管理データとして関連データ結合テーブル４に設定し、空間分布テーブル３にセル単位で関連データ結合テーブル４の管理データのアドレスの１つに対してポインタを設定して、セル単位で空間分布テーブル３を介して関連データ結合テーブル４の各管理データと図形データファイル１に格納された１乃至複数の構成点列を含む空間座標を有する各図形データとの関係付けを行い管理する。【選択図】      図１
2006011727.tif 000002
【特許請求の範囲】
【請求項１】
１乃至複数の構成点列を含む空間座標を有する図形データが格納された図形データファイルを管理する図形データ管理方法であって、
図形の存在領域をＸ，Ｙ方向にそれぞれ分割してセルに区分し、
前記セル単位で存在する図形データの分類情報を含む図形情報と、前記図形データファイルの図形データ格納場所を示す格納情報と、同一セル内に複数の図形が存在する場合の他の制御コードとの間の継続情報とを管理データとして関連データ結合テーブルに設定し、
空間分布テーブルに前記セル単位で前記関連データ結合テーブルの管理データのアドレスの１つに対してポインタを設定して、
前記セル単位で前記空間分布テーブルを介して前記関連データ結合テーブルの各管理データと前記図形データファイルに格納された各図形データとの関係付けを行い管理することを特徴とする図形データ管理方法。
【請求項２】
１乃至複数の構成点列を含む空間座標を有する図形データが格納された図形データファイルを管理する図形データ管理装置であって、
図形の存在領域をＸ，Ｙ方向にそれぞれ分割してセルに区分し、前記セル単位で存在する図形データの分類情報を含む図形情報と、前記図形データファイルの図形データ格納場所を示す格納情報と、同一セル内に複数の図形が存在する場合の他の制御コードとの間の継続情報とを管理データとして設定する関連データ結合テーブルと、
前記セル単位で前記関連データ結合テーブルの管理データのアドレスの１つに対してポインタを設定する空間分布テーブルと
を備え、前記セル単位で前記空間分布テーブルを介して前記関連データ結合テーブルの各管理データと前記図形データファイルに格納された各図形データとの関係付けを行い管理することを特徴とする図形データ管理装置。
【請求項３】
前記図形情報として、少なくとも体・面・線・点の分類情報、ノード／線上・面上・体上、端点／中間ノード、図郭線上／図郭内の識別情報、種別情報を有することを特徴とする請求項１又は２のいずれかに記載の図形データ管理方法又は図形データ管理装置。
【請求項４】
前記図形情報として、上下左右斜め方向の８方向の隣接セルに対する被参照情報を有することを特徴とする請求項３に記載の図形データ管理方法又は図形データ管理装置。
【請求項５】
前記格納情報として、前記図形データファイルにおける図形データの格納場所又は前記格納場所を有する管理データへのオフセットを有することを特徴とする請求項１乃至４のいずれかに記載の図形データ管理方法又は図形データ管理装置。
【請求項６】
図形データを複数のセルに対応して管理する複数の管理データにおいて、１つの管理データに対してのみ前記格納場所が設定され、他の管理データに対してはオフセットが設定されることを特徴とする請求項５に記載の図形データ管理方法又は図形データ管理装置。
【請求項７】
前記格納情報として、前記複数の構成点列に対応する番号を有することを特徴とする請求項１乃至６のいずれかに記載の図形データ管理方法又は図形データ管理装置。
【請求項８】
前記継続情報として、同一ノードに集まる線についての関係付け情報を有することを特徴とする請求項１乃至７のいずれかに記載の図形データ管理方法又は図形データ管理装置。
【請求項９】
前記空間分布テーブルとして、前記ポインタを設定する面ポインターテーブルと、上下左右斜め方向の８方向の隣接セルに対する参照情報を設定する参照フラグテーブルとを有することを特徴とする請求項１乃至８のいずれかに記載の図形データ管理方法又は図形データ管理装置。
【請求項１０】
前記面ポインターテーブルは、図形データが存在するセルのうち上下左右に２つおきのセルに設定し、前記参照フラグテーブルは、前記面ポインターテーブルに設定されたセルに対して上下左右斜め方向の８方向から隣接するセルに参照情報を設定することを特徴とする請求項９に記載の図形データ管理方法又は図形データ管理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、１乃至複数の構成点列を含む空間座標を有する図形データが格納された図形データファイルを管理する図形データ管理方法及び図形データ管理装置に関する。
【背景技術】
【０００２】
点（コネクタ）や線、面、体の情報で表現された図形データを格納し、検索する方法として、図形アドレステーブルに所定の図形領域内の図形を定義する図形データを格納し、図形領域を分割して得られる複数のセルごとに割り当てられた複数の一定容量のメモリ領域からなるアドレスデータテーブルに、各セル内を通過する図形に対応する図形データに対し図形アドレステーブルの格納先アドレスを格納して、各セル内を通過する図形に対応する図形データに対して、その格納先アドレスを当該セルに割り当てられたメモリ領域に格納しきれない場合には他のセルに割り当てられたメモリ領域に代替格納する方法がある（例えば、特許文献１参照）。
【特許文献１】特開平２−３６０３８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上記従来の方法は、空間図形の検索を高速化する技術に関するものであるが、セルごとに複数の一定容量のメモリ領域が割り当てられるため、実際にはデータの格納されない大量のメモリ領域を必要とし、メモリ使用効率の問題がある。また、同一点に集まる線情報を検索する時に、確実に候補にならない対象情報も参照するために検索速度を落とす問題がある。
【課題を解決するための手段】
【０００４】
本発明は、上記課題を解決するものであって、図形データの管理を簡便に行え、メモリの使用効率、検索効率の向上、検索の高速化を図るものである。
【０００５】
そのために本発明は、１乃至複数の構成点列を含む空間座標を有する図形データが格納された図形データファイルを管理する図形データ管理方法又は図形データ管理として、図形の存在領域をＸ，Ｙ方向にそれぞれ分割してセルに区分し、前記セル単位で存在する図形データの分類情報を含む図形情報と、前記図形データファイルの図形データ格納場所を示す格納情報と、同一セル内に複数の図形が存在する場合の他の制御コードとの間の継続情報とを管理データとして関連データ結合テーブルに設定し、空間分布テーブルに前記セル単位で前記関連データ結合テーブルの管理データのアドレスの１つに対してポインタを設定して、前記セル単位で前記空間分布テーブルを介して前記関連データ結合テーブルの各管理データと前記図形データファイルに格納された各図形データとの関係付けを行い管理することを特徴とする。
【０００６】
前記図形情報として、少なくとも体・面・線・点の分類情報、ノード／線上・面上・体上、端点／中間ノード、図郭線上／図郭内の識別情報、種別情報を有することを特徴とし、前記図形情報として、上下左右斜め方向の８方向の隣接セルに対する被参照情報を有することを特徴とする。
【０００７】
前記格納情報として、前記図形データファイルにおける図形データの格納場所又は前記格納場所を有する管理データへのオフセットを有することを特徴とし、１つの図形データが管理される複数の管理データのうち、１つの管理データに対してのみ前記格納場所が設定され、他の管理データに対してはオフセットが設定されることを特徴とし、前記格納情報として、前記複数の構成点列に対応する番号を有することを特徴とする。
【０００８】
前記継続情報として、同一ノードに集まる線についての関係付け情報を有することを特徴とし、前記空間分布テーブルとして、前記ポインタを設定する面ポインターテーブルと、上下左右斜め方向の８方向の隣接セルに対する参照情報を設定する参照フラグテーブルとを有することを特徴とし、前記面ポインターテーブルは、図形データが存在するセルのうち上下左右に２つおきのセルに設定し、前記参照フラグテーブルは、前記面ポインターテーブルに設定されたセルに対して上下左右斜め方向の８方向から隣接するセルに参照情報を設定することを特徴とする。
【発明の効果】
【０００９】
本発明によれば、面ポインターテーブルや参照フラグテーブルからなる２次元配列の空間分布テーブルを用いるので、メモリの使用効率を上げると同時に検索効率も向上させることができる。また、同一点（ノード）に集まる線については、ポインターの関係付けを行うことで、該ノードに関する候補を参照することができ、近傍検索においても同じ点を候補の数だけ参照する重複を回避することができる。図形データ管理テーブルとして、図形データを順番に参照するだけで構築でき、ソートなどの追加処理を必要としないためにテーブル作成の効率を上げることができる。さらに、図形編集時に追加、削除される情報に対するテーブルの修正も簡便に実行することができる。さらに、本発明によれば、地図の管理領域（メッシュ）ごとに図形データ管理テーブルを作成することができるため、広域にわたる地図データの検索にも適用可能である。
【発明を実施するための最良の形態】
【００１０】
以下、本発明の実施の形態を図面を参照しつつ説明する。図１は本発明に係る図形データ管理・検索方法の実施の形態を説明する図、図２は図形データファイルの構成概要を説明する図、図３は図形データ管理テーブルの構成概要を説明する図である。図中、１は図形データファイル、２は図形データ管理部、３は空間分布テーブル、４は関連データ結合テーブル、３１は面ポインターテーブルを示す。
【００１１】
図形データファイル１は、体、面、線、点などの各図形データ群を格納するものであり、例えば線の場合には、その図形データ毎に、種別（レーヤー：実線、点線、……）、図形を構成している点のＸ，Ｙ座標列（線分列）からなるベルトルデータが格納される。
【００１２】
空間分布テーブル３は、図形の存在領域をＸ，Ｙ方向にそれぞれ分割してセルに区分し、セル単位で関連データ結合テーブル４の管理データの１つをポイントする面ポインターテーブル３１、上下左右斜めの８方向の隣接セルの参照フラグを設定する参照フラグテーブル３２からなり、図形データを管理する図形データ管理テーブルの１つである。
【００１３】
関連データ結合テーブル４は、管理データを格納してセル単位で図形データを管理する図形データ管理テーブルの１つであり、セル単位で存在する図形データに関する管理データにより、分類情報を含む図形情報、前記図形データファイルの図形データ格納場所を示す参照情報、同一セル内に複数の図形が存在する場合の他の管理データとの間の継続情報を有する。関連データ結合テーブル４のそれぞれの管理データにおいては、図形情報として、図形データに関する情報（分類情報、識別情報、種別情報）が制御コードや種別により管理され、参照情報として、図形データファイルの図形データの格納アドレスが参照ポインターや他の管理データへのオフセットにより管理され、継続情報として、同一ノードの他図形データに関する管理データのアドレスが同一ノードポインターにより、次の図形データに関する管理データのアドレスが継続ポインターにより管理される。
【００１４】
すなわち、関連データ結合テーブル４では、セル単位で図形データを管理する管理データとして、制御コード、種別（レーヤー）、参照ポインター／オフセット、同一ノードポインター、継続ポインターを有する。制御コードには、図形の分類が点（コネクタ）か線か面か体か、ノードか線上・面上・体上か、上下左右斜めの８方向の被参照方向の情報が設定される。また、参照ポインターには、図形データファイルの各図形データの格納アドレスが格納され、同一ノードポインターには、同一ノードに集まる複数の図形データに関する管理データを関係付けするためアドレスが順に格納される。
【００１５】
図形データ管理部２は、図形データファイル１に基づき前記空間分布テーブル３、関連データ結合テーブルを設定し、設定した空間分布テーブル３、関連データ結合テーブルに基づき図形データファイル１に格納された図形データを検索する処理を行うものである。
【００１６】
図形データファイル１において、図形データがベクトルデータの場合には、例えば図２（Ａ）に示すように消去・存在フラグ、種別、使用階層、リンク数、全構成点数、Ｘ，Ｙの構成点列、地物の位置高さを示す高さ情報Ｚ、地物自身の高さを示す比高情報（変位高さ）Ｈ、地物の変遷を発生と消滅の日時で示す時間情報Ｔなどの各情報を持つ。また、コネクタの場合には、図２（Ｂ）に示すように消去・存在フラグ、種別、使用階層、代表点Ｘ，Ｙ、高さ情報、時間情報、属性（属性数）などの各情報を持つ。
【００１７】
図形データファイル１の各図形データの管理は、図形データ管理テーブルとして、例えば図３（Ａ）に示す面ポインターテーブル３１と図３（Ｂ）に示す関連データ結合テーブル４を用いて以下のように行われる。なお、図３（Ａ）に示す面ポインターテーブル３１は、空間分布テーブル３の１つである。
【００１８】
面ポインターテーブル３１では、図形の存在領域がＸ方向、Ｙ方向にそれぞれ等分割したセルＣｉｊに区分され、その区分された各セルＣｉｊからそのセル内に存在する図形データの１つを管理する関連データ結合テーブル４の管理データのアドレスが設定（ポイント）される。これに対し、関連データ結合テーブル４において、管理データでは、制御コードにより図形の分類が点（コネクタ）か線か面か体か、ノードか線上・面上・体上か、上下左右斜めの８方向の被参照方向の情報が設定され、各種ポインターに図形データの格納アドレス、他の管理データのアドレスがそれぞれ設定される。このとき、図形データを複数のセルに対応して管理する複数の管理データにおいて、１つの管理データに対してのみ参照ポインターに図形データの格納場所が設定され、他の管理データに対しては参照ポインターに図形データの格納場所が設定された管理データまでのオフセットが設定される。したがって、参照ポインターに図形データの格納場所が設定される管理データは、図形データの第１の構成点Ｘ，Ｙに対応する始点のノードのセルに対応する管理データである。
【００１９】
セル内に複数の図形が存在する場合に、面ポインターテーブル３１によりポイントされた関連データ結合テーブル４の管理データから、他の図形に関する管理データに継続ポインターを用いてリンクされ、また、同一ノードの他の図形に関する管理データに同一ノードポインターを用いてリンクされる。したがって、セル内に存在する図形が複数あっても、面ポインターテーブル３１のそのセルから関連データ結合テーブル４の管理データにアクセスすると、継続ポインターにより他の図形を追跡し、また、同一ノードポインターにより同一ノードの他の図形を追跡することができる。
【００２０】
次に、関連データ結合テーブル４をセルＣ２４に着目して説明する。図３において、セルＣ２４内には、線Ａ、Ｂ、Ｃ、Ｄが存在し、線Ａは始点のノード３がセルＣ１１に存在する中間ノードであるノード１、線Ｂ、Ｃ、Ｄは同一ノードに集まる線としてノード２をそれぞれ有している。面ポインターテーブル３１は、セルＣ２４において、線Ａ、Ｂ、Ｃ、Ｄのうち線Ａの管理データのアドレスｐ２４をポイントしている。面ポインターテーブル３１によりポイントされた関連データ結合テーブル４の線Ａの管理データｐ２４には、図３（Ｂ）に示すように線Ａの図形データにおいて２番目のノードの座標になるので、線Ａのノード１であることが設定されると共に、座標番号に２番目の座標であることを示す「２」が設定され、その始点のノード３の管理データのアドレス（ｐ１１）までのオフセットが設定され、さらに継続ポインターに他の図形である線Ｂの管理データのアドレスが設定される。なお、セルＣ１１に対応する始点のノード３の管理データｐ１１には、１番目の座標であることを示す「１」の座標番号が設定されている。
【００２１】
これに対し、線Ｂの管理データでは、線Ｂのノード２であることが設定されると共に、始点であるので参照ポインターに図形データファイルの線Ｂの図形データが格納されているアドレスが設定され、座標番号に始点、つまり１番目の座標であることを示す「１」が設定される。そして、同一ノードポインターに同一ノードの線Ｃの管理データのアドレスが設定され、継続ポインターは、同一ノードのもの以外に他の図形がないので、継続なしが例えば「０」で設定される。同様に線Ｃの管理データにおいても同一ノードポインターが設定され、同一ノードで最後の線Ｄの管理データにおいて、同一ノードポインターに同一ノードで最初の線Ｂの管理データのアドレスが設定され、一巡する。
【００２２】
このように面ポインターテーブル３１と関連データ結合テーブル４を用いて図形データファイルを管理することにより、面ポインターテーブル３１のセルからそのセル内の図形を関連データ結合テーブル４の管理データで各種ポインターを通して検索することができる。また、始点のノードが存在するセル以外の管理データでは、始点のノードの管理データのアドレスまでのオフセットを設定し、このことにより、オフセットから始点のノードの管理データを取得し、その管理データの参照ポインターから図形データファイルにおいてその図形データが格納されているアドレスを取得することができる。
【００２３】
図４は図形データが追加されたときの関連データ結合テーブル４の追加、更新処理を説明する図、図５は図形データが削除されたときの関連データ結合テーブル４の削除、更新処理を説明する図である。本実施形態では、図３（Ａ）の面ポインターテーブル３１に示した図形データに図４（Ａ）に示すように新たな線Ｅが追加されると、その追加により新たに図形が存在することとなった各セル（Ｃ３１、Ｃ３２、Ｃ２２、Ｃ１６）に対し、面ポインターテーブル３１が設定され（ｐ３１、ｐ３２、ｐ２２、ｐ１６：図示せず）、関連データ結合テーブル４に線Ｅの管理データが各セル（Ｃ３１、Ｃ３２、Ｃ２２、Ｃ１６）に対応して追加される。また、既に図形が存在するセル（Ｃ２３、Ｃ２４、Ｃ２５、Ｃ１５）においては、図４（Ｂ）の関連データ結合テーブル４に示す管理データ（ｐ２４の線Ｂ、ｐ２５の線Ｃ、ｐ１５の線Ａ）の継続ポインターにおいて、継続なしが新たな図形の管理データのアドレスに更新される。
【００２４】
図形データが削除された場合には、その図形に係る管理データを消去し、関係するポインターのリンクを張りなおすことにより削除、更新が行われる。例えば図４（Ａ）の面ポインターテーブル３１に示す例において線Ｂを削除したとき、関連データ結合テーブル４では、図５に示すように線Ｂに係る管理データ（ｐ２４〜ｐ２６）を削除すると共に、その管理データをポイントしている管理データの継続ポインター（ｐ２４の線Ａ、線Ｃ）、同一ノードポインター（ｐ２４の線Ｄ）をその次のポインターに張り直す。
【００２５】
また、図形データの削除は、図形データファイルにおいて、発生と消滅の日時で示す時間情報Ｔの設定により管理してもよい。このようにすると、削除した図形データについても含めて管理でき検索できる。なお、図形データファイルにおいて、発生と消滅の日時で示す時間情報Ｔの設定により管理する場合、状態の遷移に要する曖昧な時間が存在するときには、発生と消滅の日時をそれぞれ開始と確定の２つの日時、つまり、発生開始、発生確定、消滅開始、消滅確定の４つの日時で表すこともある。
【００２６】
次に、図形データ管理部２で行う図形データ管理テーブルの設定処理について説明する。図６は図形データ管理テーブルの設定処理の例を説明する図、図７はポインターの設定処理の例を説明する図、図８は同一ノードポインターの設定処理の例を説明する図である。
【００２７】
図形データ管理部２で行う図形データ管理テーブルの設定処理では、例えば図６に示すように図形の存在する領域をＸ，Ｙ方向にそれぞれ等分割してセルに区分した空間分布テーブル３を設定する（ステップＳ１１）。次にセル領域を選択し（ステップＳ１２）、選択したセル内に図形があるか否かを判定する（ステップＳ１３）。選択したセル内に図形があれば、セル内の図形情報を取得して（ステップＳ１４）、関連データ結合テーブル４に取得した図形の管理データを設定する（ステップＳ１５）。
【００２８】
セル内の全図形について管理データの設定が終了したか否かを判定し（ステップＳ１６）、終了していなければ、継続ポインター、同一ノードポインターを設定して（ステップＳ１７）、さらにステップＳ１４に戻り引き続きセル内の図形情報を取得して同様の処理を繰り返し実行する。
【００２９】
ステップＳ１３で選択したセル内に図形がないと判定された場合、あるいはステップＳ１６でセル内の全図形について管理データの設定が終了したと判定された場合には、さらに、全セル領域について処理が終了したか否かを判定し（ステップＳ１８）、全セル領域について処理が終了するまで、ステップＳ１２に戻って新たなセルについて同様の処理を繰り返し行う。
【００３０】
上記処理により図３に示す図形データ管理テーブルの例では、面ポインターテーブル３１のセルＣ１１〜１５、Ｃ２３〜２６、Ｃ３４〜３６に対応する面ポインターに関連データ結合テーブル４の各管理データのアドレスが設定され、また、図３（Ｂ）に示す関連データ結合テーブル４に各図形に関する管理データが設定される。
【００３１】
前記ステップＳ１７のポインターの設定処理では、例えば図７に示すように面ポインターが設定済みか否かを判定し（ステップＳ１２）、設定済みでない場合には面ポインターの該当セルに関連データ結合テーブル４における該当管理データのアドレスを設定する（ステップＳ２２）。面ポインターの設定が済めば、次にデータベース（図形データファイル）を参照する図形、つまり、始点のノードか否かを判定する（ステップＳ２３）、参照図形である場合には、参照ポインターにその図形データを格納した図形データファイルのアドレスを設定して（ステップＳ２４）、次図形への継続ポインターを設定する（ステップＳ２５）。参照図形でない場合には、その図形の参照ポインターを設定した管理データのアドレスまでのオフセットを設定する（ステップＳ２６）。
【００３２】
また、同一ノードポインターの設定処理は、例えば図８に示すように同一ノードの図形があるか否かを判定し（ステップＳ３１）、同一ノードの図形がある場合には、同一ノードポインターに同一ノードの他の図形の管理データのアドレスを設定すると共に（ステップＳ３２）、参照ポインターにその図形データを格納した図形データファイルのアドレスを設定する（ステップＳ３３）。さらに、次の図形があるか否かを判定し（ステップＳ３４）、次の図形がある場合には、継続ポインターに次の図形の管理データのアドレスを設定し（ステップＳ３５）、次の図形でない場合には、継続ポインターに継続なしを設定する（ステップＳ３６）。
【００３３】
次に、制御コードの具体的な構成例、空間分布テーブルとして面ポインターテーブルに参照フラグテーブルを加えて管理する例について説明する。図９は管理データの制御コードの具体的な設定例を説明する図、図１０は空間分布テーブルとして面ポインターテーブルと参照フラグテーブルを備えた例を説明する図である。
【００３４】
管理データの制御コードは、例えば図９に示すように上位バイトと下位バイトからなる。上位バイトでは、図形が体か面か線か点（コネクタ）かの分類（ビットマップ）にそれぞれ１／０で４ビットが割り当てられ、そして、ノードか線上・面上・体上かに１／０で１ビット、端点か中間ノードかに１／０で１ビット、図郭線上か図郭内かに１／０で１ビットがそれぞれ割り当てられ、さらに、同一座標の１つ目の（ノード）に１ビットがそれぞれ割り当てられる。また、下位バイトでは、上下左右斜めの８方向の隣接セルに対する被参照方向にそれぞれ１／０で８ビットが割り当てられる。
【００３５】
さらに、ノードで端点が設定された制御コードの管理データには、種別（レーヤー）、参照ポインター（ベクトル格納場所）、座標番号、継続ポインターが設定される。しかし、中間ノード、線上・面上・体上が設定された制御コードの管理データには、その図形の端点ノードが設定された制御コードを持つ管理データのアドレスまでのオフセットと継続ポインターが設定される。
【００３６】
図９において、面ポインターテーブル３１上に示された実線のベクトルｉは、面ポインターテーブル３１からｐ１で関連データ結合テーブル４に設定されると、アドレスｐ１の管理データの制御コードは、上位バイトに３２Ｈ、つまり、ビット１に１（線）、ビット４に１（ノード）、ビット５に１（端点）が設定され、下位バイトに０６Ｈ、つまり、被参照方向が上（ビット２）と斜め上（ビット１）のセルであることが設定される。そして、種別（レーヤー）には、０００１Ｈ（実線）、参照ポインターには図形データファイルにおけるベクトルｉの格納場所が設定され、座標番号は、第１点の座標であるので、００００が、継続ポインターには、破線のベクトルｊの管理データのアドレスｐ１０が設定される。
【００３７】
アドレスｐ１０の管理データは、同様に制御コードの上位バイトに線で中間ノードとなる１２Ｈが、下位バイトに被参照方向が右と左と左上となる１９Ｈがそれぞれ設定され、種別（レーヤー）に破線となる０００２Ｈが、参照ポインターに図形データファイルにおけるベクトルｊの格納場所が、座標番号に第２点となる０００１が、継続ポインターに継続なしとなる００００００００がそれぞれ設定される。
【００３８】
また、面ポインターテーブル３１からｐ２で設定されたアドレスｐ１の関連データ結合テーブル４の管理データの制御コードは、上位バイトに線上となる０２Ｈが、下位バイトに被参照方向が下と右と右上となる４３Ｈがそれぞれ設定され、オフセット（→ノード）にベクトルｉの端点ノードの管理データのあるアドレスまでの−０００８が、継続ポインターに継続なしとなる００００００００がそれぞれ設定される。
【００３９】
なお、関連データ結合テーブル４におけるアドレスｐ１０の管理データでは、座標番号が第２点であるので、ベクトルｊの座標番号が「１」の管理データのあるアドレスｐ１までのオフセットを与え、参照ポインターを削除してもよい。このことによっても、オフセットから座標番号が第１点の管理データを取得し、その管理データの参照ポインターと座標番号の第２点により図形データファイルにおけるＸ，Ｙ座標を容易に取得することができる。
【００４０】
上記実施の形態では、図形データ管理テーブルの１つである空間分布テーブル３として面ポインターテーブル３１だけを用い、例えば図３に示す面ポインターテーブル３１ではＣ１２、Ｃ１３、Ｃ２３を含め、図形が存在するセル領域の全てにポインターを設定したが、図１０に示すように空間分布テーブル３として面ポインターテーブル３１に参照フラグテーブル３２を組み合わせて用いることにより、関連データ結合テーブル４の管理データを削減しメモリ容量を大幅に節約することができる。
【００４１】
この参照フラグテーブル３２によれば、図１０に示すように面ポインターテーブル３１のｐ１〜ｐ５のポインターに対し、上下左右斜めの８方向コードで参照フラグを設定することにより、面ポインターテーブル３１にポインターが設定されていないセルから参照フラグテーブル３２の参照フラグにしたがって管理データの設定されているセルを参照することができる。
【００４２】
例えば図３に示した実施形態においては、参照フラグテーブル３２を備えることにより、セルＣ１２、Ｃ１３、Ｃ１５、Ｃ２３、Ｃ２５、Ｃ２６、Ｃ３４〜Ｃ３６に関して、面ポインターテーブル３１及び関連データ結合テーブル４を削減し、参照フラグテーブル３２の設定に置き換えることができるので、大幅なメモリ領域の節約ができる。
【００４３】
参照フラグテーブル３２と面ポインターテーブル３１及び関連データ結合テーブル４との関係は、例えば図３において線Ａに関する場合、セルＣ１２に対しては、ノード３の存在するセルＣ１１を参照するフラグが参照フラグテーブル３２に設定され、セルＣ１３、Ｃ２３に対して、ノード１が存在するセルＣ２４を参照するフラグが参照フラグテーブル３２に設定される。そして、セルＣ１３、Ｃ２３、Ｃ２４に対してセルＣ２４にｐ２４のポインターが面ポインターテーブル３１に設定され、ｐ２４のアドレスで関連データ結合テーブル４に管理データが設定される。
【００４４】
参照フラグテーブル３２に設定する８方向コードを先に説明した制御コードの下位ビットと同じく、ビット０に右の方向を割り当て、それから反時計廻りで、ビット１に右上の方向、ビット２に上の方向、ビット３に左上の方向、ビット４に左の方向、ビット５に左下の方向、ビット６に下の方向、ビット７に右下の方向をそれぞれ割り当てると、参照フラグテーブル３２のＣ１２には左の方向を参照方向とする１０Ｈのフラグが設定され、これに対して、参照フラグテーブル３２のＣ１３には右下の方向を参照方向とする８０Ｈのフラグが、Ｃ２３には右の方向を参照方向とする０１Ｈのフラグがそれぞれ設定される。
【００４５】
上記参照フラグテーブル３２の設定に対して、面ポインターテーブル３１のセルＣ２４で設定されるｐ２４をアドレスとする関連データ結合テーブル４の管理データから検索される線Ａのノード１の管理データには、制御コードの下位バイトに左、左上、上、右上の方向を被参照方向として１ＤＨが設定される。したがって、線Ａに関して参照フラグテーブル３２のセルＣ１３、あるいはセルＣ２３からセルＣ２４が参照された場合、面ポインターテーブル３１のセルＣ２４で設定されるｐ２４のアドレスからノード１の線Ａ、ノード２の線Ｂ、Ｃ、Ｄの管理データを取得したとき、それぞれの制御コードの下位バイトを照合することにより、その参照方向に対応する被参照方向の情報を有するノード１の線Ａに係る管理データを対象データとして取得することができる。
【００４６】
図１１はリンク結合テーブル及びノードリンク結合テーブルを備えた例を説明する図である。図２で説明したように２つの端点のノード間を複数の座標列で持つ図形データには、中間ノードの座標とそうでない座標が混在した座標列からなるマルチリンクのデータがある。このようなマルチリンクの図形データにおいては、中間ノードの座標を持つ、つまりマルチリンクの図形データを管理するテーブルとして、図１１に示すようにリンク結合テーブル５とノードリンク結合テーブル６を設定することで、マルチリンクを構成する図形データのノードの管理、検索をさらに効率的に行え、メモリ使用量を低減することができる。
【００４７】
図１１において、リンク結合テーブル５は、複数の中間ノードの座標を座標列の中に持つマルチリンクの図形データに関してそのマルチリンク単位でノードを管理するマルチリンク単位のポインタからなる固定長のテーブルである。例えば線Ａ、Ｂ、Ｃ、……がマルチリンクの図形データであれば、それぞれがリンク結合テーブルに設定されるものとなる。ノードリンク結合テーブル６は、リンク結合テーブル５に設定されたマルチリンクの図形データのそれぞれにおいて該当マルチリンクを構成するノード数に対応して、それぞれのノードについて関連データ結合テーブルへのポインタを設定することにより、マルチリンク内のノードの関連付けを行うものである。このことにより、マルチリンクの図形データに関しては、管理、検索のために使用するメモリの容量を少なくすることができ、また、検索を効率よく、高速化できる。
【００４８】
なお、本発明は、上記実施の形態に限定されるものではなく、種々の変形が可能である。例えば上記実施の形態では、図面データ管理テーブルとして、空間分布テーブル（面ポインターテーブル、参照フラグテーブル）、関連データ結合テーブルを用いて図面データファイルに格納された図面の格納、検索を含む管理を行うようにしたが、さらに、マルチリンク単位のポインターからなるリンク結合テーブル、マルチナンク内のノードの関連付けを行うポインターからなるノードリンク結合テーブルを組み合わせて用いるように構成してもよい。
【図面の簡単な説明】
【００４９】
【図１】本発明に係る図形データ管理・検索方法の実施の形態を説明する図である。
【図２】図形データファイルの構成概要を説明する図である。
【図３】図形データ管理テーブルの構成概要を説明する図である。
【図４】図形データが追加されたときの関連データ結合テーブル４の追加、更新処理を説明する図である。
【図５】図形データが削除されたときの関連データ結合テーブル４の削除、更新処理を説明する図である。
【図６】図形データ管理テーブルの設定処理の例を説明する図である。
【図７】ポインターの設定処理の例を説明する図である。
【図８】同一ノードポインターの設定処理の例を説明する図である。
【図９】管理データの制御コードの具体的な設定例を説明する図である。
【図１０】空間分布テーブルとして面ポインターテーブルと参照フラグテーブルを備えた例を説明する図である。
【図１１】リンク結合テーブル及びノードリンク結合テーブルを備えた例を説明する図である。
【符号の説明】
【００５０】
１…図形データファイル、２…図形データ管理部、３…空間分布テーブル、４…関連データ結合テーブル、３１…面ポインターテーブル
【図１】
2006011727.tif 000003
【図２】
2006011727.tif 000004
【図３】
2006011727.tif 000005
【図４】
2006011727.tif 000006
【図５】
2006011727.tif 000007
【図６】
2006011727.tif 000008
【図７】
2006011727.tif 000009
【図８】
2006011727.tif 000010
【図９】
2006011727.tif 000011
【図１０】
2006011727.tif 000012
【図１１】
2006011727.tif 000013