JPH0668259A - 直近点検索方式 - Google Patents

Abstract

(57)【要約】 【目的】 不規則に散在する被検索点の中から任意に指
定された目標点との距離が最も近い点を高速に求める。 【構成】 被検索点が存在する領域を格子状に分割した
正方領域とその中に含まれる被検索点との対応表を作る
際に、正方領域を緩衝幅によって拡張する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は直近点検索方式、特に、
地図の情報をコンピュータ処理する地理情報システムの
直近点検索方式に関する。

【０００２】

【従来の技術】従来の技術は、被検索点が存在する領域
を格子上に分割する正方領域と、その領域に含まれるす
べての被検索点の対応表を事前に作成し、指定された目
標点が含まれる正方領域を求め、最初にその正方領域に
対応する被検索点について目標点との距離を求める処理
を行う方式が利用されていた。この方式では、一般的
に、事前に作成する対応表をコンピュータの外部記憶装
置上に格納し、指定された目標点が含まれる正方領域が
求まると対応する被検索点を主記憶装置上に取り出して
距離を求める処理を行う。

【０００３】

【発明が解決しようとする課題】従来の技術は、最初に
指定された目標点が含まれる正方領域に対応する被検索
点について目標点との距離を求める処理を行うが、一般
にこの段階で求められた最も近い点が目標点の直近であ
るとは限らず、目標点が含まれる正方領域のまわりの正
方領域に対応する被検索点についても距離をもとめる処
理を行う必要があることが多い。これは、指定された目
標点が、その目標点を含む正方領域の周辺部分に位置す
る場合に多く発生する。この方式では、一般に正方領域
とそれが含む被検索点の対応表は外部記憶装置上に格納
され、一個の正方領域に対応する被検索点の情報が一回
の外部記憶装置からの入力処理により取り出される。従
って、目標点が含まれる正方領域の被検索点に対してだ
けでなく、そのまわりの正方領域に対応する被検索点に
対する処理が必要になる場合には、目標点から直近の被
検索点を求めるために複数回の外部記憶装置からの入力
処理が必要になる。目標点が与えられてから直近の被検
索点が求められるまでの処理時間の多くは、外部記憶装
置からの入力処理の時間と考えられるため、緊急性を要
する会話型のシステムにおいてこの方式を使用する場
合、応答性能が問題となる。

【０００４】

【課題を解決するための手段】本発明の直近点検索方式
は、被検索点が存在する領域を格子状に分割する正方領
域（基本領域と呼ぶ）に緩衝領域を付加した正方領域
（拡張領域と呼ぶ）と拡張領域内に含まれるすべての被
検索点の対応を記述した拡張領域・被検索点対応表と、
指定された目標点から、その目標点が基本領域に含まれ
るような拡張領域を求める手段と、拡張領域・被検索点
対応表から特定の拡張領域に対応するすべての被検索点
を取り出す手段とを有する。

【０００５】

【実施例】次に、本発明について図面を参照して説明す
る。

【０００６】図１は本発明の一実施例の模式図である。
中央処理装置１は、拡張領域・被検索点対応表作成部
４、目標点入力部５、検索領域決定部６、拡張領域・被
検索点対応表入力部７、直近点計算部８により構成され
る。外部記憶装置２は、被検索点情報９、基本領域情報
１０、拡張領域・被検索点対応表１１により構成され
る。

【０００７】拡張領域・被検索点対応表作成部４は、外
部記憶装置２上に格納された被検索点情報９、基本領域
情報１０を参照して、拡張領域・被検索点対応表１１を
外部記憶装置２上に作成する。この作業は、直近点検索
の準備作業として、事前に行われる。目標点入力部５
は、座標入力装置３から目標点の座標を入力する。検索
領域決定部６は、目標点の座標から、基本領域が目標点
を含むような拡張領域を求める。拡張領域・被検索点対
応表入力部７は、外部記憶装置２上の拡張領域・被検索
点対応表１１を参照して、指定された拡張領域に対応す
る被検索点の情報を入力する。直近点計算部８は、与え
らえた被検索点の中から目標点に直近の被検索点を求め
る。被検索点情報９にはすべての被検索点の座標が格納
される。基本領域情報１０には、被検索点が存在する領
域を格子状に分割するすべでの基本領域の四隅の座標が
格納される。格調領域・被検索点対応表１１には、拡張
領域とその中に含まれるすべての被検索点の対応情報が
格納される。

