(57)【要約】【課題】並列処理において高速に図形編集処理を実施する地図生成装置およびその生成した地図を表示装置に表示させる表示方法を提供する。【解決手段】地図生成装置は、複数の図形編集プロセスを起動させる図形編集処理部と、複数の階層の領域を定義する並列処理範囲定義部と、定義された処理範囲を最下層の領域から順番に図形編集プロセスに対して処理範囲として指定し、下位階層の領域の処理がすべて終了するまで待機してから、上位階層の領域処理の割り当てを開始する並列処理管理部と、並列処理管理部によって割り当てられた処理範囲内に包含されており、かつ、編集処理が完了していない図形のみを前記電子地図データから抽出する内包判定機能を有する処理地物抽出部とを備え、図形編集プロセスは、地図生成を行う際に必要な編集機能と、図形編集に伴い必要となる編集後の図形の検査機能および修正機能とを備えた。【選択図】図１
2014153824.tif 000002
【特許請求の範囲】
【請求項１】
地形または地物の形状を表現する図形データが含まれた電子地図データから、図形の形状に関連する編集処理を行い新たな地図を生成する地図生成装置であって、
複数の図形編集プロセスを起動させる図形編集処理部と、
複数の階層の領域を定義する並列処理範囲定義部と、
前記並列処理範囲定義部によって定義された処理範囲を最下層の領域から順番に前記図形編集プロセスに対して処理範囲として指定し、下位階層の領域の処理がすべて終了するまで待機してから、上位階層の領域処理の割り当てを開始する並列処理管理部と、
前記並列処理管理部によって割り当てられた処理範囲内に包含されており、かつ、編集処理が完了していない図形のみを前記電子地図データから抽出する内包判定機能を有する処理地物抽出部とを備え、
前記図形編集プロセスは、地図生成を行う際に必要な編集機能と、図形編集に伴い必要となる編集後の図形の検査機能および修正機能とを備えたことを特徴とする地図生成装置。
【請求項２】
前記並列処理範囲定義部は、編集する地図領域を内包する領域または前記編集する地図領域を内側に含み境界線のみ接している状態の領域を定義する最上位階層領域定義機能と、前記最上位階層領域定義機能によって定義された最上位階層領域を分割し最下位階層領域を定義する領域分割機能と、前記領域分割機能によって分割された領域を統合して上位階層の領域を定義する領域統合機能とを備えたことを特徴とする請求項１記載の地図生成装置。
【請求項３】
前記並列処理範囲定義部は、前記最上位階層領域を面積に応じて複数に等分割した領域を生成し前記最下位階層領域とすることを特徴とする請求項２記載の地図生成装置。
【請求項４】
前記並列処理範囲定義部は、前記最上位階層領域を行政区域界に応じて複数に分割した領域を生成し前記最下位階層領域とし、
前記領域統合機能は、前記行政区域界に従って分割された領域を統合することを特徴とする請求項２記載の地図生成装置。
【請求項５】
前記並列処理範囲定義部は、前記領域分割機能により前記最上位階層領域をkd-treeの概念を用いて階層毎の各領域の図形簡略処理が同処理時間で完了するように分割し、前記領域統合機能によりkd-treeの子ノードの領域を統合して前記上位階層の領域となる親ノードの領域を定義することを特徴とする請求項２記載の地図生成装置。
【請求項６】
前記並列処理管理部は、どの下位階層の領域を統合したものがどの上位階層の領域となっているのかという対応関係を管理し、構成している下位階層の領域の処理がすべて完了すれば、当該上位階層の領域の処理も可能とする処理可能範囲判定機能をさらに備えたことを特徴とする請求項１記載の地図生成装置。
【請求項７】
地形または地物の形状を表現する図形データが含まれた電子地図データから、図形の形状に関連する編集処理を行い新たな地図を生成して表示装置に表示させる地図生成装置であって、
複数の図形編集プロセスを起動させる図形編集処理部と、
複数の階層の領域を定義する並列処理範囲定義部と、
前記並列処理範囲定義部によって定義された処理範囲を最下層の領域から順番に前記図形編集プロセスに対して処理範囲として指定し、下位階層の領域の処理がすべて終了するまで待機してから、上位階層の領域処理の割り当てを開始する並列処理管理部と、
前記並列処理管理部によって割り当てられた処理範囲内に包含されており、かつ、編集処理が完了していない図形のみを前記電子地図データから抽出する内包判定機能を有する処理地物抽出部とを備え、
前記図形編集プロセスは、地図生成を行う際に必要な編集機能と、図形編集に伴い必要となる編集後の図形の検査機能および修正機能とを備えたことを特徴とする地図生成装置。
【請求項８】
地形または地物の形状を表現する図形データが含まれた電子地図データから、図形の形状に関連する編集処理を行い新たな地図を生成して表示装置に表示させる表示方法であって、
図形編集処理部が、複数の図形編集プロセスを起動させるステップと、
並列処理範囲定義部が、複数の階層の領域を定義するステップと、
並列処理管理部が、前記並列処理範囲定義部によって定義された処理範囲を最下層の領域から順番に前記図形編集プロセスに対して処理範囲として指定し、下位階層の領域の処理がすべて終了するまで待機してから、上位階層の領域処理の割り当てを開始するステップと、
処理地物抽出部が、前記並列処理管理部によって割り当てられた処理範囲内に包含されており、かつ、編集処理が完了していない図形のみを前記電子地図データから抽出する内包判定機能を有するステップとを備え、
前記図形編集プロセスが、地図生成を行う際に必要な編集ステップと、図形編集に伴い必要となる編集後の図形の検査ステップおよび修正ステップとを備えたことを特徴とする表示方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、並列処理で高速に地図を編集して生成する地図生成装置およびその生成した地図を表示装置に表示させる表示方法に関するものである。
【背景技術】
【０００２】
従来の地図データ生成装置では、地図の図形を編集する頂点間引き処理部、編集した後に不適切な形状となっている図形を抽出し整形するポリゴン整形部、さらにポリゴン形状の不適切な部分を手動で修正するデフォルメ修正部を備えている（例えば特許文献１）。
【０００３】
地図の図形を編集する場合、編集後の図形が不適切な形状となっていないか検証を行い、不適切な形状と判断された場合には修正が必要となる。この不適切な形状の検証作業は、編集した図形に対する検証作業と、編集した図形と周辺に位置する図形との検証作業の２種類必要となる。編集した図形に対する検証作業では、当該図形を構成する辺の間で図形編集前にはなかった交差や接触が発生していないかを確認する。これを図形内のねじれ検証と呼ぶものとする。編集した図形と周辺に位置する図形との検証作業では、図形の位置関係や接続関係が変化していないかを確認する。例えば、編集前にはなかった図形間の接触、重なり、または編集前には接続していた図形間で接続が失われていないか等が挙げられる。これを周辺図形との位相関係の検証と呼ぶものとする。
【０００４】
地図データ生成装置において、図形編集処理の並列処理化を実現するためには、この周辺図形との位相関係の検証作業のために周辺図形を処理するプロセスとの同期が必要である。周辺図形との位相関係の検証作業中に、周辺図形が別のプロセスによって形状を変更されないようにするため、周辺図形のデータに対してデータロックを行う。一方で、データロック中の図形を編集しようとするプロセスは待機状態となるため、効率よく並列処理を実行できない。
【０００５】
また、従来の地図データ生成装置では、ネットワークで接続された複数のコンピュータの分散処理によって地図データ生成装置を構成してもよいとされているが、分散処理時の同期や処理の割り振り方法、処理手順については検討されていない。
【０００６】
並列処理において図形の簡略化を実現する方式として、３次元ポリゴンメッシュデータを対象としたものがある（例えば非特許文献１）。
非特許文献１において、３次元ポリゴンメッシュデータを複数のサーバで簡略化処理を実施するために、領域成長法の概念を用いた領域分けを実施している。この手法はポリゴンメッシュデータのような同じ形状の図形がすべて隙間なく接続され構成されている場合には容易に適用可能であるが、地図の図形の場合には適用が困難である。なぜならば、海の形状を示すポリゴンや大陸の形状を示すポリゴンのような巨大な図形から、川や公園、ビルのような小さなポリゴンが重なった構造となり、図形の位置関係および接続関係が複雑になっているためである。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００７−２５６４０２号公報
【非特許文献】
【０００８】
【非特許文献１】吉田安男, 今野晃市, 徳山喜政, “PCクラスタ環境のための3次元モデル軽量化手法の分散化”，芸術科学会論文誌 Vol.7, No.3 pp. 113-123
【発明の概要】
【発明が解決しようとする課題】
【０００９】
このような地図生成装置において、並列処理において効率よく図形編集処理を実施するためには、周辺図形との位相関係の検証作業のために必要となるプロセス間の同期を最小限にする必要がある。しかしながら、地図の図形は大小様々な図形が重なりあった構造をしているため、巨大な陸ポリゴンのような図形の周辺図形となれば、広範囲に影響を及ぼすことになる。また、並列処理では、図形編集処理を行う各プロセスに均一に処理を割り振ることが必要となる。しかし、地図の図形は位置関係や接続関係が複雑であり、部分的な図形の密集度も異なるため、領域分けが困難である。そのため、プロセス間の同期を考慮しながらもプロセスに仕事を均等に割り振るようにしなければならず、並列処理において効率よく図形編集処理を実施するのが難しいという課題がある。
【００１０】
この発明は、上記のような課題を解決するためになされたもので、並列処理において効率よく高速に図形編集処理を実施する地図生成装置およびその生成した地図を表示装置に表示させる表示方法を提供することを目的としている。
【課題を解決するための手段】
【００１１】
この発明に係る地図生成装置は、地形または地物の形状を表現する図形データが含まれた電子地図データから、図形の形状に関連する編集処理を行い新たな地図を生成する地図生成装置であって、複数の図形編集プロセスを起動させる図形編集処理部と、複数の階層の領域を定義する並列処理範囲定義部と、前記並列処理範囲定義部によって定義された処理範囲を最下層の領域から順番に前記図形編集プロセスに対して処理範囲として指定し、下位階層の領域の処理がすべて終了するまで待機してから、上位階層の領域処理の割り当てを開始する並列処理管理部と、前記並列処理管理部によって割り当てられた処理範囲内に包含されており、かつ、編集処理が完了していない図形のみを前記電子地図データから抽出する内包判定機能を有する処理地物抽出部とを備え、前記図形編集プロセスは、地図生成を行う際に必要な編集機能と、図形編集に伴い必要となる編集後の図形の検査機能および修正機能とを備えたことを特徴とするものである。
【発明の効果】
【００１２】
この発明によれば、並列処理において効率よく高速に図形編集処理を実施することができる。
【図面の簡単な説明】
【００１３】
【図１】この発明の実施の形態１に係る地図生成装置の構成を示すブロック図である。
【図２】この発明の実施の形態１に係る地図生成装置における図形編集処理のフローチャートである。
【図３】この発明の実施の形態１に係る地図生成装置における処理範囲の定義処理のフローチャートである。
【図４】この発明の実施の形態１に係る地図生成装置における処理範囲の定義方法を示す図である。
【図５】この発明の実施の形態１に係る地図生成装置が生成する地図を内包する領域の例を示す図である。
【図６】この発明の実施の形態１に係る地図生成装置が生成する地図を行政区域界に従ってポリゴン形状に分割・統合した例を示す図である。
【図７】kd-treeを利用した領域分割方法を示した例である。
【図８】kd-treeを利用して領域分割した結果を木構造で示した例である。
【図９】この発明の実施の形態１に係る地図生成装置における図形編集処理のフローチャートである。
【図１０】この発明の実施の形態２に係る地図生成装置の構成を示すブロック図である。
【図１１】この発明の実施の形態２に係る地図生成装置における図形編集処理の一部を示すフローチャートである。
【図１２】図４を木構造で示した図である。
【図１３】実施の形態３におけるナビゲーションシステムの概要を示す図である。
【発明を実施するための形態】
【００１４】
以下、この発明をより詳細に説明するために、この発明を実施するための形態について添付の図面に従って説明する。
実施の形態１．
図１は、この発明の実施の形態１に係る地図生成装置の構成を示すブロック図である。
地図生成装置は、地図生成を並列処理にて実施することが可能な演算処理部１と、道路形状や地形情報等を含む地図データを格納する記憶部２と、地形または地物の形状を表現する図形データが含まれた電子地図データの入力を受け付ける入力部３と、処理結果を表示や音声等により出力する出力部４で構成される。なお、出力部４は、処理結果をカーナビゲーション用フォーマットのような地図データに加工して出力してもよい。
地図生成装置は、演算処理部１において地図生成を行う。具体的には、入力部３から対象となる電子地図データを読み込み、記憶部２の地図ＤＢ５（後述）に格納する。そして、演算処理部１は、記憶部２の地図ＤＢ５に含まれる図形情報に対して地図生成に必要な図形の簡略化や回転、縮尺の変換等の図形の形状に関連する図形編集作業を実施し、新たな地図を生成する。
【００１５】
記憶部２は、地図ＤＢ５を備える。地図ＤＢ５には、地図上に道路名や地物名を表示するための文字や数字そしてその表示位置を含む注記情報６、地図上にアイコンを表示するために必要なＰＯＩ(Point Of Interest)情報７、経路探索や経路誘導に用いられる道路の接続関係を示す道路ネットワーク情報８、背景に描画される地物の図形情報である背景図形情報９、一方通行や通行時間帯の規制等が含まれる交通規制情報１０などの情報が格納されている。この地図ＤＢ５内に含まれる図形情報に対して地図生成に必要な様々な図形編集作業を実施する。
【００１６】
演算処理部１は、図形編集処理部１１、並列処理範囲定義部１３、並列処理管理部１４、処理地物抽出部１６を備える。
図形編集処理部１１は、地図生成を行う際に必要な図形編集処理を行う編集機能２０と、図形編集に伴い必要となる編集後の図形の検査機能２１および修正機能２２とを備えたＮ（１以上の自然数）個の図形編集プロセス１２を有し、この図形編集プロセス１２を起動させる。
【００１７】
並列処理範囲定義部１３は、図形編集処理部１１の図形編集プロセス１２への処理範囲の定義を行うため、編集する地図領域を内包する領域、または、内側に編集する地図領域を含み境界線のみ接している状態の領域を定義する最上位階層領域定義機能１７と、最上位階層領域定義機能１７によって定義された最上位階層領域を分割し最下位階層領域を定義する領域分割機能１８と、領域分割機能１８によって分割された領域を統合して上位階層の領域を定義する領域統合機能１９を備え、複数の階層の領域を定義する。
【００１８】
並列処理管理部１４は、図形編集処理部１１の図形編集プロセス１２に対して、並列処理範囲定義部１３によって定義された処理範囲を最下層の領域から順番に処理範囲として指定し、下位階層の領域の処理がすべて終了するまで待機してから、上位階層の領域処理の割り当てを開始させる。
処理地物抽出部１６は、並列処理管理部１４によって割り当てられた処理範囲内に包含されている図形のみを記憶部２の地図ＤＢ５から判定する内包判定機能１５を備え、この内包判定機能１５を用いて図形編集処理を適用する図形を抽出する。
【００１９】
図２は、この発明の実施の形態１に係る地図生成装置における図形編集処理のフローチャートである。
まず、演算処理部１は、並列処理範囲定義部１３を起動し、並列処理範囲定義部１３が、処理範囲の定義を行う（ステップＳＴ１）。
【００２０】
ここで、ステップＳＴ１の処理範囲の定義について、図３〜４を用いて説明する。
図３は、この発明の実施の形態１に係る地図生成装置における処理範囲の定義処理のフローチャートである。
図４（ａ）〜（ｃ）は、この発明の実施の形態１に係る地図生成装置における処理範囲の定義方法を示す図である。
まず、並列処理範囲定義部１３は、最上位階層領域定義機能１７を用いて、生成する地図を内包する領域Ａを定義する（ステップＳＴ２１）。
例えば、図４（ａ）に示すように、地図１０１を生成する場合、地図１０１に含まれる図形が包含されるように領域１０２を定義する。
【００２１】
地図に含まれる図形が包含される領域とは例えばどのようなものをいうかについて、図５を用いて説明する。
図５（ａ）（ｂ）は、この発明の実施の形態１に係る地図生成装置が生成する地図を内包する領域の例を示す図である。
例えば、図５（ａ）に示すように、図形２０１ａと図形２０１ｂからなる図形集合２０１が生成する地図だった場合、地図に含まれる図形が包含される領域とは、図形集合２０１に対して領域２０２のような状態にある領域のことをいう。つまり、図形集合２０１は、領域２０２の内部に位置し、図形集合２０１と領域２０２に接している部分がない状態を指す。
【００２２】
なお、図３のステップＳＴ２１では、生成する地図を内包する領域としているが、内包ではなく、図５（ｂ）に示すように、Ｌ字形領域２０３が図形集合２０１を内部に含み、境界線で接する状態にあってもよい。
【００２３】
次に、並列処理範囲定義部１３は、ステップＳＴ２１において定義された領域Ａを、領域分割機能１８を用いて任意の数に分割し、複数の領域集合Ｂを定義する（ステップＳＴ２２）。例えば、図４（ｂ）に示すように、領域１０２を面積に応じて複数に等分割し、領域１０３〜１０８の領域集合を定義する。ここで、図形編集処理部１１の各図形編集プロセス１２への仕事の割り当て効率をよくするため（処理については後述する）、図形編集プロセス１２のプロセス数よりは多くの領域に分割させることが望ましい。
【００２４】
並列処理範囲定義部１３は、領域統合機能１９を用いて、ステップＳＴ２２で分割した領域を複数集めて統合した領域を新たに定義する（ステップＳＴ２３）。
例えば、図４（ｃ）に示すように、図４（ｂ）の領域１０３と領域１０４を統合し、領域１０９を新たに定義する。同様に、領域１０６と領域１０７を統合して領域１１０を新たに定義し、領域１０５と領域１０８を統合して領域１１１を新たに定義する。なお、図４の例では、領域を２つずつ統合しているが、２つに限るものではなく、２個以上の領域の統合を行えばよい。また、統合する際は、共通する辺を持つもの、共通する点を持つもの、共通点を持たないものの順に優先的に統合する。
【００２５】
次に並列処理範囲定義部１３は、ステップＳＴ２３において統合された領域が元の領域Ａになったかを判定する（ステップＳＴ２４）。元の領域Ａになっていないと判断された場合（ステップＳＴ２４の“ＮＯ”の場合）は、ステップＳＴ２３へ戻り、元の領域Ａになったと判断された場合（ステップＳＴ２４の“ＹＥＳ”の場合）は、処理を終了する。
このように、ステップＳＴ２３の統合処理は、ステップＳＴ２２で分割された領域が全て統合され、分割前のステップＳＴ２１における領域Ａの形状に戻るまで繰り返される。
例えば、図４（ｃ）に示す領域１０９〜領域１１１を全て統合すると、領域１０２となり、処理範囲の定義処理を終了する。
【００２６】
ステップＳＴ２２で定義される領域集合を第１階層と呼ぶ。統合を行い新たな領域集合とするたびに第２階層、第３階層と呼び、ステップＳＴ２１で定義された領域Ａが最上位階層となる。つまり、数字が大きい方が上位階層となる。図４の例では、領域１０３〜領域１０８が第１階層、領域１０９〜領域１１１が第２階層、領域１０２が第３階層であり最上位階層となる。
統合処理は、上層階層の領域を定義するために行うものである。従って、上位階層の領域は下位階層の領域より大きな領域となる必要がある。そこで、下位階層の領域を複数統合して上位階層の領域を定義するようにすれば、かならず下位階層より大きな領域を定義することが可能である。
【００２７】
なお、図４では、領域の形状は長方形による等分割となっているが、これに限定するものではない。例えば、行政区域界を示すポリゴン形状としてもよい。
図６は、この発明の実施の形態１に係る地図生成装置が生成する地図を行政区域界に従ってポリゴン形状に分割・統合した例を示す図である。
図６の場合、最上位階層を図６（ａ）の領域１１２のように国ポリゴンとし、第１階層を図６（ｂ）の領域１１３のような行政区域界を示すポリゴンとする。第１階層から上位の階層に行くにつれて１つ上位の行政区域界を示すポリゴンになるように領域統合をしていく。日本の行政区域界で例をあげると、第１階層は市町村の領域ポリゴン、第２階層を都道府県の領域ポリゴン、最上位階層を日本の国を示す領域ポリゴンのように統合していく。
【００２８】
また、最上位階層の領域を分割する際に、図形を構成する頂点を抽出し、各領域に含まれる頂点数が同じになるように分割してもよい。その場合、kd-treeを利用することができる。kd-treeとは空間分割データ構造の一つである。
図７は、kd-treeを利用した領域分割方法を示した例である。
図７は、２次元の場合のkd-treeによる領域分割方法を示している。図７（ａ）に示すように、領域４０１を最上位階層の領域とする。領域４０１の内部にある点は頂点を表している。kd-treeでは、座標軸の１つに垂直な平面を使って分割を行う。２次元の場合は、Ｘ軸に関して垂直な平面で分割、Ｙ軸に関して垂直な平面で分割、これを交互に繰り返す。３次元の場合は、Ｘ軸、Ｙ軸、Ｚ軸という３軸に関してを順番に繰り返すことになる。平衡kd-treeとなるように分割する軸に関して内部に含まれている頂点の座標値の中央値で分割を行う。
【００２９】
図７（ａ）の領域４０１に関して分割を行ったものが、図７（ｂ）に示す領域４０２〜４０３である。同様にして、図７（ｂ）に示す領域４０２〜４０３を分割したものが図７（ｃ）に示す領域４０４〜領域４０７である。さらに、図７（ｃ）に示す領域４０４〜４０７を分割したものが、図７（ｄ）に示す領域４０８〜領域４１５である。図７の例では、頂点が領域に１つになるまで繰り返したが、領域内に複数個の図形の構成点が含まれている状態で終了してもよい。また、平衡kd-treeとなるように２分割を繰り返したが、深さが同じ木構造となればよいので、３分割、４分割としてもよい。
【００３０】
図８は、kd-treeを利用して領域分割した結果を木構造で示した例である。
図７（ａ）〜（ｄ）の分割の結果得られたkd-treeを図８の木構造５０１に示す。
ノードに記した番号は、図７（ａ）〜（ｄ）の領域４０１〜領域４１５の番号に対応している。葉ノードが最下位階層の領域となる。統合時には、子ノードの指す領域を統合して親ノードの指す領域が上位階層の領域となる。頂点座標の中央値での分割でkd-treeを作成する以外にも、領域に完全に含まれる図形の数や領域に完全に含まれる図形を構成する頂点数、領域に完全に含まれる図形のジオメトリデータのサイズを等しくなるように領域を分割する方法もある。
【００３１】
図２のフローチャートにもどる。
ステップＳＴ１で並列処理範囲定義部１３が処理範囲の定義を行うと、次に、演算処理部１は並列処理管理部１４を起動させる（ステップＳＴ２）。
さらに、演算処理部１は、図形編集処理部１１によって任意の数の図形編集プロセス１２を起動させる（ステップＳＴ３）。起動された図形編集プロセス１２は待機状態となる。
【００３２】
次に、並列処理管理部１４が、階層の数ｉの初期値化を行う（ステップＳＴ４）。具体的には、ｉ＝０とする。
並列処理管理部１４は、ｉをインクリメントし（ステップＳＴ５）、第ｉ階層内の、編集処理をしていない領域を記憶部２から読み込む（ステップＳＴ６）。
なお、この時点で、並列処理管理部１４は、第ｉ階層内にいくつの領域があるかを把握している。
次に、並列処理管理部１４は、待機状態の図形編集プロセス１２があるかをチェックし（ステップＳＴ７）、待機状態の図形編集プロセス１２があれば（ステップＳＴ７の“ＹＥＳ”の場合）、まだ割り当てられていない領域があるかを判定する（ステップＳＴ８）。待機状態の図形編集プロセス１２がない場合（ステップＳＴ７の“ＮＯ”の場合）は、ステップＳＴ７を繰り返す。
ステップＳＴ８において、まだ割り当てられていない領域がある場合（ステップＳＴ８の“ＹＥＳ”の場合）、並列処理管理部１４は、まだ割り当てられていない領域の割り当てを行う（ステップＳＴ９）。
ステップＳＴ８において、まだ割り当てられていない領域がないと判定された場合（ステップＳＴ８の“ＮＯ”の場合）は、ステップＳＴ９の処理はスキップされる。
このように、並列処理管理部１４は、定期的に待機状態の編集プロセス１２がないかどうかをチェックしており、このタイミングでその都度領域の割り当てを行っている。
【００３３】
ステップＳＴ９において、図形編集プロセス１２に担当する領域が割り当てられると、図形編集処理部１１が、図形編集プロセス１２に割り当てられた領域の図形編集処理を実施させる。なお、この図形編集処理において、図形編集プロセス１２は、領域内の図形のうち、図形編集できた図形毎に処理完了フラグを立てる。領域の境界に位置するものや、領域を跨ぐもので、図形編集できなかった図形に対しては処理完了フラグを立てない。（図形編集処理については後述する）
並列処理管理部１４は、図形編集プロセス１２の図形編集処理を監視しており、図形編集プロセス１２が第ｉ階層内の全ての領域の図形編集処理を終了したか、つまり、同一階層内の全ての領域の図形編集処理が終了したかを判断する（ステップＳＴ１０）。
第ｉ階層内の全ての図形編集処理が終了していない場合（ステップＳＴ１０の“ＮＯ”の場合）、ステップＳＴ７に戻る。つまり、並列処理管理部１４は、待機状態の図形編集プロセス１２に未処理の領域を割り当てるようにする。このように、並列処理管理部１４は、同一階層内の全ての領域の図形編集処理が終了するまで待機する。
【００３４】
一方、同一階層内の全ての領域が割り当てられ、図形編集処理が終了した場合（ステップＳＴ１０の“ＹＥＳ”の場合）、並列処理管理部１４は、第ｉ階層は最上位階層であるかどうかを判断する（ステップＳＴ１１）。つまり、全ての階層に含まれている領域の図形編集処理を行ったかどうかを判断する。
第ｉ階層は最上位階層ではないと判断された場合（ステップＳＴ１１の“ＮＯ”の場合）、ステップＳＴ５の処理に戻る。つまり、ｉをインクリメントし、一つ上位の階層に含まれる領域の図形編集処理を実施する。
【００３５】
第ｉ階層は最上位階層であると判断された場合（ステップＳＴ１１の“ＹＥＳ”の場合）、並列処理管理部１４は、処理完了フラグが立っていない図形があるかどうかを調べる（ステップＳＴ１２）。
処理完了フラグが立っていない図形がないと判断された場合（ステップＳＴ１２の“ＮＯ”の場合）、処理は終了する。
【００３６】
処理完了フラグが立っていない図形があると判断された場合（ステップＳＴ１２の“ＹＥＳ”の場合）、１つの図形編集プロセス１２に単独で処理させる（ステップＳＴ１３）。これは、例えば、図５（ｂ）の領域２０３のように定義した場合に、この領域２０３と境界線が一致する図形２０１ａ，２０１ｂが処理されずに残っているため、全ての図形に対する処理を完了させるためである。
このように、並列処理管理部１４は、まず領域を１つずつ各編集プロセス１２に割り当てて、処理が早く完了した編集プロセス１２から次の領域の担当をまかせるように動作する。これは、各領域の仕事量にばらつきがあった場合に、特定の編集プロセスに仕事量が大きな領域が複数割り当てられ、他の編集プロセス１２は早くに図形編集処理を完了し、処理待ち状態に入っているという状態を発生させないためである。
【００３７】
図９は、この発明の実施の形態１に係る地図生成装置における図形編集処理のフローチャートである。
図２のステップＳＴ９で図形編集プロセス１２に担当する領域が割り当てられると、形編集処理部１１で図形編集処理が行われる。ここでは図形編集処理について、図９を用いて詳細に説明する。
図形編集処理は、図形編集処理部１１の図形編集プロセス１２が行う。
なお、図２で説明した並列処理管理部１４の処理と、ここで説明する図形編集プロセス１２による図形編集処理は別のプロセスもしくは別のスレッドにて並列動作している。
図形編集プロセス１２は、並列処理管理部１４によって仕事を割り当てられていない時は、待機状態となっている（ステップＳＴ１０１）。
並列処理管理部１４によって仕事が割り当てられると、図形編集プロセス１２は、処理地物抽出部１６に、編集対象の図形のみ、具体的には、担当領域内に完全に含まれており、かつ、図形編集処理が完了していない図形のみを抽出するよう指示する（ステップＳＴ１０２）。つまり、領域の境界に位置するものや、領域を跨ぐもの等は図形編集処理の対象とはならない。
【００３８】
ステップＳＴ１０２において処理地物抽出部１６が抽出した図形それぞれに対して、図形編集プロセス１２は、図形編集処理を実施する（ステップＳＴ１０３）。
具体的には、図形編集プロセス１２は、編集機能２０を用いて編集を実施し、編集後の図形に対して検査機能２１を用いて図形内のねじれ検証と周辺図形との位相関係の検証を実施する。問題がある場合には、修正機能２２を用いて適切な形状へと変換する。
【００３９】
次に、図形編集プロセス１２は、処理が完了した図形に対して処理完了フラグを立て、処理が完了した図形と完了していない図形を区別できるようにする（ステップＳＴ１０４）。
図形編集プロセス１２は、ステップＳＴ１０２で処理地物抽出部１６が抽出した全ての図形に対して図形編集処理を行ったかどうかを判断し（ステップＳＴ１０５）、全ての図形に対して図形編集完了と判断された場合（ステップＳＴ１０５の“ＹＥＳ”の場合）、処理を終了し、図形編集プロセス１２は待機状態に戻る。
全ての図形に対して図形編集完了と判断されなかった場合（ステップＳＴ１０５の“ＮＯ”の場合）、ステップＳＴ１０３に戻り、処理が完了していない図形に対して図形編集処理を行う。
【００４０】
以上のように、生成する地図を内包する領域を定義する最上位階層領域定義機能１７と、定義された領域を分割する領域分割機能１８と、定義された領域を統合する領域統合機能１９を有し、階層的な処理範囲を定義する並列処理範囲定義部１３を備えたことにより、任意の大きさの処理領域を定義することができ、さらに複数に階層化された処理範囲の定義が可能になる。
【００４１】
また、並列処理範囲定義部１３によって定義された各階層の処理範囲に対して、内包判定機能１５を有する処理地物抽出部１６を備えることで、処理範囲の領域に完全に含まれるものについて各図形編集プロセスが図形編集処理することができる。処理範囲の領域の境界に位置する図形は、当該階層のどの処理範囲領域に対しても完全に含まれることがないため、図形編集処理が実施されない。そのため、周辺図形との位相関係の検証作業でも、周辺図形が別の図形編集プロセス１２によって形状が変更されず、図形編集プロセス１２間で同期をとらずに処理を進めることができる。上位階層では、下位階層の処理範囲の領域を統合した領域が定義されているため、下位階層では領域に完全に含まれなかった図形に対しても処理対象の図形として抽出されるものが出てくる。
【００４２】
また、長方形による等分割では、分割数の調整が容易である。よって、分割処理が単純なアルゴリズムで高速に処理を完了することが可能である。また、行政区域界を利用した分割では、地図データに含まれている行政区域界のポリゴンを利用することができる。行政区域界の階層関係にあるポリゴンを利用することで、新たに並列処理範囲の定義用領域ポリゴンを定義して管理することが不要となる。
【００４３】
さらに、領域の分割時に図形を構成する頂点、領域に完全に含まれる図形の数、領域に完全に含まれる図形を構成する頂点数、領域に完全に含まれる図形のジオメトリデータのサイズ等に着目してkd-treeを構築する方法では、統合時にもkd-treeを利用することで、各階層の領域において仕事量の均一化を図ることが可能になる。つまり、階層毎の各領域の図形編集処理時間が等しくなるため、効率よく並列処理を行うことができ、単一の編集プロセスのみが仕事を抱え、別の編集プロセスは仕事がなく待機しているという状態を回避できる
【００４４】
なお、この実施の形態では、演算処理部１、記憶部２、入力部３、出力部４は地図生成装置がもつものとしたが、これに限らず、地図生成装置は、演算処理部１のみを備えるものとしてもよい。
【００４５】
以上のように、この実施の形態１に係る地図生成装置では、階層化された処理範囲の定義によって、各階層でプロセスが処理を実行する際には同期処理が不要となり、効率よく高速に図形編集処理を実施することができる。
また、任意の大きさの領域を指定できることから、小さく切り出せば各図形編集プロセスの仕事量の均一化を図ることができる。
【００４６】
実施の形態２．
図１０は、この発明の実施の形態２に係る地図生成装置の構成を示すブロック図である。
なお、図１で説明したものと同様の構成については、重複した説明を省略する。図１に示した地図生成装置とは、並列処理管理部１４が、処理可能範囲判定機能２３をさらに備えた点のみが異なる。
処理可能範囲判定機能２３は、並列処理範囲定義部１３が定義する階層化された処理範囲領域を木構造で管理している。つまり、どの下位階層の領域を統合したものがどの上位の階層の領域となっているのか対応関係を管理している。
【００４７】
この実施の形態２では、図２のステップＳＴ１〜ステップＳＴ３と同様の処理をした後、並列処理管理部１４は、待機状態の図形編集プロセス１２に、処理可能フラグが立っている領域を割り当てる。
その後、各図形編集プロセス１２は、担当する領域の図形編集処理を行う。
図１１は、この発明の実施の形態２に係る地図生成装置における図形編集処理の一部を示すフローチャートである。
並列処理管理部１４によって、各図形編集プロセス１２に領域が割り当てられた後の処理を、図１１を用いて説明する。
まず、図形編集処理部１１は、図形編集プロセス１２に、図形編集処理を行わせる（ステップＳＴ３１）。なお、このステップＳＴ３１の図形編集処理は、実施の形態１の図２のステップＳＴ８と同様であるので詳細な説明を省略する。
【００４８】
次に、図形編集プロセス１２は、処理可能フラグをＯＦＦする（ステップＳＴ３２）。
並列処理管理部１４の処理可能範囲判定機能２３は、木構造で管理している階層化された処理範囲領域に基づき、親ノードが存在するかどうかを調べる（ステップＳＴ３３）。
ステップＳＴ３３において、親ノードが存在しないと判断された場合（ステップＳＴ３３の“ＮＯ”の場合）、つまり、最上位階層の領域であると判断された場合、処理終了する。
【００４９】
一方、ステップＳＴ３３において、親ノードが存在すると判断された場合（ステップＳＴ３３の“ＹＥＳ”の場合）、処理可能範囲判定機能２３は、同一の親ノードの下に存在する同一の深さの子ノード全ての図形編集処理が完了しているかどうかを調べる（ステップＳＴ３４）。つまり、同一の上位階層の領域を持つ下位階層の全ての領域の図形編集処理が完了しているかどうかを調べる。具体的には、全ての下位階層の領域の処理可能フラグがオフになっているかどうかを調べる。
【００５０】
ステップＳＴ３４において、同一深さの子ノード全ての図形編集処理が完了していると判断されなかった場合（ステップＳＴ３４の“ＮＯ”の場合）、処理可能範囲判定機能２３は、待機状態となる。つまり、同一の上位階層の領域の下に存在する全ての下位階層の領域の図形編集処理が完了するまで待機する。
一方、ステップＳＴ３３において、同一深さの子ノード全ての図形編集処理が完了していると判断された場合（ステップＳＴ３５の“ＹＥＳ”の場合）、処理可能範囲判定機能２３は、親ノード、つまり、一つ上位の階層の領域の処理可能フラグを立て（ステップＳＴ３５）、終了する。
その後、並列処理管理部１４は再び、待機状態の図形編集プロセス１２に、処理可能フラグが立っている領域を割り当てる。
【００５１】
図１１の処理を、図１２を用いて説明する。
図１２は、図４の例を木構造で示した図である。
図１２（ａ）に示すように、処理可能範囲判定機能２３は、木構造３０１を作成し、処理開始時には、ノード３０２のように、葉ノードには処理可能フラグが立っている。なお、ノード内に書かれている番号は、図４の領域番号に対応し、ノードの線は処理可能フラグが立っていることを表している。
図１２（ｂ）に示すように、領域１０９の全ての子ノードである領域１０３，１０４の図形編集処理が完了すると、領域１０９に処理可能フラグが立てられ、領域１０９の図形編集処理を開始する。
【００５２】
このように、この実施の形態２では、並列処理管理部１４に処理可能範囲判定機能２３を備え、処理可能範囲判定機能２３が木構造で処理範囲領域を管理することによって、親ノードは、自身の子ノードの図形編集処理が完了すれば、他の親ノードに属する子ノードの図形編集処理が完了するのを待たずに自身の図形編集処理を開始させるようになる。つまり、上位層の領域は、自身の一つ下の層に含まれる全て領域の図形編集処理が終了すると、図形編集処理を行うことができる。
【００５３】
なお、この実施の形態では、演算処理部１、記憶部２、入力部３、出力部４は地図生成装置がもつものとしたが、これに限らず、地図生成装置は、演算処理部１のみを備えるものとしてもよい。
【００５４】
以上のように、この実施の形態２に係る地図生成装置では、各階層間で必要な同期処理も最小限に抑えることが可能となり、図形編集処理を高速に行うことが可能となる。
【００５５】
なお、図１，図１０で示した出力部４を表示機能を備える表示部とし、入力部３が、表示部に表示する範囲や縮尺、表示する地物の種類等の入力を受け付けるようにして、入力部３から指定された地図領域に対して図形編集処理を実施し、生成された地図を表示部に表示するようにすることもできる。
つまり、カーナビゲーションシステムによる地図表示に用いることも可能である。
【００５６】
実施の形態３．
以上の実施の形態１，２では、この発明における地図生成装置を、カーナビゲーションシステムに適用してもよい旨説明したが、適用するのはカーナビゲーションシステムのナビゲーション装置に限らず、人、車両、鉄道、船舶または航空機等を含む移動体用のナビゲーション装置であってもよいし、ナビゲーションシステムのサーバに適用してもよい。また、スマートフォン、タブレットＰＣ、携帯電話等の携帯情報端末等にインストールされるナビゲーションシステムのアプリケーション等、どのような形態のものにも適用することができる。
【００５７】
図１３は、この発明の実施の形態３におけるナビゲーションシステムの概要を示す図である。このナビゲーションシステムは、車載装置５００が、スマートフォンなどの携帯情報端末５０１およびサーバ５０２の少なくとも一方と連携して地図生成処理およびナビゲーション処理を行ったり、スマートフォンなどの携帯情報端末５０１およびサーバ５０２の少なくとも一方が地図生成処理およびナビゲーション処理を行い、車載装置５００に地図情報を表示させる等、様々な形態をとることができる。以下、当該ナビゲーションシステムの構成態様について説明する。
【００５８】
実施の形態１，２における地図生成装置の機能を、図１３に示す車載装置５００がすべて備える場合以外に、この実施の形態３におけるナビゲーションシステムでは、サーバ５０２が地図生成処理を行い、その地図生成結果を車載装置５００に表示させることによりユーザに提供する場合、および、携帯情報端末５０１がサーバ５０２と連携して地図生成処理を行い、その地図生成結果を車載装置５００に表示させることによりユーザに提供する場合について説明する。
【００５９】
まず、サーバ５０２が地図生成処理を行い、その地図生成結果を車載装置５００に表示させる場合、すなわち、地図生成機能を有するサーバ５０２と連携して、車載装置５００が表示装置として機能する場合について説明する。
この構成においては、車載装置５００がサーバ５０２と直接通信するか、または、車載装置５００が携帯情報端末５０１を経由してサーバ５０２と通信する場合が考えられる。サーバ５０２は、上記実施の形態１，２で説明した演算処理部１を備えた地図生成装置として機能する。また、車載装置５００は、サーバ５０２による地図生成結果をユーザに提供するための出力部４（表示機能を有する出力部）を少なくとも備える表示装置として機能する。
【００６０】
この場合、車載装置５００は基本的に通信機能および表示機能のみを有し、サーバ５０２による地図生成結果を受信してユーザに提供する。
すなわち、サーバ５０２が演算処理部１を備える地図生成装置であり、この地図生成装置であるサーバ５０２が、生成した地図生成結果を表示装置である車載装置５００に表示させる。
このように構成しても、実施の形態１，２と同様な効果を得ることができる。
【００６１】
また、携帯情報端末５０１がサーバ５０２と連携して地図生成処理を行い、その地図生成結果を車載装置５００がユーザに提供する場合について説明する。
この構成においては、車載装置５００が携帯情報端末５０１を経由してサーバ５０２と通信する場合が考えられ、携帯情報端末５０１のアプリケーションが、サーバ５０２と連携して地図生成処理を行う。また、車載装置５００は、携帯情報端末５０１とサーバ５０２による地図生成結果をユーザに提供するための出力部４（表示機能を有する出力部）を少なくとも備える表示装置として機能する。
【００６２】
この場合にも、車載装置５００は基本的に通信機能および表示機能のみを有し、携帯情報端末５０１とサーバ５０２との連携による地図生成結果を受信してユーザに提供する。
すなわち、携帯情報端末５０１のアプリケーションにより、生成した地図生成結果を表示装置である車載装置５００に表示させる。
このように構成しても、実施の形態１，２と同様な効果を得ることができる。
【００６３】
なお、本願発明はその発明の範囲内において、各実施の形態の自由な組み合わせ、あるいは各実施の形態の任意の構成要素の変形、もしくは各実施の形態において任意の構成要素の省略が可能である。
【符号の説明】
【００６４】
１  演算処理部、２  記憶部、３  入力部、４  出力部、５  地図ＤＢ、６  注記情報、７  ＰＯＩ情報、８  道路ネットワーク情報、９  背景図形情報、１０  交通規制情報、１１  図形編集処理部、１２  図形編集プロセス、１３  並列処理範囲定義部、１４  並列処理管理部、１５  内包判定機能、１６  処理地物抽出部、１７  最上位階層領域定義機能、１８  領域分割機能、１９  領域統合機能、２０  編集機能、２１  検査機能、２２  修正機能、２３  処理可能範囲判定機能、５００  車載装置、５０１  携帯情報端末、５０２  サーバ。
【図１】
2014153824.tif 000003
【図２】
2014153824.tif 000004
【図３】
2014153824.tif 000005
【図４】
2014153824.tif 000006
【図５】
2014153824.tif 000007
【図６】
2014153824.tif 000008
【図７】
2014153824.tif 000009
【図８】
2014153824.tif 000010
【図９】
2014153824.tif 000011
【図１０】
2014153824.tif 000012
【図１１】
2014153824.tif 000013
【図１２】
2014153824.tif 000014
【図１３】
2014153824.tif 000015