(57)【要約】【課題】興味ある地点を表示する方法およびシステムを提供すること。【解決手段】本発明は、地図区域および興味ある地点（ＰＯＩ）データをユーザに表示するディスプレイと、ＰＯＩデータを格納するデータベースとを含むナビゲーションシステムを提供する。検索ユニットは、表示されるべき地図区域のためのＰＯＩデータをデータベースから検索するために提供される。本発明の実施形態において、ＰＯＩデータベースは、地図領域において、ＰＯＩと、ＰＯＩの数を表す代用ＰＯＩとを含む。次いで、代用ＰＯＩか、または代用ＰＯＩが表すＰＯＩがデータベースから検索されるかは、地図区域が表示されるべき地図縮尺により得る。【選択図】図１
2012042950.tif 000002
【特許請求の範囲】
【請求項１】
異なる地図縮尺で地図を表示することが可能であるナビゲーションシステムのディスプレイ上にＰＯＩを表示する方法であって、
該ナビゲーションシステムは、ＰＯＩおよびその位置を含むＰＯＩデータを格納するデータベースを含み、
該ＰＯＩデータは、異なる地図縮尺に対して提供される異なるサイズの地図領域に対する代用ＰＯＩをさらに含み、
特定の地図領域内に位置を定められるＰＯＩの数が閾値数を超えた場合、代用ＰＯＩが該特定の地図領域に提供され、該代用ＰＯＩは該地図領域において該ＰＯＩを表し、
該方法は、
該ディスプレイ上に特定の地図縮尺で表示されるべき地図区域を決定するステップと、
該地図区域のデータベースから表示されるべきＰＯＩデータを検索するステップであって、該ＰＯＩデータの検索は、特定の地図縮尺に従ってＰＯＩまたは代用ＰＯＩのいずれかが表示のために検索されるような方法で、代用ＰＯＩが該データベースに提供される該地図区域内に位置を定められるＰＯＩに対して行われる、ステップと、
該地図区域および検索されたＰＯＩデータを表示するステップであって、該検索されたＰＯＩデータに含まれ、該地図区域内に位置を定められる該代用ＰＯＩは、該代用ＰＯＩが表す該ＰＯＩの代替物として表示される、ステップと
を包含する、方法。
【請求項２】
前記ＰＯＩデータは、木構造で前記データベースに格納され、該データベースにおいて、ＰＯＩおよび代用ＰＯＩはノードに格納され、代用ＰＯＩのノードは、該代用ＰＯＩが表す該ＰＯＩのノードにリンクされ、該木構造の異なる深度レベルは、それぞれの深度レベルの該ノードに格納される該代用ＰＯＩに関連付けられる地図領域の異なるサイズに対応、請求項１に記載の方法。
【請求項３】
前記ＰＯＩデータを検索することおよび表示することは、
前記表示されるべき地図区域に対する前記木構造の根ノードを決定するステップと、
該決定された根ルートにリンクされるノードの探索を行うステップであって、該探索は、隣り合うノードの地図位置が前記特定の地図縮尺に依存する最小距離より小さい距離を有する該木構造の深度レベルにおいて停止される、ステップと、
該停止深度レベルより高いすべての深度レベルにおいて該探索される木に含まれるＰＯＩを検索するステップと、
停止レベルより１レベル上である深度レベルにおいて該探索される木に含まれる前記代用ＰＯＩを検索するステップと、
該検索されたＰＯＩおよび代用ＰＯＩをＰＯＩデータとして表示されるように提供するステップと
を包含する、請求項２に記載の方法。
【請求項４】
前記木構造の最高の深度レベルは根ノートを含み、該根ノードは前記地図領域のうちの最大領域に関連付けられる代用ＰＯＩまたはＰＯＩを格納する、請求項２または３に記載の方法。
【請求項５】
前記木構造は、前記ＰＯＩが該ＰＯＩ間の距離に関係なく前記データベースに別個のＰＯＩとして格納される最低深度レベルを含む、請求項２〜４のいずれかに記載の方法。
【請求項６】
前記ディスプレイに表示される代用ＰＯＩをユーザ選択可能にするステップと、
ユーザ入力によって該代用ＰＯＩを選択したときに、該選択された代用ＰＯＩが表すＰＯＩの選択リストを該ユーザに提供するステップと
をさらに包含する、請求項１〜５のいずれかに記載の方法。
【請求項７】
前記データベースにおける前記ＰＯＩデータは、異なるＰＯＩカテゴリーに提供され、地図領域において同じカテゴリーのＰＯＩの数が前記閾値数を越える場合、特定のカテゴリーに対するＰＯＩデータは、該地図領域に対する該カテゴリーの代用ＰＯＩを含む、請求項１〜６のいずれかに記載の方法。
【請求項８】
表示されるべきＰＯＩの１つ以上のカテゴリーを決定するステップをさらに包含し、該表示は、概観地図縮尺ですべての決定されたカテゴリーに対するＰＯＩデータが表示されるように行われる、請求項７に記載の方法。
【請求項９】
それぞれのカテゴリーが表示されるために選択される場合、表示は、概観地図縮尺でレストランおよびガソリンスタンドのカテゴリーのうちの少なくとも１つに対するＰＯＩデータが表示されるように行われる、請求項７または８に記載の方法。
【請求項１０】
前記概観地図縮尺は、約１：５００，０００より小さく、好ましくは約１：１，０００，０００より小さく、そしてより好ましくは約１：２，０００，０００より小さい、請求項８または９に記載の方法。
【請求項１１】
代用ＰＯＩに関連付けられた地図領域のサイズは、前記木構造のより高い深度レベルにおけるノードの場合が、より低い深度レベルにおけるノードに対する場合よりも大きい、請求項１〜１０のいずれか１項、かつ、請求項２に記載の方法。
【請求項１２】
前記木構造において、ノードに格納される代用ＰＯＩの地図領域は、該ノードの親ノードに格納される代用ＰＯＩの地図領域に部分的または完全に含まれる、請求項１〜１１のいずれか１項、かつ、請求項２に記載の方法。
【請求項１３】
代用ＰＯＩは、該代用ＰＯＩが表すＰＯＩの数を示す図形記号として表示される、請求項１〜１２のいずれかに記載の方法。
【請求項１４】
地図区域およびＰＯＩデータをユーザに表示するディスプレイと、
ＰＯＩおよびその位置を含むＰＯＩデータを格納するデータベースであって、該ＰＯＩデータは異なる地図縮尺に対して提供される異なるサイズの地図領域に対する代用ＰＯＩをさらに含み、該地図領域内に位置を定められるＰＯＩの数が閾値数を超える場合、代用ＰＯＩは特定の地図領域に提供され、該代用ＰＯＩは該地図領域において該ＰＯＩを表す、データベースと、
特定の地図縮尺で表示されるべき地図区域を決定するように適合される地図ユニットと、
該地図区域に対する該データベースから表示されるべきＰＯＩデータを検索されるように適合される検索ユニットであって、該ＰＯＩデータの検索は、該地図縮尺に従ってＰＯＩまたは代用ＰＯＩのいずれかが表示のために検索されるような方法で、代用ＰＯＩが該データベースに提供される該地図区域内に位置を定められるＰＯＩに対して行われる、検索ユニットと、
表示制御ユニットであって、該表示制御ユニットは、該検索されたＰＯＩデータに含まれ、該地図区域内に位置を定められる代用ＰＯＩは、代用ＰＯＩが表す該ＰＯＩの代替物として表示されるように、該地図区域および該検索されたＰＯＩデータを表示するように適合される、表示制御ユニットと
を備えている、ナビゲーションシステム。
【請求項１５】
前記ナビゲーションシステムは、請求項２〜１３のいずれか１項に記載の方法を行うように構成される、請求項１４に記載のナビゲーションシステム。
【請求項１６】
プログラムが記録されたコンピュータ読み取り可能格納媒体であって、該プログラムは、コンピュータによって実行されると、該コンピュータに請求項１〜１３のうちのいずれか１項に記載の方法を行わせる、コンピュータ読み取り可能格納媒体。
【請求項１７】
コンピュータ読み取り可能格納媒体であって、該コンピュータ読み取り可能格納媒体に、ＰＯＩデータベースが格納され、該ＰＯＩデータベースは、異なるカテゴリーおよびその位置のＰＯＩを含み、該データベースは、異なる地図縮尺に対して提供される異なるサイズの地図領域に対する代用ＰＯＩをさらに含み、該地図領域における該同じカテゴリーのＰＯＩの数が閾値数を超えた場合、カテゴリーの代用ＰＯＩは特定の地図領域に提供され、該代用ＰＯＩは、該地図領域において該ＰＯＩを表す、コンピュータ読み取り可能格納媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
（技術分野）
本発明は、異なる地図縮尺で地図を表示することが可能なナビゲーションシステムのディスプレイ上に興味ある地点（ｐｏｉｎｔ  ｏｆ  ｉｎｔｅｒｅｓｔ）（ＰＯＩ）を表示する方法および対応するナビゲーションシステムに関する。本発明は、さらに、興味ある地点（ＰＯＩ）データベースを含むデータキャリアに関する。
【背景技術】
【０００２】
（背景）
近年、単純なハンドヘルドナビゲーションデバイスまたはより複雑な車内システムなどのナビゲーションシステムの使用が急増してきた。ほとんど例外なく、ナビゲーションデバイスは、ユーザに地図情報が与えられるディスプレイを含む。ナビゲーションデバイスに表示される地図は、概して、都市および都市間をつなぐ道路、都市のサイズ、およびそれぞれの図形記号によって表示されている道路のカテゴリーの図形表示を含む。
【０００３】
いくつかの従来のデバイスはさらに、そのような地図上に興味ある地点（ＰＯＩ）を表示することが可能である。概して、興味ある地点の異なるカテゴリーは、表示のために利用可能であり、自動的にまたはユーザインタラクションによって選ばれ得る。カテゴリーは、例えば、空港、興味ある名所、ガソリンスタンド、レストラン、薬局、映画館などに対して提供され得る。従って、ユーザは、地図上の興味ある地点の場所に興味ある地点を表すアイコンを表示することによって、有用な情報が提供され得る。ユーザにとって、このことは、特定の名所またはレストランを通過する走行経路を選ぶこと、または例えば最も近いレストランへの経路を見つけることを容易にする。
【０００４】
オリエンテーションおよびナビゲーションを容易にするために、ナビゲーションデバイスは、概して、いくつかのズームレベルを有する、すなわち異なる地図縮尺で地図を表示することが可能である地図表示機能が備え付けられる。複数のＰＯＩが存在する都市において、選択されたカテゴリーのＰＯＩは、概して、互いに妨害することなしに、より大きい地図縮尺で表示され得る。より小さい地図縮尺に対して、すなわちユーザがズームアウトした場合、より大きな地図区域が同じサイズの画面に表示され、表示されるＰＯＩアイコンの密度の増加を引き起す。このことは、結果として表示の過密が生じ得、本質的に表示情報を役に立たなくする。
【０００５】
従来のシステムにおいて、この問題は、地図上のＰＯＩの特定のカテゴリーの特定の密度を想定することによって解決され、ＰＯＩの特定のカテゴリーの特定の密度は特定の地図縮尺に対するディスプレイ画面上のアイコンの密度に対応する。ディスプレイ画面上のアイコンの想定された密度が高くなりすぎる地図縮尺において、このカテゴリーのアイコンは消され、もはや表示されない。なおまたアイコンを消すような閾値地図縮尺は過度に低く設定することはできないので、過密状態は、概して、依然として都市地域において起こる。
【０００６】
他方、田園地域において、大きい縮尺では、ディスプレイに示される地図区域が有用な情報を含むには小さすぎるので、地図データを表示するために、概して、より小さい地図縮尺が用いられる。従って、特定のカテゴリーのＰＯＩアイコンがなおも表示されている、より大きい地図縮尺において、表示される地図区域が小さすぎるので、どのアイコンも見えない。視野を拡大するために、ユーザが地図をズームアウト、すなわちより小さい地図縮尺に変更した場合、より小さい地図縮尺（および想定されたより高いアイコン密度）のためにアイコンカテゴリーが消される。一例として、レストランのカテゴリーのＰＯＩは、１：２００，０００〜１：５００，０００の地図縮尺で既に消される。従って、ユーザは、田園地域において、近くを通ることが便利なレストランを見つけることが困難である。
【０００７】
低密度インフラストラクチャのみを有するそのような田園地域に対して、従来のナビゲーションシステムは、ユーザにＰＯＩのリストを戻すＰＯＩ探索を行うよう勧めるのみである。問題は、概して特定のＰＯＩが地図上のどこに位置するか、またはＰＯＩがどの方向に位置するかをユーザが知らないことである。従って、ユーザが田園地域を通って特定のルートを走行し、ユーザがレストランで止まりたい場合、そのようなＰＯＩ探索は概してそれほど助けとはならない。
【０００８】
従って、ナビゲーションシステムにおけるＰＯＩの表示を改善すること、特に、異なる地図縮尺で便利で有用なＰＯＩの表現を提供することが望ましい。さらに、過密状態は回避されるべきであり、ＰＯＩの表示は迅速で効率的な方法で行われるべき、すなわち、所要の計算労力は低く保たれるべきである。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
（概要）
従って、上記に言及された欠点のうちの少なくともいくつかを除去し、ナビゲーションシステムにおけるＰＯＩの表示を改善する必要がある。
【課題を解決するための手段】
【００１０】
この必要は、独立請求項の特徴部によって満たされる。従属請求項において、本発明の好ましい実施形態が説明される。
【００１１】
本発明の一局面に従って、異なる地図縮尺で地図を表示することが可能であるナビゲーションシステムのディスプレイ上に興味ある地点（ＰＯＩ）を表示する方法が提供される。ナビゲーションシステムは、ＰＯＩおよびその位置を含む興味ある地点（ＰＯＩ）データを格納するデータベースを含み、ＰＯＩデータは、異なる地図縮尺に対して提供される異なるサイズの地図領域に対する代用ＰＯＩをさらに含む。特定の地図領域におけるＰＯＩの数が閾値数を超えた場合、代用ＰＯＩが特定の地図領域に提供され、代用ＰＯＩは、該地図領域においてＰＯＩを表す。方法は、ディスプレイ上に特定の地図縮尺で表示されるべき地図区域を決定するステップと、データベースから表示されるべき地図区域に対するＰＯＩデータを検索するステップとを含み、ここで、地図区域内に位置を定められるＰＯＩに対して、ＰＯＩ、または利用可能な場合、ＰＯＩを表す代用ＰＯＩがデータベースから検索されるかは特定の地図縮尺による。地図区域および検索されたＰＯＩデータは、ナビゲーションデバイスのディスプレイ上に同時に表示され、ここで、検索されたＰＯＩデータに含まれ、地図区域内に位置を定められる代用ＰＯＩは、代用ＰＯＩが表すＰＯＩの代替物として表示される。
【００１２】
シングルのＰＯＩまたは代用ＰＯＩいずれかが、地図区域を表示するために用いられる地図縮尺に従って、表示のために検索され得るので、ディスプレイ上におけるＰＯＩアイコンの過密状態が回避され得る。特に、より小さい地図縮尺に対して代用ＰＯＩが検索され、表示され得、その結果、田園地域においてさえ、ＰＯＩ情報はユーザに表示される地図上に提供され得る。他方、より大きい地図尺度でシングルＰＯＩが検索され、その結果、ユーザは、シングルＰＯＩの位置についての詳細な情報をディスプレイから得ることが可能である。代用ＰＯＩは任意の数のＰＯＩを表し得るので、表示される地図区域において複数のＰＯＩを含む都市地域においてさえ小さい地図縮尺で過密状態が起らない。
【００１３】
一実施形態において、特定の地図領域サイズに対するデータベースに格納されるＰＯＩデータ点（ＰＯＩおよび／または代用ＰＯＩ）の位置が所定の最小距離未満である距離を有する場合、次に大きいサイズの地図領域に対するＰＯＩデータがデータベースから検索され、表示される。最小距離は、地図縮尺に依存し得、ディスプレイ上の地図領域のサイズは異なる地図縮尺に対して一定であるように選ばれ得る。その結果、所定の閾値数より多いＰＯＩが地図領域に対応する、ディスプレイ上の地域に存在する場合、地図領域に対する代用ＰＯＩが表示され、それによって、過密状態およびＰＯＩを消す必要を回避する。
【００１４】
さらなる実施形態に従って、ＰＯＩデータは、木構造におけるデータベースに格納され、木構造において、ＰＯＩおよび代用ＰＯＩは、ノードに格納され、代用ＰＯＩに対するノードは、代用ノードが表すＰＯＩのノードにリンクされる。木構造において、異なる深度レベルは、それぞれの深度レベルのノードに格納される代用ＰＯＩの地図領域の異なるサイズに対応し得る。代用ＰＯＩは、直接に、または間接にすなわちさらなる代用ＰＯＩを介して、リンクされ得る。木構造のエンドノード（または、葉）は、一般的にＰＯＩノードである。代用ＰＯＩノードは、代用ＰＯＩが表すＰＯＩの数、領域サイズおよびＰＯＩの子ノードへのリンクのみを格納し得、一方、ＰＯＩノードは、システムにおいてＰＯＩに対して利用可能なすべてのデータまたそのようなデータを含む別のデータベースへのリンクを格納し得る。
【００１５】
そのような方法でＰＯＩおよび代用ＰＯＩを格納することは、特定の地図区域に対してデータベースが地図縮尺に適切なＰＯＩデータを検索するために少ない計算労力で探索され得るという利点を有する。木構造の異なる深度レベルが異なる地図領域サイズに対応するので、特定の地図縮尺に対する適切な代用ＰＯＩは、容易に識別され得る。
【００１６】
一実施形態において、ＰＯＩデータを検索し表示することは、表示されるべき地図区域に対する木構造の根ノードを決定するステップと、決定された根ルートにリンクされるノードの探索を行うステップとを含み、探索は、隣り合うノードの地図位置が特定の地図縮尺に依存する最小距離より小さい距離を有する木構造の深度レベルにおいて停止される。最小距離は、最小距離がナビゲーションシステムのディスプレイ上の同じ距離に常に対応するように選ばれ得る。方法は、停止深度レベルより高いすべての深度レベルにおいて探索される木に含まれるＰＯＩを検索することと、停止レベルより１レベル上である深度レベルにおいて探索される木に含まれる代用ＰＯＩを検索することとをさらに含む。検索されたＰＯＩおよび代用ＰＯＩは、次いでＰＯＩデータとして表示されるために提供される。探索は、例えば幅優先探索であり得るが、他のタイプの探索方法が用いられ得る。
【００１７】
従って、２つの表示されるＰＯＩデータ点間の最小距離がディスプレイ上で保たれることが確実にされ得、ＰＯＩデータポイントは、ＰＯＩまたは代用ＰＯＩのいずれかであり得る。さらに、小さい地図縮尺で、表示される地図区域において１つのみのＰＯＩが存在する場合でさえ、ＰＯＩは、検索され、表示され、その結果、ＰＯＩは、ナビゲーションデバイスのユーザによって容易に発見され得る（すなわち、ＰＯＩは消されない）。２つのＰＯＩデータポイントがナビゲーションデバイス上で保つ最小距離は、ディスプレイサイズおよび／またはディスプレイ解像度に依存し得る。最小距離は、例えば０．５ｃｍ〜４ｃｍであり得る。
【００１８】
好ましくは、探索は、表示されるべき地図区域に位置を定められるＰＯＩのノードおよび表示されるべき地図区域内に少なくとも部分的に位置を定められる関連する地図領域を有する代用ＰＯＩのノードのみを考慮する。従って探索は、加速させられ得る。
【００１９】
概して、地図区域内に位置を定められるＰＯＩおよび代用ＰＯＩのみが表示される。代用ＰＯＩが、検索されるが、地図区域外に位置を定められる場合、代用ＰＯＩは、ディスプレイの周辺に表示され得るかまたは無視され得る。
【００２０】
表示するために利用可能な最小の地図縮尺に対応し得る木構造の最高レベルにおいて、データベースのすべてのＰＯＩを包含する領域に関連付けられる代用ＰＯＩを含む根ノードが提供され得る。最高レベルにおける地図領域がシングルＰＯＩのみを含む場合、地図領域は根ルートに直接格納され得る。従って、ＰＯＩおよび代用ＰＯＩは、最小地図縮尺においてさえ容易に検索され、表示され得る。一例として、ヨーロッパの地図に対して、根ノードは、ヨーロッパを包含する地図領域に関連付けられる代用ＰＯＩ、および従って地図領域に位置を定められるすべてのＰＯＩを格納し得る。
【００２１】
さらに、最大の地図縮尺に対応する最小の所定のサイズの地図領域に対して、ＰＯＩは、最小領域のうちの１つの領域内に位置を定められるＰＯＩの数にかかわらず、データベースに別個のＰＯＩとして格納される。換言すると、木構造は、ＰＯＩ間の距離にかかわらず、ＰＯＩを直接格納するノードのみを含む最低レベルを有し得る。従って、代用ＰＯＩが高密度インフラストラクチャを有する地図区域に対してナビゲーションシステムの最大地図縮尺でなおも表示されることが回避され得る。従ってユーザは、最大地図縮尺でディスプレイ上においてシングルＰＯＩを識別することが可能になり得る。
【００２２】
動作時、方法は、例えば、地図区域の表示されるべき特定の地図縮尺が所定の最大地図縮尺と等しいかまたはそれより大きいかどうかを決定するステップと、肯定の場合、表示されるべきＰＯＩデータとして、該地図区域内に位置を定められるデータベースからすべてのＰＯＩを検索するステップとを含み得る。従って、地図区域に対して利用可能なすべてのＰＯＩは、最大地図縮尺で表示され得る。他の実施形態において、表示するために利用可能な最大地図縮尺で、代用ＰＯＩは過密状態を回避するようになおも表示され得る。
【００２３】
方法は、ディスプレイに表示される代用ＰＯＩをユーザ選択可能にするステップと、  ユーザ入力によって代用ＰＯＩを選択時に、選択された代用ＰＯＩが表すＰＯＩの選択リストをユーザに提供するステップとをさらに含み得る。リストからから選択されたＰＯＩは、次いでディスプレイ上に表示され得る。例えば、ナビゲーションシステムの第２の最大地図縮尺で選択が行われ得る。過密状態を回避するために最大地図尺ですべてのＰＯＩを表示することが不能にされる場合、特に有益である。なぜならすべてのＰＯＩは次いで選択リストによってなおも選択可能であるからである。各個々のＰＯＩへのアクセスをなおも可能にしながら、従って過密状態は回避され得る。
【００２４】
概してＰＯＩに関して上記に説明される方法は、好ましくはＰＯＩカテゴリーごとに行われる。特に、データベースにおけるＰＯＩデータは、異なるＰＯＩカテゴリーに提供され得、ここで、特定のカテゴリーに対するＰＯＩデータは、地図領域における同じカテゴリーのＰＯＩの数が該閾値数を超える場合、該地図領域に対する該カテゴリーの代用ＰＯＩを含む。代用ＰＯＩのみが表示され得る、より小さい地図縮尺においてでさえ、従ってユーザは、異なるタイプのＰＯＩ間で容易に識別することが可能になる。従って、上記に言及される特徴の各々は、ＰＯＩカテゴリーごとに行われ得、ＰＯＩデータを格納する木構造は、例えば各ＰＯＩカテゴリーに提供され得る。従って、データベースは、各ＰＯＩカテゴリーに対して根ノードを含み得る。
【００２５】
方法は、次いでＰＯＩが表示されるべき１つ以上のカテゴリーを決定するステップをさらに含み得、ここで、ＰＯＩデータを表示するステップは、概観地図縮尺ですべての決定されたカテゴリーに対してＰＯＩデータが表示されるように構成される。カテゴリーの決定は、例えば、表示される地図内容に従ってか、または例えば個々のカテゴリーもしくはカテゴリープロファイルをユーザが選択することによるなどのユーザ入力によって、自動的に行われ得るが、表示されるべきカテゴリーはまた、システムにおいて事前に規定され得る。従って、ユーザに関連するＰＯＩのみが表示されること、および、例えば許容されるカテゴリーの最大数を規定することなどによって、多すぎる異なるＰＯＩカテゴリーによる表示の過密状態が回避されることが確実にされ得る。
【００２６】
好ましくは、カテゴリー「レストラン」および「ガソリンスタンド」のそれぞれのカテゴリーが表示されるように選択された場合、概観地図縮尺で、それらのカテゴリーのうちの少なくとも１つに対するＰＯＩデータが表示されるように、表示が行われる。従って、従来のシステムにおいて、ガソリンスタンドおよびレストランのＰＯＩが既に消されているような比較的小さい概観地図縮尺においてさえ、本方法は、１つまたは両方のカテゴリーに対するＰＯＩデータをなおも表示する。従って、地図上でこれらのＰＯＩの位置を定めることは容易にされる。
【００２７】
概観地図縮尺は、約１：５００，０００より小さく、好ましくは約１：１，０００，０００より小さく、そしてさらに約１：２，０００，０００より小さくなり得る。一例として、概観地図縮尺は、１：２，０００，０００であり得る。
【００２８】
一実施形態において、地図領域のサイズは、それぞれの地図領域が提供される地図縮尺でナビゲーションデバイスのディスプレイ上に地図領域が同じサイズを有するように選ばれる。地図領域のサイズは、例えば関連する地図縮尺に反比例して計られ得る。対応する地図縮尺でディスプレイ上で測定される測定されるような地図領域サイズは、例えば０．５ｃｍ×０．５ｃｍ〜４ｃｍ×４ｃｍであり得る。地図領域は異なる長方形形状を有し得る。
【００２９】
木構造のよりより高い深度レベルでの地図領域のサイズは、低い震度レベルでの地図領域のサイズより大きくなり得る。さらに、木構造の深度レベル内の地図領域のサイズの変化は、異なる深度レベル間の地図領域のサイズの変化より小さくなり得る。特に、深度レベルにおける地図領域は、異なるサイズを有し得、重なり合いことさえあり得る。
【００３０】
木構造において、特定のノードに格納される代用ＰＯＩに関連付けられる地図領域は、該特定のノードの親ノードに格納される代用ＰＯＩに関連付けられる地図領域に部分的または完全に含まれ得る。
【００３１】
一実施形態において、地図領域におけるＰＯＩの数に対する閾値数は、１に等しい。従って、地図領域内に１つを超えるＰＯＩ（すなわち、２つ以上のＰＯＩ）が地図領域内に位置を定められる場合、代用ＰＯＩは既に提供され得る。そのような小さい閾値を選ぶことによって、過密状態は効率的に回避され得る。
【００３２】
代用ＰＯＩは、文字、アイコン、ピクトグラムまたはこれらの組み合わせなどの図形記号として表示され得、この図形記号は、代用ＰＯＩが表すＰＯＩの数を示す。この数は、代用ＰＯＩを検索するときにデータベースから検索され得る。一例として適切なインディケータは、アイコンのスタックの高さまたはアイコン内もしくはアイコンに隣接して表示される数であり得る。ＰＯＩおよび代用ＰＯＩに対する木構造のノードは、従って異なる位置に格納され得るそれぞれの図形記号へのポインタを格納し得る。
【００３３】
代用ＰＯＩの位置は、代用ＰＯＩが表すＰＯＩの位置によって決定され得る。代用ＰＯＩの位置は、例えば代用ＰＯＩが表すＰＯＩの位置の平均値または好ましくは重み付き平均であり得る。代用ＰＯＩの位置は、再び木構造のそれぞれのノードに格納され得る。
【００３４】
本発明のさらなる局面に従って、地図区域およびＰＯＩデータをユーザに表示するディスプレイと、ＰＯＩデータを格納するデータベースとを含むナビゲーションシステムが提供される。ＰＯＩデータはＰＯＩおよびその位置を含み、ＰＯＩデータは異なる地図縮尺に対して提供される異なるサイズの地図領域に対する代用ＰＯＩをさらに含み、代用ＰＯＩは、該地図領域のＰＯＩの数が閾値数を超えた場合、特定の地図領域に提供され、代用ＰＯＩは該地図領域においてＰＯＩを表す。
【００３５】
ナビゲーションシステムは、特定の地図縮尺で表示されるべき地図区域を決定するように適合される地図区域決定ユニットと、表示されるべき地図区域に対するＰＯＩデータをデータベースから検索するように適合される検索ユニットとをさらに含み、ここで、地図領域に位置を定められるＰＯＩに対して、該ＰＯＩか、または利用可能な場合、該ＰＯＩを表す代用ＰＯＩが表示のためにデータベースから検索されるかは地図縮尺による。ナビゲーションシステムのディスプレイ制御ユニットは、地図区域および検索されたＰＯＩデータを同時に表示するように適合され、ここで、検索されたＰＯＩデータに含まれ、該地図区域内に位置を定められる代用ＰＯＩは、代用ＰＯＩが表すＰＯＩの代替物として表示される。そのようなナビゲーションシステムを用いて、本発明の方法に関して上記に概説される利点に類似する利点が達成され得る。
【００３６】
ナビゲーションシステムの一実施形態に従って、ナビゲーションシステムは、上記に言及される任意の方法を行うように構成される。特に、ナビゲーションシステムのデータベースは、上記に説明されるように木構造にＰＯＩデータを格納し得る。ＰＯＩデータは、異なるＰＯＩカテゴリーに対するデータベースに提供され得、従って、上記に説明されるようにカテゴリーごとにＰＯＩデータを処理し得る。
【００３７】
本発明は、計算デバイスの内部メモリの中にロードされ得るコンピュータプログラム製品を提供し、該製品は、製品が実行されたとき、上記に言及される任意の方法を行うためのソフトウェアコード部分を含む。コンピュータプログラム製品は、電子的に読み取り可能なデータキャリアに格納されるコンピュータとして提供され得る。本発明は、計算デバイスにデータキャリアを用いる場合、制御情報が上記に言及される任意の方法を行うように構成される、格納された電子的に読み取り可能な制御情報を有する電子的に読み取り可能なデータキャリアをさらに提供する。
【００３８】
本発明のさらに別の局面は、電子的に読み取り可能なデータキャリアであって、そこに格納されるＰＯＩデータベースを含む、電子的に読み取り可能なデータキャリアを提供し、ＰＯＩデータベースは、異なるカテゴリーのＰＯＩおよびその位置を含む。データベースは、異なる地図縮尺に提供される異なるサイズの地図領域に対する代用ＰＯＩをさらに含み、カテゴリーの代用ＰＯＩは、地図領域における同じカテゴリーのＰＯＩの数が閾値数を超える場合、特定の地図領域に提供される。ＰＯＩデータベースは、本発明の任意の局面および実施形態に関して上記に説明されるように構成され得る。
【００３９】
上記に言及される特徴および以下にさらに説明される特徴が、示されるそれぞれの組み合わせに用いられ得るのみならず、本発明の範囲から離れることなく他の組み合わせまたは単独でも用いられ得ることは理解されるべきである。
【００４０】
例えば、本発明は以下の項目を提供する。
（項目１）
異なる地図縮尺で地図を表示することが可能であるナビゲーションシステムのディスプレイ上にＰＯＩを表示する方法であって、
該ナビゲーションシステムは、ＰＯＩおよびその位置を含むＰＯＩデータを格納するデータベースを含み、
該ＰＯＩデータは、異なる地図縮尺に対して提供される異なるサイズの地図領域に対する代用ＰＯＩをさらに含み、
特定の地図領域内に位置を定められるＰＯＩの数が閾値数を超えた場合、代用ＰＯＩが該特定の地図領域に提供され、該代用ＰＯＩは該地図領域において該ＰＯＩを表し、
該方法は、
該ディスプレイ上に特定の地図縮尺で表示されるべき地図区域を決定するステップと、
該地図区域のデータベースから表示されるべきＰＯＩデータを検索するステップであって、該ＰＯＩデータの検索は、特定の地図縮尺に従ってＰＯＩまたは代用ＰＯＩのいずれかが表示のために検索されるような方法で、代用ＰＯＩが該データベースに提供される該地図区域内に位置を定められるＰＯＩに対して行われる、ステップと、
該地図区域および検索されたＰＯＩデータを表示するステップであって、該検索されたＰＯＩデータに含まれ、該地図区域内に位置を定められる該代用ＰＯＩは、該代用ＰＯＩが表す該ＰＯＩの代替物として表示される、ステップと
を包含する、方法。
（項目２）
上記ＰＯＩデータは、木構造で上記データベースに格納され、該データベースにおいて、ＰＯＩおよび代用ＰＯＩはノードに格納され、代用ＰＯＩのノードは、該代用ＰＯＩが表す該ＰＯＩのノードにリンクされ、該木構造の異なる深度レベルは、それぞれの深度レベルの該ノードに格納される該代用ＰＯＩに関連付けられる地図領域の異なるサイズに対応、上記項目に記載の方法。
（項目３）
上記ＰＯＩデータを検索することおよび表示することは、
上記表示されるべき地図区域に対する上記木構造の根ノードを決定するステップと、
該決定された根ルートにリンクされるノードの探索を行うステップであって、該探索は、隣り合うノードの地図位置が上記特定の地図縮尺に依存する最小距離より小さい距離を有する該木構造の深度レベルにおいて停止される、ステップと、
該停止深度レベルより高いすべての深度レベルにおいて該探索される木に含まれるＰＯＩを検索するステップと、
停止レベルより１レベル上である深度レベルにおいて該探索される木に含まれる上記代用ＰＯＩを検索するステップと、
該検索されたＰＯＩおよび代用ＰＯＩをＰＯＩデータとして表示されるように提供するステップと
を包含する、上記項目のいずれかに記載の方法。
（項目４）
上記木構造の最高の深度レベルは根ノートを含み、該根ノードは上記地図領域のうちの最大領域に関連付けられる代用ＰＯＩまたはＰＯＩを格納する、上記項目のいずれかに記載の方法。
（項目５）
上記木構造は、上記ＰＯＩが該ＰＯＩ間の距離に関係なく上記データベースに別個のＰＯＩとして格納される最低深度レベルを含む、上記項目のいずれかに記載の方法。
（項目６）
上記ディスプレイに表示される代用ＰＯＩをユーザ選択可能にするステップと、
ユーザ入力によって該代用ＰＯＩを選択したときに、該選択された代用ＰＯＩが表すＰＯＩの選択リストを該ユーザに提供するステップと
をさらに包含する、上記項目のいずれかに記載の方法。
（項目７）
上記データベースにおける上記ＰＯＩデータは、異なるＰＯＩカテゴリーに提供され、地図領域において同じカテゴリーのＰＯＩの数が上記閾値数を越える場合、特定のカテゴリーに対するＰＯＩデータは、該地図領域に対する該カテゴリーの代用ＰＯＩを含む、上記項目のいずれかに記載の方法。
（項目８）
表示されるべきＰＯＩの１つ以上のカテゴリーを決定するステップをさらに包含し、該表示は、概観地図縮尺ですべての決定されたカテゴリーに対するＰＯＩデータが表示されるように行われる、上記項目のいずれかに記載の方法。
（項目９）
それぞれのカテゴリーが表示されるために選択される場合、表示は、概観地図縮尺でレストランおよびガソリンスタンドのカテゴリーのうちの少なくとも１つに対するＰＯＩデータが表示されるように行われる、上記項目のいずれかに記載の方法。
（項目１０）
上記概観地図縮尺は、約１：５００，０００より小さく、好ましくは約１：１，０００，０００より小さく、そしてより好ましくは約１：２，０００，０００より小さい、上記項目のいずれかに記載の方法。
（項目１１）
代用ＰＯＩに関連付けられた地図領域のサイズは、上記木構造のより高い深度レベルにおけるノードの場合が、より低い深度レベルにおけるノードに対する場合よりも大きい、上記項目のいずれかに記載の方法。
（項目１２）
上記木構造において、ノードに格納される代用ＰＯＩの地図領域は、該ノードの親ノードに格納される代用ＰＯＩの地図領域に部分的または完全に含まれる、上記項目のいずれかに記載の方法。
（項目１３）
代用ＰＯＩは、該代用ＰＯＩが表すＰＯＩの数を示す図形記号として表示される、上記項目のいずれかに記載の方法。
（項目１４）
地図区域およびＰＯＩデータをユーザに表示するディスプレイと、
ＰＯＩおよびその位置を含むＰＯＩデータを格納するデータベースであって、該ＰＯＩデータは異なる地図縮尺に対して提供される異なるサイズの地図領域に対する代用ＰＯＩをさらに含み、該地図領域内に位置を定められるＰＯＩの数が閾値数を超える場合、代用ＰＯＩは特定の地図領域に提供され、該代用ＰＯＩは該地図領域において該ＰＯＩを表す、データベースと、
特定の地図縮尺で表示されるべき地図区域を決定するように適合される地図ユニットと、
該地図区域に対する該データベースから表示されるべきＰＯＩデータを検索されるように適合される検索ユニットであって、該ＰＯＩデータの検索は、該地図縮尺に従ってＰＯＩまたは代用ＰＯＩのいずれかが表示のために検索されるような方法で、代用ＰＯＩが該データベースに提供される該地図区域内に位置を定められるＰＯＩに対して行われる、検索ユニットと、
表示制御ユニットであって、該表示制御ユニットは、該検索されたＰＯＩデータに含まれ、該地図区域内に位置を定められる代用ＰＯＩは、代用ＰＯＩが表す該ＰＯＩの代替物として表示されるように、該地図区域および該検索されたＰＯＩデータを表示するように適合される、表示制御ユニットと
を備えている、ナビゲーションシステム。
（項目１５）
上記ナビゲーションシステムは、上記項目のいずれかに記載の方法を行うように構成される、上記項目のいずれかに記載のナビゲーションシステム。
（項目１６）
プログラムが記録されたコンピュータ読み取り可能格納媒体であって、該プログラムは、コンピュータによって実行されると、該コンピュータに上記項目のいずれかに記載の方法を行わせる、コンピュータ読み取り可能格納媒体。
（項目１７）
コンピュータ読み取り可能格納媒体であって、該コンピュータ読み取り可能格納媒体に、ＰＯＩデータベースが格納され、該ＰＯＩデータベースは、異なるカテゴリーおよびその位置のＰＯＩを含み、該データベースは、異なる地図縮尺に対して提供される異なるサイズの地図領域に対する代用ＰＯＩをさらに含み、該地図領域における該同じカテゴリーのＰＯＩの数が閾値数を超えた場合、カテゴリーの代用ＰＯＩは特定の地図領域に提供され、該代用ＰＯＩは、該地図領域において該ＰＯＩを表す、コンピュータ読み取り可能格納媒体。
（項目１６Ａ）
計算デバイスの内部メモリの中にロードされ得るコンピュータプログラム製品であって、該製品は、該製品が実行されたとき、上記項目のいずれかの方法を行うためのソフトウェアコード部分を含む、コンピュータプログラム製品。
（項目１７Ａ）
電子的に読み取り可能なデータキャリアであって、そこに格納されるＰＯＩデータベースを含み、該ＰＯＩデータベースは、異なるカテゴリーおよびその位置のＰＯＩを含み、該データベースは、異なる地図縮尺に対して提供される異なるサイズの地図領域に対する代用ＰＯＩをさらに含み、該地図領域における該同じカテゴリーのＰＯＩの数が閾値数を超えた場合、カテゴリーの代用ＰＯＩは特定の地図領域に提供され、該代用ＰＯＩは、該地図領域において該ＰＯＩを表す、電子的に読み取り可能なデータキャリア。
【００４１】
（摘要）
（興味ある地点を表示する方法およびシステム）
本発明は、地図区域および興味ある地点（ＰＯＩ）データをユーザに表示するディスプレイと、ＰＯＩデータを格納するデータベースとを含むナビゲーションシステムを提供する。検索ユニットは、表示されるべき地図区域のためのＰＯＩデータをデータベースから検索するために提供される。本発明の実施形態において、ＰＯＩデータベースは、地図領域において、ＰＯＩと、ＰＯＩの数を表す代用ＰＯＩとを含む。次いで、代用ＰＯＩか、または代用ＰＯＩが表すＰＯＩがデータベースから検索されるかは、地図区域が表示されるべき地図縮尺により得る。
【００４２】
本発明の前述の特徴および利点ならびに他の特徴および利点は、添付の図面に関連して例示的実施形態の以下の詳細な説明が読まれると、その詳細な説明からさらに明らかとなる。
【図面の簡単な説明】
【００４３】
【図１】図１は、本発明に従うナビゲーションシステムの一実施形態の概略図を示す。
【図２】図２は、本発明に従う方法の一実施形態を例示するフロー図を示す。
【図３】図３は、ＰＯＩデータベースからＰＯＩデータを検索する、図２の方法のステップ２５０の起り得る実装のフロー図を示す。
【図４】図４Ａおよび図４Ｂは、異なる地図縮尺でＰＯＩおよび代用ＰＯＩの表示を例示する概略図である。
【図５】図５は、本発明の一実施形態に従うＰＯＩデータベースの木構造を例示する概略図である。
【発明を実施するための形態】
【００４４】
（詳細な説明）
図１は、ナビゲーションシステム１００の概略図を示す。ナビゲーションシステム１００は、例えば、車載ナビゲーションシステム、ハンドヘルドパーソナルナビゲーションデバイス（ＰＮＤ）、スマートフォンなどのハンドヘルト通信デバイスもしくは携帯情報端末（ＰＤＡ）において実装されるナビゲーションシステム、または類似のものとして様々な方法で実装され得る。
【００４５】
ナビゲーションシステム１００は、メモリ１０２に格納される制御命令に従って動作する処理装置１０５によって制御される。処理装置１０５は、単独または複数のマイクロプロセッサとして、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）または類似のものとして実装され得る。メモリ１０２は、ランダムアクセスメモリ、フラッシュメモリ、ハードドライブまたは類似のものなどすべてのタイプのメモリを含み得る。
【００４６】
処理装置１０５は、メモリ１０２に格納される地図データベース１０３から地図データを検索するように適合される。この目的のために、処理装置１０５は、地図ユニット１０６を含み、地図ユニット１０６は、機能ユニットであり、特定の地図縮尺で表示されるべき地図区域を決定する。処理装置１０５は、検索ユニット１０７をさらに含み、検索ユニット１０７は、機能ユニットであり、決定された地図区域のＰＯＩデータをメモリ１０２に格納されたＰＯＩデータベース１０４から検索する。決定された地図区域が表示されるべき特定の地図縮尺に従って、検索ユニット１０７は、表示される興味ある地点（ＰＯＩ）または代用ＰＯＩのいずれかをＰＯＩデータベース１０４から検索する。検索ユニット１０７は、ＰＯＩおよび代用ＰＯＩの位置、およびＰＯＩデータベース１０４においてＰＯＩに提供されるさらなる情報をさらに検索する。表示以外の目的のために、検索ユニット１０７は、例えば別のタイプのメモリまたは類似のものにおけるデータをバッファリングするために、地図縮尺とは無関係にデータベース１０４から任意のＰＯＩデータを検索し得る。
【００４７】
処理装置１０５は、表示制御ユニット１０８をさらに含み、表示制御ユニット１０８は、機能ユニットであり、決定された地図区域および検索されたＰＯＩデータから画像が表示されるようにする。描かれる画像は、地図区域内に位置を定められるＰＯＩおよび代用ＰＯＩを表す図形記号を含み、記号は、画像において地図上のＰＯＩデータ点のそれぞれの位置（ＰＯＩまたは代用ＰＯＩ）に決められる。図形記号は、メモリ１０２に格納され得、検索ユニット１０７または表示制御ユニット１０８などの処理装置１０５によって検索され得る。描かれる画像は、次いでディスプレイ１０１に与えられる。
【００４８】
機能ユニット１０６、１０７および１０８は、処理装置１０５においてランするソフトウェアコード部分として実装され得る。それでも、機能ユニット１０６、１０７および１０８はまた、別個の物理ユニットとしてかまたは異なる物理的に別個の処理装置においてランするソフトウェアコード部分として実装され得る。
【００４９】
図１に示される構成要素、ユニットまたは機能ブロック間の任意の直接の接続または結合がまた、間接の接続または結合、すなわち１つ以上の追加の介在要素との接続または結合によっても実装され得ることは理解されるべきである。さらに図１に示される構成要素、ユニットまたは機能ブロックへの分割は、これらのユニットが必ず物理的に別個のユニットとして実装されることを示すものとして解釈されるべきではなく、構成要素、ユニットまたは機能ブロックはまた、別個のユニット、回路、チップもしくは回路要素としても実装され得、または構成要素、ユニットもしくは機能ブロックは、共通の回路、チップ、回路要素もしくはユニットにおいて同様に実装され得る。例として表示制御ユニット１０８は、別個のグラフィックスプロセッサとインタフェースする処理装置１０５およびディスプレイ１０１として実装され得る。メモリ１０２は、ナビゲーションシステム１００に局所的に接続されるメモリと、ネットワークまたは別のタイプの接続を介してアクセス可能であるメモリとを含み得る。例として、ＰＯＩデータベース１０４は、有線ネットワーク接続または無線ネットワーク接続を介してナビゲーションシステムによってアクセス可能であるリモートサーバに格納され得る。
【００５０】
ナビゲーションシステム１００はまた、例えばＧＰＳ受信器、ユーザインタフェースなどの位置検出ユニットなど、ナビゲーションシステムに共通の構成要素をさらに含み得る。これらの構成要素の機能は当業者に公知であるので、これらの構成要素はここではさらに詳細には考察されない。
【００５１】
従来のナビゲーションシステムは、概して、例えば異なるズームレベルを提供することによって異なる地図縮尺で地図を表示することが可能である。従来のナビゲーションシステムは、さらに地図データと共に複数のカテゴリーに対してＰＯＩを表示することが可能である。各ＰＯＩカテゴリーに対して、地図上のＰＯＩの密度は、例えば都市地域におけるこれらのＰＯＩの平均密度に基づいて想定される。ディスプレイに表示される場合、特定のカテゴリーのＰＯＩの密度が高くなりすぎる特定の地図縮尺において、これらのＰＯＩのアイコンはもはや示されない。すなわち、特定のカテゴリーのＰＯＩは消される。例えば約１：２００，０００の地図縮尺において、レストランは消される。ＰＯＩカテゴリーの消去は特定の地図縮尺に結び付けられているので、非常に高い密度のインフラストラクチャを有する地域において過密状態がなおも起り得、一方、田園地域において、ＰＯＩがなおも表示される最小の地図縮尺は概して大きすぎて、その結果、対応して小さい、表示された地図区域はどのＰＯＩをも含まない（田園地域におけるＰＯＩの低密度による）。そのような状況においてズームアウトすると、地図縮尺は小さくなり、このことはまた、結果として、より大きい地図区域が表示されることの他にＰＯＩの消去を引き起す。従って、田園地域でＰＯＩを見つけることは、従来のシステムにおいてかなり困難である。
【００５２】
これらの問題を回避するために、特定のカテゴリーのＰＯＩが表示される地図縮尺まで下げられる閾値地図縮尺は、ナビゲーションシステム１００における概観地図縮尺に設定される。概観地図縮尺は、ナビゲーションシステム１００がより大きな地図地域にわたり概観を提供する地図縮尺である。概観地図縮尺は、概して、地図データおよびＰＯＩデータに依存し、それらのデータを用いてナビゲーションシステムが動作させられる。国および対応するＰＯＩデータベースに対して、国全体が概観地図縮尺で示され得る。概観地図縮尺は、１：５００，０００より小さい場合があり、または例えば１：２，０００，０００など１：１，０００，０００よりもさらに小さい場合がある。同じ閾値地図縮尺がすべてのＰＯＩカテゴリーに対して設定されることが好ましい。結果としてＰＯＩが概観地図縮尺でなおも見えるので、ＰＯＩは、非常に低い密度のインフラストラクチャを有する地域においてでさえ見つけられ得る。一例として閾値地図縮尺は、ＰＯＩの消去が全く起らない、できるだけ最小の地図縮尺であり得る。
【００５３】
ナビゲーションシステム１００は、さらに、表示された地図区域におけるＰＯＩの過密状態を回避するように構成される。表示されるには多すぎる、カテゴリーのＰＯＩが、表示された地図区域に対して可能な場合、過密状態が起り、その結果、ＰＯＩに対する図形記号またはアイコンが重なり合い、結果として、地図情報の明確さの欠如となり、不明瞭さとなる。過密状態を回避するために、ナビゲーションシステム１００は、ＰＯＩデータベース１０４にＰＯＩのみならず代用ＰＯＩもまた格納し、ＰＯＩおよび代用ＰＯＩの各々は、（２つ以上の）ＰＯＩのグループを表す。表示される地図区域におけるＰＯＩの密度は地図縮尺と共に変化するので、代用ＰＯＩは異なる地図縮尺に対して提供される。代用ＰＯＩは、表示されるとき、例えば特定のアイコンを用いることなどによって印を付けられ得、代用ＰＯＩが表すＰＯＩの数の表示をさらに含み得る。
【００５４】
地図縮尺であって、それによって地図区域がディスプレイ１０１に表示される、地図縮尺に従って、またディスプレイ１０１において測定される、ＰＯＩの規定された最小距離（これ自体ディスプレイのサイズおよび／または解像度に従う）などのさらなるパラメータに従って、そして表示される地図区域内に位置を定められ得るＰＯＩの数および位置に従って、検索ユニット１０７は、ＰＯＩデータベース１０４からＰＯＩまたは代用ＰＯＩのいずれかを検索する。ディスプレイ上で測定される、ＰＯＩデータ点（ＰＯＩまたは代用ＰＯＩ）間の最小距離が保たれるように、検索が行われる。ディスプレイ上のＰＯＩデータ点の最小距離は、例えば約３ｃｍなど０．５ｃｍ〜４ｃｍであり得るか、または特定のディスプレイおよびＰＯＩデータ点を表示するために用いられる図形表現に適した任意の他の最小距離であり得る。従って表示されたＰＯＩデータ点間の最小距離が保たれることが確実にされ、その結果、代用ＰＯＩを利用することによって、高密度インフラストラクチャを含む地図区域が小さい地図縮尺で表示される場合でも、過密状態が効率的に回避され得る。
【００５５】
代用ＰＯＩは、概して同じＰＯＩカテゴリーのＰＯＩを表すのみであり、その結果、ＰＯＩカテゴリーの選択的表示は使用可能の状態のままであり、情報の包括的提示が達成される。
【００５６】
ＰＯＩおよび代用ＰＯＩは、図５に例示されるように、ＰＯＩデータベース１０４における木構造のノードに格納され、その結果、迅速かつ効率的なアクセスが可能になる。木構造はＰＯＩカテゴリーごとに提供される。木構造は異なる深度レベル５１０、５２０および５３０を含み、これらの深度レベルは、本質的に、異なる地図縮尺に対応する。実際に、木構造の異なる深度レベルにおいて、代用ＰＯＩは異なるサイズの地図領域に関連付けられる。このことは、代用ＰＯＩがナビゲーションシステムの異なる地図縮尺に効果的に対応することを可能にする。一例として、より小さい地図縮尺に対して、より大きい地図領域のＰＯＩを表す、より高い深度レベルの代用ＰＯＩが表示され、一方、より大きい地図縮尺において、より低い深度レベルの代用ＰＯＩが表示される。従って、異なる深度レベルは異なる地図縮尺において包括的な表示を使用可能にするために提供されるが、但し、深度レベルがシステムにおける表示に利用可能な地図縮尺に実際は無関係であることは明らかである。
【００５７】
各ＰＯＩカテゴリーに対して、ＰＯＩデータベース１０４は根ノードを含み、根ノードは、図５の例において代用ＰＯＩ  Ｓ１を格納するノード５０１である。根ノードに格納される代用ＰＯＩは、例えば最小の地図縮尺で表示され得る。最小の地図縮尺は概観地図縮尺であり得、概観地図縮尺において地図データベース１０３が提供される国または領域の全体が表示される。地図縮尺はまた、例えば１：２，０００，０００などのより大きい地図縮尺であり得、この縮尺において、ディスプレイ上の１ｃｍは地図上の２０キロメートルに対応する（すなわち、現実の世界において）。
【００５８】
各ＰＯＩノードは、例えば、ＰＯＩ位置（経度位置および緯度位置）などの利用可能なＰＯＩデータを格納し、オプションで、ＰＯＩ名、ＰＯＩ説明などを格納する。ＰＯＩ位置のみと、ＰＯＩについてのさらなる情報を含む別のデータベースへのリンクとを格納することもまた可能である。代用ＰＯＩノードの各々は地図領域を格納し、対応する代用ＰＯＩは地図領域に位置を定められるＰＯＩを表す。地図領域は、地図上の長方形の地域として作られ、地図においてそれぞれの子ノードのＰＯＩの位置が定められる。木構造の異なる深度レベルに対して、異なるサイズの地図領域が提供され、より深いレベルはより小さい地図領域に対応する（すなわち、代用ＰＯＩに対して、子ノードは親ノードより小さい領域に関連付けられる）。根ノードに関連付けられる地図領域は、最小外接長方形（ＭＢＲ）であり、ＭＢＲは、データベース１０４に位置を定められる特定のカテゴリーのすべてのＰＯＩにわたり広がる。地図領域は、例えば、数万のＰＯＩまたは数十万のＰＯＩを表し得る。次のより低い深度レベルにおいて、代用ＰＯＩに関連付けられた地図領域は、再び、上記のＰＯＩの特定の部分にわたり各々広がる、より小さいサイズのＭＢＲであり得る。従って、ある深度レベルの地図領域は、異なるサイズを有し得、重なり合い得、親ノードの全地図領域をカバーする必要はない。地図領域は、従って、特定のパターンもしくはグリッドまたは特定の地図縮尺に対応する必要はない。
【００５９】
例として、根ノード５０１を含む最も高い深度レベル５１０において、領域サイズは、４０ｋｍ×４０ｋｍであり得、これは、（例えば、特定の地理的地域の地図に対して）概観地図縮尺でディスプレイにおいて２ｃｍ×２ｃｍに対応し得る。根ノードに関連付けられる地図領域は、地図領域がこの地理的地域内に位置を定められるすべてのＰＯＩをカバーするように選ばれる。閾値を超える数のＰＯＩが上記の地図領域に位置を定められるので、代用ＰＯＩは、地図領域に関連する木構造の根ノードに格納される。閾値数は、１に等しくし得る（すなわち、領域に位置を定められる２つ以上のＰＯＩは代用ＰＯＩの格納をもたらす）が、２、３、４、または５などの他の閾値数もまた選ばれ得る。
【００６０】
概観地図縮尺（例えば、１：２，０００，０００）で表示され得る画像４１０は、図４Ｂに概略例示される。グレーの影付き領域へのズームインは、さらなる画像４２０および４３０に例示される。図４Ａにおいて、グレーの影付き地域は、代用ＰＯＩに関連付けられた異なるサイズの地図領域をより良く例示するために常に同じ縮尺に拡大して表示される。（点線で示される）地図領域４１１は、ＰＯＩ１、ＰＯＩ２およびＰＯＩ３（参照記号４２３、４３１および４３２）を含み、従って１つを超えるＰＯＩを含み、その結果、代用ＰＯＩ  Ｓ１は、上記領域４１１に関連する根ノード５０１における木構造に格納される。概観地図縮尺で地図を表示する場合、画像４１０に例示されるように、Ｓ１は、ＰＯＩデータベースから検索され、表されたＰＯＩの数を示す図形記号用いて地図上に代用ＰＯＩ  ４１２として表示される。
【００６１】
木構造の次のより低い深度レベル５２０において、地図領域は、例えば、再び１：１，０００，０００の地図縮尺でディスプレイにおいて２ｃｍ×２ｃｍに対応する（地図上で測定されるように）２０ｋｍ×２０ｋｍのサイズを有し得る。領域４１１は、例えば次のより低い深度レベル５２０に対して４分の１のサイズを有する４つの領域に再分割されるか、またはＭＢＲは各々、ＰＯＩの部分にわたり広げられ、地図領域を形成する。この深度レベルにおいて、ＰＯＩ１（参照記号４２３）は上記領域のうちの１つの領域内に位置を定められ、ＰＯＩ２およびＰＯＩ３（参照記号４３１および４３２）は、別の領域４２２に位置を定められる。従って、ＰＯＩ１は、木５００のノード５０２に直接格納され、一方、代用ＰＯＩ  Ｓ２は、ＰＯＩ２およびＰＯＩ３を含む他の領域４２２に関連するノード５０３に格納される。従って、１：１，０００，０００であるより低い縮尺で描かれる、図４Ｂの画像４２０は、ＰＯＩ  １（参照符号４２３）を含み、地図領域４２２において代用ＰＯＩ  Ｓ２（参照符号４２４）を含み、ＰＯＩ  Ｓ２は、ＰＯＩ２およびＰＯＩ３を表し、ＰＯＩデータ点は、それぞれの地図縮尺に対してＰＯＩデータベース１０４から検索される。
【００６２】
図５に示される木５００の最低深度レベル５３０において、地図領域は、各ＰＯＩが異なる地図領域に位置を定められるように十分に小さい。従って木５００は、最低深度レベル５３０において、ＰＯＩ２およびＰＯＩ３のためのノードを含むが、どの代用ＰＯＩも含まない。このことは、図４Ｂにおいて描かれる画像４３０（地図縮尺１：５００，０００）からも見られ得、図４Ｂは、ここで、シングルのＰＯＩ４２３（ＰＯＩ１）、４３１（ＰＯＩ２）、および４３２（ＰＯＩ３）のみを示すが、代用ＰＯＩを示さない。
【００６３】
最高深度レベル５１０において、シングルのＰＯＩのみが対応する地図領域内に位置を定められる場合、根ノードはＰＯＩを直接格納し得る。代用ＰＯＩのノードは、（例えば、ノード５０３などの）他の代用ＰＯＩノードを介して直接または間接のいずれかで代用ＰＯＩが表すＰＯＩのノードにリンクされる。概して、木５００のすべての葉はＰＯＩを格納する。木構造が、例えば、地図縮尺の範囲であって、その地図縮尺の範囲にわたりＰＯＩデータが表示される、地図縮尺の範囲に従って、図５に示される深度レベルよりも多い深度レベルを含み得ることは明らかである。好ましくは、木構造は、ＰＯＩノードのみが格納される最も深いレベルを含むように構成される。最も深いレベルは、従ってどの領域サイズにも関連付けられない場合があるか、または領域サイズは、無視され得るかもしくは非常に小さい値に設定され得る。
【００６４】
さらに、木構造において代用ＰＯＩノードに関連付けられる領域サイズは地図区域がディスプレイ１０１に表示され得る地図縮尺に無関係であることは明らかである。木構造は、利用可能なあらゆる地図縮尺に対する深度レベルを含み得るが、含む必要はない。木構造５００の異なる深度レベルにおいて提供される地図領域サイズにかかわりなく任意の表示地図縮尺に対するＰＯＩデータの検索は、図２および図３に関して以下に説明される。
【００６５】
それぞれのノードに格納される代用ＰＯＩの位置は、代用ＰＯＩが表すＰＯＩの平均位置を計算することによって決定され得る。他の実施形態において、重み付き平均は、平均位置における特定のＰＯＩの影響を調整するように計算され得る。地図画像を描く場合、図形記号が地図上の代用ＰＯＩの決定された位置に含まれる。図４に例示されるように、記号は特定のＰＯＩカテゴリーのアイコンのスタックであり得、スタックの高さは表されたＰＯＩの数を示す。さらにまたは代わりに、図形記号はまた、代用ＰＯＩに対する図形記号内に表示されるかまたは代用ＰＯＩに対する図形記号に隣接して表示される数などの表されたＰＯＩの数の数字指示を含み得る。一般的に記号は、ＰＯＩカテゴリー、図４においてはカテゴリー「レストラン」を示す。
【００６６】
図４Ｂを参照することによって、ナビゲーションシステム１００の動作は、次のとおり要約され得る。最小の地図縮尺（描かれる画像４１０）においてさえ、選択されたカテゴリーのすべてのＰＯＩが示される。閾値数を超えるＰＯＩが関連する地図領域に位置を定められる場合、代用ＰＯＩが表示されるので、人口稠密な地域でさえ過密状態は起らない。概観地図縮尺で、ユーザは、その環境において選択されたカテゴリーのすべてのＰＯＩを見ることが可能であり、従って、例えば、ＰＯＩがユーザの現在のルート上または現在のルートに隣接して位置を定められる場合、特定のＰＯＩを通ることが便利であるか否かを容易に決定し得る。特定の地図地域にズームインする場合（画像４１０、４２０および４３０のシーケンスで例示されるように）、地図上のシングルのＰＯＩの位置が決定される。
【００６７】
図１のナビゲーションシステム１００によって行われ得る本発明の方法の実施形態は、図２および図３に関して以下のとおり説明される。図２に従う方法のステップ２１０において、表示されるべきＰＯＩカテゴリーが決定される。これは、例えばユーザインタフェース（図１に示されていない)によってかまたはカテゴリーを自動的に決定するナビゲーションシステムによって、レストラン、ガソリンスタンド、薬局または類似のものなどの特定のカテゴリーをユーザが選択することによって行われ得る。表示されるべきカテゴリーは、ナビゲーションシステム１００によって事前に規定され得、ナビゲーションシステム１００は、ルート案内を行った場合、例えば興味深い名所およびガソリンスタンドを表示し得る。
【００６８】
ステップ２２０において、ユーザは、特定の地図縮尺に対応するズームレベルを選択する。ナビゲーションシステムは、例えば、詳細な地図情報を提供するためにルート案内中かなり大きい縮尺で地図を表示し得る。ユーザは、より小さい地図縮尺でより大きい地図区域を見るようにズームアウトするために制御要素を作動させ得る。新しい地図縮尺に対する表示されるべき地図区域がステップ２３０において決定される。対応する地図データは、次いで地図ユニット１０６によって地図データベース１０３から検索され得る。
【００６９】
ナビゲーションシステムは、明確で包括的な画像を生成するために保たれるべき、ディスプレイ上で測定される所定の最小ＰＯＩ距離を有するように構成され得る。所定の最小ＰＯＩ距離および新しい地図縮尺から、地図上で測定される（すなわち、実世界において）、ＰＯＩデータ点に対する必要とされる最小距離が、ステップ２４０において決定される。ナビゲーションシステムは、隣り合うＰＯＩデータ点が最小地図距離を保つ場合、隣り合うＰＯＩデータ点が表示されることを可能にするのみである。一例として、新しい地図縮尺が１：２，０００，０００であり、ディスプレイ上の必要とされる最小距離が３ｃｍである場合、ＰＯＩデータ点は地図上において６０ｋｍの最小距離を保たなければならない。ステップ２５０において、ＰＯＩデータベース１０４は、選択されたＰＯＩカテゴリーに対するＰＯＩデータを検索するためにアクセスされる。
【００７０】
ステップ２５０の起り得る実装は、図３のフロー図に例示される。データベースは、各カテゴリーに対する木構造を含み、木構造は、図５に関して上記に詳細に説明されるようにＰＯＩおよび代用ＰＯＩを格納する。処理はカテゴリーごとに行われる。ステップ２５１において、処理されているＰＯＩカテゴリーの木構造の根ノードが決定される。特定の地理的地域に対するＰＯＩデータベースは、概して代用ＰＯＩを格納する１つの根ノードを含み、代用ＰＯＩの関連する地図地域は、データベースに含まれる同じカテゴリーのすべてのＰＯＩに及ぶ。根ノード（ｒｏｕｔｅ  ｎｏｄｅ）に関連付けられる地図地域は、従って概して、表示されるべき地図区域に少なくとも部分的に含まれる。根ノードは、木構造を探索する良い開始点である。決定された根ノードの木は、ステップ２５２において幅優先探索を用いて探索される。ＰＯＩを直接格納し、従ってどの子ノードも有しない根ノードは、もちろん探索される必要はない。
【００７１】
特定の深度レベルにおいてＰＯＩデータ点間の必要とされる最小距離がもはや保たれなくなるまで、探索は行われる。これは、上記の例において同じ深度レベルの２つのＰＯＩデータ点（ＰＯＩまたは代用ＰＯＩ）が６０ｋｍより小さい距離を有する場合である。幅優先探索は、まず根ノードのすべての子ノード（図５において深度レベル５２０）を考慮し、次いで孫ノード（図５において深度レベル５３０）などを考慮する。
【００７２】
現在探索されている深度レベルのノードのＰＯＩデータ点間の距離は、ステップ２５３において決定される。深度レベル５２０を探索する場合、これは、ＰＯＩ１と代用ＰＯＩ  Ｓ２との間の距離である。
【００７３】
さらに深度レベルを探索する場合、各ＰＯＩが表示されるべき地図区域内に位置を定められるかどうかを各ＰＯＩに対してチェックされ、各代用ＰＯＩの関連付けられた地図領域が表示されるべき地図区域と重なり合うかどうかを各代用ＰＯＩに対してチェックされる（決定ステップ２５４）。チェックの結果が否定であれば、考慮中のノードのトラバースは停止される（ステップ２５５）。すなわち、他のノードに対するこのノードの距離は決定される必要がなく、次の深度レベルを探索するときに、このノードの子ノードは考慮されない。そうでない場合、この方法は続行する。従って探索は木の関連するノードに制限され得、このことは探索を加速する。
【００７４】
ノードに対して別のノードとの距離が最小距離より小さい場合（決定ステップ２５６）、幅優先探索は停止される（ステップ２５７）。そうでない場合、次の深度レベルが探索される。
【００７５】
探索が停止された後、すべてのレベルにおいて停止レベルより高いと発見されたＰＯＩおよび停止レベルより１レベル上と発見された代用ＰＯＩは、それぞれのＰＯＩカテゴリーに対するＰＯＩデータとして提供される（ステップ２５８）。図５の例において、レベル５２０で探索が停止された場合、代用ＰＯＩ  Ｓ１が検索され、一方、深度レベル５３０で停止した場合、ＰＯＩ１及び第用ＰＯＩ  Ｓ２が検索される。従って、代用ＰＯＩに対して選ばれた領域サイズは木構造の「深度解像度」を決定するが、それらの領域サイズは地図区域が表示される地図縮尺とは全く無関係であることは明らかである。表示地図縮尺は、ＰＯＩデータ点間の最小距離を決定するために用いられ、従って、探索が停止される深度レベルおよびＰＯＩまたは代用ＰＯＩが検索されるかどうかも決定する。
【００７６】
決定ステップ２５９において、さらなるＰＯＩカテゴリーが処理されるべきかどうかがチェックされる。さらなるカテゴリーがある場合、方法はステップ２５１に戻る。そうでない場合、ステップ２６０において、選択されたＰＯＩカテゴリーに対して検索されたＰＯＩデータが、さらなる処理に対して提供される。
【００７７】
ＰＯＩデータベースを探索するための異なるタイプの探索アルゴリズムを用いること、木構造の深度レベルを特定の表示地図縮尺に直接に相関させること、または類似のことなどを行って、図２のステップ２５０の他の実装が確かに考えられる。
【００７８】
いくつかの例において、代用ノードはＰＯＩにリンクされ得、ＰＯＩのいくつかは表示されるべき地図区域内に位置を定められ、ＰＯＩのいくつかは地図区域外に位置を定められる。検索されたＰＯＩは概して地図区域内に位置を定められるが（決定ステップ２５４による）、検索された代用ＰＯＩは、地図区域内または地図区域外に位置を定められ得る。従って、ステップ２７０において、表示されるべき地図区域内に位置を定められる、検索されたＰＯＩデータにおける代用ＰＯＩが決定される。地図区域外に位置を定められる代用ＰＯＩは、地図区域内に位置を定められるＰＯＩになおもリンクし得るので、無視され得るか、または地図区域の周辺に表示され得る。
【００７９】
そのように決定されたＰＯＩおよび代用ＰＯＩに対して、ステップ２８０において図形記号が検索される。上記に言及されるように、代用ＰＯＩに対する図形記号は、図４に例示されるように、ＰＯＩカテゴリーおよび表されたＰＯＩの数を示し得る。ステップ２５０〜２８０は、例えば、検索ユニット１０７によって行われ得る。
【００８０】
表示制御ユニット１０８はここで画像を描き得、画像において、表示のために検索されたＰＯＩおよび代用ＰＯＩの図形記号は、それぞれの地図位置に決められる。決定された地図区域ならびに検索されたＰＯＩおよび代用ＰＯＩは、次いでステップ２９０において同時に表示される。従って、より小さい地図縮尺で、ＰＯＩカテゴリーは、消されないで、その代わりに代用ＰＯＩが表示される。
【００８１】
ステップ３００において、ユーザが新しいズームレベルを選択した場合、すなわちユーザが地図をズームインまたはズームアウトした場合、方法は繰り返される。ＰＯＩ検索および表示手順はまた、地図がユーザによってパンされる場合、確かに繰り返され得る。
【００８２】
方法およびナビゲーションシステムは、表示され得る最大の地図縮尺を有するように構成され得る。一実施形態において、選択されたカテゴリーのすべてのＰＯＩが、その最大地図縮尺で表示される。これは異なる個々のＰＯＩをユーザが区別することを可能にするが、高密度インフラストラクチャ地域において過密状態が起り得る。別の実施形態において、適用可能な場合（すなわち、木構造における２番目に低い深度レベルに対応して）、代用ＰＯＩもまた、最大地図縮尺で表示される。ユーザが特定のＰＯＩの位置を定めることを可能にするために、代用ＰＯＩは選択可能に作られ得る。ユーザが、例えば表示された地図区域上にポインタを用いるなどのユーザ入力によって代用ＰＯＩを選択する場合、選択された代用ＰＯＩによって表されるすべてのＰＯＩは、選択リストにおいてユーザに提示される（すなわち、対応する代用ＰＯＩノードの子ノードのＰＯＩ）。選択リストにおいて、ユーザは、次いで経路指定機能における目的地として入力され得るかまたは地図区域に表示され得るＰＯＩを選択し得る。
【００８３】
ＰＯＩデータベース１０４は、様々な方法で生成され得る。例として、異なるカテゴリーに対するＰＯＩおよびその地図位置は、異なるＰＯＩデータベースから検索され得る。異なる選択された地図縮尺に対して、地図領域が規定され、地図領域の縁サイズは、例えば地図縮尺に反比例する縮尺で決め得る。特定のカテゴリーのＰＯＩが位置を定められる地図領域に対して、それぞれの地図領域における上記カテゴリーのＰＯＩの数が決定される。地図領域に位置を定められる同じカテゴリーのＰＯＩの数は、所定の閾値数より大きい場合、同じカテゴリーの代用ＰＯＩが地図領域に関連するＰＯＩデータベースに格納される。対応する地図縮尺に対して、代用ＰＯＩは、ここで地図領域において同じカテゴリーのＰＯＩを表す。代用ＰＯＩは、表されたＰＯＩの位置の平均値または重み付き平均値を計算することによって決定される位置に関連して格納される。データベースは、最大サイズの領域のＰＯＩまたは代用ＰＯＩを根ノードとして規定し、親ノードに関連付けられた領域内に位置を定められる次に小さいサイズの領域に対してＰＯＩまたは代用ＰＯＩを格納するノードに根ノードをリンクさせることによって、木構造に構築される。従って、図５に例示される木構造が構築される。そのような木構造を含むＰＯＩデータベースを設定するいくつかの他の方法があることは明らかである。上記に言及されるように、ＭＢＲは、ＰＯＩの部分に広がるために用いられ得、ＰＯＩの部分は、木構造のより低い深度レベルでより小さくなる。
【００８４】
要約すると、本発明のナビゲーションシステムおよび方法は、地図データにおける興味ある地点の表示にいくつかの改善を提供する。より小さい概観地図縮尺でさえ、選択されたカテゴリーのすべてのＰＯＩが見られ得る。従って、適切なＰＯＩの位置を定めることは、ナビゲーションデバイスのユーザにとって容易にされる。これらのより小さい地図縮尺においてでさえ、高密度のＰＯＩを有する都市地域において過密状態が全く起らず、これは代用ＰＯＩを用いることによって達成される。データベースの構造により、ＰＯＩおおび代用ＰＯＩは迅速かつ効率的に検索され得る。データベースに代用ＰＯＩが備えられているので、ナビゲーションデバイスはそれ自身で代用ＰＯＩを計算する必要はない。
【符号の説明】
【００８５】
１００  ナビゲーションシステム
１０１  ディスプレイ
１０２  メモリ
１０３  地図データベース
１０４  ＰＯＩデータベース
１０５  処理装置
１０７  検索ユニット
５０１  ノード
５１０、５２０、５３０  深度レベル
【図１】
2012042950.tif 000003
【図２】
2012042950.tif 000004
【図３】
2012042950.tif 000005
【図４】
2012042950.tif 000006
【図５】
2012042950.tif 000007