【手続補正書】
【提出日】平成18年3月2日(2006.3.2)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】発明の名称
【補正方法】変更
【補正の内容】
【発明の名称】階層分類領域検索方法及び判定装置
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
所定の座標上での任意の位置を測定し得る座標位置測定ステップにより測定して得られた前記所定の座標上での任意の位置が、広域から狭域の複数の階層化されたデータ構造に分類された領域の何れに属するかを検索する階層分類領域検索方法であって、
前記所定の座標に従って位置が規定され、且つ階層的に分類された領域に関する座標情報を記憶する階層領域情報記憶ステップと、
前記所定の座標上での任意の位置が前記階層的に分類された領域の任意の一つに属するか否かを前記座標情報と、前記階層的に分類された領域の任意の一つに対して該領域の外部に設けられた参照位置の座標情報とを用いて演算して判定する領域判定演算ステップと、
前記所定の座標上での任意の位置が前記領域判定演算ステップによる演算結果に基づいて、前記階層的に分類された領域の任意の一つに属するかを検索する階層的検索ステップと、
前記階層的検索ステップによって検索した検索結果を表示する表示ステップと
を具備したことを特徴とする階層分類領域検索方法。
【請求項２】
前記階層的検索ステップが、前記階層的に分類された領域の任意の一つの領域を選択し、選択された前記任意の一つの領域に前記所定の座標上での任意の位置が属さないと、前記領域判定演算ステップにより判定されたときは、前記任意の一つの領域より広い面積の階層の領域を選択して検索を行い、選択された前記より広い面積の階層の領域に前記所定の座標上での任意の位置が属すると、前記領域判定演算手段により判定されるまで前記より広い面積の階層の領域の選択を繰り返し、前記所定の座標上の任意の位置が属すると判定された前記より広い面積の階層の領域に属する複数のより狭い階層の領域の各々について、前記所定の座標上での任意の位置が何れに属するかを前記領域判定演算ステップにより判定し、前記所定の座標上での任意の位置が属すると判定された前記より狭い階層の領域について、該より狭い階層の領域を構成する複数のさらにより狭い階層の領域について前記所定の座標上での任意の位置が属する領域を前記領域判定演算ステップにより判定し、前記所定の座標上の任意の位置が属すると判定された最狭の階層の領域を検索結果とし、選択された前記任意の一つの領域に前記所定の座標上での任意の位置が属すると、前記領域判定演算ステップにより判定されたときは、より狭い面積の階層を順次に選択して検索を行い前記領域判定演算ステップにより判定し、前記所定の座標上の任意の位置が属すると判定された最狭の階層の領域を前記検索結果とすることを特徴とする請求項１に記載の階層分類領域検索方法。
【請求項３】
前記領域判定演算ステップが、前記階層的に分類された領域の任意の一つの領域に対して外部に設定された参照位置を始点として、前記所定の座標上の任意の位置を終点とする第１のベクトルと、前記参照位置を始点として、前記任意の一つの領域を囲む複数の線分の任意の一つの線分の両端の位置を終点とする第２及び第３のベクトルとから、前記第２のベクトルと前記第１のベクトルの外積、及び前記第２のベクトルと前記第３のベクトルの外積を算出し、該外積の正負により、前記第２のベクトルが形成する線分を延長した直線で分割される２領域に対して前記所定の座標上の任意の位置と前記第３のベクトルの終点の位置が同一領域に存在するか否かを判定する第１の判定ステップと、
前記第３のベクトルと前記第１のベクトルとの外積、及び前記第３のベクトルと前記第２のベクトルとの外積を算出することにより、前記第３のベクトルを形成する線分を延長した直線で分割される２領域に対して前記所定の座標上の任意の位置と前記第２のベクトルの終点の位置が同一領域に存在するか否かを判定する第２の判定ステップと、
次に、前記任意の一つの領域を囲む複数の線分の任意の一つの線分の一端の位置を始点とし、前記参照位置を終点とする第４のベクトルとし、前記任意の一つの領域を囲む複数の線分の任意の一つの線分の一端の位置を始点とし、前記所定の座標上の任意の位置を終点とする第５のベクトルと、前記任意の一つの領域を囲む複数の線分の任意の一つの線分の一端の位置を始点とし、他端を終点とする第６のベクトルとから、前記第６のベクトルと前記第４のベクトルの外積、及び前記第６のベクトルと前記第５のベクトルの外積を算出することにより、前記第６のベクトルを形成する線分を延長した直線により分割される２領域に対して前記参照位置と前記所定の座標上の任意の位置が異なる領域に存在するか否かを判定する第３の判定ステップと、
前記第１の判定ステップと前記第２の判定ステップと前記第３の判定ステップとにより前記任意の一つの領域を囲む複数の線分の任意の一つの線分が、前記参照位置と前記所定の座標上の任意の位置を結ぶ線分と交わる交点があるか否かを判定する交点判定ステップと
を備えることを特徴とする請求項１に記載の階層分類領域検索方法。
【請求項４】
前記領域判定演算ステップが、前記階層的に分類された領域の任意の一つの領域に対して外部に設定された参照位置と前記所定の座標上の任意の位置とを結ぶ線分と、前記任意の一つの領域を囲む線分との交点の数が奇数のとき、該座標上の位置は前記任意の一つの領域の内部に存在すると判定し、前記参照位置と前記所定の座標上の位置とを結ぶ線分と、前記任意の一つの領域を囲む線分との交点が偶数のとき、前記所定の座標上の位置は前記任意の一つの領域の外部に存在すると判定することを特徴とする請求項１に記載の階層分類領域検索方法。
【請求項５】
所定の座標上での任意の位置を測定し得る座標位置測定手段により測定して得られた前記所定の座標上での任意の位置が、広域から狭域の複数の階層化されたデータ構造に分類された領域の何れに属するかを検索する階層分類領域判定装置であって、
前記所定の座標に従って位置が規定され、且つ階層的に分類された領域に関する座標情報を記憶する階層領域情報記憶手段と、
前記所定の座標上での任意の位置が前記階層的に分類された領域の任意の一つに属するか否かを前記座標情報と、前記階層的に分類された領域の任意の一つに対して該領域の外部に設けられた参照位置の座標情報とを用いて演算して判定する領域判定演算手段と、
前記所定の座標上での任意の位置が前記領域判定演算手段による演算結果に基づいて、前記階層的に分類された領域の任意の一つに属するかを検索する階層的検索手段と、
前記階層的検索手段によって検索した検索結果を表示する表示手段と
を具備したことを特徴とする階層分類領域判定装置。
【請求項６】
前記階層的検索手段が、前記階層的に分類された領域の任意の一つの領域を選択し、選択された前記任意の一つの領域に前記所定の座標上での任意の位置が属さないと、前記領域判定演算手段により判定されたときは、前記任意の一つの領域より広い面積の階層の領域を選択して検索を行い、選択された前記より広い面積の階層の領域に前記所定の座標上での任意の位置が属すると、前記領域判定演算手段により判定されるまで前記より広い面積の階層の領域の選択を繰り返し、前記所定の座標上の任意の位置が属すると判定された前記より広い面積の階層の領域に属する複数のより狭い階層の領域の各々について、前記所定の座標上での任意の位置が何れに属するかを前記領域判定演算手段により判定し、前記所定の座標上での任意の位置が属すると判定された前記より狭い階層の領域について、該より狭い階層の領域を構成する複数のさらにより狭い階層の領域について前記所定の座標上での任意の位置が属する領域を前記領域判定演算手段により判定し、前記所定の座標上の任意の位置が属すると判定された最狭の階層の領域を検索結果とし、選択された前記任意の一つの領域に前記所定の座標上での任意の位置が属すると、前記領域判定演算手段により判定されたときは、より狭い面積の階層を順次に選択して検索を行い前記領域判定演算手段により判定し、前記所定の座標上の任意の位置が属すると判定された最狭の階層の領域を前記検索結果とする
ことを特徴とする請求項５に記載の階層分類領域判定装置。
【請求項７】
前記領域判定演算手段が、前記階層的に分類された領域の任意の一つの領域に対して外部に設定された参照位置を始点として、前記所定の座標上の任意の位置を終点とする第１のベクトルと、前記参照位置を始点として、前記任意の一つの領域を囲む複数の線分の任意の一つの線分の両端の位置を終点とする第２及び第３のベクトルとから、前記第２のベクトルと前記第１のベクトルの外積、及び前記第２のベクトルと前記第３のベクトルの外積を算出し、該外積の正負により、前記第２のベクトルが形成する線分を延長した直線で分割される２領域に対して前記所定の座標上の任意の位置と前記第３のベクトルの終点の位置が同一領域に存在するか否かを判定する第１の判定手段と、
前記第３のベクトルと前記第１のベクトルとの外積、及び前記第３のベクトルと前記第２のベクトルとの外積を算出することにより、前記第３のベクトルを形成する線分を延長した直線で分割される２領域に対して前記所定の座標上の任意の位置と前記第２のベクトルの終点の位置が同一領域に存在するか否かを判定する第２の判定手段と、
次に、前記任意の一つの領域を囲む複数の線分の任意の一つの線分の一端の位置を始点とし、前記参照位置を終点とする第４のベクトルとし、前記任意の一つの領域を囲む複数の線分の任意の一つの線分の一端の位置を始点とし、前記所定の座標上の任意の位置を終点とする第５のベクトルと、前記任意の一つの領域を囲む複数の線分の任意の一つの線分の一端の位置を始点とし、他端を終点とする第６のベクトルとから、前記第６のベクトルと前記第４のベクトルの外積、及び前記第６のベクトルと前記第５のベクトルの外積を算出することにより、前記第６のベクトルを形成する線分を延長した直線により分割される２領域に対して前記参照位置と前記所定の座標上の任意の位置が異なる領域に存在するか否かを判定する第３の判定手段と、
前記第１の判定手段と前記第２の判定手段と前記第３の判定手段とにより前記任意の一つの領域を囲む複数の線分の任意の一つの線分が、前記参照位置と前記所定の座標上の任意の位置を結ぶ線分と交わる交点があるか否かを判定する交点判定手段と
を備えることを特徴とする請求項５に記載の階層分類領域判定装置。
【請求項８】
前記領域判定演算手段が、前記階層的に分類された領域の任意の一つの領域に対して外部に設定された参照位置と前記所定の座標上の任意の位置とを結ぶ線分と、前記任意の一つの領域を囲む線分との交点の数が奇数のとき、該座標上の位置は前記任意の一つの領域の内部に存在すると判定し、前記参照位置と前記所定の座標上の位置とを結ぶ線分と、前記任意の一つの領域を囲む線分との交点の数が偶数のとき、前記所定の座標上の位置は前記任意の一つの領域の外部に存在すると判定することを特徴とする請求項５に記載の階層分類領域判定装置。
【請求項９】
請求項５に記載の階層分類領域判定装置を具備した
ことを特徴とするナビゲーション装置。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
【発明の属する技術分野】
本発明は、階層分類領域検索方法及び判定装置に関し、特に現在の位置が階層分類された領域の何れの領域に属するかを判定するものである。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
【課題を解決するための手段】
上述の課題を達成するために、本発明においては、所定の座標上での任意の位置を測定し得る座標位置測定手段により測定して得られた所定の座標上での任意の位置が、より広い領域に複数のより狭い領域が含まれるというように、階層的に分類された領域の何れに属するかを判定する階層分類領域判定装置において、所定の座標に従って位置が規定され、且つ階層的に分類された領域に関する座標情報を記憶する階層領域情報記憶手段と、所定の座標上での任意の位置が階層的に分類された領域の任意の一つに属するか否かを座標情報と、階層的に分類された領域の任意の一つに対して外部に設けられた参照位置の座標情報とを用いて演算して判定する領域判定演算手段と、所定の座標上での任意の位置が階層的に分類された領域の中、何れの領域に属するかを、領域判定演算手段の出力をもとに階層的に検索する階層的検索手段と、階層的検索手段の検索した検索結果を表示する表示手段とを設けるようにする。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
また、本発明の望ましい形態としては、下記、１）〜３）である。
１）階層的検索手段が、階層的に分類された領域の任意の一つの領域を選択し、選択された任意の一つの領域に所定の座標上での任意の位置が属さないと、領域判定演算手段により判定されたときは、任意の一つの領域より広い面積の階層の領域を選択して検索を行い、選択された前記より広い面積の階層の領域に所定の座標上での任意の位置が属すると、領域判定演算手段により判定されるまでより広い面積の階層の領域の選択を繰り返し、所定の座標上の任意の位置が属すると判定されたより広い面積の階層の領域に属する複数のより狭い階層の領域の各々について、所定の座標上での任意の位置が何れに属するかを領域判定演算手段により判定し、所定の座標上での任意の位置が属すると判定されたより狭い階層の領域について、より狭い階層の領域を構成する複数のさらにより狭い階層の領域について所定の座標上での任意の位置が属する領域を領域判定演算手段により判定し、所定の座標上の任意の位置が属すると判定された最狭の階層の領域を検索結果とし、選択された任意の一つの領域に所定の座標上での任意の位置が属すると、領域判定演算手段により判定されたときは、より狭い面積の階層を順次に選択して検索を行い領域判定演算手段により判定し、所定の座標上の任意の位置が属すると判定された最狭の階層の領域を前記検索結果とするものである。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００４３
【補正方法】変更
【補正の内容】
【００４３】
【発明の効果】
以上説明したように本発明によれば、座標位置測定手段により測定して得られた所定の座標上での任意の位置が、階層的に分類された領域の何れに存在するかを、階層的検索手段と領域判定演算手段により、効率的且つ正確に検索し判定することができるので、例えば、ＧＰＳ装置などで測定して得られた現在位置が如何なる住所に属するかを検索判定するナビゲーション機器に適用した場合は、住所の領域を階層的に検索することで、飛躍的に検索処理量を減らし、且つベクトル外積を用いて領域判定を行うことで、複雑な領域の条件分けを不要とするため、計算量を大幅に削減でき、計算速度が向上するため、高速なＣＰＵが不要となり、また、計算の確度も向上し、従来技術で説明したような住所の誤判定を生じない。結果として瞬時に現在位置の住所を知ることができ、目的地へのナビゲーションが非常に手軽に簡単に行えるという効果がある。