ナビゲーションシステム、ＰＯＩ探索方法、情報配信サーバおよび携帯端末
【課題】 現在位置からＰＯＩまでの実際の移動経路を考慮して近くに存在するＰＯＩを選択でき、かつ、その経路探索を効率よく行うことができるようにする。
【解決手段】 ナビゲーションシステム１０は、各ＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩＤＢ３７と、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件を設定する探索条件設定手段（２６、２７等）と、到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段３３と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段３６と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段３８と、を備え、到達圏ＰＯＩ判別手段３８により抽出されたＰＯＩについて基準位置からＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成する。
【解決手段】 ナビゲーションシステム１０は、各ＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩＤＢ３７と、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件を設定する探索条件設定手段（２６、２７等）と、到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段３３と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段３６と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段３８と、を備え、到達圏ＰＯＩ判別手段３８により抽出されたＰＯＩについて基準位置からＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、携帯電話などの携帯端末と情報配信サーバからなる通信型のナビゲーションシステムに関するものであり、特に、ユーザが所望する位置周辺における興味対象場所（ＰＯＩ）の情報を検索し、検索されたＰＯＩへの経路を案内することができるナビゲーションシステム、情報配信サーバおよび携帯端末に関するものである。
本発明は上記のようなナビゲーションシステムにおいて、現在位置などの所望位置からＰＯＩまでの実際の移動経路の距離または時間を考慮して、前記所望位置から近くに存在するＰＯＩを選択でき、また、情報配信サーバにおけるＰＯＩまでの経路探索を素早く、効率よく行うことができるようにしたナビゲーションシステム、情報配信サーバ、携帯端末に関するものである。
【背景技術】
【０００２】
近年、携帯電話など携帯端末がブラウザを搭載し、インターネットにアクセスして所望の情報の提供を受けることができるようになっている。このようなシステムにおいては、ユーザは携帯端末を操作して、サーバに備えられた検索エンジン等を利用して所望のサイトを見出し、当該サイトのコンテンツをダウンロードして、ブラウザにより当該コンテンツを閲覧している。上記コンテンツには種々のカテゴリに属する情報があり、店舗やイベントの情報提供、鉄道路線の時刻表の提供や、鉄道の乗り換え案内なども含まれる。
【０００３】
店舗やイベントの情報提供にあっては、ユーザが携帯端末を操作して店舗やイベントのカテゴリ、検索したい地域を入力して検索要求する。サーバは指定されたカテゴリに該当し、かつ当該地域に存在する店舗やイベントを検索し、その情報が携帯端末装置に配信される。時刻表の提供においては、ユーザが携帯端末を操作して、路線を指定すると、当該路線の時刻表が携帯端末の表示装置の画面上に提示される。また、乗り換え案内においては、ユーザが、出発地や目的地を指定することにより、推奨する経路が提示される。
【０００４】
情報配信サーバも機能が充実され、上記のような鉄道路線やバス路線の時刻表の提供や乗り換え案内にとどまらず、従来の車載用ナビゲーションシステムの機能を携帯電話などの携帯端末に提供する情報配信サーバも実現されている。このようなシステムによれば、自動車の運転者のみならず、歩行者に対するナビゲーションサービスを提供することができる。
【０００５】
携帯電話のユーザは上記のようなサービスを利用して種々の所望の情報を得ることができる。例えば、ユーザが興味を持っている興味対象場所（Point of Interest：以下単にＰＯＩという）に関する地図や営業内容、価格、営業時間などの情報を得ることができる。ＰＯＩとは、例えば、ホテル、レストラン、デパート、テーマパーク、コンビニ、ガソリンスタンド、運動施設、公園などのあらゆる店舗、施設が対象となり得る。このためＰＯＩは種類（カテゴリ）が膨大であり、当該カテゴリに属する店舗、場所も無数に存在する。情報配信サーバがカバーする範囲が広ければ広い程その数も増加する。
【０００６】
従って、これら無数のＰＯＩに関する情報をユーザに提供するため、情報配信サーバはＰＯＩデータベースを備えている。このＰＯＩデータベースにおいては、ＰＯＩはカテゴリ分けされており、また、このＰＯＩカテゴリはその数の多さから大分類、中分類、小分類などと階層化されている。ユーザは携帯端末に表示されたメニュー画面から所望のＰＯＩカテゴリを選択して情報配信サーバにデータを要求することになるが、特定の所望のＰＯＩカテゴリを選択するために、大分類、中分類、小分類とカテゴリの階層をたどり、情報配信を希望するＰＯＩカテゴリを選択することになる。
【０００７】
ユーザが利用する携帯端末が携帯電話である場合、最近の携帯電話はＧＰＳ受信機を備え、ＧＰＳ衛星からの信号を受信して自身の現在位置を算出する測位機能を有しておりこの機能を利用して現在位置を情報配信サーバに送信することができる。また、ナビゲーションサービスを受けることのできる携帯端末であれば、所望の特定のＰＯＩ情報を得た後、現在位置または自宅、勤務先など所望の出発地として当該特定のＰＯＩまでの経路探索を受けることもできる。
【０００８】
このようなＰＯＩ情報提供システムは種々提案されている。例えば、下記の特許文献１（特開２００３−１３２４８３号公報）に「情報配信方法」として開示されたシステムが知られている。
【０００９】
この特許文献１に開示された情報配信方法は、情報配信コンピュータシステムと端末装置である携帯電話とからなるシステムである。この情報配信コンピュータシステムは、外部の携帯電話から或るＰＯＩの案内情報が要求されると、所望ＰＯＩの案内情報に、ＰＯＩの位置情報と最適経路情報の情報配信コンピュータシステムに対する経路探索要求用のＵＲＬをリンク情報とするリンクを付随させて要求元に返信する。該携帯電話でＰＯＩの案内情報と一緒に表示されたリンクを選択すると、ＧＰＳ受信部で検出された現在位置を出発地、ＰＯＩの位置情報を目的地、計時部で計時された日時を出発予定日時とした経路探索条件が自動設定され、情報配信コンピュータシステムに対し、経路探索条件の情報を付随した経路探索要求をするように構成されている。
【００１０】
すなわち、この情報配信コンピュータシステムは、携帯電話からＰＯＩの検索要求があり、特定のＰＯＩを検索しそのＰＯＩ案内情報（地図、営業案内など）を携帯電話に配信する際に、経路探索機能へのリンク情報を付加して配信し、携帯電話がそのリンクを選択すると現在位置から当該ＰＯＩへの最適経路を探索して配信するようにしたものである。
【００１１】
また、下記の特許文献２（特開２００３−１５０４７５公報）に「情報提供システムおよび方法」として開示されたシステムも知られている。この特許文献２に開示された情報提供システムは、携帯端末とＷｅｂアプリケーションサーバからなるシステムである。
【００１２】
この情報提供システムにおいて、携帯端末を利用するユーザは、表示された提供サービスメニューから要求するサービスを選択する。選択されたサービスの情報はＷｅｂアプリケーションサーバに送信される。ＧＰＳ衛星は位置情報を出力する。携帯端末は、位置情報を受信し、受信した位置情報に基づいて現在位置を算出し、その現在位置の情報を、インターネットを介してＷｅｂアプリケーションサーバに送信する。Ｗｅｂアプリケーションサーバは、携帯端末から送信された現在位置の情報を受信し、携帯端末を利用するユーザによって選択されたサービスに関する情報であって、その現在位置に関連する情報を携帯端末に送信する。
【００１３】
一般的に、目的とするＰＯＩカテゴリに属する特定のＰＯＩが現在位置や所望の位置周辺（例えば、半径２ｋｍの範囲）に複数存在する場合、上記のようなＰＯＩ検索システムや経路案内システムにおいて検索された複数のＰＯＩに関する位置情報や関連情報は、現在位置や所望の位置から近い順に並べられて携帯端末に配信される。近い順とは現在位置や所望の位置からの各ＰＯＩまでの直線距離が短い順である。
【００１４】
例えば、下記の特許文献３（特開平１０−２８１７９７号公報）には、現在位置から直線距離の近い順にＰＯＩを検索して案内する車載用ナビゲーション装置及び周辺施設探索方法システム端末装置が開示されている。
【００１５】
この特許文献３に開示されたシステムは、テーブル記憶部に、用途別にグループ化されるカテゴリが記憶されている。ユーザが操作部を介して用途を入力すると、制御部は入力された用途に対応するグループのカテゴリを調べ、これらのカテゴリから車両の現在位置の周辺に存在する施設を探索する。探索した施設は現在位置から近い順に並べられ、ユーザが所望の施設を選択すると、制御部は現在位置から選択された施設までの案内経路を探索するように構成されている。
【００１６】
また、特許文献３のような周辺施設探索システムにおいて、現在位置から一定の距離範囲に存在する施設（ＰＯＩ）の探索を効率よく行うように構成したシステムとして、下記の特許文献４（特開２００４−６１５０３号公報）に開示されたＰＯＩ情報表示方法およびナビゲーションシステムも知られている。
【００１７】
この特許文献４に開示されたシステムは、ナビゲーションシステムにおいて、セル配列に特定ＰＯＩをそれぞれ持つセルを配置し、使用者位置に最も近いセルに対応するセル配列におけるセル位置からの距離に基づいてセルを複数の異なるレベルにソートする。このナビゲーションシステムは所定レベルのセルからＰＯＩを抽出し、距離に応じてＰＯＩをソートし、このＰＯＩを表示するように構成したものである。
【００１８】
すなわち、このシステムは所定の緯度、経度の範囲で区切られた単位地図と同様に特定のＰＯＩが存在するセルの配列をデータベースとして蓄積し、現在位置からの距離レベルに応じて該当するセル配列を選択して当該セルに存在するＰＯＩを探索することにより探索効率を向上させたものである。
【００１９】
【特許文献１】特開２００３−１３２４８３号公報（図１、段落［０００６］）
【特許文献２】特開２００３−１５０４７５号公報（図１、図２、段落［００１３］）
【特許文献３】特開平１０−２８１７９７号公報（図１、段落［００２８］、［００２９］）
【特許文献４】特開２００４−６１５０３号公報（図４、図６、図７、図８）
【発明の開示】
【発明が解決しようとする課題】
【００２０】
現在位置や所望位置から一定の範囲内にあるＰＯＩを探索して近い順にＰＯＩを並べて案内するシステムは、上記特許文献１〜特許文献４に開示されるように、直線距離に基づいてＰＯＩをソートするものであった。しかしながら、ユーザが実際に探索されたＰＯＩを訪れたいと思った場合、実際の移動経路を考慮して近いＰＯＩが選択できることが望ましい。直線距離が近くても、実際には河川や鉄道で遮られていて、道のりが遠い場合があるからである。
【００２１】
ところが、上記特許文献１〜特許文献４に開示されるようなシステムにおいては、直線距離に基づいてＰＯＩを現在位置や所望位置から近い順にソートして案内し、ユーザが選択したＰＯＩについて、経路探索してその経路を案内するものであるから、実際の経路としては遠回りになり、必ずしも最も近いＰＯＩに到達できる保証がないという問題点があった。
【００２２】
このような問題点を解消するために、現在位置や所望位置から実際の移動経路を探索してＰＯＩを経路の近い順に案内しようとすると、情報配信サーバが候補とすべきＰＯＩ全てについて経路探索をする必要が生じる。このような案内方法は、不可能ではないが、経路探索にかなりの時間を要するものであり、（１）情報配信サーバで候補ＰＯＩ全ての経路探索を行うと、１クライアント（携帯端末）から多数、例えば、１００個のＰＯＩを対象としたＰＯＩ探索要求があり、全ＰＯＩまでの経路探索を行うと、探索要求が集中する時間帯などシステム全体では過負荷になる恐れが生じるという問題点があった。また、（２）カーナビでは、移動速度が速いので上記のような多数のＰＯＩの経路を探索していると、経路探索が終了しないうちに現在地が変わってしまい、探索結果を配信した時には既にユーザが相当な距離走行していて役に立たない情報になってしまうという問題点があった。
【００２３】
本願の発明者は上記の問題点を解消すべく種々検討を重ねた結果、現在位置や所望位置から近いＰＯＩの探索要求があった場合、先ず、現在位置や所望位置からユーザが所望する時間または距離で到達できる道路ネットワーク上の範囲（到達圏）を探索し、到達圏内のＰＯＩを抽出し最も近いノードまたはリンクと対応付けて現在位置または所望位置からの経路とし距離（または時間）の短い順に該当ＰＯＩをソートして案内すれば、上記問題点を解消し得ることに想到し本発明を完成するに至ったものである。
【００２４】
すなわち、本発明は上記の問題点を解消することを課題とし、現在位置などの所望位置からＰＯＩまでの実際の移動経路を考慮して、前記所望位置から近くに存在するＰＯＩを選択でき、また、情報配信サーバのＰＯＩまでの経路探索を効率よく行うことができるようにしたナビゲーションシステム、情報配信サーバ、携帯端末を提供することを目的とするものである。
【課題を解決するための手段】
【００２５】
前記課題を解決するために、本願の請求項１にかかる発明は、
各ＰＯＩごとにＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件を設定する探索条件設定手段と、到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段と、を備え、
前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて前記基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成することを特徴とするナビゲーションシステムである。
【００２６】
また、本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだノードを結ぶポリゴンを作成し、当該ポリゴンと重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定することを特徴とする。
【００２７】
また、本願の請求項３にかかる発明は、請求項２にかかるナビゲーションシステムにおいて、前記到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、前記ポリゴンの範囲内のＰＯＩを抽出し、各ＰＯＩごとに前記到達圏探索の及んだノードのうち当該ＰＯＩに最も近いノードをそれぞれＰＯＩに対応付けることを特徴とする。
【００２８】
また、本願の請求項４にかかる発明は、請求項３にかかるナビゲーションシステムにおいて、前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたノードのポテンシャルに基づいて前記ＰＯＩをソートすることを特徴とする。
【００２９】
本願の請求項５にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだリンクに基づいて前記到達圏と重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定することを特徴とする請求項１に記載のナビゲーションシステム。
【００３０】
また、本願の請求項６にかかる発明は、請求項５にかかるナビゲーションシステムにおいて、前記到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、当該ＰＯＩから最も近いリンクを検出し、当該リンクが前記到達圏探索の及んだリンクであるＰＯＩを抽出し、当該リンクをそれぞれＰＯＩに対応付けることを特徴とする。
【００３１】
また、本願の請求項７にかかる発明は、請求項６にかかるナビゲーションシステムにおいて、前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたリンクに基づき経路距離または所要時間を求め、前記ＰＯＩをソートすることを特徴とする。
【００３２】
本願の請求項８にかかる発明は、
各ＰＯＩごとにＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件を設定する探索条件設定手段と、到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段と、を備えたナビゲーションシステムにおけるＰＯＩ探索方法であって、
前記経路探索手段が、ＰＯＩ探索条件に従って到達圏探索を行う第１のステップと、
前記到達圏ＰＯＩ範囲判定手段が、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する第２のステップと、
前記到達圏ＰＯＩ判別手段が、前記到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置し、前記ＰＯＩ探索条件に合致するＰＯＩを抽出する第３のステップと、前記抽出したＰＯＩについて、前記基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成する第４のステップと、からなることを特徴とする。
【００３３】
また、本願の請求項９にかかる発明は、請求項８にかかるＰＯＩ探索方法において、
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、
前記第２のステップは、前記到達圏ＰＯＩ範囲判定手段が到達圏探索の及んだノードを結ぶポリゴンを作成し、当該ポリゴンと重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定するステップを含むことを特徴とする。
【００３４】
また、本願の請求項１０にかかる発明は、請求項９にかかるＰＯＩ探索方法において、
前記第３のステップは、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、前記ポリゴンの範囲内のＰＯＩを抽出するステップを含み、前記第４のステップは、各ＰＯＩごとに前記到達圏探索の及んだノードのうち当該ＰＯＩに最も近いノードをそれぞれＰＯＩに対応付けるステップを含むことを特徴とする。
【００３５】
また、本願の請求項１１にかかる発明は、請求項１０にかかるＰＯＩ探索方法において、
前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、
前記ＰＯＩソート手段が前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたノードのポテンシャルに基づいて前記ＰＯＩをソートする第５のステップを含むことを特徴とする請求項１０に記載のＰＯＩ探索方法。
【００３６】
また、本願の請求項１２にかかる発明は、請求項８にかかるＰＯＩ探索方法において、
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、
前記第２のステップは、到達圏ＰＯＩ範囲判定手段が到達圏探索の及んだリンクに基づいて前記到達圏と重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定するステップを含むことを特徴とする請求項８に記載のＰＯＩ探索方法。
【００３７】
また、本願の請求項１３にかかる発明は、請求項１２にかかるＰＯＩ探索方法において、
前記第３のステップは、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、当該ＰＯＩから最も近いリンクを検出し、当該リンクが前記到達圏探索の及んだリンクであるＰＯＩを抽出するステップを含み、前記第４のステップは、各ＰＯＩごとに当該ＰＯＩから最も近いリンクをそれぞれＰＯＩに対応付けることを特徴とする。
【００３８】
また、本願の請求項１４にかかる発明は、請求項１３にかかるＰＯＩ探索方法において、
前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、
前記ＰＯＩソート手段が前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたリンクを含む経路の経路距離または所要時間を求め、前記ＰＯＩをソートする第５のステップを含むことを特徴とする。
【００３９】
本願の請求項１５にかかる発明は、
各ＰＯＩごとにＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件に基づいて到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段と、を備え、
前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて前記基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成することを特徴とする情報配信サーバである。
【００４０】
また、本願の請求項１６にかかる発明は、請求項１５にかかる情報配信サーバにおいて、
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだノードを結ぶポリゴンを作成し、当該ポリゴンと重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定することを特徴とする。
【００４１】
また、本願の請求項１７にかかる発明は、請求項１６にかかる情報配信サーバにおいて、
前記到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、前記ポリゴンの範囲内のＰＯＩを抽出し、各ＰＯＩごとに前記到達圏探索の及んだノードのうち当該ＰＯＩに最も近いノードをそれぞれＰＯＩに対応付けることを特徴とする。
【００４２】
また、本願の請求項１８にかかる発明は、請求項１７にかかる情報配信サーバにおいて、
前記情報配信サーバは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたノードのポテンシャルに基づいて前記ＰＯＩをソートすることを特徴とする。
【００４３】
また、本願の請求項１９にかかる発明は、請求項１５にかかる情報配信サーバにおいて、
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだリンクに基づいて前記到達圏と重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定することを特徴とする。
【００４４】
また、本願の請求項２０にかかる発明は、請求項１９にかかる情報配信サーバにおいて、
前記到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、当該ＰＯＩから最も近いリンクを検出し、当該リンクが前記到達圏探索の及んだリンクであるＰＯＩを抽出し、当該リンクをそれぞれＰＯＩに対応付けることを特徴とする。
【００４５】
また、本願の請求項２１にかかる発明は、請求項２０にかかる情報配信サーバにおいて、
前記情報配信サーバは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたリンクに基づき経路距離または所要時間を求め、前記ＰＯＩをソートすることを特徴とする。
【００４６】
本願の請求項２２にかかる発明は、
各ＰＯＩごとにＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件に基づいて到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段と、を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて前記基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成する情報配信サーバにネットワークを介して接続される携帯端末であって、
前記基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件を設定する探索条件設定手段を備えたことを特徴とする。
【発明の効果】
【００４７】
請求項１にかかる発明においては、基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件を設定し、経路探索手段が、ＰＯＩ探索条件に従って到達圏探索を行い、到達圏ＰＯＩ範囲判定手段が、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定し、到達圏ＰＯＩ判別手段が、前記到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置し、前記ＰＯＩ探索条件に合致するＰＯＩを抽出し、抽出したＰＯＩについて、基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成する。
従って、まず到達圏探索によって到達圏の範囲を決めることができ、この到達圏探索は短時間で効率よく終了させることができるようになる。この到達圏探索によってＰＯＩ近辺までの経路距離または所要時間は探索済であるから、その後、到達圏範囲内のＰＯＩを抽出し、抽出された各ＰＯＩについての基準位置からの実際の経路となる経路距離または所要時間を生成することができるようになる。これにより、実際の移動経路を考慮して近いＰＯＩが選択でき、直線距離が近くても、実際には河川や鉄道で遮られていて、道のりが遠いＰＯＩを除外したＰＯＩ探索が可能になる。
【００４８】
請求項２にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだノードを結ぶポリゴンを作成し、当該ポリゴンと重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定する。
従って、到達圏探索の結果に基づいて容易に到達圏の範囲内にある所望のＰＯＩの範囲を特定することができるようになる。
【００４９】
請求項３にかかる発明においては、請求項２にかかるナビゲーションシステムにおいて、到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、前記ポリゴンの範囲内のＰＯＩを抽出し、各ＰＯＩごとに前記到達圏探索の及んだノードのうち当該ＰＯＩに最も近いノードをそれぞれＰＯＩに対応付ける。従って、到達圏探索の結果に基づいて到達圏の範囲内にある所望のＰＯＩを抽出することができ、抽出されたＰＯＩまでの経路距離または所要時間を容易に生成することができるようになる。
【００５０】
請求項４にかかる発明おいては、請求項３にかかるナビゲーションシステムにおいて、ナビゲーションシステムは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたノードのポテンシャルに基づいて前記ＰＯＩをソートする。従って、到達圏内から抽出されたＰＯＩまでの経路距離または所要時間の近い順にＰＯＩを並べてその情報を提供することができるようになる。
【００５１】
請求項５にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだリンクに基づいて前記到達圏と重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定する。
到達圏探索の結果に基づいて容易に到達圏の範囲内にある所望のＰＯＩの範囲を特定することができるようになる。
【００５２】
請求項６にかかる発明においては、請求項５にかかるナビゲーションシステムにおいて、到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、当該ＰＯＩから最も近いリンクを検出し、当該リンクが前記到達圏探索の及んだリンクであるＰＯＩを抽出し、当該リンクをそれぞれＰＯＩに対応付ける。従って、到達圏探索の結果に基づいて到達圏の範囲内にある所望のＰＯＩを抽出することができ、抽出されたＰＯＩまでの経路距離または所要時間を容易に生成することができるようになる。
【００５３】
請求項７にかかる発明においては、請求項６にかかるナビゲーションシステムにおいて、前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたリンクに基づき経路距離または所要時間を求め、前記ＰＯＩをソートする。従って、到達圏内から抽出されたＰＯＩまでの経路距離または所要時間の近い順にＰＯＩを並べてその情報を提供することができるようになる。
【００５４】
請求項８ないし請求項１４にかかる発明においては、それぞれ請求項１ないし請求項７にかかるナビゲーションシステムにおけるＰＯＩ探索方法を提供することができるようになる。また、請求項１５ないし請求項２１にかかる発明においては、それぞれ請求項１ないし請求項７にかかるナビゲーションシステムを構成する情報配信サーバを提供することができるようになる。更に、請求項２２にかかる発明においては請求項１にかかるナビゲーションシステムを構成する携帯端末を提供することができるようになる。
【発明を実施するための最良の形態】
【００５５】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。なお、以下の実施例においては、携帯電話機を端末装置とし、経路探索および経路案内を行うナビゲーションシステムにＰＯＩ情報提供機能を備えたナビゲーションシステムを具体例として説明するが、本発明はこのような実施例に限ることなく、端末装置は車載型の端末装置のような移動端末であってもよい。本明細書においては、移動端末を含めて携帯端末と総称する。ただし、情報配信サーバは経路探索用のネットワークデータを備え、経路探索を行う機能を有している必要がある。
【実施例１】
【００５６】
図１は、本発明の実施例にかかるナビゲーションシステムの構成を示す図である。ナビゲーションシステム１０は、図１に示すように、インターネットなどのネットワーク１１を介して接続される携帯端末２０と情報配信サーバ３０を備えて構成されている。情報配信サーバ３０は、端末装置２０にＰＯＩ情報を提供するため、ＰＯＩカテゴリ別に区分し、当該カテゴリに属する各ＰＯＩとその位置情報（緯度・経度）、ＰＯＩが位置する単位地図と同様の単位に区切られたメッシュの識別番号（メッシュ番号）、営業案内などＰＯＩに関連する情報を蓄積したデータベースであるＰＯＩＤＢ３７と、経路探索手段３３、到達圏ＰＯＩ範囲判定手段３６、探索用ネットワークデータ３５、到達圏ＰＯＩ判別手段３８、ＰＯＩソート手段３９などを備えている。
【００５７】
ＰＯＩＤＢ３７に蓄積される全てのＰＯＩ情報は、エリアを所定の緯度・経度で区切ったメッシュを単位とし、個々のＰＯＩが存在する場所に基づいて該当するメッシュに各ＰＯＩの情報が蓄積されている。１つのメッシュは地図を緯度・経度で区切った単位地図の大きさとおなじ大きさであってよい。もちろん異なる大きさにすることもできる。
【００５８】
図２は、上記のＰＯＩＤＢ３７に蓄積されたＰＯＩの情報の構成を示す図である。図２に示すように、蓄積されるＰＯＩの情報は、メッシュ番号０００１〜０００２〜のように所定の緯度、経度で区切ったメッシュを単位として区分され、当該メッシュに存在するＰＯＩの情報が該当するメッシュに蓄積されている。蓄積されるＰＯＩの情報は、当該ＰＯＩの属するカテゴリ、ＰＯＩ（名称）、ＰＯＩの場所（緯度・経度）、ホームページ（ＵＲＬ）、営業案内などである。また、探索用ネットワークデータ３５には経路探索用の道路ネットワークのデータ、交通ネットワークのデータが蓄積されている。道路ネットワークのデータは自動車、歩行者のための経路探索に用いられ、交通ネットワークのデータは交通機関を利用した区間の経路探索に用いられる。
【００５９】
情報配信サーバ３０はまた、制御手段３１、配信データ編集手段３２、通信手段３４、を備えている。制御手段３１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段３４は、ネットワーク１１、１２を介して携帯端末２０や、各種のＰＯＩ情報を提供するＰＯＩ情報提供サーバ５０と通信するためのインターフェースである。配信データ編集手段３２は、経路探索やＰＯＩ探索の結果を携帯端末２０に配信するためのデータに編集するためのものである。情報配信サーバ３０は、ネットワーク１２を介して各種のＰＯＩ情報提供サーバ５０からＰＯＩの情報を収集してＰＯＩＤＢ３７にデータベース登録し、ユーザに提供できるＰＯＩ情報を充実してゆくことができる。
【００６０】
携帯端末２０は例えばＧＰＳ受信機などの測位手段を搭載した携帯電話機であり、現在地や目的地周辺の周辺検索、すなわち、所望のＰＯＩ検索が行える。現在位置や目的地の位置情報を付けて周辺検索要求を情報配信サーバ３０に送ると、情報配信サーバ３０は、携帯端末２０の現在位置または目的地の位置とＰＯＩまでの経路を考慮して、経路の所要時間または経路の距離が所望の範囲内にあるＰＯＩの探索要求ができるように構成されている。以下、この経路の距離または時間を到達圏範囲ということとする。ＰＯＩ検索にあたって携帯端末２０はＰＯＩカテゴリの選択画面が表示され、ユーザは所望のＰＯＩカテゴリを選択しまた所望の到達圏範囲（距離または時間）を入力し、ＰＯＩ探索要求を情報配信サーバ３０に送信し当該ＰＯＩカテゴリに属するＰＯＩを探索させる。以下の説明においては、現在位置を基準とした周辺検索を例にとり具体例を説明することとする。
【００６１】
到達圏探索とは、特に目的地を定めずに、ある地点（例えば現在地）から所定のコスト以下（道のり（経路距離）、所要時間など）で到達できるエリアを求めるものである。主に、出店計画や不動産の選択などで用いられる技術である。この技術は、例えば、本出願人により出願され、公開された特開２０００−１８７６５３号公報に開示されている。この技術は電車路線の到達圏探索の方法を開示している。
【００６２】
本実施例においては、現在地から所定の条件（経路距離、所要時間）で到達圏探索を行い、その結果到達圏を図形的に求め、その図形に含まれるＰＯＩをリストの候補にする。そして、到達圏探索実行後は、ある地点からダイクストラ法によって各ノードのポテンシャル（最短コスト）が計算済みであるので、ＰＯＩに隣接するノード（最も近いノード）のポテンシャルをそのＰＯＩまでの経路のコストとすることによって、コストの小さい順、すなわち、現在位置からＰＯＩまでの実際の経路長または時間の小さい順にＰＯＩをソートして案内することも可能である。以下の実施例においては、経路の所要時間を含め、単に経路距離と総称することとする。
【００６３】
情報配信サーバ３０は、携帯端末２０から現在位置と所望の到達圏範囲とＰＯＩカテゴリを指定した検索要求が送信されると、経路探索手段３３は探索用ネットワークデータ３５を用いて指定された到達圏範囲の到達可能な全てのノード（道路ネットワーク上のノード）を探索する。この探索を到達圏探索といい、一般に経路探索に用いられるダイクストラ法による探索方法を用い、現在位置から順次ノードをたどり（ダイクストラ法では拡散という）、そのポテンシャル（通過したノードまでの累計距離または時間）が指定された到達圏範囲（所定の距離または時間）に達したところで拡散を停止する。拡散を停止した時の全てのノードが現在位置から所定の距離または時間で到達可能なノードである。以下このノードを到達可能ノードという。
【００６４】
次に、到達圏ＰＯＩ範囲判定手段３６は経路探索手段３３が到達圏探索により探索した到達可能ノードを結ぶ多角形の図形（ポリゴン）を作成し、到達圏と重なるＰＯＩの範囲を判定する。到達圏ＰＯＩ判別手段３８は到達圏ＰＯＩ範囲内にあり、かつ、前記ポリゴンの範囲内に存在するＰＯＩを抽出し、各ＰＯＩについて最も近いノードを対応付けする。この詳細な方法については、後に詳細に説明する。すなわち、この処理によってＰＯＩと経路のノードが対応付けられ、ＰＯＩへの経路が既に探索済であることになる。また、到達圏探索を行うのでこの探索自体は現実的な距離または時間の範囲内であれば極めて短時間に探索が終了し、同時に到達圏内のＰＯＩまでの経路探索が終了していることから、効率的にＰＯＩまでの経路を考慮した案内をすることができるようになる。
【００６５】
経路探索のための道路ネットワークは以下のように構成されている。例えば、道路が図３に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータと構成される。
【００６６】
すなわち、図３において、○印、◎印がノードを示し、◎印は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図３では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００６７】
このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図３において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【００６８】
図３ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至る可能な経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。
【００６９】
これに対して、交通機関の経路探索のための交通ネットワークデータは以下のように構成されている。例えば、図４に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図４において、○印、◎印がノードを示し、◎印は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図４では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００７０】
しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図４に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。
【００７１】
図４に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。このため交通ネットワークのデータは道路ネットワークのデータ量に比べて膨大なデータ量になる。従って、それに応じて、経路探索に要する時間も多くの時間が必要になる。
【００７２】
このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。
例えば、図４において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。
【００７３】
一方、携帯端末２０は、図１に示されるように、制御手段２１、通信手段２２、ＧＰＳ受信機などからなる測位手段２３、液晶表示ユニットなどからなる表示手段２４、情報配信サーバ３０から配信されたデータなどを記憶する配信データ記憶手段２５、情報配信サーバ３０に対する各種要求を編集する配信要求編集手段２６、操作・入力手段２７を備えている。
【００７４】
制御手段２１は、図示してはいないがＲＡＭ、ＲＯＭを有するマイクロプロセッサ（ＣＰＵ）を備えて構成され、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。操作・入力手段２７は、数字キーやアルファベットキー、その他の機能キー、選択キー、スクロールキーなどからなる操作・入力手段ためのものであり、出力手段である表示手段２４に表示されるメニュー画面から所望のメニューを選択し、あるいは、キーを操作して種々の入力操作を行うものである。従って、表示手段２４は操作・入力手段２７の一部としても機能する。通信手段２２は、ネットワーク１１を介して情報配信サーバ３０と通信するためのインターフェースである。
【００７５】
ユーザが情報配信サーバ３０にＰＯＩの検索を依頼しようとする場合、携帯端末２０において操作・入力手段２７を操作し、図５に示すサービスメニュー画面を表示手段２４に表示して所望の選択入力を行う。例えば、ユーザが現在地から近い薬局を探索したい場合、周辺検索メニュー画面でＰＯＩカテゴリ「薬局」を選択し、到達圏の範囲を、例えば、徒歩１０分（または、経路距離８００ｍ）のように入力する。前述のようにして選択されたＰＯＩカテゴリ（薬局）、入力された条件（到達圏範囲）は、配信要求編集手段２６によりＰＯＩ探索要求として編集され情報配信サーバ３０に送信される。
【００７６】
情報配信サーバ３０がＰＯＩ探索要求を受信すると、経路探索手段３３は探索用ネットワークデータ３５を参照して到達圏探索を行う。図６は、到達圏探索の概念を説明するための模式図である。図６において、Ｐは携帯端末２０が測位した現在位置、黒丸はノード、黒丸をつなぐ実線はリンクを表している。ダイクストラ法による到達圏探索は、現在位置Ｐから出るリンクＬ１〜Ｌ４の全ての方向にリンク、ノードをたどり、各ノード毎にリンクコスト（たどったリンクの距離または時間）の累積を算出してノードのポテンシャルとする。ノードのポテンシャルが所定の距離または時間の範囲に達した時点でその先のリンク、ノードへの拡散（探索）を停止する。図６においては、ノードＮ１〜Ｎ９などが到達圏内の最もポテンシャルの大きいノードであり、このノードが所定の到達圏範囲内で到達可能な最も遠いノードになる。なお、このダイクストラ法の演算経過、演算結果を一時的に記憶して、後でＰＯＩのソートと経路案内に利用する。
【００７７】
次に、到達圏ＰＯＩ範囲判定手段３６は、経路探索手段３３が探索した到達可能ノードＮ１〜Ｎ９を含む到達圏内のノードを結ぶ多角形の図形（ポリゴン）を作成する。以下このポリゴンを到達圏ポリゴンという。図７は、図６に示す到達可能ノードを図形化する処理の概念を示す模式図である。すなわち、図７において、Ｐは携帯端末２０が測位した現在位置、黒丸はノード、黒丸をつなぐ実線はリンクを表している。ノードＮ１〜Ｎ９などは到達可能ノードのうち、現在位置Ｐから最も遠いノードである。図７に点線で示すように、現在地Ｐを中心にして所定の角度（１０°）ごとに見渡して、それぞれの角度領域ごとに最も遠いノード（図７においてはノードＮ１〜Ｎ９、Ｎ１０〜Ｎ２１）を求めてそのノード番号を記憶する。もし、その角度領域にノードが無ければ、ノードを記憶しない。前記の角度範囲ごとに、最も遠い（現在位置から最も遠い）ノード同士を結んで到達圏ポリゴンを形成する。
【００７８】
このポリゴンは、例えばビデオＲＡＭ上に塗りつぶしを行う処理で内部を表現することが出来る。ビデオＲＡＭが塗りつぶされていれば、そのビットに対応する位置はポリゴンの内部、すなわち到達圏内であることがわかる。（実際にビデオＲＡＭ上で行う必要は無い。見せる必要がないので、他の処理で使用される一般のＲＡＭ上に展開しても処理することができる）。これで、到達圏を図形的に表現できたことになる。
【００７９】
この後、到達圏ＰＯＩ判別手段３８は到達圏ＰＯＩ範囲判定手段３６が作成した到達圏ポリゴン内に存在する該当ＰＯＩ（ここでは、薬局）の抽出を行う。先にＰＯＩＤＢ３７の構成（図２参照）で述べたように、エリアを所定の緯度・経度で区切ったメッシュを単位とし、個々のＰＯＩが存在する場所に基づいて該当するメッシュに各ＰＯＩの情報が蓄積されている。従って、到達圏ＰＯＩ範囲判定手段３６は、到達圏ポリゴンが重なるメッシュを特定することができ、これによって到達圏ＰＯＩ範囲を決定することができる。
【００８０】
すなわち、到達圏ＰＯＩ判別手段３８は、図８に示すように到達圏ポリゴン８１が地理的に重なったメッシュＭ１〜Ｍ４の中に存在する全てのＰＯＩから探索条件に合致したＰＯＩを抽出する。すなわち、図８は、図７のように形成された到達圏ポリゴン８１とＰＯＩの情報を蓄積したメッシュの単位との関係を示す模式図であり、到達圏ポリゴン８１と重なったメッシュＭ１〜Ｍ４を示している。
【００８１】
到達圏ＰＯＩ判別手段３８は、到達圏ポリゴン８１と重なったメッシュＭ１〜Ｍ４の中に存在する全てのＰＯＩから、探索条件として指定されたカテゴリ「薬局」を条件に該当ＰＯＩを絞り込む（図２参照）。そして、絞り込んだ「薬局」のうち到達圏ポリゴン８１内にあるものを抽出する。図８において、ＰＯＩ３は「薬局」であるが、到達圏ポリゴン８１と重なるメッシュＭ１〜Ｍ４内にないので、絞り込みの対象にはならない。
【００８２】
ＰＯＩ１、ＰＯＩ２は到達圏ポリゴン８１と重なるメッシュＭ１〜Ｍ４内にあるので、絞り込みの対象になる。そしてＰＯＩ１は到達圏ポリゴン８１の内部にあるので該当ＰＯＩとして抽出される。一方、ＰＯＩ２は、到達圏ポリゴン８１の外部にあるので該当ＰＯＩとして抽出されない。到達圏ポリゴン８１はユーザが所望する経路上の距離または時間で到達可能なく範囲を意味するから、ＰＯＩ１は所望の距離または時間で到達することができ、ＰＯＩ２は所望の距離または時間で到達することができないＰＯＩであることを意味する。従って、ＰＯＩ１を該当ＰＯＩとして抽出するのである。
【００８３】
図８においては、説明のため、到達圏ポリゴン８１内の該当ＰＯＩがＰＯＩ１のみである状態を図示しているが、複数の該当ＰＯＩが抽出された場合、次のようにして現在位置Ｐから各ＰＯＩまでの経路距離または時間の大小によってＰＯＩをソートし、現在位置から実際の経路距離または時間の小さい順にＰＯＩリストを携帯端末２０に配信して案内することができる。
【００８４】
すなわち、ＰＯＩソート手段３９は、到達圏ＰＯＩ判別手段３８が前述のようにして抽出した各ＰＯＩを、それぞれ最も近くに存在する到達圏ポリゴン８１内のノードと関連付ける。図９はこの処理を説明するための模式図であり、図８において到達圏ポリゴン内にＰＯＩ１の他にＰＯＩＮが抽出された状態を示している。図９においてノードＮ４、Ｎ１４は図６の到達圏探索で探索されたノードを示している。
【００８５】
ＰＯＩ１対してはノードＮ１４が最も近いノードであり、ＰＯＩＮにたいしてはノードＮ４が最も近いノードである。これはノードの位置情報と各ＰＯＩの位置情報を比較することによって容易に決定することができる。各ノードは到達圏探索によって得られた結果であるから、ノードのポテンシャルは現在位置から各ノードまでの経路距離または時間を表しており、各ＰＯＩに関連付けられたノードのポテンシャルは当該ＰＯＩまでの経路距離または時間を近似している。従って、各ノードのポテンシャルの大小によってＰＯＩをソートすることによって、各ＰＯＩまでの経路距離または時間の小さい順にＰＯＩを並べて探索結果とすることができる。
【００８６】
図１０は、このようにして得られたＰＯＩ探索結果を携帯端末２０に配信し、表示手段２４に表示する。図１０Ａは上記の処理によってＰＯＩ（この場合「薬局」）が現在位置から経路距離の近い順にソートされて表示されている。この画面でユーザが最も近い薬局Ａを選択してクリックすると、図１０Ｂの画面に遷移して薬局Ａに関するＰＯＩ情報が表示される。この表示画面に当該ＰＯＩを含む単位地図データ要求へのハイパーリンク（図１０Ｂ中、「地図を表示する」の文字リンク）や、ナビゲーション（経路案内）開始の要求へのハイパーリンク（図１０Ｂ中の「ここに行く」の文字リンク）をつけておくと利便性が増す。ユーザは所望のＰＯＩを選択して図１０Ｂの表示画面でこれらの文字リンクをクリックするだけで、情報配信サーバ３０に地図を要求したり、経路案内を要求したりすることができる。
【００８７】
図１０ＡのＰＯＩ探索結果回答画面で所望のＰＯＩを選択し、図１０ＢのＰＯＩ情報画面でナビゲーション開始のハイパーリンクが操作され、情報配信サーバ３０に当該ＰＯＩへの経路案内の要求があった場合、このＰＯＩに最も近いノードが関連付けられており、このノードは到達圏探索で現在位置からの経路探索が終了しているものであるから、情報配信サーバ３０は、再度経路探索することなく案内経路を携帯端末２０に配信することができる。すなわち、ＰＯＩに最も近いノードが関連付けられているので、該当ノードからリンクを逆にたどることで現在位置から該当ノード（ＰＯＩ）までの案内経路を特定することができる。
【００８８】
探索の結果、十分なＰＯＩが探索されなかった場合は、条件を変更して（徒歩時間を長くして）再探索を行うように入力画面遷移してもよい。その際に、到達圏探索の演算結果が保存されているので、その続きから拡散（経路探索）を行えば、重複した演算（経路探索）を避けることができる。
【００８９】
また、地図データが要求された場合には、情報配信サーバ当該ＰＯＩが存在するメッシュと単位地図の相対関係を検索して該当地域の地図データを携帯端末２０に配信することができる。単位地図の区分とメッシュの区分を合わせ、メッシュ番号と地図番号を同じにしておけば、容易に該当地域の地図データを特定して携帯端末２０に配信することができ好ましい。更に、探索用ネットワークデータ３５も単位地図およびＰＯＩデータを区分したメッシュと同じ単位で区切っておけば、到達圏探索が及んだノード、リンクが存在するメッシュの識別コードから該当位置の地図データ、ＰＯＩデータのメッシュとの対応が直ちに特定できる。
【００９０】
図１１は以上の処理手順を示すフローチャートである。情報配信サーバ３０は先ずステップＳ１０の処理において、携帯端末２０からのＰＯＩ探索要求を受信する。このＰＯＩ探索要求には、少なくとも、携帯端末２０の現在位置、探索を希望するＰＯＩのカデゴリ、到達圏範囲（距離または時間）が含まれている。ステップＳ１１の処理においてこの探索要求が分析され、ステップＳ１２の処理において、経路探索手段３３は到達圏範囲の指定に従って到達圏探索を行う。到達圏探索の手法については先に説明した通りである。
【００９１】
ステップＳ１３の処理において、到達圏探索が終了したか否かが判別され、終了していない場合はステップＳ１２の処理に戻り探索が継続される。到達圏検索が終了していれば、ステップＳ１３の処理において到達圏ＰＯＩ範囲判定手段３６は、到達圏内のノードを判定して到達圏ポリゴンを作成する。到達圏ポリゴンの作成の手法についても、先に詳細に説明した。
【００９２】
次に、ステップＳ１５の処理において到達圏ＰＯＩ判別手段３８は、到達圏ポリゴンと重なるメッシュを抽出しそのメッシュに含まれ（メッシュ内に位置し）、かつ、到達圏ポリゴンの内部に存在するＰＯＩを抽出する。この処理において抽出するＰＯＩは、ＰＯＩ探索条件で指定されたカテゴリに属するＰＯＩである。また、ステップＳ１５の処理において、到達圏ＰＯＩ判別手段３８は抽出したＰＯＩの各々について、当該ＰＯＩに最も近いノード（到達圏ポリゴン内のノード）を決定し、各ＰＯＩと関連付けして記憶する。
【００９３】
ステップＳ１６の処理において、上記の到達圏ＰＯＩ判別の処理が全て終了したかを判別し、処理が終了していなければステップＳ１５の処理に戻り、到達圏ＰＯＩ判別処理を継続し、処理が終了していればステップＳ１７のＰＯＩソートの処理に進む。
ステップＳ１７の処理において、ＰＯＩソート手段３９は、ステップＳ１５の処理において抽出されたＰＯＩごとに対応付けられたノードのポテンシャルを比較し、ポテンシャルの小さい順、すなわち、現在位置からの経路長（距離または時間）の短い順にＰＯＩをソートする。ソートされた結果、すなわち、ステップＳ１２〜ステップＳ１７の処理によって探索、ソートされたＰＯＩのリスト（図１０Ａ参照）がステップＳ１８の処理において配信データ編集手段３２によって編集され、携帯端末２０に配信される。
【実施例２】
【００９４】
上記実施例１においては、到達圏ＰＯＩ判別手段が到達圏ポリゴン内のＰＯＩを抽出し、抽出した各ＰＯＩごとに最も近い到達圏ポリゴン内のノードを関連付ける例を説明したが、以下に説明する実施例２のような態様をとることもできる。実施例２のナビゲーションシステムの構成は実施例１（図１）と同様であり、処理の手順が異なる。ユーザが指定したＰＯＩのカテゴリは実施例１と同様「薬局」であったとする。
【００９５】
図１２は本発明の実施例２にかかるナビゲーションシステムにおけるＰＯＩ探索の処理手順を示すフローチャートである。図１２において、ステップＳ２０からステップＳ２３までの処理手順は、図１１におけるステップＳ１０〜ステップＳ１３までの処理の手順と同様である。ステップＳ２３までの処理において到達圏探索が終了すると、ステップＳ２４の処理に進む。
【００９６】
ステップＳ２４の処理において到達圏ＰＯＩ範囲判定手段３６は、実施例１のステップＳ１４の処理と異なり、到達圏ポリゴンを作成することなく、到達圏探索で拡散が及んだノード、リンクが含まれるメッシュを抽出して到達圏ＰＯＩ範囲を特定し、そのメッシュに含まれる（メッシュ内に位置する）ＰＯＩを抽出する。この処理において抽出するＰＯＩは、ＰＯＩ探索条件で指定されたカテゴリに属するＰＯＩ（「薬局」）である。
【００９７】
その後、ステップＳ２５の処理において、到達圏ＰＯＩ判別手段３８は抽出したＰＯＩの各々について、当該ＰＯＩに最も近い最寄りリンク（ＰＯＩから最寄りリンクに垂線を降ろして最も近いリンク）を見つけ、そのリンクが到達圏探索（拡散）の及んだリンク（図６参照）だったら、到達圏に含まれたＰＯＩとみなし、そうでなければ抽出ＰＯＩから削除する。こうして絞り込まれた各ＰＯＩには最も近い最寄りリンクが関連付けられて記憶される。もしも、ＰＯＩに最も近いリンクに拡散が及んでいなかったらそのＰＯＩは到達圏内に入っていないものとして抽出したＰＯＩから捨てる（削除する）。
【００９８】
図１３は、この処理手順の概念を示す模式図である。図１３において、ＰＯＩ４、ＰＯＩ５は、到達圏ＰＯＩ範囲判定手段３６が特定したメッシュ、すなわち、特定到達圏探索の範囲と重なったメッシュに存在する「薬局」である。ＰＯＩ４、ＰＯＩ５から最寄りの垂線を降ろして最も近いリンクを見つける。ＰＯＩ４からリンクＬｎに下ろした垂線の距離Ｄ４ｎ、ＰＯＩ５からリンクＬｍに下ろした垂線の距離Ｄ５ｍが最も短いので最寄りリンクは、それぞれＬｎ、Ｌｍに決定される。
【００９９】
リンクＬｎは実線で示すように到達圏探索が及んだリンクであり、リンクＬｍは点線で示すように到達圏探索が及ばなかったリンクである。従って、ＰＯＩ４は到達圏の範囲内のＰＯＩとして抽出され、ＰＯＩ５は到達圏かの範囲外として抽出ＰＯＩから除外される。ＰＯＩへの道のり（経路長）は、接続した垂線の長さと、リンクの接続点までの距離を勘案して詳細に求めてもよい。場合によっては最寄りリンクまでが遠くて条件に入らないＰＯＩもあり得る。実施例２の処理方法によれば、その検算を行うこともできる。
【０１００】
ステップＳ２６の処理において、上記の到達圏ＰＯＩ判別の処理が全て終了したかを判別し、処理が終了していなければステップＳ２５の処理に戻り、到達圏ＰＯＩ判別処理を継続し、処理が終了していればステップＳ２７のＰＯＩソートの処理に進む。
ステップＳ２７の処理において、ＰＯＩソート手段３９は、ステップＳ２５の処理において抽出されたＰＯＩごとに対応付けられたリンクに基づいて、経路長または時間を算出し、経路長または時間の小さい順、すなわち、現在位置からの経路長（距離または時間）の短い順にＰＯＩをソートする。経路長は到達圏探索によって所定の経路範囲の全てのノード、リンクの探索がなされているためその結果を使用して簡単に求めることができる。
【０１０１】
ＰＯＩソート手段３９によってソートされた結果、経路長または時間の小さい順に並べられたＰＯＩのリスト（図１０Ａ参照）が、ステップＳ２８の処理において配信データ編集手段３２によって編集され、携帯端末２０に配信される。配信結果は実施例１において図１０により説明したと同様である。
【産業上の利用可能性】
【０１０２】
本発明は、実施例１、実施例２において、携帯端末として携帯電話を用いたシステムとして説明したが、スタンドアロンタイプのカーナビシステム、通信タイプの携帯端末を使用したナビゲーションシステムなどに適用することができる。
【図面の簡単な説明】
【０１０３】
【図１】本発明の実施例にかかるＰＯＩ情報提供システムの構成を示す図である。
【図２】ＰＯＩカテゴリデータベース（ＤＢ）に蓄積されるＰＯＩ情報のデータ構成を示す説明図である。
【図３】道路ネットワークのデータの概念を示す模式図である。
【図４】交通ネットワークのデータの概念を示す模式図である。
【図５】本発明の携帯端末における周辺検索のサービスメニュー画面の構成を示す図であり、
【図６】到達圏探索の概念を説明するための模式図である。
【図７】到達圏を構成する多角図形化（到達圏ポリゴン）処理の概念を説明するための模式図である。
【図８】到達圏ポリゴンに存在する所望ＰＯＩを探索する処理の概念を説明するための模式図である。
【図９】到達圏ポリゴン内のＰＯＩのうち探索条件に合致する複数のＰＯＩについて経路距離または時間でソートする処理の概念を説明するための模式図である。
【図１０】携帯端末におけるＰＯＩ探索のためのメニュー画面および回答画面の構成を示す画面構成図であり、図１０Ａはメニュー画面、図１０Ｂは回答画面の構成を示す図である。
【図１１】本発明の実施例１にかかるＰＯＩ探索の手順を示すフローチャートである。
【図１２】本発明の実施例２にかかるＰＯＩ探索の手順を示すフローチャートである。
【図１３】本発明の実施例２における到達圏ＰＯＩ判別の手順を説明するための模式図である。
【符号の説明】
【０１０４】
１０・・・・ナビゲーションシステム
１１、１２・・ネットワーク
２０・・・・携帯端末
２１・・・・制御手段
２２・・・・通信手段
２３・・・・測位手段
２４・・・・表示手段
２５・・・・配信データ記憶手段
２６・・・・配信要求編集手段
２７・・・・操作・入力手段
３０・・・・情報配信サーバ
３１・・・・制御手段
３２・・・・配信データ編集手段
３３・・・・経路探索手段
３４・・・・通信手段
３５・・・・探索用ネットワークデータ
３６・・・・到達圏ＰＯＩ範囲判定手段
３７・・・・ＰＯＩＤＢ（データベース）
３８・・・・到達圏ＰＯＩ判別手段
３９・・・・ＰＯＩソート手段
５０・・・・ＰＯＩ情報提供サーバ
【技術分野】
【０００１】
本発明は、携帯電話などの携帯端末と情報配信サーバからなる通信型のナビゲーションシステムに関するものであり、特に、ユーザが所望する位置周辺における興味対象場所（ＰＯＩ）の情報を検索し、検索されたＰＯＩへの経路を案内することができるナビゲーションシステム、情報配信サーバおよび携帯端末に関するものである。
本発明は上記のようなナビゲーションシステムにおいて、現在位置などの所望位置からＰＯＩまでの実際の移動経路の距離または時間を考慮して、前記所望位置から近くに存在するＰＯＩを選択でき、また、情報配信サーバにおけるＰＯＩまでの経路探索を素早く、効率よく行うことができるようにしたナビゲーションシステム、情報配信サーバ、携帯端末に関するものである。
【背景技術】
【０００２】
近年、携帯電話など携帯端末がブラウザを搭載し、インターネットにアクセスして所望の情報の提供を受けることができるようになっている。このようなシステムにおいては、ユーザは携帯端末を操作して、サーバに備えられた検索エンジン等を利用して所望のサイトを見出し、当該サイトのコンテンツをダウンロードして、ブラウザにより当該コンテンツを閲覧している。上記コンテンツには種々のカテゴリに属する情報があり、店舗やイベントの情報提供、鉄道路線の時刻表の提供や、鉄道の乗り換え案内なども含まれる。
【０００３】
店舗やイベントの情報提供にあっては、ユーザが携帯端末を操作して店舗やイベントのカテゴリ、検索したい地域を入力して検索要求する。サーバは指定されたカテゴリに該当し、かつ当該地域に存在する店舗やイベントを検索し、その情報が携帯端末装置に配信される。時刻表の提供においては、ユーザが携帯端末を操作して、路線を指定すると、当該路線の時刻表が携帯端末の表示装置の画面上に提示される。また、乗り換え案内においては、ユーザが、出発地や目的地を指定することにより、推奨する経路が提示される。
【０００４】
情報配信サーバも機能が充実され、上記のような鉄道路線やバス路線の時刻表の提供や乗り換え案内にとどまらず、従来の車載用ナビゲーションシステムの機能を携帯電話などの携帯端末に提供する情報配信サーバも実現されている。このようなシステムによれば、自動車の運転者のみならず、歩行者に対するナビゲーションサービスを提供することができる。
【０００５】
携帯電話のユーザは上記のようなサービスを利用して種々の所望の情報を得ることができる。例えば、ユーザが興味を持っている興味対象場所（Point of Interest：以下単にＰＯＩという）に関する地図や営業内容、価格、営業時間などの情報を得ることができる。ＰＯＩとは、例えば、ホテル、レストラン、デパート、テーマパーク、コンビニ、ガソリンスタンド、運動施設、公園などのあらゆる店舗、施設が対象となり得る。このためＰＯＩは種類（カテゴリ）が膨大であり、当該カテゴリに属する店舗、場所も無数に存在する。情報配信サーバがカバーする範囲が広ければ広い程その数も増加する。
【０００６】
従って、これら無数のＰＯＩに関する情報をユーザに提供するため、情報配信サーバはＰＯＩデータベースを備えている。このＰＯＩデータベースにおいては、ＰＯＩはカテゴリ分けされており、また、このＰＯＩカテゴリはその数の多さから大分類、中分類、小分類などと階層化されている。ユーザは携帯端末に表示されたメニュー画面から所望のＰＯＩカテゴリを選択して情報配信サーバにデータを要求することになるが、特定の所望のＰＯＩカテゴリを選択するために、大分類、中分類、小分類とカテゴリの階層をたどり、情報配信を希望するＰＯＩカテゴリを選択することになる。
【０００７】
ユーザが利用する携帯端末が携帯電話である場合、最近の携帯電話はＧＰＳ受信機を備え、ＧＰＳ衛星からの信号を受信して自身の現在位置を算出する測位機能を有しておりこの機能を利用して現在位置を情報配信サーバに送信することができる。また、ナビゲーションサービスを受けることのできる携帯端末であれば、所望の特定のＰＯＩ情報を得た後、現在位置または自宅、勤務先など所望の出発地として当該特定のＰＯＩまでの経路探索を受けることもできる。
【０００８】
このようなＰＯＩ情報提供システムは種々提案されている。例えば、下記の特許文献１（特開２００３−１３２４８３号公報）に「情報配信方法」として開示されたシステムが知られている。
【０００９】
この特許文献１に開示された情報配信方法は、情報配信コンピュータシステムと端末装置である携帯電話とからなるシステムである。この情報配信コンピュータシステムは、外部の携帯電話から或るＰＯＩの案内情報が要求されると、所望ＰＯＩの案内情報に、ＰＯＩの位置情報と最適経路情報の情報配信コンピュータシステムに対する経路探索要求用のＵＲＬをリンク情報とするリンクを付随させて要求元に返信する。該携帯電話でＰＯＩの案内情報と一緒に表示されたリンクを選択すると、ＧＰＳ受信部で検出された現在位置を出発地、ＰＯＩの位置情報を目的地、計時部で計時された日時を出発予定日時とした経路探索条件が自動設定され、情報配信コンピュータシステムに対し、経路探索条件の情報を付随した経路探索要求をするように構成されている。
【００１０】
すなわち、この情報配信コンピュータシステムは、携帯電話からＰＯＩの検索要求があり、特定のＰＯＩを検索しそのＰＯＩ案内情報（地図、営業案内など）を携帯電話に配信する際に、経路探索機能へのリンク情報を付加して配信し、携帯電話がそのリンクを選択すると現在位置から当該ＰＯＩへの最適経路を探索して配信するようにしたものである。
【００１１】
また、下記の特許文献２（特開２００３−１５０４７５公報）に「情報提供システムおよび方法」として開示されたシステムも知られている。この特許文献２に開示された情報提供システムは、携帯端末とＷｅｂアプリケーションサーバからなるシステムである。
【００１２】
この情報提供システムにおいて、携帯端末を利用するユーザは、表示された提供サービスメニューから要求するサービスを選択する。選択されたサービスの情報はＷｅｂアプリケーションサーバに送信される。ＧＰＳ衛星は位置情報を出力する。携帯端末は、位置情報を受信し、受信した位置情報に基づいて現在位置を算出し、その現在位置の情報を、インターネットを介してＷｅｂアプリケーションサーバに送信する。Ｗｅｂアプリケーションサーバは、携帯端末から送信された現在位置の情報を受信し、携帯端末を利用するユーザによって選択されたサービスに関する情報であって、その現在位置に関連する情報を携帯端末に送信する。
【００１３】
一般的に、目的とするＰＯＩカテゴリに属する特定のＰＯＩが現在位置や所望の位置周辺（例えば、半径２ｋｍの範囲）に複数存在する場合、上記のようなＰＯＩ検索システムや経路案内システムにおいて検索された複数のＰＯＩに関する位置情報や関連情報は、現在位置や所望の位置から近い順に並べられて携帯端末に配信される。近い順とは現在位置や所望の位置からの各ＰＯＩまでの直線距離が短い順である。
【００１４】
例えば、下記の特許文献３（特開平１０−２８１７９７号公報）には、現在位置から直線距離の近い順にＰＯＩを検索して案内する車載用ナビゲーション装置及び周辺施設探索方法システム端末装置が開示されている。
【００１５】
この特許文献３に開示されたシステムは、テーブル記憶部に、用途別にグループ化されるカテゴリが記憶されている。ユーザが操作部を介して用途を入力すると、制御部は入力された用途に対応するグループのカテゴリを調べ、これらのカテゴリから車両の現在位置の周辺に存在する施設を探索する。探索した施設は現在位置から近い順に並べられ、ユーザが所望の施設を選択すると、制御部は現在位置から選択された施設までの案内経路を探索するように構成されている。
【００１６】
また、特許文献３のような周辺施設探索システムにおいて、現在位置から一定の距離範囲に存在する施設（ＰＯＩ）の探索を効率よく行うように構成したシステムとして、下記の特許文献４（特開２００４−６１５０３号公報）に開示されたＰＯＩ情報表示方法およびナビゲーションシステムも知られている。
【００１７】
この特許文献４に開示されたシステムは、ナビゲーションシステムにおいて、セル配列に特定ＰＯＩをそれぞれ持つセルを配置し、使用者位置に最も近いセルに対応するセル配列におけるセル位置からの距離に基づいてセルを複数の異なるレベルにソートする。このナビゲーションシステムは所定レベルのセルからＰＯＩを抽出し、距離に応じてＰＯＩをソートし、このＰＯＩを表示するように構成したものである。
【００１８】
すなわち、このシステムは所定の緯度、経度の範囲で区切られた単位地図と同様に特定のＰＯＩが存在するセルの配列をデータベースとして蓄積し、現在位置からの距離レベルに応じて該当するセル配列を選択して当該セルに存在するＰＯＩを探索することにより探索効率を向上させたものである。
【００１９】
【特許文献１】特開２００３−１３２４８３号公報（図１、段落［０００６］）
【特許文献２】特開２００３−１５０４７５号公報（図１、図２、段落［００１３］）
【特許文献３】特開平１０−２８１７９７号公報（図１、段落［００２８］、［００２９］）
【特許文献４】特開２００４−６１５０３号公報（図４、図６、図７、図８）
【発明の開示】
【発明が解決しようとする課題】
【００２０】
現在位置や所望位置から一定の範囲内にあるＰＯＩを探索して近い順にＰＯＩを並べて案内するシステムは、上記特許文献１〜特許文献４に開示されるように、直線距離に基づいてＰＯＩをソートするものであった。しかしながら、ユーザが実際に探索されたＰＯＩを訪れたいと思った場合、実際の移動経路を考慮して近いＰＯＩが選択できることが望ましい。直線距離が近くても、実際には河川や鉄道で遮られていて、道のりが遠い場合があるからである。
【００２１】
ところが、上記特許文献１〜特許文献４に開示されるようなシステムにおいては、直線距離に基づいてＰＯＩを現在位置や所望位置から近い順にソートして案内し、ユーザが選択したＰＯＩについて、経路探索してその経路を案内するものであるから、実際の経路としては遠回りになり、必ずしも最も近いＰＯＩに到達できる保証がないという問題点があった。
【００２２】
このような問題点を解消するために、現在位置や所望位置から実際の移動経路を探索してＰＯＩを経路の近い順に案内しようとすると、情報配信サーバが候補とすべきＰＯＩ全てについて経路探索をする必要が生じる。このような案内方法は、不可能ではないが、経路探索にかなりの時間を要するものであり、（１）情報配信サーバで候補ＰＯＩ全ての経路探索を行うと、１クライアント（携帯端末）から多数、例えば、１００個のＰＯＩを対象としたＰＯＩ探索要求があり、全ＰＯＩまでの経路探索を行うと、探索要求が集中する時間帯などシステム全体では過負荷になる恐れが生じるという問題点があった。また、（２）カーナビでは、移動速度が速いので上記のような多数のＰＯＩの経路を探索していると、経路探索が終了しないうちに現在地が変わってしまい、探索結果を配信した時には既にユーザが相当な距離走行していて役に立たない情報になってしまうという問題点があった。
【００２３】
本願の発明者は上記の問題点を解消すべく種々検討を重ねた結果、現在位置や所望位置から近いＰＯＩの探索要求があった場合、先ず、現在位置や所望位置からユーザが所望する時間または距離で到達できる道路ネットワーク上の範囲（到達圏）を探索し、到達圏内のＰＯＩを抽出し最も近いノードまたはリンクと対応付けて現在位置または所望位置からの経路とし距離（または時間）の短い順に該当ＰＯＩをソートして案内すれば、上記問題点を解消し得ることに想到し本発明を完成するに至ったものである。
【００２４】
すなわち、本発明は上記の問題点を解消することを課題とし、現在位置などの所望位置からＰＯＩまでの実際の移動経路を考慮して、前記所望位置から近くに存在するＰＯＩを選択でき、また、情報配信サーバのＰＯＩまでの経路探索を効率よく行うことができるようにしたナビゲーションシステム、情報配信サーバ、携帯端末を提供することを目的とするものである。
【課題を解決するための手段】
【００２５】
前記課題を解決するために、本願の請求項１にかかる発明は、
各ＰＯＩごとにＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件を設定する探索条件設定手段と、到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段と、を備え、
前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて前記基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成することを特徴とするナビゲーションシステムである。
【００２６】
また、本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだノードを結ぶポリゴンを作成し、当該ポリゴンと重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定することを特徴とする。
【００２７】
また、本願の請求項３にかかる発明は、請求項２にかかるナビゲーションシステムにおいて、前記到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、前記ポリゴンの範囲内のＰＯＩを抽出し、各ＰＯＩごとに前記到達圏探索の及んだノードのうち当該ＰＯＩに最も近いノードをそれぞれＰＯＩに対応付けることを特徴とする。
【００２８】
また、本願の請求項４にかかる発明は、請求項３にかかるナビゲーションシステムにおいて、前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたノードのポテンシャルに基づいて前記ＰＯＩをソートすることを特徴とする。
【００２９】
本願の請求項５にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだリンクに基づいて前記到達圏と重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定することを特徴とする請求項１に記載のナビゲーションシステム。
【００３０】
また、本願の請求項６にかかる発明は、請求項５にかかるナビゲーションシステムにおいて、前記到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、当該ＰＯＩから最も近いリンクを検出し、当該リンクが前記到達圏探索の及んだリンクであるＰＯＩを抽出し、当該リンクをそれぞれＰＯＩに対応付けることを特徴とする。
【００３１】
また、本願の請求項７にかかる発明は、請求項６にかかるナビゲーションシステムにおいて、前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたリンクに基づき経路距離または所要時間を求め、前記ＰＯＩをソートすることを特徴とする。
【００３２】
本願の請求項８にかかる発明は、
各ＰＯＩごとにＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件を設定する探索条件設定手段と、到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段と、を備えたナビゲーションシステムにおけるＰＯＩ探索方法であって、
前記経路探索手段が、ＰＯＩ探索条件に従って到達圏探索を行う第１のステップと、
前記到達圏ＰＯＩ範囲判定手段が、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する第２のステップと、
前記到達圏ＰＯＩ判別手段が、前記到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置し、前記ＰＯＩ探索条件に合致するＰＯＩを抽出する第３のステップと、前記抽出したＰＯＩについて、前記基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成する第４のステップと、からなることを特徴とする。
【００３３】
また、本願の請求項９にかかる発明は、請求項８にかかるＰＯＩ探索方法において、
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、
前記第２のステップは、前記到達圏ＰＯＩ範囲判定手段が到達圏探索の及んだノードを結ぶポリゴンを作成し、当該ポリゴンと重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定するステップを含むことを特徴とする。
【００３４】
また、本願の請求項１０にかかる発明は、請求項９にかかるＰＯＩ探索方法において、
前記第３のステップは、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、前記ポリゴンの範囲内のＰＯＩを抽出するステップを含み、前記第４のステップは、各ＰＯＩごとに前記到達圏探索の及んだノードのうち当該ＰＯＩに最も近いノードをそれぞれＰＯＩに対応付けるステップを含むことを特徴とする。
【００３５】
また、本願の請求項１１にかかる発明は、請求項１０にかかるＰＯＩ探索方法において、
前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、
前記ＰＯＩソート手段が前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたノードのポテンシャルに基づいて前記ＰＯＩをソートする第５のステップを含むことを特徴とする請求項１０に記載のＰＯＩ探索方法。
【００３６】
また、本願の請求項１２にかかる発明は、請求項８にかかるＰＯＩ探索方法において、
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、
前記第２のステップは、到達圏ＰＯＩ範囲判定手段が到達圏探索の及んだリンクに基づいて前記到達圏と重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定するステップを含むことを特徴とする請求項８に記載のＰＯＩ探索方法。
【００３７】
また、本願の請求項１３にかかる発明は、請求項１２にかかるＰＯＩ探索方法において、
前記第３のステップは、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、当該ＰＯＩから最も近いリンクを検出し、当該リンクが前記到達圏探索の及んだリンクであるＰＯＩを抽出するステップを含み、前記第４のステップは、各ＰＯＩごとに当該ＰＯＩから最も近いリンクをそれぞれＰＯＩに対応付けることを特徴とする。
【００３８】
また、本願の請求項１４にかかる発明は、請求項１３にかかるＰＯＩ探索方法において、
前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、
前記ＰＯＩソート手段が前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたリンクを含む経路の経路距離または所要時間を求め、前記ＰＯＩをソートする第５のステップを含むことを特徴とする。
【００３９】
本願の請求項１５にかかる発明は、
各ＰＯＩごとにＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件に基づいて到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段と、を備え、
前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて前記基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成することを特徴とする情報配信サーバである。
【００４０】
また、本願の請求項１６にかかる発明は、請求項１５にかかる情報配信サーバにおいて、
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだノードを結ぶポリゴンを作成し、当該ポリゴンと重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定することを特徴とする。
【００４１】
また、本願の請求項１７にかかる発明は、請求項１６にかかる情報配信サーバにおいて、
前記到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、前記ポリゴンの範囲内のＰＯＩを抽出し、各ＰＯＩごとに前記到達圏探索の及んだノードのうち当該ＰＯＩに最も近いノードをそれぞれＰＯＩに対応付けることを特徴とする。
【００４２】
また、本願の請求項１８にかかる発明は、請求項１７にかかる情報配信サーバにおいて、
前記情報配信サーバは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたノードのポテンシャルに基づいて前記ＰＯＩをソートすることを特徴とする。
【００４３】
また、本願の請求項１９にかかる発明は、請求項１５にかかる情報配信サーバにおいて、
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだリンクに基づいて前記到達圏と重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定することを特徴とする。
【００４４】
また、本願の請求項２０にかかる発明は、請求項１９にかかる情報配信サーバにおいて、
前記到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、当該ＰＯＩから最も近いリンクを検出し、当該リンクが前記到達圏探索の及んだリンクであるＰＯＩを抽出し、当該リンクをそれぞれＰＯＩに対応付けることを特徴とする。
【００４５】
また、本願の請求項２１にかかる発明は、請求項２０にかかる情報配信サーバにおいて、
前記情報配信サーバは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたリンクに基づき経路距離または所要時間を求め、前記ＰＯＩをソートすることを特徴とする。
【００４６】
本願の請求項２２にかかる発明は、
各ＰＯＩごとにＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件に基づいて到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段と、を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて前記基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成する情報配信サーバにネットワークを介して接続される携帯端末であって、
前記基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件を設定する探索条件設定手段を備えたことを特徴とする。
【発明の効果】
【００４７】
請求項１にかかる発明においては、基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件を設定し、経路探索手段が、ＰＯＩ探索条件に従って到達圏探索を行い、到達圏ＰＯＩ範囲判定手段が、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定し、到達圏ＰＯＩ判別手段が、前記到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置し、前記ＰＯＩ探索条件に合致するＰＯＩを抽出し、抽出したＰＯＩについて、基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成する。
従って、まず到達圏探索によって到達圏の範囲を決めることができ、この到達圏探索は短時間で効率よく終了させることができるようになる。この到達圏探索によってＰＯＩ近辺までの経路距離または所要時間は探索済であるから、その後、到達圏範囲内のＰＯＩを抽出し、抽出された各ＰＯＩについての基準位置からの実際の経路となる経路距離または所要時間を生成することができるようになる。これにより、実際の移動経路を考慮して近いＰＯＩが選択でき、直線距離が近くても、実際には河川や鉄道で遮られていて、道のりが遠いＰＯＩを除外したＰＯＩ探索が可能になる。
【００４８】
請求項２にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだノードを結ぶポリゴンを作成し、当該ポリゴンと重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定する。
従って、到達圏探索の結果に基づいて容易に到達圏の範囲内にある所望のＰＯＩの範囲を特定することができるようになる。
【００４９】
請求項３にかかる発明においては、請求項２にかかるナビゲーションシステムにおいて、到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、前記ポリゴンの範囲内のＰＯＩを抽出し、各ＰＯＩごとに前記到達圏探索の及んだノードのうち当該ＰＯＩに最も近いノードをそれぞれＰＯＩに対応付ける。従って、到達圏探索の結果に基づいて到達圏の範囲内にある所望のＰＯＩを抽出することができ、抽出されたＰＯＩまでの経路距離または所要時間を容易に生成することができるようになる。
【００５０】
請求項４にかかる発明おいては、請求項３にかかるナビゲーションシステムにおいて、ナビゲーションシステムは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたノードのポテンシャルに基づいて前記ＰＯＩをソートする。従って、到達圏内から抽出されたＰＯＩまでの経路距離または所要時間の近い順にＰＯＩを並べてその情報を提供することができるようになる。
【００５１】
請求項５にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだリンクに基づいて前記到達圏と重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定する。
到達圏探索の結果に基づいて容易に到達圏の範囲内にある所望のＰＯＩの範囲を特定することができるようになる。
【００５２】
請求項６にかかる発明においては、請求項５にかかるナビゲーションシステムにおいて、到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、当該ＰＯＩから最も近いリンクを検出し、当該リンクが前記到達圏探索の及んだリンクであるＰＯＩを抽出し、当該リンクをそれぞれＰＯＩに対応付ける。従って、到達圏探索の結果に基づいて到達圏の範囲内にある所望のＰＯＩを抽出することができ、抽出されたＰＯＩまでの経路距離または所要時間を容易に生成することができるようになる。
【００５３】
請求項７にかかる発明においては、請求項６にかかるナビゲーションシステムにおいて、前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたリンクに基づき経路距離または所要時間を求め、前記ＰＯＩをソートする。従って、到達圏内から抽出されたＰＯＩまでの経路距離または所要時間の近い順にＰＯＩを並べてその情報を提供することができるようになる。
【００５４】
請求項８ないし請求項１４にかかる発明においては、それぞれ請求項１ないし請求項７にかかるナビゲーションシステムにおけるＰＯＩ探索方法を提供することができるようになる。また、請求項１５ないし請求項２１にかかる発明においては、それぞれ請求項１ないし請求項７にかかるナビゲーションシステムを構成する情報配信サーバを提供することができるようになる。更に、請求項２２にかかる発明においては請求項１にかかるナビゲーションシステムを構成する携帯端末を提供することができるようになる。
【発明を実施するための最良の形態】
【００５５】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。なお、以下の実施例においては、携帯電話機を端末装置とし、経路探索および経路案内を行うナビゲーションシステムにＰＯＩ情報提供機能を備えたナビゲーションシステムを具体例として説明するが、本発明はこのような実施例に限ることなく、端末装置は車載型の端末装置のような移動端末であってもよい。本明細書においては、移動端末を含めて携帯端末と総称する。ただし、情報配信サーバは経路探索用のネットワークデータを備え、経路探索を行う機能を有している必要がある。
【実施例１】
【００５６】
図１は、本発明の実施例にかかるナビゲーションシステムの構成を示す図である。ナビゲーションシステム１０は、図１に示すように、インターネットなどのネットワーク１１を介して接続される携帯端末２０と情報配信サーバ３０を備えて構成されている。情報配信サーバ３０は、端末装置２０にＰＯＩ情報を提供するため、ＰＯＩカテゴリ別に区分し、当該カテゴリに属する各ＰＯＩとその位置情報（緯度・経度）、ＰＯＩが位置する単位地図と同様の単位に区切られたメッシュの識別番号（メッシュ番号）、営業案内などＰＯＩに関連する情報を蓄積したデータベースであるＰＯＩＤＢ３７と、経路探索手段３３、到達圏ＰＯＩ範囲判定手段３６、探索用ネットワークデータ３５、到達圏ＰＯＩ判別手段３８、ＰＯＩソート手段３９などを備えている。
【００５７】
ＰＯＩＤＢ３７に蓄積される全てのＰＯＩ情報は、エリアを所定の緯度・経度で区切ったメッシュを単位とし、個々のＰＯＩが存在する場所に基づいて該当するメッシュに各ＰＯＩの情報が蓄積されている。１つのメッシュは地図を緯度・経度で区切った単位地図の大きさとおなじ大きさであってよい。もちろん異なる大きさにすることもできる。
【００５８】
図２は、上記のＰＯＩＤＢ３７に蓄積されたＰＯＩの情報の構成を示す図である。図２に示すように、蓄積されるＰＯＩの情報は、メッシュ番号０００１〜０００２〜のように所定の緯度、経度で区切ったメッシュを単位として区分され、当該メッシュに存在するＰＯＩの情報が該当するメッシュに蓄積されている。蓄積されるＰＯＩの情報は、当該ＰＯＩの属するカテゴリ、ＰＯＩ（名称）、ＰＯＩの場所（緯度・経度）、ホームページ（ＵＲＬ）、営業案内などである。また、探索用ネットワークデータ３５には経路探索用の道路ネットワークのデータ、交通ネットワークのデータが蓄積されている。道路ネットワークのデータは自動車、歩行者のための経路探索に用いられ、交通ネットワークのデータは交通機関を利用した区間の経路探索に用いられる。
【００５９】
情報配信サーバ３０はまた、制御手段３１、配信データ編集手段３２、通信手段３４、を備えている。制御手段３１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段３４は、ネットワーク１１、１２を介して携帯端末２０や、各種のＰＯＩ情報を提供するＰＯＩ情報提供サーバ５０と通信するためのインターフェースである。配信データ編集手段３２は、経路探索やＰＯＩ探索の結果を携帯端末２０に配信するためのデータに編集するためのものである。情報配信サーバ３０は、ネットワーク１２を介して各種のＰＯＩ情報提供サーバ５０からＰＯＩの情報を収集してＰＯＩＤＢ３７にデータベース登録し、ユーザに提供できるＰＯＩ情報を充実してゆくことができる。
【００６０】
携帯端末２０は例えばＧＰＳ受信機などの測位手段を搭載した携帯電話機であり、現在地や目的地周辺の周辺検索、すなわち、所望のＰＯＩ検索が行える。現在位置や目的地の位置情報を付けて周辺検索要求を情報配信サーバ３０に送ると、情報配信サーバ３０は、携帯端末２０の現在位置または目的地の位置とＰＯＩまでの経路を考慮して、経路の所要時間または経路の距離が所望の範囲内にあるＰＯＩの探索要求ができるように構成されている。以下、この経路の距離または時間を到達圏範囲ということとする。ＰＯＩ検索にあたって携帯端末２０はＰＯＩカテゴリの選択画面が表示され、ユーザは所望のＰＯＩカテゴリを選択しまた所望の到達圏範囲（距離または時間）を入力し、ＰＯＩ探索要求を情報配信サーバ３０に送信し当該ＰＯＩカテゴリに属するＰＯＩを探索させる。以下の説明においては、現在位置を基準とした周辺検索を例にとり具体例を説明することとする。
【００６１】
到達圏探索とは、特に目的地を定めずに、ある地点（例えば現在地）から所定のコスト以下（道のり（経路距離）、所要時間など）で到達できるエリアを求めるものである。主に、出店計画や不動産の選択などで用いられる技術である。この技術は、例えば、本出願人により出願され、公開された特開２０００−１８７６５３号公報に開示されている。この技術は電車路線の到達圏探索の方法を開示している。
【００６２】
本実施例においては、現在地から所定の条件（経路距離、所要時間）で到達圏探索を行い、その結果到達圏を図形的に求め、その図形に含まれるＰＯＩをリストの候補にする。そして、到達圏探索実行後は、ある地点からダイクストラ法によって各ノードのポテンシャル（最短コスト）が計算済みであるので、ＰＯＩに隣接するノード（最も近いノード）のポテンシャルをそのＰＯＩまでの経路のコストとすることによって、コストの小さい順、すなわち、現在位置からＰＯＩまでの実際の経路長または時間の小さい順にＰＯＩをソートして案内することも可能である。以下の実施例においては、経路の所要時間を含め、単に経路距離と総称することとする。
【００６３】
情報配信サーバ３０は、携帯端末２０から現在位置と所望の到達圏範囲とＰＯＩカテゴリを指定した検索要求が送信されると、経路探索手段３３は探索用ネットワークデータ３５を用いて指定された到達圏範囲の到達可能な全てのノード（道路ネットワーク上のノード）を探索する。この探索を到達圏探索といい、一般に経路探索に用いられるダイクストラ法による探索方法を用い、現在位置から順次ノードをたどり（ダイクストラ法では拡散という）、そのポテンシャル（通過したノードまでの累計距離または時間）が指定された到達圏範囲（所定の距離または時間）に達したところで拡散を停止する。拡散を停止した時の全てのノードが現在位置から所定の距離または時間で到達可能なノードである。以下このノードを到達可能ノードという。
【００６４】
次に、到達圏ＰＯＩ範囲判定手段３６は経路探索手段３３が到達圏探索により探索した到達可能ノードを結ぶ多角形の図形（ポリゴン）を作成し、到達圏と重なるＰＯＩの範囲を判定する。到達圏ＰＯＩ判別手段３８は到達圏ＰＯＩ範囲内にあり、かつ、前記ポリゴンの範囲内に存在するＰＯＩを抽出し、各ＰＯＩについて最も近いノードを対応付けする。この詳細な方法については、後に詳細に説明する。すなわち、この処理によってＰＯＩと経路のノードが対応付けられ、ＰＯＩへの経路が既に探索済であることになる。また、到達圏探索を行うのでこの探索自体は現実的な距離または時間の範囲内であれば極めて短時間に探索が終了し、同時に到達圏内のＰＯＩまでの経路探索が終了していることから、効率的にＰＯＩまでの経路を考慮した案内をすることができるようになる。
【００６５】
経路探索のための道路ネットワークは以下のように構成されている。例えば、道路が図３に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータと構成される。
【００６６】
すなわち、図３において、○印、◎印がノードを示し、◎印は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図３では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００６７】
このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図３において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【００６８】
図３ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至る可能な経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。
【００６９】
これに対して、交通機関の経路探索のための交通ネットワークデータは以下のように構成されている。例えば、図４に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図４において、○印、◎印がノードを示し、◎印は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図４では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００７０】
しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図４に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。
【００７１】
図４に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。このため交通ネットワークのデータは道路ネットワークのデータ量に比べて膨大なデータ量になる。従って、それに応じて、経路探索に要する時間も多くの時間が必要になる。
【００７２】
このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。
例えば、図４において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。
【００７３】
一方、携帯端末２０は、図１に示されるように、制御手段２１、通信手段２２、ＧＰＳ受信機などからなる測位手段２３、液晶表示ユニットなどからなる表示手段２４、情報配信サーバ３０から配信されたデータなどを記憶する配信データ記憶手段２５、情報配信サーバ３０に対する各種要求を編集する配信要求編集手段２６、操作・入力手段２７を備えている。
【００７４】
制御手段２１は、図示してはいないがＲＡＭ、ＲＯＭを有するマイクロプロセッサ（ＣＰＵ）を備えて構成され、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。操作・入力手段２７は、数字キーやアルファベットキー、その他の機能キー、選択キー、スクロールキーなどからなる操作・入力手段ためのものであり、出力手段である表示手段２４に表示されるメニュー画面から所望のメニューを選択し、あるいは、キーを操作して種々の入力操作を行うものである。従って、表示手段２４は操作・入力手段２７の一部としても機能する。通信手段２２は、ネットワーク１１を介して情報配信サーバ３０と通信するためのインターフェースである。
【００７５】
ユーザが情報配信サーバ３０にＰＯＩの検索を依頼しようとする場合、携帯端末２０において操作・入力手段２７を操作し、図５に示すサービスメニュー画面を表示手段２４に表示して所望の選択入力を行う。例えば、ユーザが現在地から近い薬局を探索したい場合、周辺検索メニュー画面でＰＯＩカテゴリ「薬局」を選択し、到達圏の範囲を、例えば、徒歩１０分（または、経路距離８００ｍ）のように入力する。前述のようにして選択されたＰＯＩカテゴリ（薬局）、入力された条件（到達圏範囲）は、配信要求編集手段２６によりＰＯＩ探索要求として編集され情報配信サーバ３０に送信される。
【００７６】
情報配信サーバ３０がＰＯＩ探索要求を受信すると、経路探索手段３３は探索用ネットワークデータ３５を参照して到達圏探索を行う。図６は、到達圏探索の概念を説明するための模式図である。図６において、Ｐは携帯端末２０が測位した現在位置、黒丸はノード、黒丸をつなぐ実線はリンクを表している。ダイクストラ法による到達圏探索は、現在位置Ｐから出るリンクＬ１〜Ｌ４の全ての方向にリンク、ノードをたどり、各ノード毎にリンクコスト（たどったリンクの距離または時間）の累積を算出してノードのポテンシャルとする。ノードのポテンシャルが所定の距離または時間の範囲に達した時点でその先のリンク、ノードへの拡散（探索）を停止する。図６においては、ノードＮ１〜Ｎ９などが到達圏内の最もポテンシャルの大きいノードであり、このノードが所定の到達圏範囲内で到達可能な最も遠いノードになる。なお、このダイクストラ法の演算経過、演算結果を一時的に記憶して、後でＰＯＩのソートと経路案内に利用する。
【００７７】
次に、到達圏ＰＯＩ範囲判定手段３６は、経路探索手段３３が探索した到達可能ノードＮ１〜Ｎ９を含む到達圏内のノードを結ぶ多角形の図形（ポリゴン）を作成する。以下このポリゴンを到達圏ポリゴンという。図７は、図６に示す到達可能ノードを図形化する処理の概念を示す模式図である。すなわち、図７において、Ｐは携帯端末２０が測位した現在位置、黒丸はノード、黒丸をつなぐ実線はリンクを表している。ノードＮ１〜Ｎ９などは到達可能ノードのうち、現在位置Ｐから最も遠いノードである。図７に点線で示すように、現在地Ｐを中心にして所定の角度（１０°）ごとに見渡して、それぞれの角度領域ごとに最も遠いノード（図７においてはノードＮ１〜Ｎ９、Ｎ１０〜Ｎ２１）を求めてそのノード番号を記憶する。もし、その角度領域にノードが無ければ、ノードを記憶しない。前記の角度範囲ごとに、最も遠い（現在位置から最も遠い）ノード同士を結んで到達圏ポリゴンを形成する。
【００７８】
このポリゴンは、例えばビデオＲＡＭ上に塗りつぶしを行う処理で内部を表現することが出来る。ビデオＲＡＭが塗りつぶされていれば、そのビットに対応する位置はポリゴンの内部、すなわち到達圏内であることがわかる。（実際にビデオＲＡＭ上で行う必要は無い。見せる必要がないので、他の処理で使用される一般のＲＡＭ上に展開しても処理することができる）。これで、到達圏を図形的に表現できたことになる。
【００７９】
この後、到達圏ＰＯＩ判別手段３８は到達圏ＰＯＩ範囲判定手段３６が作成した到達圏ポリゴン内に存在する該当ＰＯＩ（ここでは、薬局）の抽出を行う。先にＰＯＩＤＢ３７の構成（図２参照）で述べたように、エリアを所定の緯度・経度で区切ったメッシュを単位とし、個々のＰＯＩが存在する場所に基づいて該当するメッシュに各ＰＯＩの情報が蓄積されている。従って、到達圏ＰＯＩ範囲判定手段３６は、到達圏ポリゴンが重なるメッシュを特定することができ、これによって到達圏ＰＯＩ範囲を決定することができる。
【００８０】
すなわち、到達圏ＰＯＩ判別手段３８は、図８に示すように到達圏ポリゴン８１が地理的に重なったメッシュＭ１〜Ｍ４の中に存在する全てのＰＯＩから探索条件に合致したＰＯＩを抽出する。すなわち、図８は、図７のように形成された到達圏ポリゴン８１とＰＯＩの情報を蓄積したメッシュの単位との関係を示す模式図であり、到達圏ポリゴン８１と重なったメッシュＭ１〜Ｍ４を示している。
【００８１】
到達圏ＰＯＩ判別手段３８は、到達圏ポリゴン８１と重なったメッシュＭ１〜Ｍ４の中に存在する全てのＰＯＩから、探索条件として指定されたカテゴリ「薬局」を条件に該当ＰＯＩを絞り込む（図２参照）。そして、絞り込んだ「薬局」のうち到達圏ポリゴン８１内にあるものを抽出する。図８において、ＰＯＩ３は「薬局」であるが、到達圏ポリゴン８１と重なるメッシュＭ１〜Ｍ４内にないので、絞り込みの対象にはならない。
【００８２】
ＰＯＩ１、ＰＯＩ２は到達圏ポリゴン８１と重なるメッシュＭ１〜Ｍ４内にあるので、絞り込みの対象になる。そしてＰＯＩ１は到達圏ポリゴン８１の内部にあるので該当ＰＯＩとして抽出される。一方、ＰＯＩ２は、到達圏ポリゴン８１の外部にあるので該当ＰＯＩとして抽出されない。到達圏ポリゴン８１はユーザが所望する経路上の距離または時間で到達可能なく範囲を意味するから、ＰＯＩ１は所望の距離または時間で到達することができ、ＰＯＩ２は所望の距離または時間で到達することができないＰＯＩであることを意味する。従って、ＰＯＩ１を該当ＰＯＩとして抽出するのである。
【００８３】
図８においては、説明のため、到達圏ポリゴン８１内の該当ＰＯＩがＰＯＩ１のみである状態を図示しているが、複数の該当ＰＯＩが抽出された場合、次のようにして現在位置Ｐから各ＰＯＩまでの経路距離または時間の大小によってＰＯＩをソートし、現在位置から実際の経路距離または時間の小さい順にＰＯＩリストを携帯端末２０に配信して案内することができる。
【００８４】
すなわち、ＰＯＩソート手段３９は、到達圏ＰＯＩ判別手段３８が前述のようにして抽出した各ＰＯＩを、それぞれ最も近くに存在する到達圏ポリゴン８１内のノードと関連付ける。図９はこの処理を説明するための模式図であり、図８において到達圏ポリゴン内にＰＯＩ１の他にＰＯＩＮが抽出された状態を示している。図９においてノードＮ４、Ｎ１４は図６の到達圏探索で探索されたノードを示している。
【００８５】
ＰＯＩ１対してはノードＮ１４が最も近いノードであり、ＰＯＩＮにたいしてはノードＮ４が最も近いノードである。これはノードの位置情報と各ＰＯＩの位置情報を比較することによって容易に決定することができる。各ノードは到達圏探索によって得られた結果であるから、ノードのポテンシャルは現在位置から各ノードまでの経路距離または時間を表しており、各ＰＯＩに関連付けられたノードのポテンシャルは当該ＰＯＩまでの経路距離または時間を近似している。従って、各ノードのポテンシャルの大小によってＰＯＩをソートすることによって、各ＰＯＩまでの経路距離または時間の小さい順にＰＯＩを並べて探索結果とすることができる。
【００８６】
図１０は、このようにして得られたＰＯＩ探索結果を携帯端末２０に配信し、表示手段２４に表示する。図１０Ａは上記の処理によってＰＯＩ（この場合「薬局」）が現在位置から経路距離の近い順にソートされて表示されている。この画面でユーザが最も近い薬局Ａを選択してクリックすると、図１０Ｂの画面に遷移して薬局Ａに関するＰＯＩ情報が表示される。この表示画面に当該ＰＯＩを含む単位地図データ要求へのハイパーリンク（図１０Ｂ中、「地図を表示する」の文字リンク）や、ナビゲーション（経路案内）開始の要求へのハイパーリンク（図１０Ｂ中の「ここに行く」の文字リンク）をつけておくと利便性が増す。ユーザは所望のＰＯＩを選択して図１０Ｂの表示画面でこれらの文字リンクをクリックするだけで、情報配信サーバ３０に地図を要求したり、経路案内を要求したりすることができる。
【００８７】
図１０ＡのＰＯＩ探索結果回答画面で所望のＰＯＩを選択し、図１０ＢのＰＯＩ情報画面でナビゲーション開始のハイパーリンクが操作され、情報配信サーバ３０に当該ＰＯＩへの経路案内の要求があった場合、このＰＯＩに最も近いノードが関連付けられており、このノードは到達圏探索で現在位置からの経路探索が終了しているものであるから、情報配信サーバ３０は、再度経路探索することなく案内経路を携帯端末２０に配信することができる。すなわち、ＰＯＩに最も近いノードが関連付けられているので、該当ノードからリンクを逆にたどることで現在位置から該当ノード（ＰＯＩ）までの案内経路を特定することができる。
【００８８】
探索の結果、十分なＰＯＩが探索されなかった場合は、条件を変更して（徒歩時間を長くして）再探索を行うように入力画面遷移してもよい。その際に、到達圏探索の演算結果が保存されているので、その続きから拡散（経路探索）を行えば、重複した演算（経路探索）を避けることができる。
【００８９】
また、地図データが要求された場合には、情報配信サーバ当該ＰＯＩが存在するメッシュと単位地図の相対関係を検索して該当地域の地図データを携帯端末２０に配信することができる。単位地図の区分とメッシュの区分を合わせ、メッシュ番号と地図番号を同じにしておけば、容易に該当地域の地図データを特定して携帯端末２０に配信することができ好ましい。更に、探索用ネットワークデータ３５も単位地図およびＰＯＩデータを区分したメッシュと同じ単位で区切っておけば、到達圏探索が及んだノード、リンクが存在するメッシュの識別コードから該当位置の地図データ、ＰＯＩデータのメッシュとの対応が直ちに特定できる。
【００９０】
図１１は以上の処理手順を示すフローチャートである。情報配信サーバ３０は先ずステップＳ１０の処理において、携帯端末２０からのＰＯＩ探索要求を受信する。このＰＯＩ探索要求には、少なくとも、携帯端末２０の現在位置、探索を希望するＰＯＩのカデゴリ、到達圏範囲（距離または時間）が含まれている。ステップＳ１１の処理においてこの探索要求が分析され、ステップＳ１２の処理において、経路探索手段３３は到達圏範囲の指定に従って到達圏探索を行う。到達圏探索の手法については先に説明した通りである。
【００９１】
ステップＳ１３の処理において、到達圏探索が終了したか否かが判別され、終了していない場合はステップＳ１２の処理に戻り探索が継続される。到達圏検索が終了していれば、ステップＳ１３の処理において到達圏ＰＯＩ範囲判定手段３６は、到達圏内のノードを判定して到達圏ポリゴンを作成する。到達圏ポリゴンの作成の手法についても、先に詳細に説明した。
【００９２】
次に、ステップＳ１５の処理において到達圏ＰＯＩ判別手段３８は、到達圏ポリゴンと重なるメッシュを抽出しそのメッシュに含まれ（メッシュ内に位置し）、かつ、到達圏ポリゴンの内部に存在するＰＯＩを抽出する。この処理において抽出するＰＯＩは、ＰＯＩ探索条件で指定されたカテゴリに属するＰＯＩである。また、ステップＳ１５の処理において、到達圏ＰＯＩ判別手段３８は抽出したＰＯＩの各々について、当該ＰＯＩに最も近いノード（到達圏ポリゴン内のノード）を決定し、各ＰＯＩと関連付けして記憶する。
【００９３】
ステップＳ１６の処理において、上記の到達圏ＰＯＩ判別の処理が全て終了したかを判別し、処理が終了していなければステップＳ１５の処理に戻り、到達圏ＰＯＩ判別処理を継続し、処理が終了していればステップＳ１７のＰＯＩソートの処理に進む。
ステップＳ１７の処理において、ＰＯＩソート手段３９は、ステップＳ１５の処理において抽出されたＰＯＩごとに対応付けられたノードのポテンシャルを比較し、ポテンシャルの小さい順、すなわち、現在位置からの経路長（距離または時間）の短い順にＰＯＩをソートする。ソートされた結果、すなわち、ステップＳ１２〜ステップＳ１７の処理によって探索、ソートされたＰＯＩのリスト（図１０Ａ参照）がステップＳ１８の処理において配信データ編集手段３２によって編集され、携帯端末２０に配信される。
【実施例２】
【００９４】
上記実施例１においては、到達圏ＰＯＩ判別手段が到達圏ポリゴン内のＰＯＩを抽出し、抽出した各ＰＯＩごとに最も近い到達圏ポリゴン内のノードを関連付ける例を説明したが、以下に説明する実施例２のような態様をとることもできる。実施例２のナビゲーションシステムの構成は実施例１（図１）と同様であり、処理の手順が異なる。ユーザが指定したＰＯＩのカテゴリは実施例１と同様「薬局」であったとする。
【００９５】
図１２は本発明の実施例２にかかるナビゲーションシステムにおけるＰＯＩ探索の処理手順を示すフローチャートである。図１２において、ステップＳ２０からステップＳ２３までの処理手順は、図１１におけるステップＳ１０〜ステップＳ１３までの処理の手順と同様である。ステップＳ２３までの処理において到達圏探索が終了すると、ステップＳ２４の処理に進む。
【００９６】
ステップＳ２４の処理において到達圏ＰＯＩ範囲判定手段３６は、実施例１のステップＳ１４の処理と異なり、到達圏ポリゴンを作成することなく、到達圏探索で拡散が及んだノード、リンクが含まれるメッシュを抽出して到達圏ＰＯＩ範囲を特定し、そのメッシュに含まれる（メッシュ内に位置する）ＰＯＩを抽出する。この処理において抽出するＰＯＩは、ＰＯＩ探索条件で指定されたカテゴリに属するＰＯＩ（「薬局」）である。
【００９７】
その後、ステップＳ２５の処理において、到達圏ＰＯＩ判別手段３８は抽出したＰＯＩの各々について、当該ＰＯＩに最も近い最寄りリンク（ＰＯＩから最寄りリンクに垂線を降ろして最も近いリンク）を見つけ、そのリンクが到達圏探索（拡散）の及んだリンク（図６参照）だったら、到達圏に含まれたＰＯＩとみなし、そうでなければ抽出ＰＯＩから削除する。こうして絞り込まれた各ＰＯＩには最も近い最寄りリンクが関連付けられて記憶される。もしも、ＰＯＩに最も近いリンクに拡散が及んでいなかったらそのＰＯＩは到達圏内に入っていないものとして抽出したＰＯＩから捨てる（削除する）。
【００９８】
図１３は、この処理手順の概念を示す模式図である。図１３において、ＰＯＩ４、ＰＯＩ５は、到達圏ＰＯＩ範囲判定手段３６が特定したメッシュ、すなわち、特定到達圏探索の範囲と重なったメッシュに存在する「薬局」である。ＰＯＩ４、ＰＯＩ５から最寄りの垂線を降ろして最も近いリンクを見つける。ＰＯＩ４からリンクＬｎに下ろした垂線の距離Ｄ４ｎ、ＰＯＩ５からリンクＬｍに下ろした垂線の距離Ｄ５ｍが最も短いので最寄りリンクは、それぞれＬｎ、Ｌｍに決定される。
【００９９】
リンクＬｎは実線で示すように到達圏探索が及んだリンクであり、リンクＬｍは点線で示すように到達圏探索が及ばなかったリンクである。従って、ＰＯＩ４は到達圏の範囲内のＰＯＩとして抽出され、ＰＯＩ５は到達圏かの範囲外として抽出ＰＯＩから除外される。ＰＯＩへの道のり（経路長）は、接続した垂線の長さと、リンクの接続点までの距離を勘案して詳細に求めてもよい。場合によっては最寄りリンクまでが遠くて条件に入らないＰＯＩもあり得る。実施例２の処理方法によれば、その検算を行うこともできる。
【０１００】
ステップＳ２６の処理において、上記の到達圏ＰＯＩ判別の処理が全て終了したかを判別し、処理が終了していなければステップＳ２５の処理に戻り、到達圏ＰＯＩ判別処理を継続し、処理が終了していればステップＳ２７のＰＯＩソートの処理に進む。
ステップＳ２７の処理において、ＰＯＩソート手段３９は、ステップＳ２５の処理において抽出されたＰＯＩごとに対応付けられたリンクに基づいて、経路長または時間を算出し、経路長または時間の小さい順、すなわち、現在位置からの経路長（距離または時間）の短い順にＰＯＩをソートする。経路長は到達圏探索によって所定の経路範囲の全てのノード、リンクの探索がなされているためその結果を使用して簡単に求めることができる。
【０１０１】
ＰＯＩソート手段３９によってソートされた結果、経路長または時間の小さい順に並べられたＰＯＩのリスト（図１０Ａ参照）が、ステップＳ２８の処理において配信データ編集手段３２によって編集され、携帯端末２０に配信される。配信結果は実施例１において図１０により説明したと同様である。
【産業上の利用可能性】
【０１０２】
本発明は、実施例１、実施例２において、携帯端末として携帯電話を用いたシステムとして説明したが、スタンドアロンタイプのカーナビシステム、通信タイプの携帯端末を使用したナビゲーションシステムなどに適用することができる。
【図面の簡単な説明】
【０１０３】
【図１】本発明の実施例にかかるＰＯＩ情報提供システムの構成を示す図である。
【図２】ＰＯＩカテゴリデータベース（ＤＢ）に蓄積されるＰＯＩ情報のデータ構成を示す説明図である。
【図３】道路ネットワークのデータの概念を示す模式図である。
【図４】交通ネットワークのデータの概念を示す模式図である。
【図５】本発明の携帯端末における周辺検索のサービスメニュー画面の構成を示す図であり、
【図６】到達圏探索の概念を説明するための模式図である。
【図７】到達圏を構成する多角図形化（到達圏ポリゴン）処理の概念を説明するための模式図である。
【図８】到達圏ポリゴンに存在する所望ＰＯＩを探索する処理の概念を説明するための模式図である。
【図９】到達圏ポリゴン内のＰＯＩのうち探索条件に合致する複数のＰＯＩについて経路距離または時間でソートする処理の概念を説明するための模式図である。
【図１０】携帯端末におけるＰＯＩ探索のためのメニュー画面および回答画面の構成を示す画面構成図であり、図１０Ａはメニュー画面、図１０Ｂは回答画面の構成を示す図である。
【図１１】本発明の実施例１にかかるＰＯＩ探索の手順を示すフローチャートである。
【図１２】本発明の実施例２にかかるＰＯＩ探索の手順を示すフローチャートである。
【図１３】本発明の実施例２における到達圏ＰＯＩ判別の手順を説明するための模式図である。
【符号の説明】
【０１０４】
１０・・・・ナビゲーションシステム
１１、１２・・ネットワーク
２０・・・・携帯端末
２１・・・・制御手段
２２・・・・通信手段
２３・・・・測位手段
２４・・・・表示手段
２５・・・・配信データ記憶手段
２６・・・・配信要求編集手段
２７・・・・操作・入力手段
３０・・・・情報配信サーバ
３１・・・・制御手段
３２・・・・配信データ編集手段
３３・・・・経路探索手段
３４・・・・通信手段
３５・・・・探索用ネットワークデータ
３６・・・・到達圏ＰＯＩ範囲判定手段
３７・・・・ＰＯＩＤＢ（データベース）
３８・・・・到達圏ＰＯＩ判別手段
３９・・・・ＰＯＩソート手段
５０・・・・ＰＯＩ情報提供サーバ
【特許請求の範囲】
【請求項１】
各ＰＯＩごとにＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件を設定する探索条件設定手段と、到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段と、を備え、
前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて前記基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成することを特徴とするナビゲーションシステム。
【請求項２】
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだノードを結ぶポリゴンを作成し、当該ポリゴンと重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項３】
前記到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、前記ポリゴンの範囲内のＰＯＩを抽出し、各ＰＯＩごとに前記到達圏探索の及んだノードのうち当該ＰＯＩに最も近いノードをそれぞれＰＯＩに対応付けることを特徴とする請求項２に記載のナビゲーションシステム。
【請求項４】
前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたノードのポテンシャルに基づいて前記ＰＯＩをソートすることを特徴とする請求項３に記載のナビゲーションシステム。
【請求項５】
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだリンクに基づいて前記到達圏と重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項６】
前記到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、当該ＰＯＩから最も近いリンクを検出し、当該リンクが前記到達圏探索の及んだリンクであるＰＯＩを抽出し、当該リンクをそれぞれＰＯＩに対応付けることを特徴とする請求項５に記載のナビゲーションシステム。
【請求項７】
前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたリンクに基づき経路距離または所要時間を求め、前記ＰＯＩをソートすることを特徴とする請求項６に記載のナビゲーションシステム。
【請求項８】
各ＰＯＩごとにＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件を設定する探索条件設定手段と、到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段と、を備えたナビゲーションシステムにおけるＰＯＩ探索方法であって、
前記経路探索手段が、ＰＯＩ探索条件に従って到達圏探索を行う第１のステップと、
前記到達圏ＰＯＩ範囲判定手段が、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する第２のステップと、
前記到達圏ＰＯＩ判別手段が、前記到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置し、前記ＰＯＩ探索条件に合致するＰＯＩを抽出する第３のステップと、前記抽出したＰＯＩについて、前記基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成する第４のステップと、
からなることを特徴とするＰＯＩ探索方法。
【請求項９】
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、
前記第２のステップは、前記到達圏ＰＯＩ範囲判定手段が到達圏探索の及んだノードを結ぶポリゴンを作成し、当該ポリゴンと重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定するステップを含むことを特徴とする請求項８に記載のＰＯＩ探索方法。
【請求項１０】
前記第３のステップは、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、前記ポリゴンの範囲内のＰＯＩを抽出するステップを含み、前記第４のステップは、各ＰＯＩごとに前記到達圏探索の及んだノードのうち当該ＰＯＩに最も近いノードをそれぞれＰＯＩに対応付けるステップを含むことを特徴とする請求項９に記載のＰＯＩ探索方法。
【請求項１１】
前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、
前記ＰＯＩソート手段が前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたノードのポテンシャルに基づいて前記ＰＯＩをソートする第５のステップを含むことを特徴とする請求項１０に記載のＰＯＩ探索方法。
【請求項１２】
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、
前記第２のステップは、到達圏ＰＯＩ範囲判定手段が到達圏探索の及んだリンクに基づいて前記到達圏と重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定するステップを含むことを特徴とする請求項８に記載のＰＯＩ探索方法。
【請求項１３】
前記第３のステップは、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、当該ＰＯＩから最も近いリンクを検出し、当該リンクが前記到達圏探索の及んだリンクであるＰＯＩを抽出するステップを含み、前記第４のステップは、各ＰＯＩごとに当該ＰＯＩから最も近いリンクをそれぞれＰＯＩに対応付けることを特徴とする請求項１２に記載のＰＯＩ探索方法。
【請求項１４】
前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、
前記ＰＯＩソート手段が前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたリンクを含む経路の経路距離または所要時間を求め、前記ＰＯＩをソートする第５のステップを含むことを特徴とする請求項１３に記載のＰＯＩ探索方法。
【請求項１５】
各ＰＯＩごとにＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件に基づいて到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段と、を備え、
前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて前記基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成することを特徴とする情報配信サーバ。
【請求項１６】
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだノードを結ぶポリゴンを作成し、当該ポリゴンと重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定することを特徴とする請求項１５に記載の情報配信サーバ。
【請求項１７】
前記到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、前記ポリゴンの範囲内のＰＯＩを抽出し、各ＰＯＩごとに前記到達圏探索の及んだノードのうち当該ＰＯＩに最も近いノードをそれぞれＰＯＩに対応付けることを特徴とする請求項１６に記載の情報配信サーバ。
【請求項１８】
前記情報配信サーバは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたノードのポテンシャルに基づいて前記ＰＯＩをソートすることを特徴とする請求項１７に記載の情報配信サーバ。
【請求項１９】
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだリンクに基づいて前記到達圏と重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定することを特徴とする請求項１５に記載の情報配信サーバ。
【請求項２０】
前記到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、当該ＰＯＩから最も近いリンクを検出し、当該リンクが前記到達圏探索の及んだリンクであるＰＯＩを抽出し、当該リンクをそれぞれＰＯＩに対応付けることを特徴とする請求項１９に記載の情報配信サーバ。
【請求項２１】
前記情報配信サーバは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたリンクに基づき経路距離または所要時間を求め、前記ＰＯＩをソートすることを特徴とする請求項２０に記載の情報配信サーバ。
【請求項２２】
各ＰＯＩごとにＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件に基づいて到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段と、を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて前記基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成する情報配信サーバにネットワークを介して接続される携帯端末であって、
前記基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件を設定する探索条件設定手段を備えたことを特徴とする携帯端末。
【請求項１】
各ＰＯＩごとにＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件を設定する探索条件設定手段と、到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段と、を備え、
前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて前記基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成することを特徴とするナビゲーションシステム。
【請求項２】
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだノードを結ぶポリゴンを作成し、当該ポリゴンと重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項３】
前記到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、前記ポリゴンの範囲内のＰＯＩを抽出し、各ＰＯＩごとに前記到達圏探索の及んだノードのうち当該ＰＯＩに最も近いノードをそれぞれＰＯＩに対応付けることを特徴とする請求項２に記載のナビゲーションシステム。
【請求項４】
前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたノードのポテンシャルに基づいて前記ＰＯＩをソートすることを特徴とする請求項３に記載のナビゲーションシステム。
【請求項５】
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだリンクに基づいて前記到達圏と重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項６】
前記到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、当該ＰＯＩから最も近いリンクを検出し、当該リンクが前記到達圏探索の及んだリンクであるＰＯＩを抽出し、当該リンクをそれぞれＰＯＩに対応付けることを特徴とする請求項５に記載のナビゲーションシステム。
【請求項７】
前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたリンクに基づき経路距離または所要時間を求め、前記ＰＯＩをソートすることを特徴とする請求項６に記載のナビゲーションシステム。
【請求項８】
各ＰＯＩごとにＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件を設定する探索条件設定手段と、到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段と、を備えたナビゲーションシステムにおけるＰＯＩ探索方法であって、
前記経路探索手段が、ＰＯＩ探索条件に従って到達圏探索を行う第１のステップと、
前記到達圏ＰＯＩ範囲判定手段が、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する第２のステップと、
前記到達圏ＰＯＩ判別手段が、前記到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置し、前記ＰＯＩ探索条件に合致するＰＯＩを抽出する第３のステップと、前記抽出したＰＯＩについて、前記基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成する第４のステップと、
からなることを特徴とするＰＯＩ探索方法。
【請求項９】
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、
前記第２のステップは、前記到達圏ＰＯＩ範囲判定手段が到達圏探索の及んだノードを結ぶポリゴンを作成し、当該ポリゴンと重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定するステップを含むことを特徴とする請求項８に記載のＰＯＩ探索方法。
【請求項１０】
前記第３のステップは、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、前記ポリゴンの範囲内のＰＯＩを抽出するステップを含み、前記第４のステップは、各ＰＯＩごとに前記到達圏探索の及んだノードのうち当該ＰＯＩに最も近いノードをそれぞれＰＯＩに対応付けるステップを含むことを特徴とする請求項９に記載のＰＯＩ探索方法。
【請求項１１】
前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、
前記ＰＯＩソート手段が前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたノードのポテンシャルに基づいて前記ＰＯＩをソートする第５のステップを含むことを特徴とする請求項１０に記載のＰＯＩ探索方法。
【請求項１２】
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、
前記第２のステップは、到達圏ＰＯＩ範囲判定手段が到達圏探索の及んだリンクに基づいて前記到達圏と重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定するステップを含むことを特徴とする請求項８に記載のＰＯＩ探索方法。
【請求項１３】
前記第３のステップは、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、当該ＰＯＩから最も近いリンクを検出し、当該リンクが前記到達圏探索の及んだリンクであるＰＯＩを抽出するステップを含み、前記第４のステップは、各ＰＯＩごとに当該ＰＯＩから最も近いリンクをそれぞれＰＯＩに対応付けることを特徴とする請求項１２に記載のＰＯＩ探索方法。
【請求項１４】
前記ナビゲーションシステムは更に、ＰＯＩソート手段を備え、
前記ＰＯＩソート手段が前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたリンクを含む経路の経路距離または所要時間を求め、前記ＰＯＩをソートする第５のステップを含むことを特徴とする請求項１３に記載のＰＯＩ探索方法。
【請求項１５】
各ＰＯＩごとにＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件に基づいて到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段と、を備え、
前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて前記基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成することを特徴とする情報配信サーバ。
【請求項１６】
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだノードを結ぶポリゴンを作成し、当該ポリゴンと重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定することを特徴とする請求項１５に記載の情報配信サーバ。
【請求項１７】
前記到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、前記ポリゴンの範囲内のＰＯＩを抽出し、各ＰＯＩごとに前記到達圏探索の及んだノードのうち当該ＰＯＩに最も近いノードをそれぞれＰＯＩに対応付けることを特徴とする請求項１６に記載の情報配信サーバ。
【請求項１８】
前記情報配信サーバは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたノードのポテンシャルに基づいて前記ＰＯＩをソートすることを特徴とする請求項１７に記載の情報配信サーバ。
【請求項１９】
前記ＰＯＩデータベースは、所定の地理的面積のメッシュ単位に前記ＰＯＩ情報を蓄積し、前記到達圏ＰＯＩ範囲判定手段は到達圏探索の及んだリンクに基づいて前記到達圏と重なる前記メッシュを特定して到達圏ＰＯＩ範囲を決定することを特徴とする請求項１５に記載の情報配信サーバ。
【請求項２０】
前記到達圏ＰＯＩ判別手段は、前記決定されたメッシュに含まれ、前記探索条件設定手段により設定されたＰＯＩカテゴリの属するＰＯＩであって、当該ＰＯＩから最も近いリンクを検出し、当該リンクが前記到達圏探索の及んだリンクであるＰＯＩを抽出し、当該リンクをそれぞれＰＯＩに対応付けることを特徴とする請求項１９に記載の情報配信サーバ。
【請求項２１】
前記情報配信サーバは更に、ＰＯＩソート手段を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて、前記ＰＯＩごとに対応付けられたリンクに基づき経路距離または所要時間を求め、前記ＰＯＩをソートすることを特徴とする請求項２０に記載の情報配信サーバ。
【請求項２２】
各ＰＯＩごとにＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件に基づいて到達圏探索を行いその探索過程と探索結果を記憶する経路探索手段と、到達圏探索の及んだ範囲を含む所定の到達圏ＰＯＩ範囲を判定する到達圏ＰＯＩ範囲判定手段と、ＰＯＩ探索条件に合致する到達圏ＰＯＩ範囲内に存在し、かつ、到達圏内に位置するＰＯＩを抽出する到達圏ＰＯＩ判別手段と、を備え、前記到達圏ＰＯＩ判別手段により抽出されたＰＯＩについて前記基準位置から当該ＰＯＩまでの経路距離または所要時間を含むＰＯＩ情報を生成する情報配信サーバにネットワークを介して接続される携帯端末であって、
前記基準位置と基準位置からの到達圏の範囲と所望のＰＯＩカテゴリを含むＰＯＩ探索条件を設定する探索条件設定手段を備えたことを特徴とする携帯端末。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２００７−４０７２１（Ｐ２００７−４０７２１Ａ）
【公開日】平成１９年２月１５日（２００７．２．１５）
【国際特許分類】
【出願番号】特願２００５−２２２２３４（Ｐ２００５−２２２２３４）
【出願日】平成１７年７月２９日（２００５．７．２９）
【出願人】（５００１６８８１１）株式会社ナビタイムジャパン (410)
【Ｆターム（参考）】
【公開日】平成１９年２月１５日（２００７．２．１５）
【国際特許分類】
【出願日】平成１７年７月２９日（２００５．７．２９）
【出願人】（５００１６８８１１）株式会社ナビタイムジャパン (410)
【Ｆターム（参考）】
[ Back to top ]