JPS6381573A - 図面情報管理方法 - Google Patents
図面情報管理方法Info
- Publication number
- JPS6381573A JPS6381573A JP22593886A JP22593886A JPS6381573A JP S6381573 A JPS6381573 A JP S6381573A JP 22593886 A JP22593886 A JP 22593886A JP 22593886 A JP22593886 A JP 22593886A JP S6381573 A JPS6381573 A JP S6381573A
- Authority
- JP
- Japan
- Prior art keywords
- mesh
- size
- management method
- information management
- drawing information
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Landscapes
- Processing Or Creating Images (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は、各種の設計図面や地図などの図面情報の対話
的な検索・編集を高速に行う方法に係り、特に図面内に
大きさの変化が激しい成分を含む場合に好適な高速化手
法に関する。
的な検索・編集を高速に行う方法に係り、特に図面内に
大きさの変化が激しい成分を含む場合に好適な高速化手
法に関する。
従来、図面や地図など２次元以上の空間的な位置情報を
含む図面データを高速に検索するために、各種の高速化
手法が提案されている。例えば、特願昭６０−２８５５
１２号で述べられているように、図面の多元空間を一定
の格子に分割しく以降これをメツシュと呼ぶ）、図面情
報として記憶されている各図形要素が通過するメツシュ
位置を記憶しておき、検索時には、指定されたメツシュ
位置から、限定された図形要素だけを処理の対象と 。
含む図面データを高速に検索するために、各種の高速化
手法が提案されている。例えば、特願昭６０−２８５５
１２号で述べられているように、図面の多元空間を一定
の格子に分割しく以降これをメツシュと呼ぶ）、図面情
報として記憶されている各図形要素が通過するメツシュ
位置を記憶しておき、検索時には、指定されたメツシュ
位置から、限定された図形要素だけを処理の対象と 。
することにより、処理の高速化を図る方式がある（以下
文献（１）と呼ぶ）。
文献（１）と呼ぶ）。
一方、ジェー・エル・ベントレー“マルチディメンジョ
ナル バイナリ−サーチ トリー ユーズド フォー
アソシアティブ サーチング″コミユニケージ目ン オ
ブ ニーシーエム。
ナル バイナリ−サーチ トリー ユーズド フォー
アソシアティブ サーチング″コミユニケージ目ン オ
ブ ニーシーエム。
第１８巻９号、１９７５年刊
（Ｊ、Ｌ、ＢＥＮＴＬＥＹ “ＭｔＪＬＴＩ−ＤＩＭ
ＥＮＳＩＯＮＡＬ ＢＩＮＡＲＹＳＥＡＲＣＨＴＲＥ
ＥＳ ＵＳＥＤ ＦＯＲＡＳＳＯＣＩＡＴＩＶＥ
５ＥＡＲＣＨＩＮＧ”ＣＯＭＭＵＮ、ＡＣＭ、１８．
９ （１９７５））では、に−Ｄ木と呼ばれる領域分割
方式が考案されている。この方式では、上述のメツシュ
の代わりに、２分法を基本とする手法により、各図形要
素を包含するような大きさの異なる領域（以降これをキ
ーエリアと略称する。）に図面を分割し、キーエリアに
含まれる図形要素の数が均一となるまでキーエリアへの
分割と木構造化を繰返す手法があった（以下文献（２）
と呼ぶ）。これにより。
ＥＮＳＩＯＮＡＬ ＢＩＮＡＲＹＳＥＡＲＣＨＴＲＥ
ＥＳ ＵＳＥＤ ＦＯＲＡＳＳＯＣＩＡＴＩＶＥ
５ＥＡＲＣＨＩＮＧ”ＣＯＭＭＵＮ、ＡＣＭ、１８．
９ （１９７５））では、に−Ｄ木と呼ばれる領域分割
方式が考案されている。この方式では、上述のメツシュ
の代わりに、２分法を基本とする手法により、各図形要
素を包含するような大きさの異なる領域（以降これをキ
ーエリアと略称する。）に図面を分割し、キーエリアに
含まれる図形要素の数が均一となるまでキーエリアへの
分割と木構造化を繰返す手法があった（以下文献（２）
と呼ぶ）。これにより。
処理対象図形の限定のために使われるキーエリアの量は
少くなる。
少くなる。
ところが一般に、設計図面や地図などには、大きさの変
化の激しい図形要素が含まれる上に、図形位置の変更な
どの編集操作がひんばんに行われる。このような状況下
で、まず文献（１）の手法を適用すると、図形要素の寸
法の大きなものに対しては、図形要素の通過するメツシ
ュ数が多くなる。従って、例えば編集操作で図形要素位
置の移動などを加える場合、上記通過メツシュ位置の変
更処理量が大きくなるなどの問題があった。次に文献（
２）の手法を適用すると、同様な図形要素位置の移動な
どの編集処理を行う場合には、図形要素がキーエリアの
構造木内のどの位置に移動したかを知り、しかもキーエ
リアの構造木をたどりながら、所定の木の位置を検定し
、木の構造を修正するといった一連の処理を行う必要が
ある。しかし一般にこれらの一連の処理は複雑になり、
しかも修正によるに−Ｄ木の性能が著しく低下するため
、実質上に−Ｄ木の変更は不可能に近い間層がある。
化の激しい図形要素が含まれる上に、図形位置の変更な
どの編集操作がひんばんに行われる。このような状況下
で、まず文献（１）の手法を適用すると、図形要素の寸
法の大きなものに対しては、図形要素の通過するメツシ
ュ数が多くなる。従って、例えば編集操作で図形要素位
置の移動などを加える場合、上記通過メツシュ位置の変
更処理量が大きくなるなどの問題があった。次に文献（
２）の手法を適用すると、同様な図形要素位置の移動な
どの編集処理を行う場合には、図形要素がキーエリアの
構造木内のどの位置に移動したかを知り、しかもキーエ
リアの構造木をたどりながら、所定の木の位置を検定し
、木の構造を修正するといった一連の処理を行う必要が
ある。しかし一般にこれらの一連の処理は複雑になり、
しかも修正によるに−Ｄ木の性能が著しく低下するため
、実質上に−Ｄ木の変更は不可能に近い間層がある。
本発明の目的は、以上の問題点を解決し、検索・編集等
の処理対象とする図形要素が大きな場合でも、関係する
メツシュ数が多くなり過ぎないような処理高速化のため
の管理方法を提供することにある。
の処理対象とする図形要素が大きな場合でも、関係する
メツシュ数が多くなり過ぎないような処理高速化のため
の管理方法を提供することにある。
上記目的は、高速化のための管理方法として、図形成分
が包含又は通過するメツシュ位置を記憶する方法を基本
とし、処理対象とする図面要素の通過メツシュ数が一定
値を越えないよう、適応的にメツシュの大きさを変える
ような管理を行うことにより達成される。
が包含又は通過するメツシュ位置を記憶する方法を基本
とし、処理対象とする図面要素の通過メツシュ数が一定
値を越えないよう、適応的にメツシュの大きさを変える
ような管理を行うことにより達成される。
本発明による管理方法によれば、処理対象とする図形要
素の大きさが小さいものに対しては、従来のメツシュ管
理により、処理のための候補の限定が容易な上に１図形
要素の大きさが大きくなっても、その大きさに適合した
大きさのメツシュで管理しているので、処理のための図
形候補の数がむやみに多くなり過ぎることがない。これ
により検索・編集などによる管理情報の変更はきわめて
容易となる。
素の大きさが小さいものに対しては、従来のメツシュ管
理により、処理のための候補の限定が容易な上に１図形
要素の大きさが大きくなっても、その大きさに適合した
大きさのメツシュで管理しているので、処理のための図
形候補の数がむやみに多くなり過ぎることがない。これ
により検索・編集などによる管理情報の変更はきわめて
容易となる。
〔実施例〕
以下、本発明の一実施例を図面を参照して説明する。第
２図は本発明を実現したシステムの摺成例を示すブロッ
ク図である。図中１０は、マイクロプロセッサやミニコ
ンピユータのＣＰＵなどの処理装置、２０は検索・編集
などの処理を加えるための図面・地図データを表示する
ためのＣＲＴ。
２図は本発明を実現したシステムの摺成例を示すブロッ
ク図である。図中１０は、マイクロプロセッサやミニコ
ンピユータのＣＰＵなどの処理装置、２０は検索・編集
などの処理を加えるための図面・地図データを表示する
ためのＣＲＴ。
３０と４０はＣＲＴでの位置を指定するためのスタイラ
スと座標入力装置、５０は処理対象とする図面・地図デ
ータや検索高速化のための管理情報を一時的に記憶する
メモリ、６０は地図・図面データを記憶するための磁気
ディスク等のファイル装置をそれぞれ示す。
スと座標入力装置、５０は処理対象とする図面・地図デ
ータや検索高速化のための管理情報を一時的に記憶する
メモリ、６０は地図・図面データを記憶するための磁気
ディスク等のファイル装置をそれぞれ示す。
このような構成において、まず６０のファイル装置に記
憶される図面・地図データの形式について説明する。本
実施例において、図面・地図内の図形成分は、全て多角
形で記述されるものとする′と、第３図に示すように、
１つの線セグメントは。
憶される図面・地図データの形式について説明する。本
実施例において、図面・地図内の図形成分は、全て多角
形で記述されるものとする′と、第３図に示すように、
１つの線セグメントは。
それぞれ先頭座標、終点座標の２座標で定義されたベク
トルの連続した集合として定義され、第４図に示す形式
の図形テーブルに記憶される。この第４図におけるセグ
メント番号１ｎｏは、各セグメントの記憶位置を、物理
的なアドレスではなく。
トルの連続した集合として定義され、第４図に示す形式
の図形テーブルに記憶される。この第４図におけるセグ
メント番号１ｎｏは、各セグメントの記憶位置を、物理
的なアドレスではなく。
固有番号でアクセスするための整理番号であり、セグメ
ントタイプｌｋは、セグメントをＣＲＴ１０上に表示す
る場合に、実線・破線・鎖線などの線種の区別及び線色
を反映した値とする。
ントタイプｌｋは、セグメントをＣＲＴ１０上に表示す
る場合に、実線・破線・鎖線などの線種の区別及び線色
を反映した値とする。
構成点数ｎは、セグメントを構成するベクトルの数であ
り、座標データ （Ｘ＋Ｙ＋・・・・・・ｘ ｎ ｗｙ
ｎ）はセグメントを構成する各ベクトルの始点。
り、座標データ （Ｘ＋Ｙ＋・・・・・・ｘ ｎ ｗｙ
ｎ）はセグメントを構成する各ベクトルの始点。
終点座標である。
一方図面・地図内の文字・記号成分は、第５図に示すよ
うに、文字・記号を配置する外接長方形の対角左下座標
ｇｎ （ｘ、Ｑｔ ｙｘ）と右上座標ｇ ｎ （Ｘ ｎ
ｓ Ｙ ｎ） 、及びその傾斜角度θを第６図に示す形
式の文字・記号テーブルに記憶する。
うに、文字・記号を配置する外接長方形の対角左下座標
ｇｎ （ｘ、Ｑｔ ｙｘ）と右上座標ｇ ｎ （Ｘ ｎ
ｓ Ｙ ｎ） 、及びその傾斜角度θを第６図に示す形
式の文字・記号テーブルに記憶する。
そしてこの第６図におけるテキスト番号は、図形テーブ
ルのセグメント番号と同様に、固有番号でアクセスする
ための整理番号であり、テキストタイプは、明朝体・ゴ
シック体など、字体・字の太さ等を規定する値である。
ルのセグメント番号と同様に、固有番号でアクセスする
ための整理番号であり、テキストタイプは、明朝体・ゴ
シック体など、字体・字の太さ等を規定する値である。
又第６図のテキストデータｆｉｐｆ２ｙ・・・・・・ｆ
ｍは第５図のＦ １ ｒＦ ２ ＋・・・・・・ＦＩＴ
ｌを象徴的に示している。
ｍは第５図のＦ １ ｒＦ ２ ＋・・・・・・ＦＩＴ
ｌを象徴的に示している。
次に、処理高速化のための階層化管理用のインデックス
（以降、適応メツシュと略称する）の作成方法について
説明する。この適応メツシュを作成するタイミングは、
あらかじめ検索・編集などの処理とは独立に作成して、
第２図のファイル装置６０に記憶しておき、処理直前に
図形データを一時メモリ５０へ転送するのと同じタイミ
ングで転送する場合と、処理の対象成分をファイル装置
６０から一時メモリ５０へ転送した直後に動的に作成す
る方法とが考えられる。本実施例では、このどちらにも
共通する手法について述べる。又この適応メツシュの作
成方法は次に示すように、図形成分用と文字・記号成分
とで異なるが、結果は同一の適応メツシュ内に記憶され
る。
（以降、適応メツシュと略称する）の作成方法について
説明する。この適応メツシュを作成するタイミングは、
あらかじめ検索・編集などの処理とは独立に作成して、
第２図のファイル装置６０に記憶しておき、処理直前に
図形データを一時メモリ５０へ転送するのと同じタイミ
ングで転送する場合と、処理の対象成分をファイル装置
６０から一時メモリ５０へ転送した直後に動的に作成す
る方法とが考えられる。本実施例では、このどちらにも
共通する手法について述べる。又この適応メツシュの作
成方法は次に示すように、図形成分用と文字・記号成分
とで異なるが、結果は同一の適応メツシュ内に記憶され
る。
まず図形成分用の適応メツシュの作成方法について説明
する。処理対象とする図面・地図の範囲（以降ドメイン
と略称。）を（ＤＸ、ＤＹＩとし、各ＤＸ、ＤＹを等間
隔に分割した仮想のメツシュを作成する。このメツシュ
は、大きさの異なる複数組を考え、それらをメツシュの
大きさに順じ、階層化する。例えば第７図に示すように
１分割の規則として、ＤＸ、ＤＹをそれぞれ１７２分割
し、ドメインを１７２２ ｎ分割する方法では、メツシ
ュの大きさが、ドメイン全体に対し、 １／１ １／４ １／１６ １／６４ １／２５６
・・・（ｎ＝ｏ） （ｎ＝１） （ｎ ＝２）
（ｎ＝３） （ｎ＝４）のように細分化される
。この場合メツシュの最小サイズは、第８図に示すよう
な各セグメントのベクトル成分の長さを横軸にし、その
頻度を縦軸にとった頻度分布に適合するように決める。
する。処理対象とする図面・地図の範囲（以降ドメイン
と略称。）を（ＤＸ、ＤＹＩとし、各ＤＸ、ＤＹを等間
隔に分割した仮想のメツシュを作成する。このメツシュ
は、大きさの異なる複数組を考え、それらをメツシュの
大きさに順じ、階層化する。例えば第７図に示すように
１分割の規則として、ＤＸ、ＤＹをそれぞれ１７２分割
し、ドメインを１７２２ ｎ分割する方法では、メツシ
ュの大きさが、ドメイン全体に対し、 １／１ １／４ １／１６ １／６４ １／２５６
・・・（ｎ＝ｏ） （ｎ＝１） （ｎ ＝２）
（ｎ＝３） （ｎ＝４）のように細分化される
。この場合メツシュの最小サイズは、第８図に示すよう
な各セグメントのベクトル成分の長さを横軸にし、その
頻度を縦軸にとった頻度分布に適合するように決める。
例えば。
メツシュサイズの最小値をその頻度分布の最頻値となる
寸法に最も近い値を選択する。次に各セグメントのベク
トルに着目し、各ベクトルがどのメツシュを通過するか
を検定し、その結果をベクトルと通過メツシュを関係付
けたＶ−Ｍ関係表（第９図）に記憶する、この場合、ベ
クトルの通過するメツシュ番号を求める処理は、メツシ
ュサイズが最小のものから行っていく。第１図に示すよ
うな仮想的なメツシュ系列（１／４．１／１６゜１／６
４）に対し、■から■のベクトルの適応メツシュを求め
る。ここで、適応メツシュを求める方法を説明する。
寸法に最も近い値を選択する。次に各セグメントのベク
トルに着目し、各ベクトルがどのメツシュを通過するか
を検定し、その結果をベクトルと通過メツシュを関係付
けたＶ−Ｍ関係表（第９図）に記憶する、この場合、ベ
クトルの通過するメツシュ番号を求める処理は、メツシ
ュサイズが最小のものから行っていく。第１図に示すよ
うな仮想的なメツシュ系列（１／４．１／１６゜１／６
４）に対し、■から■のベクトルの適応メツシュを求め
る。ここで、適応メツシュを求める方法を説明する。
第１０図は、図形データの適応メツシュ作成アルゴリズ
ムを示している。
ムを示している。
ステップ１００では、処理対象とするメツシュの大きさ
を最小のものに設定する。
を最小のものに設定する。
ステップ１１０では、ベクトルの始端座標（υｘ１υｙ
ｓ）−終端座ＦＡ（ｖＸｉｌ＋ ｖｙｘ）のそれぞれに
対し、現行のメツシュに対し、どのメツシュに含まれる
かを計算し、メツシュ番号を求め、これをＭＳ、ＭＥと
する。
ｓ）−終端座ＦＡ（ｖＸｉｌ＋ ｖｙｘ）のそれぞれに
対し、現行のメツシュに対し、どのメツシュに含まれる
かを計算し、メツシュ番号を求め、これをＭＳ、ＭＥと
する。
ステップ１２０では、上記ＭＳから出発し、 ′ＭＥ
に至るまでに通過するメツシュ番号を求め。
に至るまでに通過するメツシュ番号を求め。
先のＭＳ、ＭＥと合わせてリスト化を行う。これをメツ
シュリストと呼び、 （ＭＳ、ＭＭｌ、・・・・、ＭＭ ｋ２ＭＥ）とする。
シュリストと呼び、 （ＭＳ、ＭＭｌ、・・・・、ＭＭ ｋ２ＭＥ）とする。
このメツシュ番号は１例えば、プレゼンハムのアルゴリ
ズムにより求める。この手法については、「アルゴリズ
ム フォー コンピューター コントロール オブ デ
ィジタル プロッター」バイ プレゼンハム アイビー
エム システム ジャーナル ４．Ｉ Ｐ、２５〜３
０（１９６５） （ｒＡＬＧＯＲＩＴＨＭ ＦＯ
ＲＣＯＭＰＵＴＥＲＣ０ＮＴＲ０Ｌ ０ＦＤＩＧＩ
ＴＡＬ ＰＬＯＴＴＥＲＪ ＢＹＢＲＥＳＥＮＨ
ＮＭ ＩＢＭ ＳＹＳＴＥＭＪＯＵＲＮＡＬ
４．Ｉ Ｐ、２５〜３０（１９６５））に記載
されている。
ズムにより求める。この手法については、「アルゴリズ
ム フォー コンピューター コントロール オブ デ
ィジタル プロッター」バイ プレゼンハム アイビー
エム システム ジャーナル ４．Ｉ Ｐ、２５〜３
０（１９６５） （ｒＡＬＧＯＲＩＴＨＭ ＦＯ
ＲＣＯＭＰＵＴＥＲＣ０ＮＴＲ０Ｌ ０ＦＤＩＧＩ
ＴＡＬ ＰＬＯＴＴＥＲＪ ＢＹＢＲＥＳＥＮＨ
ＮＭ ＩＢＭ ＳＹＳＴＥＭＪＯＵＲＮＡＬ
４．Ｉ Ｐ、２５〜３０（１９６５））に記載
されている。
ステップ１３０ではメツシュリストの要素数を調べ、そ
の値が、ＫＬ以下か、ＫＬより大きいかを判定する。ス
テップ１４０では要素数がＫＬ以下の場合には、処理中
のメツシュの大きさと共に、メツシュリストの内容を、
第９図のＶ−Ｍ関係表の様式で記憶する。
の値が、ＫＬ以下か、ＫＬより大きいかを判定する。ス
テップ１４０では要素数がＫＬ以下の場合には、処理中
のメツシュの大きさと共に、メツシュリストの内容を、
第９図のＶ−Ｍ関係表の様式で記憶する。
ステップ１５０では、もしメツシュリストの要素数が上
記ＫＬより大きい場合には、メツシュのサイズを上位の
ものに変更し、ステップ１１０にもどる。
記ＫＬより大きい場合には、メツシュのサイズを上位の
ものに変更し、ステップ１１０にもどる。
以上のステップ１１０からステップ１４０までを、全て
のベクトルに対して繰返す。
のベクトルに対して繰返す。
上記アルゴリズムのステップ１３０におけるベクトルの
通過メツシュ数から、メツシュサイズの切換を行うため
のパラメータＫＬの値に関しては任意であるが、例えば
第１図に示すような１７２２ ｎ分割のメツシュの場合
には、ＫＬ＝４に設定する。また、ＫＬ＝−１に設定し
た場合には、各ベクトルが１つのメツシュ内に完全に包
含されるかどうかの判定を行うことと同等になる。また
、第９図に示したＶ−Ｍ関係表は、商用化されている各
種の関係データベース管理システムで管理すれば、多様
な検索が可能となる。この関係データベース管理システ
ムについては、例えば、「アリレイショナル モデル
オブ データ フォーラージ シェアード データ バ
ンクス」パイコツト イー エフ コミユニケイジョン
オブザ ニーシーエム ブイオーエル１３．ＮＯ，６
゜シュン１９７０ （ｒＡ ＲＥＬＡＴＩＯＮＡＬＭ
ＯＤＥＬ ＯＦ ＤＡＴＡ ＦＯＲＬＡＲＧＥ
５ＨＡＲＥＤ ＤＡＴＡＢＡＮＫＳＪ ＢＹ Ｃ
０ＤＤ、Ｅ、ＦＣＯＭＭＵＮＥＣＡＴＩ○Ｎ ＯＦ
ＴＨＥＡＣＭ ＶＯＬ、１３．ＮＯ，６，ＪＵＮ
Ｅ１９７０）に記載されている。但し、第９図の■−Ｍ
関係表におけるベクトル番号は、先頭４ケタをセグメン
ト番号１ｎＯ１下２ケタをセグメント内相対ベクトル位
置を示す番号に割当てている。
通過メツシュ数から、メツシュサイズの切換を行うため
のパラメータＫＬの値に関しては任意であるが、例えば
第１図に示すような１７２２ ｎ分割のメツシュの場合
には、ＫＬ＝４に設定する。また、ＫＬ＝−１に設定し
た場合には、各ベクトルが１つのメツシュ内に完全に包
含されるかどうかの判定を行うことと同等になる。また
、第９図に示したＶ−Ｍ関係表は、商用化されている各
種の関係データベース管理システムで管理すれば、多様
な検索が可能となる。この関係データベース管理システ
ムについては、例えば、「アリレイショナル モデル
オブ データ フォーラージ シェアード データ バ
ンクス」パイコツト イー エフ コミユニケイジョン
オブザ ニーシーエム ブイオーエル１３．ＮＯ，６
゜シュン１９７０ （ｒＡ ＲＥＬＡＴＩＯＮＡＬＭ
ＯＤＥＬ ＯＦ ＤＡＴＡ ＦＯＲＬＡＲＧＥ
５ＨＡＲＥＤ ＤＡＴＡＢＡＮＫＳＪ ＢＹ Ｃ
０ＤＤ、Ｅ、ＦＣＯＭＭＵＮＥＣＡＴＩ○Ｎ ＯＦ
ＴＨＥＡＣＭ ＶＯＬ、１３．ＮＯ，６，ＪＵＮ
Ｅ１９７０）に記載されている。但し、第９図の■−Ｍ
関係表におけるベクトル番号は、先頭４ケタをセグメン
ト番号１ｎＯ１下２ケタをセグメント内相対ベクトル位
置を示す番号に割当てている。
従って第９図におけるベクトル管理番号の値が１００１
０１の場合は、セグメント番号１００１で、第１番目の
ベクトルをさす。以上の方法によりＶ−Ｍ関係表に記憶
されるメツシュサイズとメツシュ番号を、セグメントの
各ベクトルに対する適応メツシュと呼ぶ。
０１の場合は、セグメント番号１００１で、第１番目の
ベクトルをさす。以上の方法によりＶ−Ｍ関係表に記憶
されるメツシュサイズとメツシュ番号を、セグメントの
各ベクトルに対する適応メツシュと呼ぶ。
次に文字・記号成分用の適応メツシュの作成方法につい
て説明する。基本的な処理は、図形の場合と同様である
。まず、第６図の文字・記号テーブルのテキスト傾きθ
とテキスト外接長方形対角座標ｇｘ（ｘぷ１３’λ）＋
ｇｎ（Ｘｎνｙｎ）から、外接長方形を構成するセグメ
ント（ＰｘＰｊＺｒ ｐｒ ＰｒｊＺ Ｐｘ）を求
める。この文字・記号成分用の適応メツシュは、この外
接長方形が通過し、かつその中に含まれるメツシュ番号
の値である。
て説明する。基本的な処理は、図形の場合と同様である
。まず、第６図の文字・記号テーブルのテキスト傾きθ
とテキスト外接長方形対角座標ｇｘ（ｘぷ１３’λ）＋
ｇｎ（Ｘｎνｙｎ）から、外接長方形を構成するセグメ
ント（ＰｘＰｊＺｒ ｐｒ ＰｒｊＺ Ｐｘ）を求
める。この文字・記号成分用の適応メツシュは、この外
接長方形が通過し、かつその中に含まれるメツシュ番号
の値である。
まず、ステップ２００でメツシュサイズを最小のものに
設定する。文字・記号データの適応メツシュ作成アルゴ
リズムを第１１図のフローチャートにより説明する。
設定する。文字・記号データの適応メツシュ作成アルゴ
リズムを第１１図のフローチャートにより説明する。
ステップ２１０では外接長方形セグメントの４つのベク
トルに着目し、各ベクトルの通過メツシュリストをプレ
ゼンハムのアルゴリズムにより求。
トルに着目し、各ベクトルの通過メツシュリストをプレ
ゼンハムのアルゴリズムにより求。
める。
ステップ２２０では４つのベクトルのメツシュリストを
Ｙ軸方向の同一メツシュ番号別に、Ｘ軸方向の大きさ順
にソートする。
Ｙ軸方向の同一メツシュ番号別に、Ｘ軸方向の大きさ順
にソートする。
ステップ２３０ではこの各Ｘ軸方向にソートされた。メ
ツシュ番号のリストの中に重複する部分があれば、唯一
化を図り、更に各リスト別にメツシュ番号のＸ軸方向へ
の最小値をＬＳｍＬｎ、最大値をＬ Ｓ ｍ ａ ｘと
する。
ツシュ番号のリストの中に重複する部分があれば、唯一
化を図り、更に各リスト別にメツシュ番号のＸ軸方向へ
の最小値をＬＳｍＬｎ、最大値をＬ Ｓ ｍ ａ ｘと
する。
ステップ２４０では各メツシュリストのＬ Ｓ ｍ Ｌ
ｎ ｅ Ｌ Ｓ ｍ ａ ｘの間に、連続しないメツ
シュ番号のものがある場合には、その間をつなぐメツシ
ュ番号をそれのリストに加える。
ｎ ｅ Ｌ Ｓ ｍ ａ ｘの間に、連続しないメツ
シュ番号のものがある場合には、その間をつなぐメツシ
ュ番号をそれのリストに加える。
ステップ２５０では、これらのメツシュリストの全ての
要素数を加算し、その値がＫＡＬ以下か。
要素数を加算し、その値がＫＡＬ以下か。
ＫＡＬより大きいかを判定する。ステップ２６０ではそ
の要素数がＫＡＬ以下の場合には、処理中のメツシュの
大きさと共にメツシュリストの内容を第９図と同様の第
１３図のＶ−Ｍ関係表の様式で記憶する。
の要素数がＫＡＬ以下の場合には、処理中のメツシュの
大きさと共にメツシュリストの内容を第９図と同様の第
１３図のＶ−Ｍ関係表の様式で記憶する。
もしメツシュリストの要素数がＫＡＬより大きい場合に
はメツシュのサイズを、上位のものに変更し、ステップ
２１０にもどる。
はメツシュのサイズを、上位のものに変更し、ステップ
２１０にもどる。
上記のステップを各ベクトルに対して繰り返す。
上述のアルゴリズムのうち、第１３図に示すＶ−Ｍ関係
表を作成するまでのステップ２００からステップ２６０
までの過程を第１２図を用いて具体的に説明すると次の
ようになる。まずステップ２１０までに得られるメツシ
ュ番号リストは、ＰｊＺＰＪＺｒ分： （（３，２）（
４，２）（５，３）（６，３）（７，３））ＰｊＺｒＰ
ｒ分： （（７，３）（７，４）（６，４）（６，５）
）ＰｒＰｒｊＺ分： （（６、５）（５、５）（４，５
）（４，４）（３，４）（２，４））ＰｒｊＺＰｊＺ分
： （（２，４）（２，３）（２，２）（３，２））と
なり、さらにこれをステップ２２０で処理すると、 Ｙ＝２成分（（２，２）（３，２）（４，２））Ｙ＝３
成分（（２，３）（５，３）（６，３）（７，３））”
ｙ’＝４成分（（２，４）（３，４）（４，４）（６，
４）（７，４））Ｙ＝５成分（（４，５）（５，５）（
６，５））となり、ステップ２４０で最終的に得られる
メツシュリストの内容は、 （（２，２）（３，２）（４，２）（２，３）（３，３
）（４，３）（５，３）（６，３）（７，３）（２，４
）（３，４）（４，４）（６，４）（７，４）（４，５
）（５，５）（６，５））となる。そしてメツシュリス
トの要素番号は１８となり、パラメータとの比較を行い
、適合すればＶ−Ｍ関係表に記憶する。
表を作成するまでのステップ２００からステップ２６０
までの過程を第１２図を用いて具体的に説明すると次の
ようになる。まずステップ２１０までに得られるメツシ
ュ番号リストは、ＰｊＺＰＪＺｒ分： （（３，２）（
４，２）（５，３）（６，３）（７，３））ＰｊＺｒＰ
ｒ分： （（７，３）（７，４）（６，４）（６，５）
）ＰｒＰｒｊＺ分： （（６、５）（５、５）（４，５
）（４，４）（３，４）（２，４））ＰｒｊＺＰｊＺ分
： （（２，４）（２，３）（２，２）（３，２））と
なり、さらにこれをステップ２２０で処理すると、 Ｙ＝２成分（（２，２）（３，２）（４，２））Ｙ＝３
成分（（２，３）（５，３）（６，３）（７，３））”
ｙ’＝４成分（（２，４）（３，４）（４，４）（６，
４）（７，４））Ｙ＝５成分（（４，５）（５，５）（
６，５））となり、ステップ２４０で最終的に得られる
メツシュリストの内容は、 （（２，２）（３，２）（４，２）（２，３）（３，３
）（４，３）（５，３）（６，３）（７，３）（２，４
）（３，４）（４，４）（６，４）（７，４）（４，５
）（５，５）（６，５））となる。そしてメツシュリス
トの要素番号は１８となり、パラメータとの比較を行い
、適合すればＶ−Ｍ関係表に記憶する。
以上適応メツシュの作成方法に関するアルゴリズムにつ
いて述べたが、これらの適応メツシュを用いた高速検索
アルゴリズムを第１４図のフローチャートにより説明す
る。一般に検索には、点指定・線指定・領域指定などが
考えられるが、これらの指定要素との完全マツチングで
はなく、最小距離検索などの場合には、領域指定による
検索候補の選択に帰着される。従って以下長方形領域指
定からの検索アルゴリズムについて述べる。
いて述べたが、これらの適応メツシュを用いた高速検索
アルゴリズムを第１４図のフローチャートにより説明す
る。一般に検索には、点指定・線指定・領域指定などが
考えられるが、これらの指定要素との完全マツチングで
はなく、最小距離検索などの場合には、領域指定による
検索候補の選択に帰着される。従って以下長方形領域指
定からの検索アルゴリズムについて述べる。
まず、ステップ３００で長方形領域を指定する。
ステップ３１０では長方形領域を構成する４つの座標位
巴を計算する。
巴を計算する。
ステップ３２０ではこれらの４座標を使って指定した長
方形領域を覆うメツシュ番号を得る。この手法としては
、第１１図のフローチャートのステップ２１０からステ
ップ２４０までと同じ手法により求める。これを処理中
の各メツシュサイズとペアにしたリストを作成し、これ
をＭＳ−Ｌｉｓｔとする。
方形領域を覆うメツシュ番号を得る。この手法としては
、第１１図のフローチャートのステップ２１０からステ
ップ２４０までと同じ手法により求める。これを処理中
の各メツシュサイズとペアにしたリストを作成し、これ
をＭＳ−Ｌｉｓｔとする。
Ｍ Ｓ −Ｌｉ５ｔ、＝ （ｉ番目メツシュサイズ、メ
ッシュ番号リスト）ステップ３３０では、各ＭＳ−Ｌ
ｉｓｔのメツシュサイズとメツシュ番号とを順に呼び出
し、第１３図のＶ−Ｍ関係表におけるメツシュサイズと
メツシュ番号の両者の値が合致する位置におけるベクト
ル管理番号９文字・記号番号とを得、これをＶ Ｃ−Ｌ
ｉｓｔとする。
ッシュ番号リスト）ステップ３３０では、各ＭＳ−Ｌ
ｉｓｔのメツシュサイズとメツシュ番号とを順に呼び出
し、第１３図のＶ−Ｍ関係表におけるメツシュサイズと
メツシュ番号の両者の値が合致する位置におけるベクト
ル管理番号９文字・記号番号とを得、これをＶ Ｃ−Ｌ
ｉｓｔとする。
ステップ３４０ではこのＶ Ｃ−Ｌ ｉｎにおいて、各
要素の重複を調べ１重複のある場合には唯−化を図る。
要素の重複を調べ１重複のある場合には唯−化を図る。
ステップ３５０では指定した長方形領域の中心位置（例
えば同心）をＧＰとし、ＶＣ−Ｌｉｓｔに登録されてい
る要素の代表点間の距離（例えばベクトルとＧＰ間の距
離や１文字・記号外接長方形の図心とＧＰ間距離など）
を調べ、最も値の小さなものを選択する。
えば同心）をＧＰとし、ＶＣ−Ｌｉｓｔに登録されてい
る要素の代表点間の距離（例えばベクトルとＧＰ間の距
離や１文字・記号外接長方形の図心とＧＰ間距離など）
を調べ、最も値の小さなものを選択する。
ステップ３６０では、選ばれた要素をＣＲＴに再表示し
、選択されたものが適当かどうかを判定する。
、選択されたものが適当かどうかを判定する。
本発明によれば１図面内の図形・文字・記号全ての成分
に対し、大きさの変化に依存しない一定個数以下のメツ
シュリストが得られるので、検索や編集などの処理速度
及び手順を大幅に短縮できる効果がある。
に対し、大きさの変化に依存しない一定個数以下のメツ
シュリストが得られるので、検索や編集などの処理速度
及び手順を大幅に短縮できる効果がある。
第１図は、本発明による適応メツシュの作成手順を示す
図、第２図はシステムの端成図、第３図は図形成分の例
図、第４何は図形成分の内部記憶様式、第５図は文字・
記号成分の例図、第６図は文字・記号成分の内部記憶様
式、第７図は適応メツシュのサイズによる階層化を示す
図、第８図はベクトル長と出現数による頻度分布、第９
図は図形データに関する適応メツシュの記憶表、第１０
図は、図形データの適応メツシュ作成アルゴリズムを示
すフローチャート、第１１図は、文字・記号データの適
応メツシュ作成アルゴリズムを示すフローチャート、第
１２図は文字・記号成分のメツシュ通過番号を求めるた
めの例図、第１３図は文字・記号データに関する適応メ
ツシュの記憶表。 第１４図は、適応メツシュを用いた検索アルゴリズムを
示すフローチャートである。 １０・・・処理装置、２０・・・表示装置、３０・・・
座標入力装置、４０・・・スタイラス、５０・・・−時
メモリ。 ６０・・・ファイル装置。 隼１図 ７ ｚ 串２目 竿５ＴＥ２ ９１＠ 楽７Ｔｆ！Ｉ ベグドアしに＃（メ゛／ンエｙ４ズノ ＄ ７ 凹 峯１０１！１ 滲 ７１ 図 捺７２国 拳７３目 半７４圓
図、第２図はシステムの端成図、第３図は図形成分の例
図、第４何は図形成分の内部記憶様式、第５図は文字・
記号成分の例図、第６図は文字・記号成分の内部記憶様
式、第７図は適応メツシュのサイズによる階層化を示す
図、第８図はベクトル長と出現数による頻度分布、第９
図は図形データに関する適応メツシュの記憶表、第１０
図は、図形データの適応メツシュ作成アルゴリズムを示
すフローチャート、第１１図は、文字・記号データの適
応メツシュ作成アルゴリズムを示すフローチャート、第
１２図は文字・記号成分のメツシュ通過番号を求めるた
めの例図、第１３図は文字・記号データに関する適応メ
ツシュの記憶表。 第１４図は、適応メツシュを用いた検索アルゴリズムを
示すフローチャートである。 １０・・・処理装置、２０・・・表示装置、３０・・・
座標入力装置、４０・・・スタイラス、５０・・・−時
メモリ。 ６０・・・ファイル装置。 隼１図 ７ ｚ 串２目 竿５ＴＥ２ ９１＠ 楽７Ｔｆ！Ｉ ベグドアしに＃（メ゛／ンエｙ４ズノ ＄ ７ 凹 峯１０１！１ 滲 ７１ 図 捺７２国 拳７３目 半７４圓
Claims (1)
- 【特許請求の範囲】 １、図形、文字、記号などの要素からなる図面全体を複
数のメッシュに分割し、各要素が通過するメッシュ数を
求め、該メッシュ数が１つの要素につき所定の条件を満
たすまで、メッシュの大きさを変更して図面全体を再分
割し、該所定の条件を満足する場合に、メッシュの大き
さと通過メッシュ位置とを記憶することを特徴とする図
面情報管理方法。 ２、特許請求範囲第１項において、上記再分割の出発と
するメッシュの大きさを、各要素の大きさの頻度の最頻
値に最も近い値に設定することを特徴とする図面情報管
理方法。 ３、特許請求範囲第１項において、上記再分割の単位を
１／２＾２＾ｎ（ｎ＝０、１、２、・・・）にすること
を特徴とする図面情報管理方法。 ４、特許請求の範囲第１項において、各要素の固有番号
とメッシュの大きさ及び通過メッシュ位置とを関係付け
た表を作成し、該表を関係形式で管理することを特徴と
する図面情報管理方法。 ５、特許請求範囲第１項において、文字・記号位置を示
すための外接長方形を用い、該外接長方形の閉領域と重
畳関係を持つメッシュ位置を記憶することを特徴とする
図面情報管理方法。 ６、特許請求範囲第１項において、各要素がメッシュ内
に完全に包含されるようにメッシュの大きさを大きなも
のとなるように再分割し、そのメッシュ位置を記憶する
ことを特徴とする図面情報管理方法。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61225938A JP2644735B2 (ja) | 1986-09-26 | 1986-09-26 | 図面情報管理方法 |
| US07/101,020 US4811244A (en) | 1986-09-26 | 1987-09-25 | Drawing information management system |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61225938A JP2644735B2 (ja) | 1986-09-26 | 1986-09-26 | 図面情報管理方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS6381573A true JPS6381573A (ja) | 1988-04-12 |
| JP2644735B2 JP2644735B2 (ja) | 1997-08-25 |
Family
ID=16837249
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP61225938A Expired - Fee Related JP2644735B2 (ja) | 1986-09-26 | 1986-09-26 | 図面情報管理方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2644735B2 (ja) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH01233566A (ja) * | 1988-03-14 | 1989-09-19 | Fujitsu Ltd | 図形の座標管理方法 |
| JPH03174672A (ja) * | 1989-12-04 | 1991-07-29 | Ibiden Co Ltd | 画像データ登録方式 |
| JPH05266166A (ja) * | 1992-01-10 | 1993-10-15 | Internatl Business Mach Corp <Ibm> | 空間的に構成されたコンピュータ表示システムおよびコンピュータ実施方法 |
| JP2002324228A (ja) * | 2001-04-25 | 2002-11-08 | Dream Technologies Kk | データ管理装置及び地図データ記憶システム |
-
1986
- 1986-09-26 JP JP61225938A patent/JP2644735B2/ja not_active Expired - Fee Related
Non-Patent Citations (1)
| Title |
|---|
| A.GEOGRAPHIC.INFORMATION.SYSTEM.USING.QUADTREES=1984 * |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH01233566A (ja) * | 1988-03-14 | 1989-09-19 | Fujitsu Ltd | 図形の座標管理方法 |
| JPH03174672A (ja) * | 1989-12-04 | 1991-07-29 | Ibiden Co Ltd | 画像データ登録方式 |
| JPH05266166A (ja) * | 1992-01-10 | 1993-10-15 | Internatl Business Mach Corp <Ibm> | 空間的に構成されたコンピュータ表示システムおよびコンピュータ実施方法 |
| JP2002324228A (ja) * | 2001-04-25 | 2002-11-08 | Dream Technologies Kk | データ管理装置及び地図データ記憶システム |
Also Published As
| Publication number | Publication date |
|---|---|
| JP2644735B2 (ja) | 1997-08-25 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN105339931B (zh) | 用于处理数据容器的方法和设备 | |
| US8194974B1 (en) | Merge and removal in a planar map of an image | |
| JPH10124528A (ja) | 多次元データ管理方法、多次元データ管理装置、多次元データ管理プログラムを記録した媒体 | |
| JP3481296B2 (ja) | グラフィックスクリーン上の項目の選択方法 | |
| US5572637A (en) | Process for merging CAD vector files and automatically removing duplicate and obsolete patterns | |
| US4811244A (en) | Drawing information management system | |
| Castermans et al. | Agglomerative clustering of growing squares | |
| JPS6381573A (ja) | 図面情報管理方法 | |
| JP2001014338A (ja) | 図形データ管理方法およびシステム、記憶媒体 | |
| CN117931810B (zh) | 一种空间影像数据的结构化管理方法及系统 | |
| US20020154149A1 (en) | System, method and computer program product for associative region generation and modification | |
| JP2577397B2 (ja) | 図形表示装置 | |
| JP2590327B2 (ja) | 図面情報の管理方法 | |
| JP4001392B2 (ja) | 構造化文書処理装置 | |
| US7047511B2 (en) | Electronic circuit design | |
| JPH07296145A (ja) | 図形処理装置 | |
| Finke et al. | A spatial data model and a topological sweep algorithm for map overlay | |
| JPH04348468A (ja) | データベース装置 | |
| JPH11194480A (ja) | 描画用マスクパタンデータ生成方法とその装置 | |
| JP3647075B2 (ja) | 画像検索方法及びその装置 | |
| JPH10228492A (ja) | Ｃａｄシステム | |
| Nakamura et al. | Interactive Graphics and Spatial Data Management for GIS using the Hierarchical Data Structure | |
| KR20020030587A (ko) | 가상 시설레코드를 이용한 중첩시설물 정보 처리 장치 및그 방법 | |
| JPH07319874A (ja) | 文書処理装置 | |
| JPS63214831A (ja) | ワ−クステ−シヨンにおけるフアイルの管理方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |