(57)【特許請求の範囲】
【請求項１】
所定の座標上での任意の位置を測定し得る座標位置測定手段により測定して得られた前記所定の座標上の測定位置が、広域から狭域の複数の階層化されたデータ構造に分類された領域の何れに属するかを検索する階層分類領域検索方法であって、
前記所定の座標に従って位置が規定され、かつ階層的に分類された階層領域に関する座標情報を記憶する階層領域情報記憶ステップと、
前記記憶された座標情報に基づいて、前記測定位置が前記階層化された階層領域の１つに属するか否かを、前記座標情報と、前記１つの階層領域に対して該領域の外部に設けられた参照位置の座標情報とを用いて演算して判定する領域判定演算ステップと、
前記領域判定演算ステップによる演算結果に基づいて、前記測定位置が前記階層的に分類された領域の１つに属するかを検索する階層的検索ステップと、
前記階層的検索ステップによって検索した検索結果を表示する表示ステップと
を具え、
前記階層的検索ステップは、
前記階層的に分類された領域のうちの１つの階層領域を選択し、選択された前記１つの階層領域に前記測定位置が属さないと、前記領域判定演算ステップにより判定されたとき、当該１つの階層領域より広い面積の階層の階層領域を選択して検索を行い、前記領域判定演算手段により選択された前記より広い面積の階層の階層領域に前記測定位置が属すると判定されるまで前記より広い面積の階層における階層領域の選択を繰り返し、前記測定位置が属すると判定されたとき、前記より広い面積の階層の階層領域に属する複数のより狭い階層の領域の各々について、前記測定位置が何れに属するかを前記領域判定演算ステップにより判定し、当該判定された前記より狭い階層の階層領域について、該より狭い階層の階層領域を構成する複数のさらにより狭い階層の階層領域について前記測定位置が属する階層領域を前記領域判定演算ステップにより判定し、前記測定位置が属すると判定された最狭の階層の階層領域を検索結果とし、選択された前記１つの階層領域に前記測定位置が属すると前記領域判定演算ステップにより判定されたときは、より狭い面積の階層の階層領域を順次に選択して検索を行い前記領域判定演算ステップにより判定し、前記測定位置が属すると判定された最狭の階層の階層領域を前記検索結果とし、
前記領域判定演算ステップは、
前記検索対象となった階層領域内の任意の１つの住所領域に対して外部に設定された参照位置を始点としかつ前記測定位置を終点とする第１のベクトルと、前記参照位置を始点としかつ前記任意の１つの住所領域を囲む複数の線分の任意の１つの線分の両端の位置を終点とする第２及び第３のベクトルとから、前記第２のベクトルと前記第１のベクトルとの外積、及び前記第２のベクトルと前記第３のベクトルとの外積を算出し、該外積の正負により、前記第２のベクトルが形成する線分を延長した直線で分割される２領域に対して前記測定位置と前記第３のベクトルの終点の位置とが同一領域に存在するか否かを判定し、前記同一領域に存在しないと判定したとき当該領域判定演算処理を終了させるのに対して前記同一領域に存在すると判定したとき次の判定ステップに進む第１の判定ステップと、
前記第３のベクトルと前記第１のベクトルとの外積、及び前記第３のベクトルと前記第２のベクトルとの外積を算出することにより、前記第３のベクトルを形成する線分を延長した直線で分割される２領域に対して前記測定位置と前記第２のベクトルの終点の位置が同一領域に存在するか否かを判定し、前記同一領域に存在しないと判断したとき当該領域判定演算処理を終了させるのに対して上記同一領域に存在すると判定したとき次の判定ステップに進む第２の判定ステップと、
次に、前記任意の１つの領域を囲む複数の線分の任意の１つの線分の一端の位置を始点としかつ前記参照位置を終点とする第４のベクトルと、前記任意の１つの領域を囲む複数の線分の任意の１つの線分の一端の位置を始点としかつ前記測定位置を終点とする第５のベクトルと、前記任意の１つの住所領域を囲む複数の線分の任意の１つの線分の一端の位置を始点としかつ他端を終点とする第６のベクトルとから、前記第６のベクトルと前記第４のベクトルとの外積、及び前記第６のベクトルと前記第５のベクトルとの外積を算出することにより、前記第６のベクトルを形成する線分を延長した直線により分割される２領域に対して前記参照位置と前記測定位置が異なる領域に存在するか否かを判定する第３の判定ステップと、
前記第１の判定ステップと前記第２の判定ステップと前記第３の判定ステップとにより前記任意の１つの住所領域を囲む複数の線分の任意の１つの線分が、前記参照位置と前記測定位置を結ぶ線分と交わる交点があるか否かを判定する交点判定ステップと
を具備することを特徴とする階層分類領域検索方法。
【請求項２】
前記領域判定演算ステップが、前記階層的に分類された領域の任意の１つの領域に対して外部に設定された参照位置と前記測定位置とを結ぶ線分と、前記任意の１つの領域を囲む線分との交点の数が奇数のとき、該測定位置は前記任意の１つの領域の内部に存在すると判定し、前記参照位置と前記測定位置とを結ぶ線分と、前記任意の１つの領域を囲む線分との交点が偶数のとき、前記測定位置は前記任意の１つの領域の外部に存在すると判定することを特徴とする請求項１に記載の階層分類領域検索方法。
【請求項３】
所定の座標上での任意の位置を測定し得る座標位置測定手段により測定して得られた前記所定の座標上の測定位置が、広域から狭域の複数の階層化されたデータ構造に分類された領域の何れに属するかを検索する階層分類領域判定装置であって、
前記所定の座標に従って位置が規定され、かつ階層的に分類された階層領域に関する座標情報を記憶する階層領域情報記憶手段と、
前記記憶された座標情報に基づいて、前記測定位置が前記階層化された階層領域の１つに属するか否かを、前記座標情報と、前記１つの階層領域に対して該領域の外部に設けられた参照位置の座標とを用いて演算して判定する領域判定演算手段と、
前記領域判定演算手段による演算結果に基づいて、前記測定位置が前記階層的に分類された領域の１つに属するか否かを検索する階層的検索手段と、
前記階層的検索手段によって検索した検索結果を表示する表示手段と
を具え、
前記階層的検索手段は、
前記階層的に分類された領域のうちの１つの階層領域を選択し、選択された前記１つの階層領域に前記測定位置が属さないと、前記領域判定演算手段により判定されたとき、当該１つの階層領域より広い面積の階層の階層領域を選択して検索を行い、前記領域判定演算手段により選択された前記より広い面積の階層の階層領域に前記測定位置が属すると判定されるまで前記より広い面積の階層における階層領域の選択を繰り返し、前記測定位置が属すると判定されたとき、前記より広い面積の階層の領域に属する複数のより狭い階層の階層領域の各々について、前記測定位置が何れに属するかを前記領域判定演算手段により判定し、当該判定された前記より狭い階層の階層領域について、該より狭い階層の階層領域を構成する複数のさらにより狭い階層の階層領域について前記測定位置が属する階層領域を前記領域判定演算手段により判定し、前記測定位置が属すると判定された最狭の階層の階層領域を検索結果とし、選択された前記１つの階層領域に前記測定位置が属すると前記領域判定演算手段により判定されたときは、より狭い面積の階層の階層領域を順次に選択して検索を行い前記領域判定演算手段により判定し、前記測定位置が属すると判定された最狭の階層の階層領域を前記検索結果とし、
前記領域判定演算手段は、
前記検索対象となった階層領域内の任意の１つの住所領域に対して外部に設定された参照位置を始点としかつ前記測定位置を終点とする第１のベクトルと、前記参照位置を始点としかつ前記任意の１つの住所領域を囲む複数の線分の任意の１つの線分の両端の位置を終点とする第２及び第３のベクトルとから、前記第２のベクトルと前記第１のベクトルとの外積、及び前記第２のベクトルと前記第３のベクトルとの外積を算出し、該外積の正負により、前記第２のベクトルが形成する線分を延長した直線で分割される２領域に対して前記測定位置と前記第３のベクトルの終点の位置とが同一領域に存在するか否かを判定し、前記同一領域に存在しないと判定したとき当該領域判定演算処理を終了させるのに対して前記同一領域に存在すると判定したとき次の判定ステップに進む第１の判定手段と、
前記第３のベクトルと前記第１のベクトルとの外積、及び前記第３のベクトルと前記第２のベクトルとの外積を算出することにより、前記第３のベクトルを形成する線分を延長した直線で分割される２領域に対して前記測定位置と前記第２のベクトルの終点位置とが同一領域に存在するか否かを判定し、前記同一領域に存在しないと判断したとき当該領域判定演算処理を終了させるのに対して前記同一領域に存在すると判定したとき次の判定ステップに進む第２の判定手段と、
次に、前記任意の１つの住所領域を囲む複数の線分の任意の１つの線分の一端の位置を始点としかつ前記参照位置を終点とする第４のベクトルと、前記任意の１つの住所領域を囲む複数の線分の任意の１つの線分の一端の位置を始点としかつ前記測定位置を終点とする第５のベクトルと、前記任意の１つの住所領域を囲む複数の線分の任意の１つの線分の一端の位置を始点としかつ他端を終点とする第６のベクトルとから、前記第６のベクトルと前記第４のベクトルとの外積、及び前記第６のベクトルと前記第５のベクトルとの外積を算出することにより、前記第６のベクトルを形成する線分を延長した直線により分割される２領域に対して前記参照位置と前記測定位置とが異なる領域に存在するか否かを判定する第３の判定手段と、
前記第１の判定手段と前記第２の判定手段と前記第３の判定手段とにより前記任意の１つの住所領域を囲む複数の線分の任意の１つの線分が、前記参照位置と前記測定位置を結ぶ線分と交わる交点があるか否かを判定する交点判定手段と
を具備することを特徴とする記載の階層分類領域判定装置。
【請求項４】
前記領域判定演算手段が、前記階層的に分類された領域の任意の１つの領域に対して外部に設定された参照位置と前記測定位置とを結ぶ線分と、前記任意の１つの領域を囲む線分との交点の数が奇数のとき、該測定位置は前記任意の１つの領域の内部に存在すると判定し、前記参照位置と前記測定位置とを結ぶ線分と、前記任意の１つの領域を囲む線分との交点が偶数のとき、前記測定位置は前記任意の１つの領域の外部に存在すると判定することを特徴とする請求項３に記載の階層分類領域判定装置。
【請求項５】
請求項３に記載の階層分類領域判定装置を具備した
ことを特徴とするナビゲーション装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、階層分類領域検索方法及び判定装置に関し、特に現在の位置が階層分類された領域の何れの領域に属するかを判定するものである。
【０００２】
【従来の技術】
従来、ＧＰＳ装置等の座標位置測定手段において、任意の点（以下位置と記す）の表示には、北緯３５度３７分３７秒、東経１３９度４４分５０秒というように緯度経度を使い、図１３のような緯度経度の記載された紙上地図や電子地図上での位置確認を行っている。
【０００３】
また、図１４は従来のナビゲーション機器を示したもので、電子地図を表示するために、電子地図記憶装置１および電子地図表示装置２等が必要であり、また、従来ＧＰＳ装置６により得られた任意の位置がいずれの住所領域に所属するかを調べるには、ＣＰＵ３、メモリ４、電子地図制御装置５等で構成される検索手段により単純に検索対象の住所領域をすべて検索している。
【０００４】
また、緯度経度から住所を検索する際に用いられる住所判定方法については、図１５のように、現在地Ｐの緯度経度と住所の代表点Ｋi（ｉ ＝１〜４）の緯度経度との距離差が一番小さい住所をＧＰＳ装置６等の座標位置測定手段において得られた現在の位置の属する住所と判定することが一般的である。
【０００５】
【発明が解決しようとする課題】
しかしながら、図１３のような緯度経度の記載された紙上地図や電子地図上での緯度経度を用いた位置確認は非常に煩雑であるという問題がある。寧ろ知りたいのは現在の位置の緯度経度よりも、地図上の如何なる住所に現在位置が属するのかということである。
【０００６】
図１４のような緯度経度を表示できる電子地図記憶装置１および電子地図表示装置２等は大規模で複雑であり、また、従来任意の点がいずれの住所領域に所属するかを調べるために、単純に検索対象の住所領域をすべて評価するという検索方法では、対象となる住所領域の数が増えるに従って、その検索に要する処理は膨大となり、検索手段の構成規模や検索速度も大きいものになるという問題がある。
【０００７】
さらに、図１５のように、現在地Ｐの緯度経度と住所の代表点Ｋi（ｉ ＝１〜４）の緯度経度との距離差が一番小さい住所をＧＰＳ装置等の座標位置測定手段において得られた現在の位置の属する住所と判定するという判定方法では、複雑な境界線を持った住所領域などでは、間違った住所表示を行うことがある。例えば、図１５に示したように、現在地Ｐと各領域代表点Ｋi との距離を求めると、Ｋ1 が一番近いことになる。そのため、実際は港南２丁目にいるにも関らず、現在地が港南１丁目と判断され誤った判定結果を示してしまうという問題がある。
【０００８】
本発明はこのような点に鑑みてなされたものであり、座標位置測定手段によって得られた所定の座標上の位置が、如何なる階層的に分類された領域に属するか、例えば上述の例では、ＧＰＳ装置により得られた現在地Ｐの緯度経度が、如何なる住所に属するかを高速且つ正確に検索及び判定する小型、低消費電力で、検索結果を簡単明瞭に判断し得る階層分類領域判定装置及びこれを具備した位置測定可能な一般機器を提供することを課題とする。
【０００９】
【課題を解決するための手段】
上述の課題を達成するために、本発明においては、所定の座標上での任意の位置を測定し得る座標位置測定手段により測定して得られた所定の座標上での任意の測定位置が、より広い領域に複数のより狭い領域が含まれるというように、階層的に分類された領域の何れに属するかを判定する階層分類領域判定装置において、所定の座標に従って位置が規定され、且つ階層的に分類された領域に関する座標情報を記憶する階層領域情報記憶手段と、所定の座標上での任意の位置が階層的に分類された領域の任意の一つに属するか否かを座標情報と、階層的に分類された領域の任意の一つに対して外部に設けられた参照位置と測定位置との間に形成されたベクトルの外積演算とを用いて演算して判定する領域判定演算手段と、所定の座標上での任意の位置が階層的に分類された領域の中、何れの領域に属するかを、領域判定演算手段の出力をもとに階層的に検索する階層的検索手段と、階層的検索手段の検索した検索結果を表示する表示手段とを設けるようにする。
【００１０】
また、本発明の望ましい形態としては、下記、１）〜３）である。
１）階層的検索手段が、階層的に分類された領域の任意の一つの領域を選択し、選択された任意の一つの領域に所定の座標上での任意の位置が属さないと、領域判定演算手段により判定されたときは、任意の一つの領域より広い面積の階層の領域を選択して検索を行い、選択された前記より広い面積の階層の領域に所定の座標上での任意の位置が属すると、領域判定演算手段により判定されるまでより広い面積の階層の領域の選択を繰り返し、所定の座標上の任意の位置が属すると判定されたより広い面積の階層の領域に属する複数のより狭い階層の領域の各々について、所定の座標上での任意の位置が何れに属するかを領域判定演算手段により判定し、所定の座標上での任意の位置が属すると判定されたより狭い階層の領域について、より狭い階層の領域を構成する複数のさらにより狭い階層の領域について所定の座標上での任意の位置が属する領域を領域判定演算手段により判定し、所定の座標上の任意の位置が属すると判定された最狭の階層の領域を検索結果とし、選択された任意の一つの領域に所定の座標上での任意の位置が属すると、領域判定演算手段により判定されたときは、より狭い面積の階層を順次に選択して検索を行い領域判定演算手段により判定し、所定の座標上の任意の位置が属すると判定された最狭の階層の領域を前記検索結果とするものである。
【００１１】
２）領域判定演算手段が、階層的に分類された領域の任意の一つの領域に対して外部に設定された参照位置を始点として、所定の座標上の任意の位置を終点とする第１のベクトルと、参照位置を始点として、任意の一つの領域を囲む複数の線分の任意の一つの線分の両端の位置を終点とする第２及び第３のベクトルとから、第２のベクトルと第１のベクトルの外積、及び第２のベクトルと第３のベクトルの外積を算出し、外積の正負により、第２のベクトルが形成する線分を延長した直線で分割される２領域に対して所定の座標上の任意の位置と第３のベクトルの終点の位置が同一領域に存在するか否かを判定し、第３のベクトルと第１のベクトルとの外積、及び第３のベクトルと第２のベクトルとの外積を算出することにより、第３のベクトルを形成する線分を延長した直線で分割される２領域に対して所定の座標上の任意の位置と第２のベクトルの終点の位置が同一領域に存在するか否かを判定し、
【００１２】
次に、任意の一つの領域を囲む複数の線分の任意の一つの線分の一端の位置を始点とし、参照位置を終点とする第４のベクトルとし、任意の一つの領域を囲む複数の線分の任意の一つの線分の一端の位置を始点とし、所定の座標上の任意の位置を終点とする第５のベクトルと、任意の一つの領域を囲む複数の線分の任意の一つの線分の一端の位置を始点とし、他端を終点とする第６のベクトルとから、第６のベクトルと第４のベクトルの外積、及び第６のベクトルと第５のベクトルの外積を算出することにより、第６のベクトルを形成する線分を延長した直線により分割される２領域に対して参照位置と所定の座標上の任意の位置が異なる領域に存在するか否かにより、任意の一つの領域を囲む複数の線分の任意の一つの線分が、参照位置と所定の座標上の任意の位置を結ぶ線分と交わる交点があるか否かを判定するものである。
【００１３】
３）領域判定演算手段が、階層的に分類された領域の任意の一つの領域に対して外部に設定された参照位置と所定の座標上の位置とを結ぶ線分と、任意の一つの領域を囲む線分との交点の数が奇数のとき、座標上の位置は任意の一つの領域の内部に存在すると判定し、参照位置と所定の座標上の位置とを結ぶ線分と、任意の一つの領域を囲む線分との交点が偶数のとき、所定の座標上の位置は任意の一つの領域の外部に存在すると判定するものである。
【００１４】
以下上述した手段の作用について説明する。
面積により階層的に分類された領域に関する情報、東京都の地図の例を挙げるならば、東京都という最上位階層、港区という次位階層、番地という最下位層に分類された領域を囲む線分の座標情報及びその領域に対する参照位置情報を階層領域情報記憶手段に記憶しておき、座標位置測定手段により得られた任意の座標位置が、上述の階層的に分類された領域の何れに属するかを上述の階層的に分類された領域を囲む線分の座標情報及び参照位置を用いて領域判定演算手段により判定し、且つ判定結果を基にして階層的検索手段により階層的に検索を行う。
【００１５】
【発明の実施の形態】
以下図１〜図１２を参照して本発明の階層分類領域判定装置及びこれを具備した位置測定可能な一般機器の実施の形態例について説明する。
本実施の形態例ではＧＰＳ装置により測定された現在位置が地図上のどの住所に属するか検索し判定する事例を説明するが、本発明の階層分類領域判定装置及びこれを具備した位置測定可能な一般機器はこれに限るものではなく、所定の座標上の任意の位置を測定し得る座標位置測定手段により測定して得られた任意の位置が、階層的に分類された領域の何れに属するかを検索し判定する一般の階層分類領域判定装置及びこれを具備した位置測定可能な一般機器に適用できるものである。また、本実施の形態例を説明するにあたり、従来の技術と同様な構造をなすものについては同一の符号を付するものとする。
【００１６】
図１は本実施の形態例の全体の構成を示したものである。位置測定可能な一般機器の例としてのナビゲーション機器１６はＧＰＳ装置６及び階層分類領域判定装置１５から構成され、さらに、階層分類領域判定装置１５は、表示装置１４、表示制御装置１３、ＣＰＵ３、メモリ４、階層領域情報記憶手段１７で構成されており、図示は省略するが、ＣＰＵ３、メモリ４は請求項１で述べた領域判定演算手段及び階層的検索手段を、メモリ４に搭載されるプログラムにより実現する。メモリ４はこの他にナビゲーション機器１６の全体の制御を行うための情報を格納し、ＣＰＵ３はメモリ４に格納された情報を読み出してナビゲーション機器の全体の制御を行う。
【００１７】
次に、本実施の形態例の動作を説明する。まず、ＧＰＳ装置６で測定された緯度経度情報はＣＰＵ３に送られ、ＣＰＵ３では階層領域情報記憶手段１７に記憶された住所情報を用いて住所検索を行う。検索された結果の住所情報を表示制御装置１３を介して表示装置１４に表示する。表示装置１４に表示する住所情報としては文字であってもよいし、住所を示す図形であっても構わない。
【００１８】
図２は階層分類領域判定装置１５の、図示を省略する階層的検索手段の動作をフローチャートで示したものである。以下文章の途中にステップＳ１〜Ｓ８を挿入しながらフローチャートについて説明する。まず、ＧＰＳ装置６で緯度経度の位置情報が得られ階層的検索手段に入力される（Ｓ１）。つぎに任意の検索領域をひとつ選択し（Ｓ２）、その領域内にＧＰＳ装置６で測定された位置が含まれているかの判定をする（Ｓ３）。
【００１９】
この判定の結果、選択領域に含まれていないと判定された場合は、同一階層内の全領域の検索が終了したかどうかを次に判定する（Ｓ４）。この判定の結果、同一階層内の検索がまだ終了していない場合は、検索対象領域を変更し（Ｓ２）、再び領域内判断を行う（Ｓ３）。
【００２０】
同一階層内の検索が終了している場合は、検索対象の階層を広域化し（Ｓ５）検索対象領域を選択し（Ｓ２）、再び領域内判定を行い、これを繰り返して、ＧＰＳ装置６で測定された位置が含まれていると判定された住所領域の位置情報が選択された領域内に含まれると判定された場合は（Ｓ３）、検索対象領域の階層がこれ以上の狭域の領域がないかどうかを判定し（Ｓ６）、これ以上の狭域階層がない場合には、選択された住所領域の情報、例えば名称を文字表示し（Ｓ８）終了となる。
【００２１】
選択対象領域がこれ以上の狭域階層を持つ場合には（Ｓ６）、さらに階層を狭域化して検索領域を変更し（Ｓ７）領域内判断を行う（Ｓ２）。このようにして、ＧＰＳ装置６で測定された緯度経度の位置情報が最も狭い狭域階層領域内にあると判定されるまで、この判定の繰り返しを続けていく。そして、位置情報が最も狭い狭域階層領域内にあると判定された場合は、その選択された領域の名称を表示し、住所検索の動作を終了する。
【００２２】
上述のように、階層的検索手段が、階層的に分類された領域の任意の一つを選択し検索領域の初期領域とし、選択された検索領域にＧＰＳ装置６で測定された位置が属さないときは、広域化した階層の領域を順次に選択して検索を行い、ＧＰＳ装置６で測定された位置が属する領域を判定し、当該領域を構成する複数のより狭い領域の各々について検索し、ＧＰＳ装置６で測定された位置が属する領域を判定し、判定された領域を構成するさらに狭い複数の領域について同様に検索を行い、最終的に最も狭い階層の領域として判定された領域を検索結果として表示し、選択された初期領域にＧＰＳ装置６で測定された位置が属する場合は、より狭域化した階層を順次に選択して検索を行い、最終的に最も狭い階層の領域として判定された領域を検索結果として表示する。
【００２３】
図３はこの階層化された領域の例を示したものである。都道府県に代表される階層があり、それぞれ、都道府県境でかこまれた領域を持っている。この例と、図３の階層分類領域判定装置１５の図示を省略する階層的検索手段の動作を示したフローチャートを用いて階層化された領域の検索手順について説明する。
【００２４】
この階層内で、例えば北緯３５度３７分３７秒、東経１３９度４４分５０秒という位置が含まれる領域を検索すると、東京都に含まれると判断される。次に、この東京都の階層はまだ狭域な領域すなわち、市区町村の階層を持っている。そのため、階層を狭域化し、市区町村の階層にて領域の検索を行う。その結果、港区の領域内にその位置が含まれると判定される。
【００２５】
次に、同様にして最も狭い最狭階層かどうか調べると、まだ丁の階層を持っていることがわかる。従って、さらに階層を狭域化し、領域を検索する。その結果、港南１丁目にその位置が含まれることがわかり、これ以上狭い階層が無いことから、この港南１丁目の検索結果が求められたことになる。
【００２６】
次に、図１で参照した階層分類領域判定装置１５の、図示を省略する領域判定演算手段が、ＧＰＳ装置６で測定された位置が選択された階層の領域内にあるかどうかを判定する動作について詳細に説明する。
まず、領域の内外の判定に使う座標情報について図４及び図５を参照して説明する。住所の領域は、通常、複数の線分により囲まれている。ここで、この領域の境界線を単純な線分の集まりとする近似を行うことで、線分とその頂点による近似領域が得られる。頂点の数が多ければ、より近似領域が実際の領域に近づくが、領域を表すための情報量がより多く必要となる。逆に、頂点の数が少なければ、近似領域と実際の領域の差が大きくなるが、領域を表すための情報量は少なくて済む。
【００２７】
この情報量と領域精度は単純にはトレードオフの関係にあるので、目的に応じてその適度な値を選択する必要がある。図４に、ある住所領域を近似した状況を示した。この図４から、港南１丁目は点Ｐ1-1、点Ｐ1-2、点Ｐ1-3、点Ｐ1-4、点Ｐ1-5、点Ｐ1-6  が構成する線分によって囲まれていることが示されている。その他の住所領域も、それぞれの示されている頂点により囲まれていることが示されている。図５は、このような住所の領域の線分による符号情報化の例を示したものである。
【００２８】
上述のように、まず住所の領域を単純な線分で囲まれた領域で近似し、次に近似された領域内に評価される位置があるか否かを判定する。そして、実際にこの近似された住所の領域内にＧＰＳ装置６で測定された位置があるか否かを判定するには以下に説明する階層分類領域判定装置１５の図示を省略する領域判定演算手段の動作ステップが必要となる。
【００２９】
図６に線分で囲まれて近似された住所の領域Ｐi（ｉ ＝１−１，１−２，…）と、ＧＰＳ装置６で測定された位置Ｐe、そして領域外である参照位置Ｐrefを示した。後述する交点（Ｘで示す）の数について説明するために、領域外の点Ｐouti（ｉ＝１〜４）も示している。ここで、位置Ｐeと参照位置Ｐrefを結ぶ線分と住所の領域Ｐiの各線分との交点の数を調べることにより、位置Ｐeが住所の領域Ｐiの内外にあるか否かの判定を行うことができる。
【００３０】
すなわち、図６に示すように、位置Ｐeが近似された住所の領域Ｐiの内部にある場合は、位置Ｐeと住所の領域Ｐiの各線分との交点の数が奇数であり、位置Ｐeが住所の領域Ｐiの外（Ｐouti）にある場合はその交点の数が偶数である。
【００３１】
この判定方法は、内角が１８０度以上の角を持つ多角形でも有効であり、常に、位置Ｐeと参照位置Ｐrefを結ぶ線分が住所の領域Ｐi の各線分と交わる点の数を調べるだけで、住所の領域Ｐiの内外の判定を容易に行うことができる。
【００３２】
図６では、実際に位置Ｐｅと参照位置Ｐｒｅｆを結ぶ線分は住所Ｐｉの線分（Ｐ１−４，Ｐ１−５）と１回だけ交わっているので、位置Ｐｅは、住所の領域Ｐｉの内部であるといえる。住所の領域Ｐｉの外部の点、またＰｏｕｔ１は、住所の領域Ｐｉ（Ｐ１−３，Ｐ１−２）及び（Ｐ１−４，Ｐ１−５）と交わるため交点の数が２個で偶数であるから、住所の領域Ｐｉの外部と判定される。他の住所の領域Ｐｉの外部の点Ｐｏｕｔ１も同様に住所の領域Ｐｉを含む線分との交点数を数えると、すべて偶数であることが判る。このようにして、住所の領域Ｐｉの内部にＧＰＳ装置６で測定された位置Ｐｅがあるか否かの判定が非常に簡単に行うことができる。
【００３３】
次に、上述した交点の有無を判定する方法ついて説明する。説明をわかりやすくするために、最初に、任意のベクトルに対して、任意の２点の位置関係が如何になるかを説明することから始める。そのために、外積ベクトルの後述するＺ成分の符号を調べる方法について説明する。
【００３４】
図７及び図８は、任意の３個のベクトル（Ｐ１，Ｐｅ１），（Ｐ１，Ｐｅ２），（Ｐ１，Ｐ２）について任意の点（Ｐ１，Ｐｅ１，Ｐｅ２，Ｐ２）の位置関係を説明しようとするものである。図７は、（Ｐ１，Ｐ２）ベクトルに対して、点Ｐｅ１，Ｐｅ２が同じ側にある状態を示している。すなわち、点Ｐ１と点Ｐ２を結ぶ線分を延長して得られた直線により分割された２つの領域の中、同一の領域に点Ｐｅ１，Ｐｅ２は属している。
【００３５】
このとき、（Ｐ１，Ｐ２）ベクトルと（Ｐ１，Ｐｅ１）ベクトルの外積ベクトルは、右手系においては紙面下から上方向である。また（Ｐ１，Ｐ２）ベクトルと（Ｐ１，Ｐｅ２）ベクトルの外積ベクトルも、同様にして右手系においては紙面下から上方向である。従って、任意のベクトルに対して任意の２点が同じ側にある場合には、それぞれの外積のＺ成分（紙面に垂直な座標軸、以下同様）の符号が同じであることがわかる。
【００３６】
図８は、（Ｐ１，Ｐ２）ベクトルに対して、点Ｐｅ１，Ｐｅ２が反対側にある状態を示している。このとき、（Ｐ１，Ｐ２）ベクトルと（Ｐ１，Ｐｅ１）ベクトルの外積ベクトルは、右手系においては紙面下から上方向である。また（Ｐ１，Ｐ２）ベクトルと（Ｐ１，Ｐｅ２）ベクトルの外積ベクトルは、右手系においては紙面上から下方向である。従って、任意のベクトルに対して任意の２点が反対側にある場合には、それぞれの外積のＺ成分の符号が異なることがわかる。図１２にａ(a1,a2,a3)ベクトルと、ｂ(b1,b2,b3)ベクトルの外積計算式を示す。
【００３７】
次に、上述の説明を基にして階層分類領域判定装置１５の図示を省略する領域判定演算手段が、ＧＰＳ装置６により測定された位置Ｐeと参照位置Ｐrefを結ぶ線分と住所の領域Ｐi の線分との間に交点を持つか否かを判定する動作について図９のフローチャート及び図１０，１１を参照して説明する。図９のフローチャートは図２を参照して説明したと同様にステップＳを文章に挿入して説明する。
【００３８】
図１０で、（Ｐref，Ｐi）ベクトルに対して、ＰeとＰi+1とが同じ側かどうかを、前述の外積計算により判定する（Ｓ９）。ＰeとＰi+1とが同じ側に無ければ、交点が無いことが示されたことになり、評価はここで終わる。図１０ではＰe とＰi+1とが同じ側にあるのでＹＥＳと判定される（Ｓ９）。
【００３９】
次に（Ｐref，Ｐi+1）ベクトルに対して、ＰeとＰiとが同じ側にあるか、前述の外積計算により判定する（Ｓ１０）。ＰeとＰiとが同じ側にない場合は、交点がないことになり評価はここで終わる。図１０ではＰeとＰiとが同じ側であるのでＹＥＳと判定される（Ｓ１０）。
【００４０】
最後に、（Ｐi，Ｐi+1）ベクトルに対して、ＰeとＰrefが反対側にあるか、前述の外積計算により判定する（Ｓ１１）。ここでＰeとＰrefが同じ側にあると、交点がないことになり評価は終了する。図１１で示すように、ＰeとＰrefとは反対側にあるのでＹＥＳと判定され、線分（Ｐi，Ｐi+1）と線分（Ｐref，Ｐe）は交点を持つことになる（Ｓ１２）。
【００４１】
上述のように、住所の領域Ｐｉを構成する一つの線分とＧＰＳ装置６で測定された位置Ｐｅと参照位置Ｐｒｅｆを結ぶ線分との交点の有無を調べ、住所の領域Ｐｉを構成する残りの線分についても同様な手順を行うことで、住所の領域Ｐｉを構成する各線分とＧＰＳ装置６で測定された位置Ｐｅと参照位置Ｐｒｅｆを結ぶ線分との全ての交点の有無を判定することができる。その結果、前述したように、交点数が奇数の場合はＧＰＳ装置６で測定された位置Ｐｅは住所の領域Ｐｉの内部に位置し、交点数が偶数の場合には、ＧＰＳ装置６で測定された位置Ｐｅは住所の領域Ｐｉの外部に位置することが判定できる。
【００４２】
以上本発明の階層分類領域判定装置について説明したが、本発明の階層分類領域判定装置は上述したようなＧＰＳ装置６のみならず、一般に所定の座標上での任意の位置測定が可能な座標位置測定手段を具備した位置測定可能な一般機器に搭載して、現在の位置が、予め知られている図形上のどの領域に属するかを判定する場合にも適用できる。例えば、顕微鏡で観測した集積回路上での探針の位置が既知の集積回路の図形パターンのどの部分に属しているかは、顕微鏡が探針の位置の座標を測定でき、且つ集積回路の図形パターンが顕微鏡の座標に従って規定されていれば本発明の階層分類領域判定装置により検索判定可能である。
【００４３】
【発明の効果】
以上説明したように本発明によれば、座標位置測定手段により測定して得られた所定の座標上での任意の位置が、階層的に分類された領域の何れに存在するかを、階層的検索手段と領域判定演算手段により、効率的且つ正確に検索し判定することができるので、例えば、ＧＰＳ装置などで測定して得られた現在位置が如何なる住所に属するかを検索判定するナビゲーション機器に適用した場合は、住所の領域を階層的に検索することで、飛躍的に検索処理量を減らし、且つ判定対象となる領域の外部に設置した参照位置と測定位置との間に形成したベクトルのベクトル外積を用いて領域判定を行うことで、複雑な領域の条件分けを不要とするため、計算量を大幅に削減でき、計算速度が向上するため、高速なＣＰＵが不要となり、また、計算の確度も向上し、従来技術で説明したような住所の誤判定を生じない。結果として瞬時に現在位置の住所を知ることができ、目的地へのナビゲーションが非常に手軽に簡単に行えるという効果がある。
【００４４】
またこのナビゲーション機器では、例えば、現在位置のような任意の点を住所情報で表示するので、緯度経度表示の紙地図もしくは、電子地図表示装置が不要となり、さらに、地図を線分により近似した領域を用いて住所検索と表示を行うため、当該地図の座標情報を記憶する階層領域情報記憶手段の記憶容量が大幅に削減でき、結果として、ナビゲーション機器の構成規模を小型且つ低消費電力化、低コストとすることができるのみでなく、非常に手軽に簡単に、位置確認を行ない得るという効果がある。
【００４５】
さらに、本発明の階層分類領域判定装置及びこれを具備した位置測定可能な一般機器は、例えばナビゲーション機器に適用した場合は、一般的で誰にでもわかりやすい、住所表示により現在地を認識できることにより現在の位置の住所確認作業の信頼性が向上し、目的地の進路への確信を深め得るという効果がある。
【図面の簡単な説明】
【図１】  本発明の階層分類領域判定装置及びこれを具備した位置測定可能な一般機器がナビゲーション機器に適用された場合の概略構成図である。
【図２】  本発明の階層分類領域判定装置を構成する階層的検索手段の動作を示すフローチャートである。
【図３】  階層的に分類された領域の例である東京都の住所を説明するための説明図である。
【図４】  階層的に分類された領域である住所を複数の線分で近似できることを説明するための説明図である。
【図５】  階層的に分類された領域である住所を複数の線分で近似できることを説明するための別の説明図である。
【図６】  本発明の階層分類領域判定装置を構成する領域判定演算手段の動作を説明するための説明図である。
【図７】  本発明の階層分類領域判定装置を構成する領域判定演算手段の動作を説明するための別の説明図である。
【図８】  本発明の階層分類領域判定装置を構成する領域判定演算手段の動作を説明するためのさらに別の説明図である。
【図９】  本発明の階層分類領域判定装置を構成する領域判定演算手段の動作を説明するためのフローチャートである。
【図１０】  本発明の階層分類領域判定装置を構成する領域判定演算手段の交点の有無を判定する動作を説明するための説明図である。
【図１１】  本発明の階層分類領域判定装置を構成する領域判定演算手段の交点の有無を判定する動作を説明するための別の説明図である。
【図１２】  本発明の階層分類領域判定装置を構成する領域判定演算手段のベクトル外積を計算する計算式を説明するための説明図である。
【図１３】  従来の緯度経度により表示された地図の例である。
【図１４】  従来のナビゲーション機器の概略構成図である。
【図１５】  従来のナビゲーション機器の検索手段による位置判定を説明するための説明図である。
【符号の説明】
１…電子地図記憶装置、２…電子地図表示装置、３…ＣＰＵ、４…メモリ、５…電子地図制御装置、６…ＧＰＳ装置、１３…表示制御装置、１４…表示装置、１５…階層分類領域判定装置、１６…ナビゲーション機器、１７…階層領域情報記憶手段
【図１】
0004196237.tif 000002
【図２】
0004196237.tif 000003
【図３】
0004196237.tif 000004
【図４】
0004196237.tif 000005
【図５】
0004196237.tif 000006
【図６】
0004196237.tif 000007
【図７】
0004196237.tif 000008
【図８】
0004196237.tif 000009
【図９】
0004196237.tif 000010
【図１０】
0004196237.tif 000011
【図１１】
0004196237.tif 000012
【図１２】
0004196237.tif 000013
【図１３】
0004196237.tif 000014
【図１４】
0004196237.tif 000015
【図１５】
0004196237.tif 000016