【０００８】図２は、図１に示す拡張領域・被検索点対
応表作成部４の動作のフローを示している。ステップ１
２は、未処理の基本領域が存在するかどうかのチェック
であり、すべての基本領域に対して処理が終了していれ
ば、拡張領域・被検索点対応表作成部４の動作は終了す
る。未処理の基本領域が存在する場合、ステップ１３
で、基本領域情報１０から先頭の基本領域が取り出され
る。ステップ１４では、被検索点情報９が参照され、ス
テップ１３で取り出された基本領域に含まれるすべての
被検索点が求められる。ステップ１５では、ステップ１
３で取り出された基本領域において、ステップ１４で求
められた被検索点の中で最も近い被検索点までの距離が
最大となるような点を求める。ステップ１６では、ステ
ップ１５の処理で求められた点とその点に最も近い被検
索点との距離を緩衝幅として、ステップ１３で取り出さ
れた基本領域から格調領域を生成し、被検索点情報９を
参照して拡張領域に含まれるすべての被検索点を求め
る。ステップ１７では、ステップ１６で求められた拡張
領域と拡張領域に含まれる被検索点の対応情報が拡張領
域・被検索点対応表１１に出力されて、一個の基本領域
に関する処理が終了し、以後ステップ１２からの繰り返
しとなる。

【０００９】図３は、本発明の一実施例における直近点
検索の処理フローを示している。まず、ステップ１８で
目標点入力部５が、座標入力装置３から利用者が指定し
た目標点の座標を取り込む。次にステップ１９で、検索
領域決定部６により、目標点が基本領域に含まれるよう
な拡張領域が求められる。ステップ２０では、拡張領域
・被検索点対応表入力部７により、ステップ１９で求め
られた拡張領域に対応する被検索点の情報が拡張領域・
被検索点対応表１１から取り込まれる。ステップ２１で
は、ステップ２０で取り込まれた被検索点の中から目標
点に最も近い点が求められる。

【００１０】

【発明の効果】以上説明したように、本発明の直近点検
索方式は、直近点を求める際に発生する外部記憶装置か
らの入力処理は、常に一回だけである。そのため直近点
を求める際の応答性能が安定しており、緊急性を用する
システムにおいても問題なく使用することが可能であ
る。

【図面の簡単な説明】

【図１】本発明の一実施例を示す模式図である。

【図２】拡張領域・被検索点対応表作成の処理フロー図
である。

【図３】直近点検索の処理フロー図である。

【符号の説明】

１ 中央処理装置 ２ 外部記憶装置 ３ 座標入力装置 ４ 拡張領域・被検索点対応表作成部 ５ 目標点入力部 ６ 検索領域決定部 ７ 拡張領域・被検索点対応表入力部 ８ 直近点計算部 ９ 被検索点情報 １０ 基本領域情報 １１ 拡張領域・被検索点対応表

Claims (1)

【特許請求の範囲】
1. 【請求項１】 不規則に散在する被検索点の中から、任
   意に指定された目標点との距離が最も近い点を求める直
   近点検索方式において、被検索点が存在する領域を格子
   状に分割する正方領域（基本領域と呼ぶ）に緩衝領域を
   付加した正方領域（拡張領域と呼ぶ）と拡張領域内に含
   まれるすべての被検索点の対応を記述した拡張領域・被
   検索点対応表と指定された目標点からその目標点が基本
   領域に含まれるような拡張領域を求める手段と、拡張領
   域・被検索点対応表から特定の拡張領域に対応するすべ
   ての被検索点を取り出す手段とを有することを特徴とす
   る直近点検索方式。