【誤訳訂正書】
【提出日】平成24年10月25日(2012.10.25)
【誤訳訂正１】
【訂正対象書類名】明細書
【訂正対象項目名】全文
【訂正方法】変更
【訂正の内容】
【発明の詳細な説明】
【発明の名称】道路セグメントのディレクトリの作成方法、探索領域内のすべての道路セグメントの検出方法、およびコンピュータプログラム
【技術分野】
【０００１】
本発明は、ナビゲーションシステム用のデジタル道路地図の道路セグメントのディレクトリの作成方法に関する。
【０００２】
本発明はまた、探索領域内のすべての道路セグメントを検出する検出方法にも関し、
また、道路セグメントのディレクトリの作成方法を実施するためのコンピュータプログラム、ならびに、探索領域内のすべての道路セグメントを検出する検出方法を実施するためのコンピュータプログラムにも関する。
【０００３】
車両用のナビゲーションシステムは、基本機能である測位機能、目的地選択機能、ルート計算機能および目的地案内機能を実施するために、道路網のデジタル地図を必要とする。このデジタル道路地図はたいてい、たとえばＣＤ，ＤＶＤまたはＳＤカード等のデジタル記憶媒体上に記憶されている。このような記憶媒体上では、デジタル道路地図を表現するためのデータがファイルに格納されている。このデータはファイル内に線形に連続して設けられる。
【０００４】
ナビゲーションシステムは、たとえば道路網の地図をスクリーン上に表示したり、または現在の位置を道路網の次の道路に投影するために、このようなデータを必要とする。この現在の位置は、たとえばＧＰＳ（Global Positioning System）またはガリレオおよび／または別の慣性センサによって検出することができ、たとえば走行距離計、回転速度センサまたは加速度センサによって検出することができる。
【０００５】
記憶媒体上に記憶された道路網全体の大部分が重要でないナビゲーションのアプリケーション、または大して重要でないナビゲーションのアプリケーションが数多く存在する。たとえば、州全体の道路網が記憶されているにもかかわらず、具体的なターゲットルート案内を地方の範囲に制限することができる。また、ユーザが、現在位置の拡大された一部分を表示させたい場合も考えられる。
【０００６】
線形に記憶されたデジタル道路地図において２次元の探索領域内のすべての道路を探索する場合、道路地図全体を探索しなければならない。このことは、著しい時間的な手間に繋がる。さらに、デジタル道路地図の情報内容は増加し続けており、個々の道路はますますより短い道路セグメントに分解され、また、たとえばガソリンスタンドまたはいわゆるポイント・オブ・インタレスト（ＰＯＩ）の地理的位置等の、取り込まれる情報も増加している。道路地図全体を探索するために必要な時間的手間によって表示が遅延され、このことはユーザにとって煩わしいものとなる。
【０００７】
このような場合に道路地図全体を完全に探索することを回避するためには、デジタル道路地図に含まれる道路を構造化する。
【０００８】
隣接する道路を情報単位に、いわゆるクラスタにまとめることが公知である。その際には、市内地域、市境界、群境界、または類似する地理的境界を参照する。隣接するクラスタは、より上位の階層のクラスタにまとめられる。この過程はより上位のレベルに対して継続される。その結果、比較的良好に均衡がとれた階層ツリーが得られる。この階層ツリーが過度に大きくならないようにするためには、最下位レベルで道路を地理的に区分して線形に格納する。このレベルでの典型的な道路数は約１０００個である。
【０００９】
別の公知の構造化では、デジタル化された道路網に均等なラスタを重畳する。このラスタはたとえば、多数の等しい大きさの方形から、いわゆるタイルから構成される。１つのタイルにある道路はすべてまとめて格納される。記憶媒体上に、これらのタイルに地理的座標を割り当てるインデックスが記憶されており、このインデックスによって座標からタイルに高速にアクセスすることができる。しかしこのことの欠点は、タイルにおける道路の占有状態が非常に異なっており、非常に多くの道路を含むタイルがある一方で、他方では道路を有さないタイルがあったり、含まれる道路が非常に少ないタイルもある。このことによって記憶が非効率的になり、探索に必要とされる時間は探索領域の位置に大きく依存する。
【００１０】
したがって本発明として、請求項１に記載の方法を提供する。
【００１１】
本発明では、従来技術において付加的な構造情報を必要とすることなく、道路セグメントを、順序づけられたＮツリーに配置する。本発明による方法は、そのつど、道路地図を分割するための出発点として、すなわち道路地図の「スペースディバイダ」として道路地図の道路セグメントを使用する。道路セグメントを位置決定するために必要なデータ、たとえば始点および終点の地理的座標等のデータと、場合によっては別の中間点、いわゆる形状点（Shapepoint）とは、地図中にすでに存在する。道路地図を分割するための付加的なデータは必要ない。このことによって所要記憶スペースは低減され、かつ、本発明のツリーで行われる探索の負荷は軽減される。総じてアクセス時間を短縮することができる。それと同時にこのことによって、所定の探索時間で付加的な情報を、たとえばＰＯＩを考慮することもできるようになる。
【００１２】
本発明の方法は、道路地図全体にも適用することができ、また、すでに公知の手法と組み合わせても使用することができる。公知の手法と組み合わせる場合、本発明の方法は有利には、多数の道路が線形のファイルで記憶された最下位レベル、典型的には１０００個のオーダの道路が線形のファイルで記憶された最下位レベルで使用される。本発明による方法によって、このようなレベルで行われる約１０００個の道路すべての探索を約１０〜２０個の道路の探索に制限することができ、著しい時間削減を実現することができる。このことによって本発明によるツリーは、従来使用されてきたデータ構造と両立できるようになる。
【００１３】
好適には、どの部分平面に道路セグメントが完全に含まれるかに応じて、道路セグメントを部分平面に割り当てる。道路セグメントを部分平面のうち１つに一義的に割り当てることができない場合、パーティショニングを発生させる道路セグメントが存在する部分平面に割り当てる。
【００１４】
本発明による方法の１つの実施形態では、Ｎ＝３である。この場合、道路セグメントのディレクトリはトライツリー（Tri-Baum）で配置される。各道路セグメントが道路地図を３つの部分平面にパーティショニングする。有利には、これら３つの部分平面を以下のように配置する：
まず、道路セグメントの始点および終点によって直線を定義する。そして、この最初の第１の直線に対して平行な２本の直線を形成して、道路セグメントがこれら２つの平行な直線の間に完全に画定されるように、すなわち存在する可能性のある形状点を含むように含まれるように、これらの直線を相互に配置する。その際には、これら２つの平行な直線の相互間に、道路セグメントのすべての点がちょうど包含されるような間隔をおいて、これらの平行な直線を配置することが有利である。道路セグメントは始点および終点によって一義的な方向を有し、たとえば始点から終点への方向を有する。道路セグメントのこのような方向の向きに該道路セグメントを考慮する場合、３つの部分平面のうち１つは一義的に道路セグメントの左側にあり、別の部分平面は該道路セグメントのちょうど右側にあり、第３の部分平面は該道路セグメント自体を含む。すなわち第３の部分平面は「中間」にある。
【００１５】
本発明による方法の別の実施形態では、Ｎ＝５である。この場合、道路セグメントのディレクトリはいわゆる５ツリーで構造化される。有利には、これら５つの部分平面を以下のように配置する：
まず、考慮されている道路セグメントに方形を重ねる。たとえば、道路セグメントの始点および終点が方形の対角線の終点を成し、すべての形状点が方形内に含まれるように該方形の大きさを選択する。その際には、方形を可能な限り小さく選択するのが有利である。第２のステップでは、この方形の辺を補完して、それぞれ数学的に等しい方向を有する半直線を形成し、たとえば時計回りまたは反時計回りの方向に等しい方向を有する半直線を形成する。この方形と４つの半直線とによって、道路地図を一義的に５つの部分平面にパーティショニングする。これらの部分平面は、道路セグメントの方向に関連して位置によって、「左側」、「中間」（方形）、「右側」、「先行部分」、「後続部分」と称することができる。
【００１６】
各ノードに、直接後続するノードをポインティングするポインタを記憶する場合、本発明にしたがって生成されたＮツリー内の探索を特に高速に実施することができる。このようにして、各ノードに直接、直接後続するもののアドレスが得られ、時間遅延なくこのノードのサブツリーに入ることができる。
【００１７】
さらに本発明として、請求項７に記載の方法を提供する。
【００１８】
従来の線形のリストの場合、道路セグメントを探索する時間は、該リストに記憶された道路セグメントの数に比例する。それに対して、本発明にしたがって生成されるＮツリーの場合、ＮがＮツリーに記憶された道路セグメント数ないしはＮツリーのノード数である場合、探索時間の増加分はｌｏｇ（Ｎ）だけである。とりわけ、記憶された道路セグメントが多数である場合、本発明による方法のこの利点は顕著になる。
【００１９】
好適には、Ｎツリーはオフラインで生成される。このことによって、Ｎツリーの均衡性に多くの時間を投ずることができるようになり、オンラインの探索時間すなわちナビゲーションシステムにおいて行われる探索の時間を著しく短縮することができる。
【００２０】
有利には、探索領域内のすべての道路セグメントを求めるための本発明の方法は、探索領域が方形であることを特徴とする。方形の探索領域の場合、探索領域を一義的に定義するために必要なデータは非常に少なくなる。さらに非常に簡単に処理を行えるようになるので、複雑な幾何的形状の探索領域と比較して探索時間が短縮される。
【００２１】
本発明として、請求項９および１０に記載の、プログラムコードを有するコンピュータプログラムを提供する。
【００２２】
次に、添付の図面に示された実施例に基づき本発明を詳しく説明する。
【図面の簡単な説明】
【００２３】
【図１】第１のデジタル道路地図の一部分を示す。
【図２】第２のデジタル道路地図の一部分を示す。
【図３】第３のデジタル道路地図の一部分を示す。
【図４】図３に示された一部分に対する３ツリー（トライツリー）を示す。
【００２４】
図１に、第１のデジタル道路地図１の一部分が示されている。
【００２５】
デジタル道路地図１は道路セグメント２を含む。道路セグメント２は始点３ａを有し、その次に２つの形状点３ｂ，３ｃと終点３ｄとを有する。両形状点３ｂ，３ｃは、直線の経過から偏差する道路セグメント２の経過を表す。すなわち、道路セグメント２の曲線状の経過を表す。デジタル道路地図１にはこの道路セグメント２に対して地理的座標が記憶されており、たとえば地理的長さと地理的幅とが記憶されている。たとえば、道路セグメント２の海抜または該道路セグメント２に存在するガソリンスタンドに関するデータまたはＰＯＩに関するデータ等の別の情報を記憶することもできる。
【００２６】
道路セグメント２には方向が割り当てられている。この方向は、始点３ａから終点３ｄへ方向づけされた矢印４によって示されている。
【００２７】
図１にはさらに、相互に平行な２つの直線５ａ，５ｂが示されている。これら２つの直線５ａ，５ｂの間に中間の部分平面６ａが形成されている。この道路セグメント２は、この中間の部分平面６ａ内に完全に含まれる。
【００２８】
道路セグメント２の方向の向きで見て該道路セグメント２ないしは中間部分平面６ａの左隣に左側部分平面６ｂが存在し、該道路セグメント２ないしは中間部分平面６ａの右側に右側部分平面６ｃが存在する。
【００２９】
道路セグメント２の方向で行われる部分平面６ａ，６ｂ，６ｃのこのような配置は一義的である。
【００３０】
これら３つの部分平面６ａ，６ｂ，６ｃによって一義的な分割が行われ、デジタル道路地図１のパーティショニングが行われる。
【００３１】
図１に示された、デジタル道路地図１を道路セグメント２によって３つの部分平面６ａ，６ｂ，６ｃに分割するこのパーティショニングは、別の道路セグメントを整理してトライツリーを形成するための基礎となる。
【００３２】
図２に、道路セグメント８によって行われる５つの部分平面９ａ，９ｂ，９ｃ，９ｄ，９ｅへの第２のデジタル道路地図７の分割が示されている。道路セグメント８の方向は矢印１０によって示されている。
【００３３】
道路セグメント８は始点１１ａと終点１１ｂと２つの形状点１１ｃ，１１ｄとを有する。始点１１ａと終点１１ｂと形状点１１ｃ，１１ｄとを有する道路セグメントはすべて、部分平面９ａ，９ｂ，９ｃ，９ｄ，９ｅのうち１つを表す方形内に含まれる。方形の辺は補完されて、４つの半直線１２ａ，１２ｂ，１２ｃ，１２ｄが形成されている。時計回りにこの方形の辺を補完して、半直線１２ａ，１２ｂ，１２ｃ，１２ｄを形成する。
【００３４】
この方形および半直線１２ａ，１２ｂ，１２ｃ，１２ｄによってデジタル道路地図７は、前記５つの部分平面９ａ，９ｂ，９ｃ，９ｄ，９ｅに分割される。道路セグメント８の方向に依存してこれらの部分平面９ａ，９ｂ，９ｃ，９ｄ，９ｅを、「中間」部分平面９ａ、「右側」部分平面９ｂ、「左側」部分平面９ｄ、「前方」部分平面９ｃおよび「後方」部分平面９ｅに配置することができる。
【００３５】
図３に、第３のデジタル道路地図１３の一部分が示されている。
【００３６】
デジタル道路地図１３は１０個の道路セグメント１４ａ〜１４ｊを有し、これらの方向はそれぞれ矢印１５によって示されている。概観しやすくするため、道路セグメント１４ｆに対応する矢印１５のみが示されている。
【００３７】
図３にはさらに探索領域１６が示されている。この探索領域は少なくとも部分的に、道路セグメント１４ａ，１４ｂ，１４ｃを含む。
【００３８】
以下でまず初めに、本発明による方法によって道路セグメント１４ａ〜１４ｊのディレクトリをどのように作成するかを説明する。
【００３９】
このディレクトリは、図４に示されたようなトライツリー１７の構造を有するようになる。
【００４０】
このようなトライツリー１７を形成するためには、道路セグメント１４ｅを例にとると、以下の探索ツリー条件が定義される：同名のノードの道路セグメント１４ｅによって、道路地図１３は３つの部分平面にパーティショニングされ、これらの部分平面のうちで道路セグメント１４ｅを含むのはちょうど１つである。これらの部分平面は、道路セグメント１４ｅの方向に依存して相互に配置される。他のすべての道路セグメント１４ａ〜１４ｄはこれらの部分平面のうちちょうどいずれか１つに割り当て、ひいてはこのノードの部分ツリーに割り当てることができる。左側の部分平面に道路セグメント１４ａ〜１４ｄが残っており、中間の部分平面には道路セグメント１４ｆが残っており、右側の部分平面には道路セグメント１４ｇ〜１４ｊが残っている。
【００４１】
次のステップにおいて、左側の部分平面をさらに分割する。こうするためには、この部分平面内に存在する道路セグメント１４ａ〜１４ｄのうちで１つを選択する。この例では、この選択される道路セグメントは道路セグメント１４ｃである。
【００４２】
道路セグメント１４ｃは左側の部分平面をさらに３つの部分平面に分割し、これらの部分平面のうち１つは道路１４ｃの方向に関して左側にある部分平面であり、別の１つの部分平面は中間にある部分平面であり、さらに別の第３の部分平面は右側にある部分平面である。
【００４３】
未だ選択されていない道路セグメント１４ａ，１４ｂ，１４ｄをこれらの部分平面に割り当てる。道路セグメント１４ａは道路セグメント１４ｃの左側の部分平面にあり、中間の部分平面は空であり、右側の部分平面には道路セグメント１４ｂ，１４ｃがある。
【００４４】
次に、道路セグメント１４ｄを次のノードとして選択する。ここでは道路セグメント１４ｂが未だ残っている。この道路セグメント１４ｂは、道路セグメント１４ｄで見て左側の部分平面にある。中間の部分平面および右側の部分平面には道路セグメントは存在しない。このようにして道路セグメント１４ｅに関して、トライツリーのルートに関して、左側の部分ツリー内のすべての道路セグメント１４ａ〜１４ｄが組み込まれる。
【００４５】
このことに相応して、中間の部分ツリーおよび右側の部分ツリーについてもノードをセットする。このようにして、図４に示されたトライツリー１７が得られる。
【００４６】
以下で、道路地図１３とトライツリー１７と探索領域１６とを例にして、探索領域内のすべての道路セグメントを検出するための本発明の方法を説明する。
【００４７】
トライツリー１７における探索は常にルートで開始され、このケースでは道路セグメント１４ｅで開始される。
【００４８】
道路セグメント１４ｅで見て、探索領域１６は左側の部分平面内に完全に含まれる。探索領域１６は中間の部分平面と交差する部分を有さないので、道路セグメント１４ｅは可能性のある探索結果として考えられることはない（ステップｆ）。
【００４９】
以下の例では、ステップｇ）において左側の部分平面のみが検出される。
【００５０】
ステップｈ）の後には、左側の部分平面に割り当てられた部分ツリー１８を検出しなければならない。部分ツリー１８は道路セグメント１４ａ〜１４ｄを含む。
【００５１】
ステップｉ）で部分ツリー１８に標識が付される（Merken）。
【００５２】
ステップｊ）の後には、ステップｉ）で標識が付された部分ツリーに選択肢を制限して、考慮されるすべての部分ツリーが１回だけ選択されるまで、ステップｂ）〜ｉ）を繰り返す。
【００５３】
この例では、ツリー１８のみに標識を付するので、このツリー１８のみを選択することができる。この部分ツリー１８のルートノードは、道路セグメント１４ｅを有するノードである。道路セグメント１４ｃに関しては、探索領域１６は左側の部分平面にも右側の部分平面にも中間の部分平面にも存在する。ステップｆ）の後には、道路セグメント１４ｃが可能性のある探索結果として考えられて標識が付される。
【００５４】
ここで、道路セグメント１４ｃのノードに繋がる部分ツリー１９ａ，１ｂを検出しなければならない。１つの部分ツリー１９ａは、道路セグメント１４ａとのノードのみから成る。第２の部分ツリー１９ｂは、該部分ツリー１９ｂのルートノードであり道路セグメント１４ｄに繋がるノードと、道路セグメント１４ｂとから構成される。
【００５５】
道路セグメント１４ａに関し、探索領域１６は左側の部分平面と右側の部分平面と中間の部分平面とに存在する。道路セグメント１４ａに繋がるノードはトライツリー１７の葉であるから、標識を付さなければならない部分ツリーはもう無い。存在する可能性があり標識を付さなければならない探索結果は、道路セグメント１４ａのみである。
【００５６】
道路セグメント１４ｄを有する部分ツリーをルートとして検査することにより、探索領域１６は左側の部分平面内に完全に含まれる。このようにして道路セグメント１４ｂが得られる。トライツリー１７の葉に相応する道路セグメント１４ｂに関しては、探索領域１６は中間の部分平面内に存在する。このことによって道路セグメント１４ｂも探索結果として考えられて標識が付される。
【００５７】
ここで、１回標識が付された部分ツリー１８，１９ａおよび１９ｂがすべて処理されたことになる。
【００５８】
最後のステップにおいて、可能性のある、標識が付された次のような探索結果、すなわち、探索領域１６と実際に交差しない道路セグメント１４ａ，１４ｂ，１４ｃが切り取られる。ここでは、道路セグメント１４ａ，１４ｂ，１４ｃを切り取らなくてもよい。したがって、探索結果は道路セグメント１４ａ，１４ｂ，１４ｃとなる。
【誤訳訂正２】
【訂正対象書類名】特許請求の範囲
【訂正対象項目名】全文
【訂正方法】変更
【訂正の内容】
【特許請求の範囲】
【請求項１】
ナビゲーションシステム用のデジタル道路地図（１，７）の道路セグメント（２，８，１４ａ〜１４ｊ）のディレクトリの作成方法であって、
前記ディレクトリは、前記道路セグメント（２，８，１４ａ〜１４ｊ）がノードで記憶される整列されたＮツリー（１７）のデータ構造を含む作成方法において、
ａ）前記道路セグメント（２，８，１４ａ〜１４ｊ）すべてに地理的位置を割り当てるステップと、
ｂ）前記道路セグメント（２，８，１４ａ〜１４ｊ）すべてに方向を割り当てるステップと、
ｃ）（ｉ）前記ノードの前記道路セグメント（２，８，１４ａ〜１４ｊ）によって、前記デジタル道路地図をＮ個の部分平面（６ａ，６ｂ，６ｃ）にパーティショニングし、該部分平面（６ａ，６ｂ，６ｃ）のうちちょうど１つの部分平面は前記道路セグメント（２，８，１４ａ〜１４ｊ）を含むようにし、
（ii）前記道路セグメント（２，８，１４ａ〜１４ｊ）の方向に依存して前記部分平面を相互に配置し、
（iii）すべての道路セグメント（２，８，１４ａ〜１４ｊ）を前記部分平面のうちちょうど１つに割り当てて、前記ノードのちょうど１つの部分ツリーに割り当てることにより、探索ツリー条件を定義するステップと、
ｄ）前記道路セグメント（２，８，１４ａ〜１４ｊ）のうち１つを選択するステップと、
ｅ）前記選択された道路セグメントを前記Ｎツリー（１７）内で探索し、該選択された道路セグメントの探索を、該選択された道路セグメント（２，８，１４ａ〜１４ｊ）を含む部分ツリーを含まない最大Ｎ−１個の部分ツリーを有するノード［終点ノード］で終了するステップと、
ｆ）前記選択された道路セグメント（２，８，１４ａ〜１４ｊ）を葉として、前記探索ツリー条件にしたがって終点ノードに繋げるステップと、
ｇ）すべての道路セグメント（２，８，１４ａ〜１４ｊ）がちょうど１回選択されるまで、ステップｄ）〜ｆ）を繰り返すステップと、
ｈ）前記ディレクトリをデータ担体に記憶するステップ
とを実施することを特徴とする、作成方法。
【請求項２】
前記ステップ（iii）からの前記道路セグメントを、該道路セグメントが完全に含まれる部分平面に割り当てるか、または、前記ステップ（ｉ）からの道路セグメントが含まれる部分平面に割り当てる、請求項１記載の作成方法。
【請求項３】
Ｎ＝３である、請求項１または２記載の作成方法。
【請求項４】
ａ）前記道路セグメント（２，８，１４ａ〜１４ｊ）の始点および終点によって第１の直線を定義するステップと、
ｂ）相互間に前記道路セグメント（２，８，１４ａ〜１４ｊ）を完全に含む、相互に平行でありかつ前記第１の直線に対して平行な２つの直線を形成するステップと、
ｃ）前記道路セグメント（２，８，１４ａ〜１４ｊ）の方向に依存して３つの前記部分平面（「左側」、「中間」、「右側」）を配置するステップ
とを実施して、前記３つの部分平面を形成する、請求項３記載の作成方法。
【請求項５】
Ｎ＝５である、請求項１または２記載の作成方法。
【請求項６】
ａ）前記道路セグメント（２，８，１４ａ〜１４ｊ）を含む方形を形成するステップと、
ｂ）前記方形の辺に沿って、前記道路セグメント（２，８，１４ａ〜１４ｊ）の方向と同一の方向を有する半直線を形成するステップと、
ｃ）前記道路セグメント（２，８，１４ａ〜１４ｊ）の方向に依存して、前記部分平面を５つ配置する（「左側」、「中間」、「右側」、「前方」、「後方」）ステップ
とによって、前記部分平面を５つ形成する、請求項５記載の作成方法。
【請求項７】
各ノードに、後続のノートを示すポインタを記憶する、請求項１から６までのいずれか１項記載の作成方法。
【請求項８】
探索領域内で、請求項１から７までのいずれか１項記載の作成方法にしたがって作成されたディレクトリのすべての道路セグメント（２，８，１４ａ〜１４ｊ）を検出するための検出方法において、
ａ）前記探索領域（１６）を、デジタル道路地図の部分領域として定義するステップと、
ｂ）Ｎツリー（１７）で開始して部分ツリーのうち１つを選択するステップと、
ｃ）前記選択された部分ツリーのルートノードを決定するステップと、
ｄ）前記ルートノードに記憶された道路セグメント（２，８，１４ａ〜１４ｊ）の部分平面を検出するステップと、
ｅ）前記探索領域が、前記決定された部分平面のうちどれと交差する部分を有するかを検出するステップと、
ｆ）前記探索領域が、前記道路セグメントがある部分平面と交差する部分を有する場合、該道路セグメント（２，８，１４ａ〜１４ｊ）に、可能性のある探索結果として標識を付するステップと、
ｇ）さらに探索するために、前記探索領域と交差する部分を有する他の部分平面を検出するステップと、
ｈ）前記ステップｇ）において検出された部分平面に割り当てられた部分ツリーを検出するステップと、
ｉ）前記ステップｈ）において検出された部分ツリーに標識を付するステップと、
ｊ）標識が付されたすべての部分ツリーがちょうど１回選択されるまで、前記ステップｉ）で標識が付された部分ツリーに選択肢を限定して前記ステップｂ）〜ｉ）を繰り返すステップと、
ｋ）前記ステップｆ）で標識が付された道路セグメント（２，８，１４ａ〜１４ｊ）であって、前記探索領域と交差しない道路セグメント（２，８，１４ａ〜１４ｊ）を切り取るステップ
とを実施することを特徴とする、検出方法。
【請求項９】
前記探索領域は方形である、請求項８記載の検出方法。
【請求項１０】
プログラムコードを有するコンピュータプログラムにおいて、
前記プログラムコードは、当該コンピュータプログラムがコンピュータで実行される場合に請求項１から９までのいずれか１項記載の方法のすべてのステップを実施するために設けられていることを特徴とする、コンピュータプログラム。
【請求項１１】
機械読み取り可能な担体上に記憶されたプログラムコードを有するコンピュータプログラムにおいて、
前記プログラムコードは、当該コンピュータプログラムがコンピュータで実行される場合に、請求項１から９までのいずれか１項記載の方法を実施するように設けられていることを特徴とする、コンピュータプログラム。