(57)【要約】【課題】  本発明は、ラインから内点のデータを簡単に間引き得る地図データを作成する地図データ作成装置、該方法、該プログラム及び記録媒体並びに地図出力装置を提供する。【解決手段】  本発明の二分木地図データ作成出力装置１は、被分割ラインにおける始点及び終点の各座標値と、この被分割ラインの始点及び終点の間におけるこの被分割ライン上に在る内点の離間度のうちの最大の離間度と、この被分割ラインとこの該被分割ラインから生成された第１及び第２分割ラインとの対応関係である親子関係を表す親子関係情報とを対応付けて備える二分木地図データを作成する。【選択図】      図１
2006195172.tif 000002
【特許請求の範囲】
【請求項１】
被分割ラインにおける始点及び終点の各座標値と、該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点の離間度のうちの最大の離間度と、該被分割ラインと該被分割ラインから生成された第１及び第２分割ラインとの対応関係である親子関係を表す親子関係情報とを対応付けて備え、
前記離間度は、被分割ラインの始点及び終点の間における該被分割ライン上に在る内点が該被分割ラインの始点及び終点を結ぶ線分からどれだけ離れているかを表す尺度であって、
前記第１及び第２分割ラインは、最大の離間度を持つ内点で被分割ラインを２個に分割することによって生成され、
前記被分割ラインは、始点及び終点の各座標値と該始点及び終点の間における当該線上に在る内点の座標値とを備える地図上に線で表され得るラインと、第１及び第２分割ラインのうちの内点を持たない分割ラインを除く分割ラインとである二分木地図データを作成する二分木地図データ作成装置。
【請求項２】
被分割ラインにおける始点及び終点の各座標値と、親離間度として該被分割ラインを生成する際に用いられた離間度と、子離間度として該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点の離間度のうちの最大の離間度とを対応付けて備え、
前記離間度は、被分割ラインの始点及び終点の間における該被分割ライン上に在る内点が該被分割ラインの始点及び終点を結ぶ線分からどれだけ離れているかを表す尺度であって、
前記被分割ラインは、始点及び終点の各座標値と該始点及び終点の間における該線上に在る内点の座標値とを備える地図上に線で表され得るラインと、最大の離間度を持つ内点で被分割ラインを２個に分割することによって生成される総ての第１及び第２分割ラインであって、
前記親離間度及び子離間度は、被分割ラインと該被分割ラインから生成された第１及び第２分割ラインとの対応関係を親子関係とした場合に、前記ラインから内点を持たない分割ラインまでの親から子孫まで被分割ラインを第１及び第２分割ラインに分割する際に用いた離間度を順次に辿った場合に、当該分割する際の離間度を含め子孫側の離間度のうちの最大値で置き換えた値である二分木地図データを作成する二分木地図データ作成装置。
【請求項３】
始点及び終点の各座標値と該始点及び終点の間における該線上に在る内点の座標値とを備え地図上に線で表されるラインの地図データを二分木地図データに変換する二分木地図データ作成装置において、
被分割ラインにおける始点及び終点を結ぶ線分から該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点がどれだけ離れているかを表す尺度である離間度を演算する離間度演算部と、
前記離間度演算部で演算した離間度のうちの最大の離間度を持つ内点で前記被分割ラインを２個の第１及び第２分割ラインに分割する被分割ライン分割処理部と、
前記ラインを最初の被分割ラインとすると共に前記被分割ライン分割処理部で分割することによって生成された分割ラインを新たな被分割ラインとすることで、分割ラインに内点が無くなるまで順次に前記ラインを分割するライン分割処理部と、
前記ライン分割処理部で被分割ラインとされた前記ライン及び分割ラインにおける始点及び終点の各座標値と、前記被分割ライン分割処理部で前記被分割ラインを分割する際に用いた前記最大の離間度と、前記被分割ライン分割処理部で生成された第１及び第２分割ラインと前記被分割ラインとの対応関係である親子関係を表す親子関係情報とを対応付けて備える前記二分木地図データを作成する作成処理部とを備えること
を特徴とする二分木地図データ作成装置。
【請求項４】
請求項３に記載の二分木地図データ作成装置において、
前記被分割ライン分割処理部で前記被分割ラインを分割する際に用いた前記最大の離間度を子離間度とすると共に前記被分割ラインを生成する際に用いられた離間度を親離間度として、前記親離間度及び子離間度を、前記ラインから前記内点を持たない分割ラインまでの親から子孫まで前記被分割ラインを前記第１及び第２分割ラインに分割する際に用いた離間度を順次に辿った場合に、当該分割する際の離間度を含め子孫側の離間度のうちの最大値で置き換える置換処理部をさらに備え、
前記作成処理部は、前記ライン及び総ての分割ラインにおける始点及び終点の各座標値と、前記置換処理部で処理された親離間度と、前記置換処理部で処理された子離間度とを対応付けて備える前記二分木地図データを作成すること
を特徴とする二分木地図データ作成装置。
【請求項５】
始点及び終点の各座標値と該始点及び終点の間における該線上に在る内点の座標値とを備え地図上に線で表されるラインの地図データを二分木地図データに変換する二分木地図データ作成方法において、
被分割ラインにおける始点及び終点を結ぶ線分から該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点がどれだけ離れているかを表す尺度である離間度を演算する離間度演算ステップと、
前記離間度演算ステップで演算した離間度のうちの最大の離間度を持つ内点で前記被分割ラインを２個の第１及び第２分割ラインに分割する被分割ライン分割処理ステップと、
前記ラインを最初の被分割ラインとすると共に前記被分割ライン分割処理ステップで分割することによって生成された分割ラインを新たな被分割ラインとすることで、分割ラインに内点が無くなるまで順次に前記ラインを分割するライン分割処理ステップと、
前記ライン分割処理ステップで被分割ラインとされた前記ライン及び分割ラインにおける始点及び終点の各座標値と、前記被分割ライン分割処理ステップで前記被分割ラインを分割する際に用いた前記最大の離間度と、前記被分割ライン分割処理ステップで生成された第１及び第２分割ラインと前記被分割ラインとの対応関係である親子関係を表す親子関係情報とを対応付けて備える前記二分木地図データを作成する作成処理ステップとを備えること
を特徴とする二分木地図データ作成方法。
【請求項６】
請求項５に記載の二分木地図データ作成方法において、
前記被分割ライン分割処理ステップで前記被分割ラインを分割する際に用いた前記最大の離間度を子離間度とすると共に前記被分割ラインを生成する際に用いられた離間度を親離間度として、前記親離間度及び子離間度を、前記ラインから前記内点を持たない分割ラインまでの親から子孫まで前記被分割ラインを前記第１及び第２分割ラインに分割する際に用いた離間度を順次に辿った場合に、当該分割する際の離間度を含め子孫側の離間度のうちの最大値で置き換える置換処理ステップをさらに備え、
前記作成処理ステップは、前記ライン及び総ての分割ラインにおける始点及び終点の各座標値と、前記置換処理ステップで処理された親離間度と、前記置換処理ステップで処理された子離間度とを対応付けて備える前記二分木地図データを作成すること
を特徴とする二分木地図データ作成方法。
【請求項７】
始点及び終点の各座標値と該始点及び終点の間における該線上に在る内点の座標値とを備え地図上に線で表されるラインの地図データを二分木地図データに変換する、コンピュータに実行させるための二分木地図データ作成プログラムにおいて、
被分割ラインにおける始点及び終点を結ぶ線分から該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点がどれだけ離れているかを表す尺度である離間度を演算する離間度演算ステップと、
前記離間度演算ステップで演算した離間度のうちの最大の離間度を持つ内点で前記被分割ラインを２個の第１及び第２分割ラインに分割する被分割ライン分割処理ステップと、
前記ラインを最初の被分割ラインとすると共に前記被分割ライン分割処理ステップで分割することによって生成された分割ラインを新たな被分割ラインとすることで、分割ラインに内点が無くなるまで順次に前記ラインを分割するライン分割処理ステップと、
前記ライン分割処理ステップで被分割ラインとされた前記ライン及び分割ラインにおける始点及び終点の各座標値と、前記被分割ライン分割処理ステップで前記被分割ラインを分割する際に用いた前記最大の離間度と、前記被分割ライン分割処理ステップで生成された第１及び第２分割ラインと前記被分割ラインとの対応関係である親子関係を表す親子関係情報とを対応付けて備える前記二分木地図データを作成する作成処理ステップとを備えること
を特徴とする二分木地図データ作成プログラム。
【請求項８】
請求項７に記載の二分木地図データ作成プログラムにおいて、
前記被分割ライン分割処理ステップで前記被分割ラインを分割する際に用いた前記最大の離間度を子離間度とすると共に前記被分割ラインを生成する際に用いられた離間度を親離間度として、前記親離間度及び子離間度を、前記ラインから前記内点を持たない分割ラインまでの親から子孫まで前記被分割ラインを前記第１及び第２分割ラインに分割する際に用いた離間度を順次に辿った場合に、当該分割する際の離間度を含め子孫側の離間度のうちの最大値で置き換える置換処理ステップをさらに備え、
前記作成処理ステップは、前記ライン及び総ての分割ラインにおける始点及び終点の各座標値と、前記置換処理ステップで処理された親離間度と、前記置換処理ステップで処理された子離間度とを対応付けて備える前記二分木地図データを作成すること
を特徴とする二分木地図データ作成プログラム。
【請求項９】
始点及び終点の各座標値と該始点及び終点の間における該線上に在る内点の座標値とを備え地図上に線で表されるラインの地図データを二分木地図データに変換する、コンピュータに実行させるための二分木地図データ作成プログラムを記録した記録媒体において、
前記二分木地図データ作成プログラムは、
被分割ラインにおける始点及び終点を結ぶ線分から該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点がどれだけ離れているかを表す尺度である離間度を演算する離間度演算ステップと、
前記離間度演算ステップで演算した離間度のうちの最大の離間度を持つ内点で前記被分割ラインを２個の第１及び第２分割ラインに分割する被分割ライン分割処理ステップと、
前記ラインを最初の被分割ラインとすると共に前記被分割ライン分割処理ステップで分割することによって生成された分割ラインを新たな被分割ラインとすることで、分割ラインに内点が無くなるまで順次に前記ラインを分割するライン分割処理ステップと、
前記ライン分割処理ステップで被分割ラインとされた前記ライン及び分割ラインにおける始点及び終点の各座標値と、前記被分割ライン分割処理ステップで前記被分割ラインを分割する際に用いた前記最大の離間度と、前記被分割ライン分割処理ステップで生成された第１及び第２分割ラインと前記被分割ラインとの対応関係である親子関係を表す親子関係情報とを対応付けて備える前記二分木地図データを作成する作成処理ステップとを備えること
を特徴とする記録媒体。
【請求項１０】
請求項９に記載の記録媒体において、
前記被分割ライン分割処理ステップで前記被分割ラインを分割する際に用いた前記最大の離間度を子離間度とすると共に前記被分割ラインを生成する際に用いられた離間度を親離間度として、前記親離間度及び子離間度を、前記ラインから前記内点を持たない分割ラインまでの親から子孫まで前記被分割ラインを前記第１及び第２分割ラインに分割する際に用いた離間度を順次に辿った場合に、当該分割する際の離間度を含め子孫側の離間度のうちの最大値で置き換える置換処理ステップをさらに備え、
前記作成処理ステップは、前記ライン及び総ての分割ラインにおける始点及び終点の各座標値と、前記置換処理ステップで処理された親離間度と、前記置換処理ステップで処理された子離間度とを対応付けて備える前記二分木地図データを作成すること
を特徴とする記録媒体。
【請求項１１】
被分割ラインにおける始点及び終点の各座標値と、該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点の離間度のうちの最大の離間度と、該被分割ラインと該被分割ラインから生成された第１及び第２分割ラインとの対応関係である親子関係を表す親子関係情報とを対応付けて備え、前記離間度が、被分割ラインの始点及び終点の間における該被分割ライン上に在る内点が該被分割ラインの始点及び終点を結ぶ線分からどれだけ離れているかを表す尺度であって、前記第１及び第２分割ラインが、最大の離間度を持つ内点で被分割ラインを２個に分割することによって生成され、前記被分割ラインが、始点及び終点の各座標値と該始点及び終点の間における当該線上に在る内点の座標値とを備える地図上に線で表され得るラインと、第１及び第２分割ラインのうちの内点を持たない分割ラインを除く分割ラインとである二分木地図データから、所定の内点を間引いて出力する地図出力装置において、
前記ラインの内点を間引く度合いである間引き度を入力するための入力部と、
前記ラインから内点を持たない分割ラインまでの親から子孫まで前記被分割ラインの前記最大の離間度と前記入力部で入力された間引き度とを順次に比較し、比較した結果、前記間引き度以下の前記最大の離間度を持つ被分割ラインにおける始点及び終点の座標値を取得する出力地図作成処理部と、
前記出力地図作成処理部で取得した前記始点及び終点の座標値を結ぶ線分を出力する出力部とを備えること
を特徴とする地図出力装置。
【請求項１２】
被分割ラインにおける始点及び終点の各座標値と、親離間度として該被分割ラインを生成する際に用いられた離間度と、子離間度として該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点の離間度のうちの最大の離間度とを対応付けて備え、前記離間度が、被分割ラインの始点及び終点の間における該被分割ライン上に在る内点が該被分割ラインの始点及び終点を結ぶ線分からどれだけ離れているかを表す尺度であって、前記被分割ラインが、始点及び終点の各座標値と該始点及び終点の間における該線上に在る内点の座標値とを備える地図上に線で表され得るラインと、最大の離間度を持つ内点で被分割ラインを２個に分割することによって生成される総ての第１及び第２分割ラインであって、前記親離間度及び子離間度が、被分割ラインと該被分割ラインから生成された第１及び第２分割ラインとの対応関係を親子関係とした場合に、前記ラインから内点を持たない分割ラインまでの親から子孫まで被分割ラインを第１及び第２分割ラインに分割する際に用いた離間度を順次に辿った場合に、当該分割する際の離間度を含め子孫側の離間度のうちの最大値で置き換えた値である二分木地図データから、所定の内点を間引いて出力する地図出力装置において、
前記ラインの内点を間引く度合いである間引き度を入力するための入力部と、
前記被分割ラインの前記親離間度及び前記子離間度と前記入力部で入力された間引き度とを順次に比較し、比較した結果、前記間引き度より大きい前記親離間度を持ち、かつ、前記間引き度以下の前記子離間度を持つ被分割ラインにおける始点及び終点の座標値を取得する出力地図作成処理部と、
前記出力地図作成処理部で取得した前記始点及び終点の座標値を結ぶ線分を出力する出力部とを備えること
を特徴とする地図出力装置。
【請求項１３】
請求項１２に記載の地図出力装置において、
前記二分木地図データは、所定の間隔が空けられて増加していく複数の整数に所定の規則で前記親離間度及び前記子離間度をそれぞれ丸めた丸め親離間度及び丸め子離間度を対応付けてさらに備え、
前記出力地図作成処理部は、前記被分割ラインの前記丸め親離間度及び前記丸め子離間度と前記入力部で入力された間引き度を前記複数の整数に前記所定の規則で丸めた丸め間引き度とを用いて前記所定の規則に応じた等式により前記始点及び終点の座標値を取得すべき被分割ラインを判別すること
を特徴とする地図出力装置。
【請求項１４】
請求項１１又は請求項１２に記載の地図出力装置において、
前記入力部は、前記出力部に出力すべき矩形の出力範囲がさらに入力され、
前記出力地図作成処理部は、前記入力部で入力された矩形の出力範囲に一部又は全部がかかるラインにおける被分割ラインを前記比較の対象とすること
を特徴とする地図出力装置。
【請求項１５】
請求項１１又は請求項１２に記載の地図出力装置において、
前記二分木地図データは、前記二分木地図データに設けられたｘｙ座標系において、一定間隔の格子を備える複数の層であって各層間で該格子の間隔が所定の間隔を空けられて増加していく複数の層における該格子点の座標値に所定の規則で前記被分割ラインの始点及び終点の座標値を丸めた丸め座標値を対応付けてさらに備え、
前記入力部は、前記出力部に出力すべき矩形の出力範囲がさらに入力され、
前記出力地図作成処理部は、前記格子によって形成される格子領域のうちの前記入力部で入力された矩形の出力範囲に一部又は全部がかかる格子領域における格子点の座標値に丸められた丸め座標値を持つ被分割ラインを前記比較の対象とすること
を特徴とする地図出力装置。
【請求項１６】
被分割ラインにおける始点及び終点の各座標値と、該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点の離間度のうちの最大の離間度と、該被分割ラインと該被分割ラインから生成された第１及び第２分割ラインとの対応関係である親子関係を表す親子関係情報とを対応付けて備え、
前記離間度は、被分割ラインの始点及び終点の間における該被分割ライン上に在る内点が該被分割ラインの始点及び終点を結ぶ線分からどれだけ離れているかを表す尺度であって、
前記第１及び第２分割ラインは、最大の離間度を持つ内点で被分割ラインを２個に分割することによって生成され、
前記被分割ラインは、始点及び終点の各座標値と該始点及び終点の間における当該線上に在る内点の座標値とを備える地図上に線で表され得るラインと、第１及び第２分割ラインのうちの内点を持たない分割ラインを除く分割ラインとである二分木地図データが記録されたコンピュータに読み取り可能な記録媒体。
【請求項１７】
被分割ラインにおける始点及び終点の各座標値と、親離間度として該被分割ラインを生成する際に用いられた離間度と、子離間度として該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点の離間度のうちの最大の離間度とを対応付けて備え、
前記離間度は、被分割ラインの始点及び終点の間における該被分割ライン上に在る内点が該被分割ラインの始点及び終点を結ぶ線分からどれだけ離れているかを表す尺度であって、
前記被分割ラインは、始点及び終点の各座標値と該始点及び終点の間における該線上に在る内点の座標値とを備える地図上に線で表され得るラインと、最大の離間度を持つ内点で被分割ラインを２個に分割することによって生成される総ての第１及び第２分割ラインであって、
前記親離間度及び子離間度は、被分割ラインと該被分割ラインから生成された第１及び第２分割ラインとの対応関係を親子関係とした場合に、前記ラインから内点を持たない分割ラインまでの親から子孫まで被分割ラインを第１及び第２分割ラインに分割する際に用いた離間度を順次に辿った場合に、当該分割する際の離間度を含め子孫側の離間度のうちの最大値で置き換えた値である二分木地図データが記録されたコンピュータに読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地理情報システムの技術に関する。
【背景技術】
【０００２】
旅行や訪問等で地理空間を移動する場合、災害の被害予測や被害状況等を表示する場合、人口密度や土地利用実態等の統計結果を表示する場合、及び、避難経路やゴミの収集経路等の行動経路を表示する場合等、様々な目的で地図が利用されている。地図は、地理空間の構成要素を所定の規約（図式）に従って紙やディスプレイ等の２次元媒体に可視的に表示したものであるが、これらの利用目的に応じて地図を加工する必要がある。また、地理空間の構成要素は、自然な事象により、あるいは、人為的な事象により、時間経過と共に変化するものであることから、地図を更新する必要もある。
【０００３】
このため、ディジタル形式で記述された地理情報を管理、分析及び表示するコンピュータシステムである地理情報システム（Geographic Information System、以下、「ＧＩＳ」と略記する。）が開発され、実用化されている（例えば、非特許文献１）。ＧＩＳにおいて、地理情報は、地理空間の構成要素（エンティティ（Entity）又は空間エンティティという。）の特性を記述した情報の総称であり、一般に、位置、形状、物理的又は社会的な特性である属性、機能、年月日及び相互関係を備えて構成される。
【０００４】
ＧＩＳでは、例えば、地理情報を一定の規則に従って分類された複数の層（レイヤ）を重ね合わせることで地図が表現される。この地図を構成するレイヤは、点（ポイント）、線（ライン）、面（ポリゴン）でエンティティの位置と形状を表現する方法であるベクタ方式、地理空間を隙間なく分割して規則的なセルの集合でエンティティの位置と形状とを表現する方法であるラスタ方式、及び、規則的なセルの集合で表面を区分して表面を表現する方法であるＴＩＮ（Triangulated Irregular Network）方式のうちの何れかによって記述される。行政界を表示するレイヤ、道路を表示するレイヤ、水系を表示するレイヤ及び建物を表示するレイヤ等の、離散的なエンティティが集まるレイヤは、通常、ベクタ方式で記述され、地形等の連続的に変化する表面は、通常、ラスタ方式やＴＩＮ方式で記述される。
【０００５】
このベクタ方式では、地図上又は実地上のエンティティの輪郭がデータ化され、位置及び形状が図形データとしてデータ化され、属性、機能及び年月日が属性データとしてデータ化され、そして、相互関係がトポロジデータとしてデータ化される。この図形データにおいて、ポイントは、当該ポイントの座標値でデータ化され、ラインは、始点、ライン上の１又は複数の内点（中間点）及び終点の各座標値でデータ化され、そして、ポリゴンは、例えば、ポリゴンを構成するラインのデータでデータ化される。このように、ラインは、始点、内点及び終点の各座標値でデータ化されるため、曲線は、折れ線によって表現されることになる。
【０００６】
ＧＩＳの基本データ（メタデータ）となる基本的な地理情報は、日本では陸域について国土地理院が整備を行っており、海域について海上保安庁水路部が整備を行っている。例えば、国土地理院は、数値地図２５００、数値地図１００００総合及び数値地図２５０００等を発行している。
【非特許文献１】巌網林、「ＧＩＳの原理と応用」、日科技連、２００３年５月２６日発行
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ところで、地図は、上述したように様々な目的に利用されており、その利用目的に応じて地理情報を取捨選択する必要がある。即ち、利用目的に応じて、データ化されている総ての情報を盛り込んで地図を作成する必要もあるし、また、データ化されている総ての情報のうち一部の情報のみを盛り込んで地図を作成する必要もある。
【０００８】
また、地図には、周知のように大縮尺や小縮尺等の様々な縮尺があり、この縮尺に応じて、データ化されている総ての情報を盛り込んで地図を作成する必要もあるし、また、データ化されている総ての情報のうち一部の情報のみを盛り込んで地図を作成する必要もある。
【０００９】
さらに、地図を表示するディスプレイには、周知のように様々なサイズや解像度があり、このサイズや解像度に応じて、データ化されている総ての情報を盛り込んで地図を表示する必要もあるし、また、データ化されている総ての情報のうち一部の情報のみを盛り込んで地図を作成する必要もある。
【００１０】
このような場合、従来では、人手で地理情報を取捨選択することによって、利用目的に応じた、縮尺に応じた、あるいは、サイズや解像度に応じた地図を作成していた。そのため、地図の作成及び保守（メンテナンス）に多大な時間と手間を要していた。
【００１１】
本発明は、上述の事情に鑑みて為された発明であり、ベクタ方式のラインデータから内点のデータを簡単に間引き得る地図データを作成する地図データ作成装置、地図データ作成方法、地図データ作成プログラム及び地図データ作成プログラムを記録したコンピュータに読取り可能な記録媒体を提供することを目的とする。そして、本発明に係る地図データからデータを間引いた地図を出力することができる地図出力装置を提供することを目的とする。さらに、ベクタ方式のラインデータから内点のデータを簡単に間引き得る地図データを記録したコンピュータに読取り可能な記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上述の目的を達成するために、本発明の一態様に係る二分木地図データ作成装置は、被分割ラインにおける始点及び終点の各座標値と、該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点の離間度のうちの最大の離間度と、該被分割ラインと該被分割ラインから生成された第１及び第２分割ラインとの対応関係である親子関係を表す親子関係情報とを対応付けて備え、前記離間度が、被分割ラインの始点及び終点の間における該被分割ライン上に在る内点が該被分割ラインの始点及び終点を結ぶ線分からどれだけ離れているかを表す尺度であって、前記第１及び第２分割ラインが、最大の離間度を持つ内点で被分割ラインを２個に分割することによって生成され、前記被分割ラインが、始点及び終点の各座標値と該始点及び終点の間における当該線上に在る内点の座標値とを備える地図上に線で表され得るラインと、第１及び第２分割ラインのうちの内点を持たない分割ラインを除く分割ラインとである二分木地図データを作成することを特徴とする。
【００１３】
そして、本発明の他の一態様に係る二分木地図データ作成装置は、被分割ラインにおける始点及び終点の各座標値と、親離間度として該被分割ラインを生成する際に用いられた離間度と、子離間度として該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点の離間度のうちの最大の離間度とを対応付けて備え、前記離間度が、被分割ラインの始点及び終点の間における該被分割ライン上に在る内点が該被分割ラインの始点及び終点を結ぶ線分からどれだけ離れているかを表す尺度であって、前記被分割ラインが、始点及び終点の各座標値と該始点及び終点の間における該線上に在る内点の座標値とを備える地図上に線で表され得るラインと、最大の離間度を持つ内点で被分割ラインを２個に分割することによって生成される総ての第１及び第２分割ラインであって、前記親離間度及び子離間度が、被分割ラインと該被分割ラインから生成された第１及び第２分割ラインとの対応関係を親子関係とした場合に、前記ラインから内点を持たない分割ラインまでの親から子孫まで被分割ラインを第１及び第２分割ラインに分割する際に用いた離間度を順次に辿った場合に、当該分割する際の離間度を含め子孫側の離間度のうちの最大値で置き換えた値である二分木地図データを作成することを特徴とする。
【００１４】
また、本発明の他の一態様に係る、始点及び終点の各座標値と該始点及び終点の間における該線上に在る内点の座標値とを備え地図上に線で表されるラインの地図データを二分木地図データに変換する二分木地図データ作成装置は、被分割ラインにおける始点及び終点を結ぶ線分から該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点がどれだけ離れているかを表す尺度である離間度を演算する離間度演算部と、前記離間度演算部で演算した離間度のうちの最大の離間度を持つ内点で前記被分割ラインを２個の第１及び第２分割ラインに分割する被分割ライン分割処理部と、前記ラインを最初の被分割ラインとすると共に前記被分割ライン分割処理部で分割することによって生成された分割ラインを新たな被分割ラインとすることで、分割ラインに内点が無くなるまで順次に前記ラインを分割するライン分割処理部と、前記ライン分割処理部で被分割ラインとされた前記ライン及び分割ラインにおける始点及び終点の各座標値と、前記被分割ライン分割処理部で前記被分割ラインを分割する際に用いた前記最大の離間度と、前記被分割ライン分割処理部で生成された第１及び第２分割ラインと前記被分割ラインとの対応関係である親子関係を表す親子関係情報とを対応付けて備える前記二分木地図データを作成する作成処理部とを備えることを特徴とする。
【００１５】
さらに、上述の二分木地図データ作成装置において、前記被分割ライン分割処理部で前記被分割ラインを分割する際に用いた前記最大の離間度を子離間度とすると共に前記被分割ラインを生成する際に用いられた離間度を親離間度として、前記親離間度及び子離間度を、前記ラインから前記内点を持たない分割ラインまでの親から子孫まで前記被分割ラインを前記第１及び第２分割ラインに分割する際に用いた離間度を順次に辿った場合に、当該分割する際の離間度を含め子孫側の離間度のうちの最大値で置き換える置換処理部をさらに備え、前記作成処理部は、前記ライン及び総ての分割ラインにおける始点及び終点の各座標値と、前記置換処理部で処理された親離間度と、前記置換処理部で処理された子離間度とを対応付けて備える前記二分木地図データを作成することを特徴とする。
【００１６】
そして、本発明の他の一態様に係る、始点及び終点の各座標値と該始点及び終点の間における該線上に在る内点の座標値とを備え地図上に線で表されるラインの地図データを二分木地図データに変換する二分木地図データ作成方法、コンピュータに実行させるための二分木地図データ作成プログラム、及び、コンピュータに実行させるための二分木地図データ作成プログラムを記録した記録媒体における該二分木地図データ作成プログラムは、被分割ラインにおける始点及び終点を結ぶ線分から該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点がどれだけ離れているかを表す尺度である離間度を演算する離間度演算ステップと、前記離間度演算ステップで演算した離間度のうちの最大の離間度を持つ内点で前記被分割ラインを２個の第１及び第２分割ラインに分割する被分割ライン分割処理ステップと、前記ラインを最初の被分割ラインとすると共に前記被分割ライン分割処理ステップで分割することによって生成された分割ラインを新たな被分割ラインとすることで、分割ラインに内点が無くなるまで順次に前記ラインを分割するライン分割処理ステップと、前記ライン分割処理ステップで被分割ラインとされた前記ライン及び分割ラインにおける始点及び終点の各座標値と、前記被分割ライン分割処理ステップで前記被分割ラインを分割する際に用いた前記最大の離間度と、前記被分割ライン分割処理ステップで生成された第１及び第２分割ラインと前記被分割ラインとの対応関係である親子関係を表す親子関係情報とを対応付けて備える前記二分木地図データを作成する作成処理ステップとを備えることを特徴とする。
【００１７】
また、上述の二分木地図データ作成方法、コンピュータに実行させるための二分木地図データ作成プログラム、及び、コンピュータに実行させるための二分木地図データ作成プログラムを記録した記録媒体における該二分木地図データ作成プログラムにおいて、前記被分割ライン分割処理ステップで前記被分割ラインを分割する際に用いた前記最大の離間度を子離間度とすると共に前記被分割ラインを生成する際に用いられた離間度を親離間度として、前記親離間度及び子離間度を、前記ラインから前記内点を持たない分割ラインまでの親から子孫まで前記被分割ラインを前記第１及び第２分割ラインに分割する際に用いた離間度を順次に辿った場合に、当該分割する際の離間度を含め子孫側の離間度のうちの最大値で置き換える置換処理ステップをさらに備え、前記作成処理ステップは、前記ライン及び総ての分割ラインにおける始点及び終点の各座標値と、前記置換処理ステップで処理された親離間度と、前記置換処理ステップで処理された子離間度とを対応付けて備える前記二分木地図データを作成することを特徴とする。
【００１８】
さらに、本発明の他の一態様に係る、被分割ラインにおける始点及び終点の各座標値と、該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点の離間度のうちの最大の離間度と、該被分割ラインと該被分割ラインから生成された第１及び第２分割ラインとの対応関係である親子関係を表す親子関係情報とを対応付けて備え、前記離間度が、被分割ラインの始点及び終点の間における該被分割ライン上に在る内点が該被分割ラインの始点及び終点を結ぶ線分からどれだけ離れているかを表す尺度であって、前記第１及び第２分割ラインが、最大の離間度を持つ内点で被分割ラインを２個に分割することによって生成され、前記被分割ラインが、始点及び終点の各座標値と該始点及び終点の間における当該線上に在る内点の座標値とを備える地図上に線で表され得るラインと、第１及び第２分割ラインのうちの内点を持たない分割ラインを除く分割ラインとである二分木地図データから、所定の内点を間引いて出力する地図出力装置は、前記ラインの内点を間引く度合いである間引き度を入力するための入力部と、前記ラインから内点を持たない分割ラインまでの親から子孫まで前記被分割ラインの前記最大の離間度と前記入力部で入力された間引き度とを順次に比較し、比較した結果、前記間引き度以下の前記最大の離間度を持つ被分割ラインにおける始点及び終点の座標値を取得する出力地図作成処理部と、前記出力地図作成処理部で取得した前記始点及び終点の座標値を結ぶ線分を出力する出力部とを備えることを特徴とする。
【００１９】
そして、本発明の他の一態様に係る、被分割ラインにおける始点及び終点の各座標値と、親離間度として該被分割ラインを生成する際に用いられた離間度と、子離間度として該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点の離間度のうちの最大の離間度とを対応付けて備え、前記離間度が、被分割ラインの始点及び終点の間における該被分割ライン上に在る内点が該被分割ラインの始点及び終点を結ぶ線分からどれだけ離れているかを表す尺度であって、前記被分割ラインが、始点及び終点の各座標値と該始点及び終点の間における該線上に在る内点の座標値とを備える地図上に線で表され得るラインと、最大の離間度を持つ内点で被分割ラインを２個に分割することによって生成される総ての第１及び第２分割ラインであって、前記親離間度及び子離間度が、被分割ラインと該被分割ラインから生成された第１及び第２分割ラインとの対応関係を親子関係とした場合に、前記ラインから内点を持たない分割ラインまでの親から子孫まで被分割ラインを第１及び第２分割ラインに分割する際に用いた離間度を順次に辿った場合に、当該分割する際の離間度を含め子孫側の離間度のうちの最大値で置き換えた値である二分木地図データから、所定の内点を間引いて出力する地図出力装置は、前記ラインの内点を間引く度合いである間引き度を入力するための入力部と、前記被分割ラインの前記親離間度及び前記子離間度と前記入力部で入力された間引き度とを順次に比較し、比較した結果、前記間引き度より大きい前記親離間度を持ち、かつ、前記間引き度以下の前記子離間度を持つ被分割ラインにおける始点及び終点の座標値を取得する出力地図作成処理部と、前記出力地図作成処理部で取得した前記始点及び終点の座標値を結ぶ線分を出力する出力部とを備えることを特徴とする。
【００２０】
また、上述の地図出力装置において、前記二分木地図データは、所定の間隔が空けられて増加していく複数の整数に所定の規則で前記親離間度及び前記子離間度をそれぞれ丸めた丸め親離間度及び丸め子離間度を対応付けてさらに備え、前記出力地図作成処理部は、前記被分割ラインの前記丸め親離間度及び前記丸め子離間度と前記入力部で入力された間引き度を前記複数の整数に前記所定の規則で丸めた丸め間引き度とを用いて前記所定の規則に応じた等式により前記始点及び終点の座標値を取得すべき被分割ラインを判別することを特徴とする。
【００２１】
さらに、これら上述の地図出力装置において、前記入力部は、前記出力部に出力すべき矩形の出力範囲がさらに入力され、前記出力地図作成処理部は、前記入力部で入力された矩形の出力範囲に一部又は全部がかかるラインにおける被分割ラインを前記比較の対象とすることを特徴とする。
【００２２】
そして、これら上述の地図出力装置において、前記二分木地図データは、前記二分木地図データに設けられたｘｙ座標系において、一定間隔の格子を備える複数の層であって各層間で該格子の間隔が所定の間隔を空けられて増加していく複数の層における該格子点の座標値に所定の規則で前記被分割ラインの始点及び終点の座標値を丸めた丸め座標値を対応付けてさらに備え、前記入力部は、前記出力部に出力すべき矩形の出力範囲がさらに入力され、前記出力地図作成処理部は、前記格子によって形成される格子領域のうちの前記入力部で入力された矩形の出力範囲に一部又は全部がかかる格子領域における格子点の座標値に丸められた丸め座標値を持つ被分割ラインを前記比較の対象とすることを特徴とする。
【００２３】
また、本発明の他の一態様に係るコンピュータに読み取り可能な記録媒体は、被分割ラインにおける始点及び終点の各座標値と、該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点の離間度のうちの最大の離間度と、該被分割ラインと該被分割ラインから生成された第１及び第２分割ラインとの対応関係である親子関係を表す親子関係情報とを対応付けて備え、前記離間度が、被分割ラインの始点及び終点の間における該被分割ライン上に在る内点が該被分割ラインの始点及び終点を結ぶ線分からどれだけ離れているかを表す尺度であって、前記第１及び第２分割ラインが、最大の離間度を持つ内点で被分割ラインを２個に分割することによって生成され、前記被分割ラインが、始点及び終点の各座標値と該始点及び終点の間における当該線上に在る内点の座標値とを備える地図上に線で表され得るラインと、第１及び第２分割ラインのうちの内点を持たない分割ラインを除く分割ラインとである二分木地図データが記録されていることを特徴とする。
【００２４】
さらに、本発明の他の一態様に係るコンピュータに読み取り可能な記録媒体は、被分割ラインにおける始点及び終点の各座標値と、親離間度として該被分割ラインを生成する際に用いられた離間度と、子離間度として該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点の離間度のうちの最大の離間度とを対応付けて備え、前記離間度が、被分割ラインの始点及び終点の間における該被分割ライン上に在る内点が該被分割ラインの始点及び終点を結ぶ線分からどれだけ離れているかを表す尺度であって、前記被分割ラインが、始点及び終点の各座標値と該始点及び終点の間における該線上に在る内点の座標値とを備える地図上に線で表され得るラインと、最大の離間度を持つ内点で被分割ラインを２個に分割することによって生成される総ての第１及び第２分割ラインであって、前記親離間度及び子離間度が、被分割ラインと該被分割ラインから生成された第１及び第２分割ラインとの対応関係を親子関係とした場合に、前記ラインから内点を持たない分割ラインまでの親から子孫まで被分割ラインを第１及び第２分割ラインに分割する際に用いた離間度を順次に辿った場合に、当該分割する際の離間度を含め子孫側の離間度のうちの最大値で置き換えた値である二分木地図データが記録されていることを特徴とする。
【発明の効果】
【００２５】
本発明に係る二分木地図データ作成装置、該方法、該方法のプログラム、及び記録媒体に記録された該方法のプログラムは、被分割ラインにおける始点及び終点の各座標値と、該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点の離間度のうちの最大の離間度と、該被分割ラインと該被分割ラインから生成された第１及び第２分割ラインとの対応関係である親子関係を表す親子関係情報とを対応付けて備える二分木地図データや、被分割ラインにおける始点及び終点の各座標値と、親離間度として該被分割ラインを生成する際に用いられた離間度と、子離間度として該被分割ラインの始点及び終点の間における該被分割ライン上に在る内点の離間度のうちの最大の離間度とを対応付けて備える二分木地図データを作成する。このため、本発明に係る地図出力装置は、この作成された二分木地図データや記録媒体に記憶されている二分木地図データを用いて、表示する地図の範囲、縮尺、または、解像度に応じて、ラインから内点のデータを間引いたデータを高速に取り出すことができ、高速に地図を作成することができる。
【発明を実施するための最良の形態】
【００２６】
以下、本発明に係る実施形態を図面に基づいて説明する。なお、各図において同一の符号を付した構成は、同一の構成であることを示し、その説明を省略する。
（第１の実施形態の構成）
第１の実施形態における二分木地図データ作成表示装置は、元地図データから二分木地図データを作成する場合には、ラインを最大離間度Ｓｍａｘの内点で第１及び第２分割ラインに分割する二分木処理を行い、この分割した第１及び第２分割ラインを新たな二分木処理の対象とするラインとして二分木処理を再帰的に繰り返すことにより、ツリー構造の二分木地図データを作成し、そして、二分木地図データに基づいて間引き度に応じた地図を出力する場合には、二分木地図データのツリー構造における各ラインデータに対し、ラインの離間度と間引き度とを比較してラインの離間度が間引き度以下である場合には当該ラインを出力する間引き処理をツリー構造の根（ルート）から末端に向けて深さ優先探索を行うことにより、間引き度に応じた地図を出力するものである。
【００２７】
図１は、第１の実施形態に係る二分木地図データ作成出力装置の構成を示すブロック図である。図１において、二分木地図データ作成出力装置１は、例えば、演算処理部１１と、入力部１２と、出力部１３と、記憶部１４と、バス１５とを備えて構成される。
【００２８】
入力部１２は、二分木地図データの作成開始を指示する作成開始コマンドや地図の出力開始を指示する出力開始コマンド等の各種コマンド、及び、元地図データや間引き度の値等の各種データを二分木地図データ作成出力装置１に入力する機器であり、例えば、キーボードやマウス等である。元地図データは、本発明に係る二分木地図データを作成するための基礎となる、ベクタ方式におけるラインのデータ（ラインデータ）から構成される地図データであり、例えば、上述した国土地理院発行の数値地図データが利用される。ラインは、道路、水道管、下水路、川等の水系、等高線及び水深線等の離散的なエンティティを表すものである。ラインが閉ループを構成する場合でも当該ラインを複数のラインで表現することによって適用可能である。間引き度Ｔは、二分木地図データに基づく地図を生成する場合においてラインの内点を間引く度合いであり、間引き度Ｔは、後述から分かるように、元ラインデータにおける内点のデータを採用するか否かを判別する閾値となる。出力部１３は、入力部１２から入力されたコマンドやデータ、及び、本二分木地図データ作成出力装置１によって作成された二分木地図データのファイル名や二分木地図データに基づく間引き度Ｔに応じた地図等を出力する機器であり、例えばＣＲＴディスプレイ、ＬＣＤ、有機ＥＬディスプレイ又はプラズマディスプレイ等の表示装置やプリンタ等の印字装置等である。
【００２９】
記憶部１４は、元地図データから二分木地図データを作成する本発明に係る二分木地図データ作成プログラムを記憶する二分木地図データ作成プログラム記憶部３１と、二分木地図データに基づく間引き度Ｔに応じた地図を作成してこの作成した地図を出力部１３に出力する出力地図作成プログラムを記憶する出力地図作成プログラム記憶部３２と、元地図データを記憶する元地図データ記憶部３３と、本発明に係る二分木地図データを記憶する二分木地図データ記憶部３４とを備え、各種プログラム及び各種プログラムの実行中に生じるデータ等の各種データを記憶する。記憶部１４は、例えば、演算処理部１１の所謂ワーキングメモリとなるＲＡＭ（Random Access Memory）等の揮発性の記憶素子、及び、ＲＯＭ（Read Only Memory）や書換え可能なＥＥＰＲＯＭ（Electrically Erasable Programmable Read Only Memory）等の不揮発性の記憶素子を備えて構成される。
【００３０】
演算処理部１１は、例えば、マイクロプロセッサ及びその周辺回路等を備えて構成され、機能的に、二分木地図データ作成処理部２１と、出力地図作成処理部２２とを備えると共に、制御プログラムに従い入力部１２、出力部１３及び記憶部１４を当該機能に応じてそれぞれ制御する。
【００３１】
二分木地図データ作成処理部２１は、後述の動作によって元地図データから第１の実施形態に係る二分木地図データを作成するものであり、本実施形態では、被分割ラインにおける始点及び終点の各座標値と、この被分割ラインの始点及び終点の間における被分割ライン上に在る内点の離間度Ｓのうちの最大の離間度Ｓｍａｘと、この最大の離間度Ｓｍａｘを持つ内点で被分割ラインを２個に分割することによって生成された第１及び第２分割ラインと被分割ラインとの親子関係を表す親子関係情報とを対応付けて備え、この被分割ラインが、ライン及び被分割ラインを最大の離間度Ｓｍａｘを持つ内点で２個に分割することによって生成される第１及び第２分割ラインのうちの内点を持たない分割ラインを除く分割ラインである第１の実施形態に係る二分木地図データを作成するものである。より具体的には、二分木地図データ作成処理部２１は、例えば、本実施形態では、離間度Ｓを演算する離間度演算部２１１と、離間度演算部２１１で演算した離間度Ｓのうちの最大の離間度Ｓｍａｘを持つ内点で被分割ラインを２個の第１及び第２分割ラインに分割する被分割ライン分割処理部２１２と、ラインを最初の被分割ラインとすると共に被分割ライン分割処理部で分割することによって生成された分割ラインを新たな被分割ラインとすることで、分割ラインに内点が無くなるまで順次にラインを分割するライン分割処理部２１３と、ライン分割処理部２１３で被分割ラインとされた被分割ラインにおける始点及び終点の各座標値と、被分割ライン分割処理部２１２で被分割ラインを分割する際の最大の離間度Ｓｍａｘと、被分割ライン分割処理部２１２で生成された第１及び第２分割ラインと被分割ラインとの対応関係である親子関係を表す親子関係情報とを対応付けて備える二分木地図データを作成する作成処理部２１４とを備える。
【００３２】
ここで、ラインの始点及び終点とその間に位置する内点とについて考えると、仮に内点が総て始点及び終点を結ぶ線分上に乗っていれば、内点を総て間引いて、つまり、内点を総て採用することなく始点、終点及びこれら両点を結ぶ線分でラインを描画したとしても、始点から終点に向けて内点を順に線分で結んでラインを描画した場合と見た目は、同一である。従って、内点を間引くか否かは、始点及び終点を結ぶ線分と当該内点と離れ度合いによって判定することができる。そこで、本発明では、始点及び終点を結ぶ線分から各内点がどれだけ離れているかを表す尺度として離間度Ｓが定義される。例えば、本実施形態では、離間度Ｓは、簡易に演算可能であるという観点から、内点から始点及び終点を通る直線までの距離Ｄである。
【００３３】
出力地図作成処理部２２は、後述の動作によって二分木地図データに基づく間引き度Ｔに応じた地図を作成してこの作成した地図を出力部１３に出力するものであり、本実施形態では、ラインから内点を持たない分割ラインまでの親から子孫まで被分割ラインの最大の離間度Ｓｍａｘと入力部１２で入力された間引き度Ｔとを順次に比較し、比較した結果、間引き度Ｔ以下の最大の離間度Ｓｍａｘを持つ被分割ラインにおける始点及び終点の各座標値を取得し、出力部１３に出力するものである。
【００３４】
これら演算処理部１１、入力部１２、出力部１３及び記憶部１４は、データを相互に交換することができるようにバス１５でそれぞれ接続される。
【００３５】
このような二分木地図データ作成出力装置１は、例えば、コンピュータ、より具体的にはノート型やディスクトップ型等のパーソナルコンピュータ等によって構成可能である。
【００３６】
なお、必要に応じて二分木地図データ作成出力装置１は、破線で示すように、外部記憶部１６及び／又は通信インタフェース部１７をさらに備えてもよい。外部記憶部１６は、例えば、フレキシブルディスク、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Compact Disc Recordable）及びＤＶＤ−Ｒ（Digital Versatile Disc Recordable）等の記録媒体との間でデータを読み込み及び／又は書き込みを行う装置であり、例えば、フレキシブルディスクドライブ、ＣＤ−ＲＯＭドライブ、ＣＤ−Ｒドライブ及びＤＶＤ−Ｒドライブ等である。通信インタフェース部１７は、ローカル・エリア・ネットワークや外部のネットワーク（例えば、インターネット）等のネットワークに接続され、このネットワークを介して他の通信端末装置との間で通信信号を送受信するためのインターフェース回路であり、演算処理部１１からのデータに基づいてネットワークの通信プロトコルに従った通信信号を作成すると共にネットワークからの通信信号を演算処理部１１が処理可能な形式のデータに変換する。
【００３７】
ここで、二分木地図データ作成プログラムや地図出力プログラム等の各プログラム及び元地図データや二分木地図データ等の各データが格納されていない場合には、各プログラムや各データがこれらを記録した記録媒体から外部記憶部１６を介して記憶部１４にインストールされるように構成してもよく、また、これら各プログラムや各データを管理するサーバ（不図示）からネットワーク及び通信インターフェース部１７を介して各プログラムや各データがダウンロードされるように構成してもよい。あるいは、作成した二分木地図データが外部記憶部１６を介して記録媒体に記録されるように構成してもよく、また、作成した二分木地図データがネットワーク及び通信インターフェース部１７を介してサーバにアップロードされるように構成してもよい。
【００３８】
次に、本実施形態の動作について説明する。
（第１の実施形態の動作）
まず、二分木地図データ作成出力装置１が元地図データから二分木地図データを作成する動作について説明する。
【００３９】
図２は、第１の実施形態に係る二分木地図データ作成出力装置における二分木地図データを作成する動作を示すフローチャートである。
【００４０】
例えば、ユーザが元地図データを入力部１２から二分木地図データ作成出力装置１に入力することによって、元地図データが記憶部１４の元地図データ記憶部３３に記憶される。そして、記憶部１４の二分木地図データ作成プログラム記憶部３１から二分木地図データ作成プログラムが呼び出されて実行され、例えば、ユーザが、元地図データから二分木地図データを二分木地図データ作成出力装置１に作成させるべく、二分木地図データの作成開始コマンドを入力部１２から入力すると、演算処理部１１の二分木地図データ作成処理部２１は、記憶部１４の元地図データ記憶部３３に記憶されている元地図データに基づいて二分木地図データを作成する。
【００４１】
即ち、図２において、まず、演算処理部１１の二分木地図データ作成処理部２１は、ライン分割処理部２１３によって、元地図データのラインデータを本発明に係る二分木地図データに変換すべく、元地図データから一のラインデータを取り出す（Ｓ１０）。なお、元地図データのラインデータを重複して後述の処理Ｓ１１乃至処理Ｓ１４の二分木処理を実行することを避けるため、この処理Ｓ１０において、ラインデータを元地図データから順に取り出したり、取出し済みであることを示す符号（１又は複数の記号列）を元地図データのラインデータに付したり等する。
【００４２】
次に、二分木地図データ作成処理部２１は、離間度演算部２１１によって、この取り出したラインを被分割ラインとしてその各内点の離間度Ｓを演算する（Ｓ１１）。
【００４３】
次に、二分木地図データ作成処理部２１は、被分割ライン分割処理部２１２によって、各内点の離間度Ｓのうち最大の離間度Ｓｍａｘを持つ内点を検索し、抽出する（Ｓ１２）。
【００４４】
次に、二分木地図データ作成処理部２１は、被分割ライン分割処理部２１２によって、処理Ｓ１２で抽出した内点で被分割ラインを二分する（Ｓ１３）。このラインを二分することによって生成されたラインを分割ラインと、この分割ラインのうち始点と処理Ｓ１２で抽出した内点とを結ぶラインを第１分割ラインと、この分割ラインのうち処理Ｓ１２で抽出した内点と終点とを結ぶラインを第２分割ラインと、それぞれ呼称することとする。
【００４５】
次に、二分木地図データ作成処理部２１は、作成処理部２１４によって、当該ラインを描画するためのデータと、当該ラインと分割ライン（第１及び第２分割ライン）との対応関係である親子関係と、当該ラインを分割する内点の離間度Ｓ（最大の離間度Ｓｍａｘ）との対応関係を表す第１の実施形態に係る二分木データを作成し、記憶部１４に一時的に記憶する（Ｓ１４）。
【００４６】
処理Ｓ１１乃至処理Ｓ１４を実行することより、被分割ラインを最大離間度Ｓｍａｘの内点で二分することにより、被分割ラインを親とし第１及び第２分割ラインを子とする木構造（ツリー構造）のデータが作成されるので、この処理Ｓ１１乃至処理Ｓ１４の処理を二分木処理と呼称することとする。
【００４７】
次に、二分木地図データ作成処理部２１は、ライン分割処理部２１３によって、第１及び第２分割ラインに内点が存在するか否かを判断する（Ｓ１５）。
【００４８】
処理Ｓ１５における判断の結果、第１及び第２分割ラインの双方に内点が存在する場合（双方有り）には、二分木地図データ作成処理部２１は、ライン分割処理部２１３によって、一方の分割ラインを新たな被分割ラインとすると共に他方の分割ラインを記憶部１４に一時的に記憶し（Ｓ２１）、処理を処理Ｓ１１に戻して二分木処理を続行する。
【００４９】
また、処理Ｓ１５における判断の結果、第１及び第２分割ラインの一方に内点が存在する場合（一方有り）には、二分木地図データ作成処理部２１は、ライン分割処理部２１３によって、内点の存在する分割ラインを新たな被分割ラインとし（Ｓ２２）、処理を処理Ｓ１１に戻して二分木処理を続行する。ここで、処理Ｓ２１及び処理Ｓ２２おいて、第１分割ラインが新たな被分割ラインとされる場合には、第１分割ラインの内点が新たな被分割ラインにおける終点とされ、第２分割ラインが新たな被分割ラインとされる場合には、第２分割ラインの内点が新たな被分割ラインにおける始点とされる。後述の処理Ｓ２３も同様である。
【００５０】
さらに、処理Ｓ１５における判断の結果、第１及び第２分割ラインの双方に内点が存在しない場合（双方なし）には、二分木地図データ作成処理部２１は、ライン分割処理部２１３によって、処理Ｓ１６を実行し、記憶部１４を参照することで二分木処理を施されていない分割ラインが記憶部１４に記憶されているか否かを判断することで総ての分割ラインについて二分木処理が終了したか否かを判断する。
【００５１】
この処理Ｓ１６における判断の結果、総ての分割ラインについて二分木処理が終了していない場合（Ｎｏ）には、二分木地図データ作成処理部２１は、ライン分割処理部２１３によって、記憶部１４に記憶されている二分木処理が未処理の分割ラインを新たな被分割ラインとし（Ｓ２３）、処理を処理Ｓ１１に戻して二分木処理を続行する。
【００５２】
一方、処理Ｓ１６における判断の結果、総ての分割ラインについて二分木処理が終了している場合（Ｙｅｓ）には、二分木地図データ作成処理部２１は、作成処理部２１４によって、処理Ｓ１７を実行し、これら作成した各被分割ラインの二分木データを纏めて二分木地図データとして記憶部１４の二分木地図データ記憶部３４にファイル名を付して記憶する。
【００５３】
次に、二分木地図データ作成処理部２１は、ライン分割処理部２１３によって、元地図データを構成する総てのラインについて二分木地図データを作成したか否かを判断する（Ｓ１８）。
【００５４】
この処理Ｓ１８における判断の結果、元地図データの総てのラインについて二分木地図データが作成されていない場合（Ｎｏ）には、二分木地図データ作成処理部２１は、ライン分割処理部２１３によって、元地図データの他のラインについて二分木地図データを作成すべく、処理を処理Ｓ１０に戻して上述の処理Ｓ１０乃至処理Ｓ１７の処理を続行する。
【００５５】
一方、処理Ｓ１８における判断の結果、元地図データの総ての元ラインについて二分木データが作成されている場合（Ｙｅｓ）には、二分木地図データ作成処理部２１は、処理を終了する。
【００５６】
このように動作することによって元地図データから、二分木地図データ作成出力装置１は、被分割ラインを描画するためのデータと、被分割ラインを分割した内点の離間度Ｓ（最大の離間度Ｓｍａｘ）と、被分割ラインと第１及び第２分割ラインとの親子関係との対応関係を表すツリー構造又はテーブル形式の二分木地図データを作成し記憶することができる。そして、このような二分木地図データは、後述するように、間引き度Ｔに応じた地図を作成するために必要なデータを高速に取り出され得る。
【００５７】
上述から分かるように、元地図データから生成される二分木地図データは、元地図データを構成する各ラインデータに対し二分木処理を実行し、その結果得られた二分木データをツリー構造に纏めたものである。このため、図２に示す処理をより具体的に説明するために、一のラインデータから二分木データを作成する一具体例について以下で説明する。
【００５８】
図３は、ラインを示す図である。図３（Ａ）は、実地上のエンティティにおける輪郭を相似で略輪郭通りの曲線で記述した場合であり、図３（Ｂ）は、この曲線を折れ線のラインで記述した場合である。図４乃至図６は、二分木地図データ作成出力装置における二分木地図データを作成する動作を説明するための図である。図４（Ａ）は、ライン（最初の被分割ライン、元のライン）を１回目の内点で分割する場合であり、図４（Ｂ）は、１回目の内点でラインを分割することによって生成された第１及び第２分割ラインを２回目の内点で分割する場合である。図５（Ａ）は、２回目の内点で被分割ラインを分割することによって生成された第１及び第２分割ラインを３回目の内点で分割する場合であり、図５（Ｂ）は、３回目の内点で被分割ラインを分割することによって生成された第１及び第２分割ラインを４回目の内点で分割する場合である。図６（Ａ）は、４回目の内点で被分割ラインを分割することによって生成された第１及び第２分割ラインを５回目の内点で分割する場合であり、図６（Ｂ）は、５回目の内点で被分割ラインを分割することによって生成された第１及び第２分割ラインを６回目の内点で分割する場合である。図７は、第１の実施形態に係るテーブルで表現した二分木地図データを示す図である。図８は、第１の実施形態に係るツリー構造で表現した二分木地図データを示す図である。
【００５９】
例えば、図３（Ａ）に示す、実地上のエンティティにおける輪郭を略輪郭通りに相似で記述された曲線ＡＢは、曲線の曲がり度合いに応じて内点が設定され、例えば、図３（Ａ）に示すようにＰ2乃至Ｐ17の１６個の内点が設定される。ここで、曲線ＡＢの始点Ａ及び終点Ｂも内点と同様の表記とするために、始点ＡにＰ1を割り当て、終点ＢにＰ18を割り当てている。このように内点を設定することにより、曲線ＡＢは、図３（Ｂ）に示す折れ線で記述され、各点Ｐ1〜Ｐ18の座標値を求めることにより、ベクタ方式の図形データにおけるラインデータが作成される。この各点Ｐ1〜Ｐ18の座標値からなる図形データにおけるラインデータが元地図データに相当する。
【００６０】
このような各点Ｐ1〜Ｐ18の座標値からなる図形データのラインデータから二分木地図データを作成すべく、二分木地図データ作成出力装置１が動作すると、演算処理部１１の二分木地図データ作成処理部２１は、処理Ｓ１０でラインＰ1Ｐ18のラインデータを被分割ラインのデータとして取り出し、処理Ｓ１１を実行することにより、図４（Ａ）に示すように、各点Ｐ2〜Ｐ17に対し、各点Ｐ2〜Ｐ17から始点Ｐ1及び終点Ｐ18を通る線分までの距離Ｄを離間度Ｓとしてそれぞれ演算する。内点ｘの離間度ＳをＳ（ｘ）で表記するとすると、この例では、Ｓ（Ｐ2）＝６．４、Ｓ（Ｐ3）＝１０．８、Ｓ（Ｐ4）＝８．４、Ｓ（Ｐ5）＝１．２、Ｓ（Ｐ6）＝２．８、Ｓ（Ｐ7）＝５．０、Ｓ（Ｐ8）＝２．４、Ｓ（Ｐ9）＝５．６、Ｓ（Ｐ10）＝９．４、Ｓ（Ｐ11）＝１１．２、Ｓ（Ｐ12）＝９．８、Ｓ（Ｐ13）＝５．８、Ｓ（Ｐ14）＝１．２、Ｓ（Ｐ15）＝４．８、Ｓ（Ｐ16）＝７．６、Ｓ（Ｐ17）＝５．２である。
【００６１】
このため、二分木地図データ作成処理部２１は、処理Ｓ１２を実行することにより、最大離間度Ｓｍａｘ＝１１．２の内点Ｐ11が検索され、抽出される。このため、二分木地図データ作成処理部２１は、処理Ｓ１３を実行することにより、図４（Ｂ）に示すように、被分割ラインＰ1Ｐ18を内点Ｐ11で二分し、第１分割ラインＰ1Ｐ11及び第２分割ラインＰ11Ｐ18を生成する。そして、二分木地図データ作成処理部２１は、処理Ｓ１４を実行することにより、被分割ラインＰ1Ｐ18を描画するためのデータと、被分割ラインＰ1Ｐ18と第１及び第２分割ラインＰ1Ｐ11、Ｐ11Ｐ18との親子関係と、被分割ラインＰ1Ｐ18を分割した内点Ｐ11の離間度Ｓ（Ｐ11）＝１１．２との対応関係を表す二分木データを作成し、記憶部１４に一時的に記憶する。
【００６２】
第１の実施形態に係る二分木データは、そのまま二分木地図データとすべく、例えば、図７に示すようにテーブル形式で記憶される。この図７に示す二分木地図データテーブル１０１は、テーブルの各レコードを識別し特定するための識別子である管理番号を登録する管理番号フィールド１１１、被分割ラインに関するデータを登録する被分割ラインフィールド１１２、及び、分割ラインに関するデータを登録する分割ラインフィールド１１３の各フィールドを備えて構成され、被分割ラインごとにレコードが作成される。被分割ラインフィールド１１１は、さらに、被分割ラインを識別し特定するための識別子である被分割ラインの名称を登録する被分割ライン名称サブフィールド１２１、被分割ラインにおける始点の座標値を登録する始点座標サブフィールド１２２、被分割ラインにおける終点の座標値を登録する終点座標サブフィールド１２３、被分割ラインを分割する内点の離間度Ｓを登録する離間度サブフィールド１２４の各サブフィールドを備えて構成される。そして、始点座標サブフィールド１２２及び終点座標サブフィールド１２３は、それぞれ、ｘ座標サブフィールド１３１、１３３及びｙ座標サブフィールド１３２、１３４の各サブフィールドを備えて構成される。また、分割ラインフィールド１１３は、第１及び第２分割ラインを識別し特定するための識別子である第１及び第２分割ラインにおけるラインの名称を登録する第１及び第２分割ライン名称サブフィールド１２５、１２６の各サブフィールドを備えて構成される。被分割ライン及び分割ラインの名称は、任意の符号（１又は複数の記号列）でよいが、本実施形態では、ラインの始点及び終点を表す符合の組合わせで表記され、例えば、ラインの始点Ｐ1及び終点Ｐ18のラインの名称は、Ｐ1Ｐ18となる。
【００６３】
このように二分木地図データテーブル１０１が構成されるので、被分割ラインを描画するためのデータとして始点の座標値及び終点の座標値が始点座標サブフィールド１２２及び終点座標サブフィールド１２３にそれぞれ登録され、被分割ラインと分割ラインとの親子関係として被分割ラインの名称、第１分割ラインの名称及び第２分割ラインの名称が被分割ライン名称サブフィールド１２１、第１及び第２分割ライン名称サブフィールド１２５、１２６にそれぞれ登録され、被分割ラインを分割する内点の離間度Ｓが離間度サブフィールド１２４に登録され、これらが同一のレコードに登録されることでこれらの対応関係が示される。
【００６４】
そして、二分木地図データ作成処理部２１は、処理Ｓ１５を実行することにより、第１及び第２分割ラインＰ1Ｐ11、Ｐ11Ｐ18に内点が存在するか否かを判断する。この判断の結果、第１分割ラインＰ1Ｐ11には内点Ｐ2〜Ｐ10が存在し、第２分割ラインＰ11Ｐ18には内点Ｐ12〜Ｐ17が存在するから、二分木地図データ作成処理部２１は、処理Ｓ２１を実行することにより、例えば、第１分割ラインＰ1Ｐ11を新たな被分割ラインＰ1Ｐ11に置換え、処理を処理Ｓ１１に戻すと共に、第２分割ラインＰ11Ｐ18の名称Ｐ11Ｐ18を記憶部１４に記憶する。
【００６５】
このため、二分木地図データ作成処理部２１は、処理Ｓ１１を実行することにより、図４（Ｂ）に示すように、各点Ｐ2〜Ｐ10に対し、各点Ｐ2〜Ｐ10から始点Ｐ1及び終点Ｐ11を通る線分までの距離Ｄを離間度Ｓとしてそれぞれ演算する。この例では、Ｓ（Ｐ2）＝５．６、Ｓ（Ｐ3）＝８．８、Ｓ（Ｐ4）＝５．６、Ｓ（Ｐ5）＝２．８、Ｓ（Ｐ6）＝７．２、Ｓ（Ｐ7）＝１０．４、Ｓ（Ｐ8）＝９．２、Ｓ（Ｐ9）＝３．２、Ｓ（Ｐ10）＝０．４である。
【００６６】
このため、二分木地図データ作成処理部２１は、処理Ｓ１２を実行することにより、最大離間度Ｓｍａｘ＝１０．４の内点Ｐ7が検索され、抽出される。このため、二分木地図データ作成処理部２１は、処理Ｓ１３を実行することにより、図５（Ａ）に示すように、被分割ラインＰ1Ｐ11を内点Ｐ7で二分し、第１分割ラインＰ1Ｐ7及び第２分割ラインＰ7Ｐ11を生成する。そして、二分木地図データ作成処理部２１は、処理Ｓ１４を実行することにより、被分割ラインＰ1Ｐ11を描画するためのデータと、被分割ラインＰ1Ｐ11と第１及び第２分割ラインＰ1Ｐ7、Ｐ7Ｐ11との親子関係と、被分割ラインＰ1Ｐ11を分割した内点Ｐ7の離間度Ｓ（Ｐ7）＝１０．４との対応関係を表す二分木データを作成し、記憶部１４に一時的に記憶する。
【００６７】
そして、二分木地図データ作成処理部２１は、処理Ｓ１５を実行することにより、第１及び第２分割ラインＰ1Ｐ7、Ｐ7Ｐ11に内点が存在するか否かを判断する。この判断の結果、第１分割ラインＰ1Ｐ7には内点Ｐ2〜Ｐ6が存在し、第２分割ラインＰ7Ｐ11には内点Ｐ8〜Ｐ11が存在するから、二分木地図データ作成処理部２１は、処理Ｓ２１を実行することにより、例えば、第１分割ラインＰ1Ｐ7を新たな被分割ラインＰ1Ｐ7に置換え、処理を処理Ｓ１１に戻すと共に、第２分割ラインＰ7Ｐ11の名称Ｐ7Ｐ11を記憶部１４に記憶する。
【００６８】
このため、二分木地図データ作成処理部２１は、処理Ｓ１１を実行することにより、図５（Ａ）に示すように、各点Ｐ2〜Ｐ6に対し、各点Ｐ2〜Ｐ6から始点Ｐ1及び終点Ｐ7を通る線分までの距離Ｄを離間度Ｓとして演算する。この例では、Ｓ（Ｐ2）＝６．６、Ｓ（Ｐ3）＝１１．８、Ｓ（Ｐ4）＝１０．６、Ｓ（Ｐ5）＝４．６、Ｓ（Ｐ6）＝１．２である。
【００６９】
このため、二分木地図データ作成処理部２１は、処理Ｓ１２を実行することにより、最大離間度Ｓｍａｘ＝１１．８の内点Ｐ3が検索され、抽出される。このため、二分木地図データ作成処理部２１は、処理Ｓ１３を実行することにより、図５（Ｂ）に示すように、被分割ラインＰ1Ｐ7を内点Ｐ3で二分し、第１分割ラインＰ1Ｐ3及び第２分割ラインＰ3Ｐ7を生成する。そして、二分木地図データ作成処理部２１は、処理Ｓ１４を実行することにより、被分割ラインＰ1Ｐ7を描画するためのデータと、被分割ラインＰ1Ｐ7と第１及び第２分割ラインＰ1Ｐ3、Ｐ3Ｐ7との親子関係と、被分割ラインＰ1Ｐ7を分割した内点Ｐ3の離間度Ｓ（Ｐ3）＝１１．８との対応関係を表す二分木データを作成し、記憶部１４に一時的に記憶する。
【００７０】
そして、二分木地図データ作成処理部２１は、処理Ｓ１５を実行することにより、第１及び第２分割ラインＰ1Ｐ3、Ｐ3Ｐ7に内点が存在するか否かを判断する。この判断の結果、第１分割ラインＰ1Ｐ3には内点Ｐ2が存在し、第２分割ラインＰ3Ｐ7には内点Ｐ4〜Ｐ6が存在するから、二分木地図データ作成処理部２１は、処理Ｓ２１を実行することにより、第１分割ラインＰ1Ｐ3を新たな被分割ラインＰ1Ｐ3に置換え、処理を処理Ｓ１１に戻すと共に、第２分割ラインＰ3Ｐ7の名称Ｐ3Ｐ7を記憶部１４に記憶する。
【００７１】
このため、二分木地図データ作成処理部２１は、処理Ｓ１１を実行することにより、図５（Ｂ）に示すように、点Ｐ2に対し、点Ｐ2から始点Ｐ1及び終点Ｐ3を通る線分までの距離Ｄを離間度Ｓとして演算する。この例では、Ｓ（Ｐ2）＝１．４である。
【００７２】
このため、二分木地図データ作成処理部２１は、処理Ｓ１２を実行することにより、最大離間度Ｓｍａｘ＝１．４の内点Ｐ2が検索され、抽出される。このため、二分木地図データ作成処理部２１は、処理Ｓ１３を実行することにより、図６（Ａ）に示すように、被分割ラインＰ1Ｐ3を内点Ｐ2で二分し、第１分割ラインＰ1Ｐ2及び第２分割ラインＰ2Ｐ3を生成する。そして、二分木地図データ作成処理部２１は、処理Ｓ１４を実行することにより、被分割ラインＰ1Ｐ3を描画するためのデータと、被分割ラインＰ1Ｐ3と第１及び第２分割ラインＰ1Ｐ2、Ｐ2Ｐ3との親子関係と、被分割ラインＰ1Ｐ3を分割した内点Ｐ2の離間度Ｓ（Ｐ2）＝１．４との対応関係を表す二分木データを作成し、記憶部１４に一時的に記憶する。
【００７３】
そして、二分木地図データ作成処理部２１は、処理Ｓ１５を実行することにより、第１及び第２分割ラインＰ1Ｐ2、Ｐ2Ｐ3に内点が存在するか否かを判断する。この判断の結果、第１及び第２分割ラインＰ1Ｐ2、Ｐ2Ｐ3の双方に内点が存在しないから、二分木地図データ作成処理部２１は、処理Ｓ１６を実行することにより、記憶部１４を参照することによって、総ての分割ラインについて二分木処理が終了したか否かを判断する。記憶部１４には、分割ラインの名称Ｐ3Ｐ7、Ｐ7Ｐ11、Ｐ11Ｐ18が記憶されているから、二分木地図データ作成処理部２１は、総ての分割ラインについて二分木処理が終了していないと判断され、処理Ｓ２３を実行することにより、記憶部１４に記憶されている二分木処理が未処理の分割ライン、例えば、分割ラインＰ3Ｐ7を新たな被分割ラインに置換え、処理を処理Ｓ１１に戻す。ここで、処理Ｓ２１における分割ラインの名称を記憶部１４に記憶する場合は、分割ラインの名称を順にスタックし、処理Ｓ２３における新たな被分割ラインに置き換える分割ラインの取り出しは、ラースト・イン・ファースト・アウト（Last In First Out）としてもよい。
【００７４】
分割ラインＰ3Ｐ7、Ｐ7Ｐ11、Ｐ11Ｐ18についても同様に処理され、処理Ｓ１６を実行することにより二分木地図データ作成処理部２１が総ての分割ラインについて二分木処理が終了したと判断されると、記憶部１４には、ラインＰ1Ｐ18に対し図７に示す二分木地図データテーブル１０１が作成、完成され、記憶部１４の二分木地図データ記憶部３４に記憶される。
【００７５】
ラインＰ1Ｐ18に対しこのような二分木処理が実行されると、ラインＰ1Ｐ18のラインデータは、図７に示す二分木地図データテーブル１０１の二分木地図データに変換される。
【００７６】
また、被分割ラインの名称及び被分割ラインを分割する内点の離間度Ｓを上位層の節点である親節点に割り当て、第１及び第２分割ラインの各名称を親節点から２個に分岐した下位層の節点である第１及び第２子節点にそれぞれ割り当てると共に、被分割ラインと第１及び第２分割ラインとの親子関係を親節点と第１及び第２子節点とを結ぶ線分（「枝」と呼称する。）で表すツリー構造で示すと、ラインＰ1Ｐ18のラインデータを変換した二分木地図データは、図８に示すツリー構造になる。なお、最初の親節点を「根」と呼称し、２個に分岐しない末端の節点を「葉」と呼称する。
【００７７】
図８に示すツリー構造は、第０階層及び第1階層において、ラインＰ1Ｐ18をツリー構造の根（ルート）として、まず、ラインＰ1Ｐ18が離間度Ｓ（Ｐ11）＝１１．２で子の第１分割ラインＰ1Ｐ11及び第２分割ラインＰ11Ｐ18に分かれている。第１階層及び第２階層において、第１分割ラインＰ1Ｐ11を新たな被分割ラインＰ1Ｐ11とすると共に親として、ラインＰ1Ｐ11が離間度Ｓ（Ｐ7）＝１０．４で子の第１分割ラインＰ1Ｐ7及び第２分割ラインＰ7Ｐ11に分かれ、そして、第２分割ラインＰ11Ｐ18を新たな被分割ラインＰ11Ｐ18とすると共に親として、ラインＰ11Ｐ18が離間度Ｓ（Ｐ16）＝９．８で子の第１分割ラインＰ11Ｐ16及び第２分割ラインＰ16Ｐ18に分かれている。第２階層及び第３階層において、第１分割ラインＰ1Ｐ7を新たな被分割ラインＰ1Ｐ7とすると共に親として、ラインＰ1Ｐ7が離間度Ｓ（Ｐ3）＝１１．８で子の第１分割ラインＰ1Ｐ3及び第２分割ラインＰ3Ｐ7に分かれ、第２分割ラインＰ7Ｐ11を新たな被分割ラインＰ7Ｐ11とすると共に親として、ラインＰ7Ｐ11が離間度Ｓ（Ｐ10）＝１．２で子の第１分割ラインＰ7Ｐ10及び第２分割ラインＰ10Ｐ11に分かれている。そして、第１分割ラインＰ11Ｐ16を新たな被分割ラインＰ11Ｐ16とすると共に親として、ラインＰ11Ｐ16が離間度Ｓ（Ｐ13）＝２．２で子の第１分割ラインＰ11Ｐ13及び第２分割ラインＰ13Ｐ16に分かれ、第２分割ラインＰ16Ｐ18を新たな被分割ラインＰ16Ｐ18とすると共に親として、ラインＰ16Ｐ18が離間度Ｓ（Ｐ17）＝１．６で子の第１分割ラインＰ16Ｐ17及び第２分割ラインＰ17Ｐ16に分かれている。第３階層及び第４階層において、第１分割ラインＰ1Ｐ3を新たな被分割ラインＰ1Ｐ3とすると共に親として、ラインＰ1Ｐ3が離間度Ｓ（Ｐ2）＝１．４で子の第１分割ラインＰ1Ｐ2及び第２分割ラインＰ2Ｐ3に分かれ、第２分割ラインＰ3Ｐ7を新たな被分割ラインＰ3Ｐ7とすると共に親として、ラインＰ3Ｐ7が離間度Ｓ（Ｐ6）＝１．６で子の第１分割ラインＰ3Ｐ6及び第２分割ラインＰ6Ｐ7に分かれている。第１分割ラインＰ7Ｐ10を新たな被分割ラインＰ7Ｐ10とすると共に親として、ラインＰ7Ｐ10が離間度Ｓ（Ｐ8）＝１．４で子の第１分割ラインＰ7Ｐ8及び第２分割ラインＰ8Ｐ10に分かれている。そして、第１分割ラインＰ11Ｐ13を新たな被分割ラインＰ11Ｐ13とすると共に親として、ラインＰ11Ｐ13が離間度Ｓ（Ｐ12）＝１．０で子の第１分割ラインＰ11Ｐ12及び第２分割ラインＰ12Ｐ13に分かれ、第２分割ラインＰ13Ｐ16を新たな被分割ラインＰ13Ｐ16とすると共に親として、ラインＰ13Ｐ16が離間度Ｓ（Ｐ15）＝１．２で子の第１分割ラインＰ13Ｐ15及び第２分割ラインＰ15Ｐ16に分かれている。第４階層及び第５階層において、第１分割ラインＰ3Ｐ6を新たな被分割ラインＰ3Ｐ6とすると共に親として、ラインＰ3Ｐ6が離間度Ｓ（Ｐ4）＝１．２で子の第１分割ラインＰ3Ｐ4及び第２分割ラインＰ4Ｐ6に分かれている。第２分割ラインＰ8Ｐ10を新たな被分割ラインＰ8Ｐ10とすると共に親として、ラインＰ8Ｐ10が離間度Ｓ（Ｐ9）＝０．３で子の第１分割ラインＰ8Ｐ9及び第２分割ラインＰ9Ｐ10に分かれている。そして、第１分割ラインＰ13Ｐ15を新たな被分割ラインＰ13Ｐ15とすると共に親として、ラインＰ13Ｐ15が離間度Ｓ（Ｐ14）＝０．１で子の第１分割ラインＰ13Ｐ14及び第２分割ラインＰ14Ｐ15に分かれている。第５階層及び第６階層において、第２分割ラインＰ4Ｐ6を新たな被分割ラインＰ4Ｐ6とすると共に親として、ラインＰ4Ｐ6が離間度Ｓ（Ｐ5）＝０．１で子の第１分割ラインＰ4Ｐ5及び第２分割ラインＰ5Ｐ6に分かれている。
【００７８】
このようなツリー構造の二分木地図データは、例えば、被分割ラインを描画するための始点及び終点の各座標値と、離間度Ｓと、第１及び第２分割ラインのデータを格納するメモリアドレスとを一つのメモリアドレスに格納することによっても表記することができ、親子関係は、メモリアドレスの相互関係で示され、被分割ラインのデータを格納するメモリアドレスと、この被分割ラインのデータにおける第１及び第２分割ラインのデータを格納するメモリアドレスとの関係で示される。より具体的には、ツリー構造の二分木地図データは、例えば、ツリー構造の節点をＣ言語の構造体に対応させ、構造体に被分割ラインを描画するための始点及び終点の各座標値と、離間度Ｓと、第１及び第２分割ラインのデータを格納するポインタ変数を含ませることによって表記され、ポインタによって親子関係が示される。
【００７９】
なお、図４（Ｂ）には、分割ラインＰ11Ｐ18における各内点Ｐ11〜Ｐ18の離間度Ｓも示されている。図５（Ａ）には、分割ラインＰ7Ｐ11における各内点Ｐ8〜Ｐ10の離間度Ｓも示され、分割ラインＰ11Ｐ18がその最大離間度の内点Ｐ16で分割されている様子、分割ラインＰ11Ｐ16における各内点Ｐ12〜Ｐ15の離間度Ｓ及び分割ラインＰ16Ｐ18における内点Ｐ17の離間度Ｓも示されている。図５（Ｂ）には、分割ラインＰ3Ｐ7における各内点Ｐ4〜Ｐ6の離間度Ｓも示され、分割ラインＰ7Ｐ11がその最大離間度の内点Ｐ10で分割されている様子、及び、分割ラインＰ7Ｐ10における各内点Ｐ8、Ｐ9の離間度Ｓも示され、分割ラインＰ11Ｐ16がその最大離間度の内点Ｐ13で分割されている様子、分割ラインＰ11Ｐ13における内点Ｐ12の離間度Ｓ、及び、分割ラインＰ13Ｐ16における各内点Ｐ12〜Ｐ15の離間度Ｓも示され、そして、分割ラインＰ16Ｐ18がその最大離間度の内点Ｐ17で分割されている様子も示されている。図６（Ａ）には、分割ラインＰ3Ｐ7がその最大離間度の内点Ｐ6で分割されている様子、及び、分割ラインＰ3Ｐ6における各内点Ｐ4、Ｐ5の離間度Ｓも示され、分割ラインＰ7Ｐ10がその最大離間度の内点Ｐ8で分割されている様子、及び、分割ラインＰ8Ｐ10における内点Ｐ9の離間度Ｓも示され、分割ラインＰ11Ｐ13がその最大離間度の内点Ｐ12で分割されている様子も示され、そして、分割ラインＰ13Ｐ16がその最大離間度の内点Ｐ15で分割されている様子、及び、分割ラインＰ13Ｐ15における内点Ｐ14の離間度Ｓも示されている。そして、図６（Ｂ）には、分割ラインＰ3Ｐ6がその最大離間度の内点Ｐ4で分割されている様子、及び、分割ラインＰ4Ｐ6における内点Ｐ5の離間度Ｓが示され、分割ラインＰ8Ｐ10がその最大離間度の内点Ｐ9で分割されている様子が示され、分割ラインＰ13Ｐ15がその最大離間度の内点Ｐ14で分割されている様子が示されている。
【００８０】
次に、二分木地図データ作成出力装置１が二分木地図データから間引き度に応じた地図を出力する動作について説明する。
【００８１】
図９は、第１の実施形態に係る二分木地図データ作成出力装置における二分木地図データから間引き度に応じた地図を出力する動作を示すフローチャートである。
【００８２】
例えば、ユーザが上述の動作によって二分木地図データ作成出力装置１に二分木地図データを作成させることによって、あるいは、二分木地図データを記録した記録媒体から外部記憶部１６を介してインストールすることによって、第１の実施形態に係る二分木地図データが記憶部１４の二分木地図データ記憶部３４に記憶される。そして、記憶部１４の出力地図作成プログラム記憶部３２から第１の実施形態に係る出力地図作成プログラムが呼び出されて実行され、例えば、ユーザが、二分木元地図データから間引き度Ｔに応じた地図を二分木地図データ作成出力装置１に出力させるべく、地図の出力開始コマンドを入力部１２から入力すると、演算処理部１１の出力地図作成処理部２２は、記憶部１４の二分木地図データ記憶部３４に記憶されている二分木地図データに基づいて間引き度Ｔに応じた地図を出力する。
【００８３】
即ち、図９において、まず、演算処理部１１の出力地図作成処理部２２は、ユーザに間引き度Ｔの入力を促し、ユーザが入力部１２から間引き度Ｔを入力することによって、間引き度を受付ける（Ｓ３０）。次に、出力地図作成処理部２２は、二分木地図データから一のラインのデータを取り出し、この取り出したラインのデータから根のデータを最初の被分割ラインのデータとして取り出す（Ｓ３１）。ここで、二分木地図データから根のデータを取り出すために、例えば、根のデータであることを示す符号（１又は複数の記号列）を根のデータに付したり、二分木地図データの特定の領域に根のデータを登録したり等すればよい。例えば、図７に示す二分木地図データテーブル１０１をラインごとに用意し、各二分木地図データにおいて、当該ラインの根のデータを常に管理番号１のレコードに登録するように構成する。
【００８４】
次に、出力地図作成処理部２２は、被分割ラインのデータにおける離間度Ｓと間引き度Ｔとの大小関係を比較し、被分割ラインのデータにおける離間度Ｓが間引き度Ｔ以下であるか否かを判断する（Ｓ３２）。
【００８５】
ここで、被分割ラインのデータにおける離間度Ｓが間引き度Ｔより大きい場合では、この離間度Ｓの内点は、当該被分割ラインの始点と終点とを結ぶ線分から間引き度より大きく離れているので、当該被分割ラインは、少なくともこの離間度Ｓの内点で折れる折れ線で描画する必要がある。つまり、当該被分割ラインの分割ラインに対してさらにそのデータにおける離間度Ｓが間引き度Ｔ以下であるか否かを判断する必要がある。一方、被分割ラインのデータにおける離間度Ｓが間引き度Ｔ以下である場合では、当該被分割ラインの内点は、当該被分割ラインの始点と終点とを結ぶ線分から間引き度Ｔ以下の離間度Ｓでしか離れていないので、当該被分割ラインの内点は、間引いてよい。つまり、当該被分割ラインの内点は、描画のデータとして採用しなくてもよく、当該被分割ラインを当該被分割ラインの始点及び終点を結ぶ線分で描画してよい。
【００８６】
従って、処理Ｓ３２における判断の結果、被分割ラインのデータにおける離間度Ｓが間引き度Ｔより大きい場合（Ｎｏ）には、出力地図作成処理部２２は、当該被分割ラインの分割ラインを未処理データとして記憶部１４に記憶する（Ｓ３３）。そして、出力地図作成処理部２２は、記憶部１４に記憶されている未処理データから一の分割ラインを取り出し、この取り出した分割ラインを新たな被分割ラインとして置換え（Ｓ３４）、処理を処理Ｓ３２に戻す。このように動作することによって被分割ラインの内点がユーザの間引き度Ｔに対応して間引くことが可能か否かが判断され、ツリー構造で言えば、第０階層の根から末端の下位の階層に向けて順に、深さ優先探索で判断される。
【００８７】
ここで、処理Ｓ３３における分割ラインを未処理データとして記憶部１４に記憶する場合は、分割ラインにおけるラインの名称を順にスタックし、処理Ｓ３４における新たな被分割ラインに置き換える分割ラインの取り出しは、ラースト・イン・ファースト・アウトとしてもよい。
【００８８】
一方、処理Ｓ３２における判断の結果、被分割ラインの二分木データにおける離間度Ｓが間引き度Ｔ以下である場合では、出力地図作成処理部２２は、当該被分割ラインの内点を間引いて、当該被分割ラインを当該被分割ラインの始点及び終点の各座標値を出力部１３に出力する（Ｓ４１）。出力部１３は、この始点及び終点を結ぶ線分を描画する。このように動作することによって当該被分割ラインの内点を間引いて当該被分割ラインが出力され、当該被分割ラインに含まれる各分割ラインに対し、当該分割ラインの内点をユーザの間引き度に対応して間引くことが必要であるか否かを判断する必要がない。ツリー構造で言えば、当該被分割ラインの階層より末端の下位の階層における分割ラインに対し、ユーザの間引き度Ｔに対応して間引くことが必要であるか否かを判断する必要がない。即ち、データの処理時間が省略され、ユーザの間引き度Ｔに応じた地図が高速に出力される。
【００８９】
そして、出力地図作成処理部２２は、分割ラインで未処理データがあるか否かを判断する（Ｓ４２）。処理Ｓ４２における判断の結果、未処理データがある場合（Ｙｅｓ）には、出力地図作成処理部２２は、記憶部１４に記憶されている未処理データから一の分割ラインを取り出し、この取り出した分割ラインを新たな被分割ラインとして置換え（Ｓ４３）、処理を処理Ｓ３２に戻す。一方、処理Ｓ４２における判断の結果、未処理データがない場合（Ｎｏ）には、出力地図作成処理部２２は、上述の処理Ｓ３２乃至処理Ｓ３４及び処理Ｓ４１乃至処理Ｓ４３の間引き処理が未処理の、二分木地図データにおけるラインがあるか否かを判断する（Ｓ３５）。
【００９０】
処理Ｓ３５における判断の結果、二分木地図データにおいて間引き処理が未処理のラインがある場合（Ｙｅｓ）には、出力地図作成処理部２２は、二分木地図データの他のラインについて間引き処理を実行すべく、処理を処理Ｓ３２に戻して上述の処理Ｓ３２乃至処理Ｓ３４及び処理Ｓ４１乃至処理Ｓ４３の処理を続行する。一方、処理Ｓ３５における判断の結果、二分木地図データにおいて間引き処理が未処理のラインがない場合（Ｎｏ）には、出力地図作成処理部２２は、処理を終了する。
【００９１】
このように動作することによって二分木地図データ作成出力装置１は、二分木地図データからユーザの間引き度Ｔに応じた地図を出力することができる。そして、二分木地図データ作成出力装置１は、地図の被分割ライン（元のライン及び分割ライン）を出力する場合、被分割ラインを分割する内点の離間度Ｓとユーザが入力した間引き度Ｔを比較することにより当該離間度Ｓが間引き度Ｔ以下である場合には、当該被分割ラインに含まれる各分割ラインに対し、当該分割ラインの内点をユーザの間引き度Ｔに対応して間引くことが必要であるか否かを判断する必要がない。従って、二分木地図データ作成出力装置１は、データの処理時間が省略され、ユーザの間引き度Ｔに応じた地図を高速に出力し得る。このため、ユーザは、利用目的に応じて間引いた地図を二分木地図データ作成出力装置１によって容易に、高速に得ることができる。そして、間引き度Ｔと縮尺とを適宜に対応付けることにより、二分木地図データ作成出力装置１は、任意縮尺の地図を容易に、高速に作成することができる。また、間引き度Ｔとサイズとを適宜に対応付けることにより、二分木地図データ作成出力装置１は、任意サイズに応じた地図を容易に、高速に作成することができる。さらに、間引き度Ｔと解像度とを適宜に対応付けることにより、二分木地図データ作成出力装置１は、任意解像度に応じた地図を容易に、高速に作成することができる。
【００９２】
上述から分かるように、二分木地図データから間引き度に応じて作成される地図は、二分木地図データを構成する各ラインデータに対し間引き処理を実行し、その結果得られた各被分割ライン（元のライン及び分割ライン）を順に出力するものである。このため、図９に示す処理をより具体的に説明するために、一具体例として図７に示す二分木地図データテーブル１０１を用いて、１つのラインを出力する場合について以下に説明する。
【００９３】
図１０は、記憶部１４に未処理データとして記憶される分割ラインの様子を示す図である。図１１は、間引き処理後のラインを示す図である。
【００９４】
図７に示す二分木地図データから間引き度に応じた地図を出力すべく、二分木地図データ作成出力装置１が動作すると、演算処理部１１の出力地図作成処理部２２は、処理Ｓ３０を実行する。出力地図作成処理部２２は、処理Ｓ３０で例えば間引き度Ｔ＝５が入力されると、処理Ｓ３１を実行することにより、被分割ラインのデータとしてラインＰ1Ｐ18の根のデータを取り出すべく、図７に示す例では、二分木地図データテーブル１０１から管理番号１のレコードにおけるデータを取り出す。
【００９５】
そして、出力地図作成処理部２２は、処理Ｓ３２を実行することにより、この取り出した被分割ラインＰ1Ｐ18のデータにおける離間度Ｓ（Ｐ11）＝１１．２が間引き度Ｔ＝５以下であるか否かを判断する。判断の結果、離間度Ｓが間引き度Ｔよりも大きいので、出力地図作成処理部２２は、処理Ｓ３３を実行することにより、被分割ラインＰ1Ｐ18のデータからその第１及び第２分割ラインＰ1Ｐ11、Ｐ11Ｐ18を記憶部１４に記憶する（図１０（Ａ）参照）。次に、出力地図作成処理部２２は、処理Ｓ３４を実行することにより、記憶部１４に記憶されている分割ラインＰ1Ｐ11、Ｐ11Ｐ18から例えばラースト・イン・ファースト・アウトで分割ラインＰ1Ｐ11を取り出し（図１０（Ｂ）参照）、この取り出した分割ラインＰ1Ｐ11を新たな被分割ラインＰ1Ｐ11に置換え、処理をＳ３２に戻す。
【００９６】
処理が戻され、出力地図作成処理部２２は、処理Ｓ３２を実行することにより、この被分割ラインＰ1Ｐ11のデータにおける離間度Ｓ（Ｐ7）＝１０．４が間引き度Ｔ＝５以下であるか否かを判断する。判断の結果、離間度Ｓが間引き度Ｔよりも大きいので、出力地図作成処理部２２は、処理Ｓ３３を実行することにより、被分割ラインＰ1Ｐ11のデータからその第１及び第２分割ラインＰ1Ｐ7、Ｐ7Ｐ11を記憶部１４に記憶する（図１０（Ｃ）参照）。次に、出力地図作成処理部２２は、処理Ｓ３４を実行することにより、記憶部１４に記憶されている分割ラインＰ1Ｐ7、Ｐ7Ｐ11、Ｐ11Ｐ18から例えば分割ラインＰ1Ｐ7を取り出し（図１０（Ｄ）参照）、この取り出した分割ラインＰ1Ｐ7を新たな被分割ラインＰ1Ｐ7に置換え、処理をＳ３２に戻す。
【００９７】
処理が戻され、出力地図作成処理部２２は、処理Ｓ３２を実行することにより、このラインＰ1Ｐ7のデータにおける離間度Ｓ（Ｐ3）＝１１．８が間引き度Ｔ＝５以下であるか否かを判断する。判断の結果、離間度Ｓが間引き度Ｔよりも大きいので、出力地図作成処理部２２は、処理Ｓ３３を実行することにより、被分割ラインＰ1Ｐ7のデータからその第１及び第２分割ラインＰ1Ｐ3、Ｐ3Ｐ7を記憶部１４に記憶する（図１０（Ｅ）参照）。次に、出力地図作成処理部２２は、処理Ｓ３４を実行することにより、記憶部１４に記憶されている分割ラインＰ1Ｐ3、Ｐ3Ｐ7、Ｐ7Ｐ11、Ｐ11Ｐ18から例えば分割ラインＰ1Ｐ3を取り出し（図１０（Ｆ）参照）、この取り出した分割ラインＰ1Ｐ3を新たな被分割ラインＰ1Ｐ3に置換え、処理をＳ３２に戻す。
【００９８】
処理が戻され、出力地図作成処理部２２は、処理Ｓ３２を実行することにより、このラインＰ1Ｐ3のデータにおける離間度Ｓ（Ｐ2）＝１．４が間引き度Ｔ＝５以下であるか否かを判断する。判断の結果、離間度Ｓが間引き度Ｔよりも小さいので、出力地図作成処理部２２は、処理Ｓ４１を実行することにより、被分割ラインＰ1Ｐ3のデータからその始点Ｐ1の座標値（ｘ1、ｙ1）及び終点Ｐ3の座標値（ｘ3、ｙ3）を取り出し、始点Ｐ1及び終点Ｐ3を結ぶ線分を出力部１３に出力する。次に、出力地図作成処理部２２は、処理Ｓ４２を実行することにより、記憶部１４に未処理データとして分割ラインが記憶されているか否かを判断する。判断の結果、記憶部１４には分割ラインＰ3Ｐ7、Ｐ7Ｐ11、Ｐ11Ｐ18が記憶されているので、未処理データとしての分割ラインがあると判断され、出力地図作成処理部２２は、処理Ｓ４３を実行することにより、例えば分割ラインＰ3Ｐ7を取り出し（図１０（Ｇ）参照）、この取り出した分割ラインＰ3Ｐ7を新たな被分割ラインＰ3Ｐ7に置換え、処理をＳ３２に戻す。
【００９９】
処理が戻され、未処理データとしての分割ラインＰ3Ｐ7、Ｐ7Ｐ11、Ｐ11Ｐ18についても同様に処理されることにより、記憶部１４の記憶内容が図１０（Ｈ）から図１０（Ｌ）まで順に変化しながら、分割ラインＰ3Ｐ7の始点Ｐ3及び終点Ｐ7を結ぶ線分、分割ラインＰ7Ｐ11の始点Ｐ7及び終点Ｐ11を結ぶ線分、分割ラインＰ11Ｐ16の始点Ｐ11及び終点Ｐ16を結ぶ線分、分割ラインＰ16Ｐ18の始点Ｐ16及び終点Ｐ18を結ぶ線分がこの順で出力部１３に出力される。なお、図１０（Ｉ）、図１０（Ｌ）は、記憶部１４に未処理データとしての分割ラインが記憶されていない状態を示している。
【０１００】
図３（Ｂ）に示すラインＰ1Ｐ18は、図７に示す二分木地図データテーブル１０１に基づいてこのように処理されることにより、間引き度Ｔ＝５の場合には、図１１に示すように、分割ラインＰ1Ｐ3、分割ラインＰ3Ｐ7、分割ラインＰ7Ｐ11、分割ラインＰ11Ｐ16及び分割ラインＰ16Ｐ18を結ぶ線分として出力部１３に出力され、描画される。
【０１０１】
ここで、ツリー構造の二分木地図データをＣ言語の構造体を用いて表記した場合には、例えば、ツリー構造の根から一つの分岐における末端の葉に向けて、当該節点における離間度Ｓと間引き度Ｔとを比較しながら各節点のデータを辿り、比較の結果、離間度Ｓが間引き度Ｔ以下になったところで当該節点のデータにおける被分割ラインを描画すべく出力し、未処理の分岐を持つ上位階層の節点に上がる。この未処理の分岐を処理すべく、同様に、末端の葉に向けて当該節点における離間度Ｓと間引き度Ｔとを比較しながら各節点のデータを辿り、比較の結果、離間度Ｓが間引き度Ｔ以下になったところで当該節点のデータにおける被分割ラインを描画すべく出力し、未処理の分岐を持つ上位階層の節点に上がる。このような処理を未処理の分岐が無くなるまで繰り返すことによって二分木地図データから間引き度Ｔに応じた地図を出力する動作が行われる。このとき、出力されるラインに対応する節点とそれより上位階層に位置する節点しか探索しないことから、計算に要するステップ数が出力すべきラインの本数に略比例する数で抑えることができる。ツリー構造の二分木地図データをＣ言語の構造体を用いて表記した場合には、ポインタを用いて親子関係を辿れるので、より高速に二分木地図データから間引き度Ｔに応じた地図をそのデータサイズに略比例する計算量だけで出力することができる。
【０１０２】
次に、別の実施形態について説明する。
（第２の実施形態の構成）
上述した第１の実施形態に係る二分木地図データ作成出力装置１では、二分木地図データは、被分割ラインとされたライン及び分割ラインについてデータを備えればよいので、二分木地図データの容量は、少なくいて済むが、地図を出力する場合にツリー構造で言えば根のデータから下位の階層に向けて深さ優先探索で各データを間引き処理する必要があり、データ処理効率の点で改善する余地がある。
【０１０３】
そこで、第２の実施形態に係る二分木地図データ作成出力装置２は、元地図データから二分木地図データを作成する場合には、上述のように作成されるツリー構造の二分木地図データに対し、さらにツリー構造における各離間度Ｓを、ライン（根）から内点を持たない分割ライン（葉）までの親から子孫まで、被分割ラインを第１及び第２分割ラインに分割する際の離間度Ｓを順次に辿った場合に、当該分割する際の離間度Ｓを含め子孫側の離間度Ｓのうちの最大値で置き換え、ライン及び総ての分割ラインのデータを備えるように二分木地図データを構成し、二分木地図データに基づいて間引き度Ｔに応じた地図を出力する場合には、ライン及び各分割ラインにおける後述の親離間度Ｓｐ及び子離間度Ｓｃと間引き度Ｔとを比較し、所定の条件を満たすライン及び分割ラインを抽出することにより、間引き度Ｔに応じた地図を出力するものである。
【０１０４】
このため、第２の実施形態に係る二分木地図データ作成出力装置２は、第１の実施形態に係る二分木地図データ作成出力装置１における二分木地図データ作成プログラム記憶部３１及び出力地図作成プログラム記憶部３２の代わりに、後述のように動作する第２の実施形態に係る二分木地図データ作成プログラム及び出力地図作成プログラムをそれぞれ記憶する二分木地図データ作成プログラム記憶部５１及び出力地図作成プログラム記憶部５２が備えられ、第１の実施形態に係る二分木地図データ作成出力装置１における二分木地図データ作成処理部２１及び出力地図作成処理部２２の代わりに、第２の実施形態に係る二分木地図データ作成処理部４１及び出力地図作成処理部４２が備えられ、第１の実施形態に係る二分木地図データ作成出力装置１における二分木地図データ記憶部３４の代わりに、二分木地図データ作成処理部４１が作成した後述の二分木地図データを記憶する二分木地図データ記憶部５４が備えられる点を除き、第１の実施形態に係る二分木地図データ作成出力装置１の構成と同様であるので、その説明を省略する。
【０１０５】
この第２の実施形態に係る二分木地図データ作成処理部４１は、後述の動作によって元地図データから第２の実施形態に係る二分木地図データを作成するものであり、本実施形態では、被分割ラインにおける始点及び終点の各座標値と、親離間度Ｓｐとして被分割ラインを生成する際の離間度Ｓと、子離間度Ｓｃとして被分割ラインの始点及び終点の間における被分割ライン上に在る内点の離間度Ｓのうちの最大の離間度Ｓｍａｘと、最大の離間度Ｓｍａｘを持つ内点で被分割ラインを２個に分割することによって生成された第１及び第２分割ラインと当該被分割ラインを生成した被分割ラインとの対応関係である親子関係を表す親子関係情報とを対応付けて備え、被分割ラインが、始点及び終点の各座標値と前記始点及び終点の間における当該線上に在る内点の座標値とを備える地図上に線で表され得るライン、及び、被分割ラインを最大の離間度を持つ内点で２個に分割することによって生成される総ての第１及び第２分割ラインであって、親離間度Ｓｐ及び子離間度Ｓｃは、ラインから内点を持たない分割ラインまでの親から子孫まで被分割ラインを第１及び第２分割ラインに分割する際の離間度Ｓを順次に辿った場合に、当該分割する際の離間度Ｓを含め子孫側の離間度Ｓのうちの最大値で置き換えた値である第２の実施形態に係る二分木地図データを作成するものである。より具体的には、二分木地図データ作成処理部４１は、例えば、本実施形態では、離間度演算部２１１と、被分割ライン分割処理部２１２と、ライン分割処理部２１３と、被分割ライン分割処理部２１２で被分割ラインを分割する際の最大の離間度Ｓｍａｘを子離間度Ｓｃとすると共に被分割ラインを生成する際の離間度Ｓを親離間度Ｓｐとして、親離間度Ｓｐ及び子離間度Ｓｃを、ラインから内点を持たない分割ラインまでの親から子孫まで被分割ラインを第１及び第２分割ラインに分割する際の離間度Ｓを順次に辿った場合に、当該分割する際の離間度Ｓを含め子孫側の離間度Ｓのうちの最大値で置き換える置換処理部４１５（図１に破線で示す。）と、第１の実施形態における作成処理部２１４の代わりに、ライン及び総ての分割ラインにおける始点及び終点の各座標値と、置換処理部４１５で処理された親離間度Ｓｐと、置換処理部４１５で処理された子離間度Ｓｃと、被分割ライン分割処理部２１２で生成された第１及び第２分割ラインと当該被分割ラインを生成した被分割ラインとの対応関係である親子関係を表す親子関係情報とを対応付けて備える二分木地図データを作成する作成処理部４１４とを備える。
【０１０６】
また、第２の実施形態に係る出力地図作成処理部４２は、後述の動作によって二分木地図データに基づく間引き度Ｔに応じた地図を作成してこの作成した地図を出力部１３に出力するものであり、被分割ラインの親離間度Ｓｐ及び子離間度Ｓｃと入力部１２で入力された間引き度Ｔとを順次に比較し、比較した結果、間引き度Ｔより大きい親離間度Ｓｐを持ち、かつ、間引き度Ｔ以下の子離間度Ｓｃを持つ被分割ラインにおける始点及び終点の各座標値を取得し、出力部１３に出力するものである。
【０１０７】
次に、本実施形態の動作について説明する。
（第２の実施形態の動作）
まず、二分木地図データ作成出力装置２が元地図データから二分木地図データを作成する動作について説明する。
【０１０８】
図１２は、第２の実施形態に係る二分木地図データ作成出力装置における二分木地図データを作成する動作を示すフローチャートである。図１３は、第２の実施形態に係る二分木地図データ作成出力装置における離間度の置換処理の動作を示すフローチャートである。図１４は、第２の実施形態に係るテーブルで表現した二分木地図データ（置換処理前）を示す図である。図１５は、第２の実施形態に係るテーブルで表現した二分木地図データ（置換処理後）を示す図である。図１６は、第２の実施形態に係るツリー構造で表現した二分木地図データを示す図である。
【０１０９】
例えば、第１の実施形態と同様に、元地図データが記憶部１４の元地図データ記憶部３３に記憶され、記憶部１４の二分木地図データ作成プログラム記憶部５１から二分木地図データ作成プログラムが呼び出されて実行され、ユーザが二分木地図データの作成開始コマンドを入力部１２から入力すると、演算処理部１１の二分木地図データ作成処理部４１は、記憶部１４の元地図データ記憶部３３に記憶されている元地図データに基づいて二分木地図データを作成する。
【０１１０】
即ち、図１２において、まず、演算処理部１１の二分木地図データ作成処理部４１は、ライン分割処理部２１３によって、元地図データのラインデータを二分木地図データに変換すべく、元地図データから一のラインデータを取り出す（Ｓ５０）。
【０１１１】
続けて二分木地図データ作成処理部４１が実行する、各内点の離間度を演算する処理（Ｓ５１）、最大離間度の内点を検索し抽出する処理（Ｓ５２）、及び、ラインを二分する処理（Ｓ５３）は、図２に基づいて上述した第１の実施形態における二分木地図データ作成処理部２１が実行する、処理Ｓ１１、処理Ｓ１２及び処理Ｓ１３とそれぞれ同様であるので、その説明を省略する。
【０１１２】
そして、次に、二分木地図データ作成処理部４１は、作成処理部４１４によって、当該ラインを描画するためのデータ、当該ラインと分割ライン（第１及び第２分割ライン）との関係、当該ラインが生成される際の内点の離間度Ｓ（親離間度Ｓｐ）、及び、当該ラインを分割する内点の離間度Ｓ（子離間度Ｓｃ）の対応関係を表す第２の実施形態に係る二分木データを作成し、記憶部１４に一時的に記憶する（Ｓ５４）。
【０１１３】
第２の実施形態に係る二分木データは、そのまま二分木地図データとすべく、例えば、図１４及び図１５に示すようにテーブル形式で記憶される。この図１４及び図１５に示す二分木地図データテーブル２０１’、２０１は、テーブルの各レコードを識別し特定するための識別子である管理番号を登録する管理番号フィールド２１１、被分割ラインに関するデータを登録する被分割ラインフィールド２１２、当該被分割ラインに対する親子関係に関するデータを登録する親子関係フィールド２１３、及び、当該被分割ラインに対する離間度Ｓに関するデータを登録する離間度フィールド２１４の各フィールドを備えて構成され、ライン及び総ての分割ラインごとにレコードが作成される。被分割ラインフィールド２１２は、さらに、被分割ラインを識別し特定するための識別子であるラインの名称を登録する被分割ライン名称サブフィールド２２１、当該被分割ラインにおける始点の座標値を登録する始点座標サブフィールド２２２、及び、当該被分割ラインにおける終点の座標値を登録する終点座標サブフィールド２２３の各サブフィールドを備えて構成される。そして、始点座標サブフィールド２２２及び終点座標サブフィールド２２３は、それぞれ、ｘ座標サブフィールド２３１、２３３及びｙ座標サブフィールド２３２、２３４の各サブフィールドを備えて構成される。また、親子関係フィールド２１３は、さらに、最大離間度Ｓｍａｘの内点で二分割されることによって当該被分割ラインを生成した被分割ライン（親のライン）を識別し特定するための識別子であるラインの名称を登録する被分割ライン名称サブフィールド２２４、及び、当該被分割ラインを二分割することによって生成される第１及び第２分割ライン（子のライン）に関するデータを登録する分割ラインサブフィールド２２５の各サブフィールドを備えて構成される。分割ラインサブフィールド２２５は、第１及び第２分割ラインを識別し特定するための識別子であるラインの名称を登録する第１及び第２分割ライン名称サブフィールド２３５、２３６の各サブフィールドを備えて構成される。離間度フィールド２１４は、さらに、当該被分割ラインを生成する際に被分割ラインを二分割した内点の離間度（親離間度Ｓｐ）を登録する親離間度サブフィールド２２６、及び、当該被分割ラインを二分割する内点の離間度（子離間度Ｓｃ）を登録する子離間度サブフィールド２２７の各サブフィールドを備えて構成される。なお、ツリー構造の根となる最初のラインに対しては、被分割ライン名称及び親離間度Ｓｐは、存在しないので、被分割ライン名称サブフィールド２２４には、値が存在しないことを示す符号、例えば「＊」が記憶部１４に一時的に記憶され、親離間度サブフィールド２２６には、間引き度Ｔとして入力部１２から入力されることがないほど、充分に大きな値、例えば「９９９９９」が記憶部１４に一時的に記憶される。
【０１１４】
このように二分木地図データテーブル２０１’、２０１が構成されるので、被分割ラインを描画するためのデータとして始点の座標値及び終点の座標値が始点座標サブフィールド２２２及び終点座標サブフィールド２２３にそれぞれ登録され、被分割ラインと分割ラインとの親子関係として被分割ラインの名称、第１及び第２分割ラインの各名称が被分割ライン名称サブフィールド２２４、第１及び第２分割ライン名称サブフィールド２３５、２３６にそれぞれ登録され、親離間度Ｓｐ及び子離間度Ｓｃが親離間度サブフィールド２２６及び子離間度サブフィールド２２７にそれぞれ登録され、これらが同一のレコードに登録されることでこれらの対応関係が示される。
【０１１５】
続けて二分木地図データ作成処理部４１が実行する、第１及び第２分割ラインに内点が存在するか否かを判断する処理（Ｓ５５）、この処理Ｓ５５における判断の結果、双方に内点が存在する場合（双方有り）における一方を新たな被分割ラインとすると共に他方を一時的に記憶する処理（Ｓ６１）、この処理Ｓ５５における判断の結果、一方に内点が存在する場合（一方有り）における内点の存在する分割ラインを新たな被分割ラインとする処理（Ｓ６２）は、図２に基づいて上述した第１の実施形態における二分木地図データ作成処理部２１が実行する、処理Ｓ１５、処理Ｓ２１及び処理Ｓ２２とそれぞれ同様であるので、その説明を省略する。
【０１１６】
一方、処理Ｓ５５における判断の結果、第１及び第２分割ラインの双方に内点が存在しない場合（双方なし）には、二分木地図データ作成処理部４１は、処理Ｓ５６を実行し、処理Ｓ５３において被分割ラインを最大離間度の内点によって二分することによって生成された第１及び第２分割ラインに対し、この分割ラインを新たな被分割ラインとみなして、処理Ｓ５４と同様な二分木データを作成し、記憶部１４に一時的に記憶し、処理Ｓ５７を実行する。なお、この処理Ｓ５６における分割ラインは、内点が存在せず、これ以上分割することができない分割ラインであるから、分割ラインサブフィールド２２５に登録すべき分割ラインの名称、及び、子離間度サブフィールド２２７に登録すべき子離間度Ｓｃは、存在しないので、分割ラインサブフィールド２２５には、値が存在しないことを示す符号、例えば「＊」が記憶部１４に一時的に記憶され、子離間度サブフィールド２２７には、「０」が記憶部１４に一時的に記憶される。
【０１１７】
続けて二分木地図データ作成処理部４１が実行する、処理Ｓ５７の総ての分割ラインについて二分木処理が終了したか否かを判断する処理、この処理Ｓ５７における判断の結果、二分木処理が終了していない場合（Ｎｏ）における二分木処理が未処理の分割ラインを新たな被分割ラインとする（Ｓ６３）、及び、この処理Ｓ５７における判断の結果、二分木処理が終了している場合（Ｙｅｓ）における各ラインデータの二分木データを纏めて二分木地図データとして二分木地図データ記憶部５４に記憶する処理（Ｓ５８）は、図２に基づいて上述した第１の実施形態における二分木地図データ作成処理部２１が実行する、処理Ｓ１６、処理Ｓ２３及び処理Ｓ１７とそれぞれ同様であるので、その説明を省略する。
【０１１８】
処理Ｓ５８に続けて、二分木地図データ作成処理部４１は、ツリー構造における各離間度を当該離間度Ｓを含めて子孫側の中の最大値で置き換える離間度Ｓの置換処理を実行する（Ｓ５９）。この離間度Ｓの置換処理については、後述する。
【０１１９】
次に、二分木地図データ作成処理部４１は、元地図データを構成する総てのラインについて二分木地図データを作成したか否かを判断する（Ｓ６０）。
【０１２０】
この処理Ｓ６０における判断の結果、元地図データの総てのラインについて二分木地図データが作成されていない場合（Ｎｏ）には、二分木地図データ作成処理部４１は、元地図データの他のラインについて二分木地図データを作成すべく、処理を処理Ｓ５０に戻して上述の処理Ｓ５０乃至処理Ｓ５９の処理を続行する。
【０１２１】
一方、処理Ｓ６０における判断の結果、元地図データの総てのラインについて二分木データが作成されている場合（Ｙｅｓ）には、二分木地図データ作成処理部４１は、処理を終了する。
【０１２２】
このような処理を実行することにより、第２の実施形態に係る二分木地図データ作成出力装置２は、被分割ラインを描画するためのデータと、当該被分割ラインを生成した親の被分割ライン及び当該被分割ラインから生成された第１及び第２分割ラインの親子関係と、親離間度Ｓｐと、子離間度Ｓｃとの対応関係を表すツリー構造又はテーブル形式の二分木地図データを作成し記憶することができる。そして、このような二分木地図データは、後述するように、間引き度Ｔに応じた地図を作成するために必要なデータを高速に取り出され得る。例えば、図３（Ｂ）に示すラインに対し、図１４に示す置換処理前の二分木地図データテーブル２０１’が生成され、離間度Ｓの置換処理により、図１５に示す置換処理後の二分木地図データテーブル２０１が生成される。
【０１２３】
ここで、離間度Ｓの置換処理について説明する。図１３において、二分木地図データ作成処理部４１は、二分木地図データ記憶部５４に記憶されている処理中のラインにおける二分木地図データの中からツリー構造における端末（葉）二分木データを検索し、抽出する（Ｓ７１）。この検索は、例えば、二分木地図データテーブル２０１’における親子関係フィールド２１３における分割ラインサブフィールド２２５（第１及び第２分割ライン名称サブフィールド２３５、２３６）に値が存在しないことを表す符号、上述の例では「＊」が登録されているレコードを探索することによって行うことができる。あるいは、この検索は、例えば、二分木地図データテーブル２０１’における離間度フィールド２１４における子離間度サブフィールド２２７に値が存在しないことを表す符号、上述の例では「０」が登録されているレコードを探索することによって行うことができる。
【０１２４】
次に、二分木地図データ作成処理部４１は、この抽出した葉の二分木データにおける子離間度Ｓｃが親離間度Ｓｐよりも大きいか否かを判断する（Ｓ７２）。この判断の結果、子離間度Ｓｃが親離間度Ｓｐよりも大きくない場合（Ｎｏ）、即ち、子離間度Ｓｃが親離間度Ｓｐ以下である場合には、二分木地図データ作成処理部４１は、後述の処理Ｓ７４を実行する。一方、この判断の結果、子離間度Ｓｃが親離間度Ｓｐよりも大きい場合（Ｙｅｓ）、二分木地図データ作成処理部４１は、親離間度Ｓｐを子離間度Ｓｃで置き換えると共に、この置き換えられた親離間度Ｓｐを親離間度Ｓｐ又は子離間度Ｓｃに持つ他のレコードにおける親離間度Ｓｐ及び子離間度Ｓｃも置き換えて（Ｓ７３）、処理Ｓ７４を実行する。
【０１２５】
処理Ｓ７４において、二分木地図データ作成処理部４１は、親子関係フィールド２１３の被分割ライン名称サブフィールド２２４を参照することによって、処理中の二分木データに対し親（一階層上）の二分木データを検索し、抽出する。
【０１２６】
次に、二分木地図データ作成処理部４１は、この抽出した親の二分木データがツリー構造における根であるか否かを判断する（Ｓ７５）。この判断は、例えば、親子関係フィールド２１３の被分割ライン名称サブフィールド２２４に値が存在しないことを表す符号、上述の例では「＊」が登録されているか否かを判断することによって行うことができる。あるいは、この判断は、例えば、離間度フィールド２１４の親離間度サブフィールド２２６に値が存在しないことを表す符号、上述の例では「９９９９９」が登録されているか否かを判断することによって行うことができる。
【０１２７】
この判断の結果、親の二分木データがツリー構造における根ではない場合（Ｎｏ）には、二分木地図データ作成処理部４１は、さらに、離間度Ｓの置換処理を行うべく、処理を処理Ｓ７２に戻す。一方、判断の結果、親の二分木データがツリー構造における根である場合（Ｙｅｓ）には、二分木地図データ作成処理部４１は、総ての葉の二分木データに対して処理を実行したか否かを判断する（Ｓ７６）。
【０１２８】
処理Ｓ７６における判断の結果、総ての葉の二分木データに対して処理を実行していない場合には、二分木地図データ作成処理部４１は、さらに、他の葉の二分木データに対し離間度Ｓの置換処理を行うべく、処理を処理Ｓ７１に戻す。一方。処理Ｓ７６における判断の結果、総ての葉の二分木データに対して処理を実行している場合には、二分木地図データ作成処理部４１は、この離間度Ｓの置換処理を終了する。
【０１２９】
このような処理を実行することにより、第２の実施形態に係る二分木地図データ作成出力装置２は、例えば、図１４に示す置換処理前の二分木地図データテーブル２０１’を図１５に示す置換処理後の二分木地図データテーブル２０１を生成する。図１４に示す置換処理前の二分木地図データテーブル２０１’と図１５に示す置換処理後の二分木地図データテーブル２０１とを比較すると分かるように、管理番号「１」乃至「５」の各レコード（図中、矢印で示す。）における離間度Ｓの値が置換されている。また、図１５に示す二分木地図データをツリー構造で示すと、図１６に示すツリー構造となり、節点Ｐ1Ｐ11の離間度Ｓが「１０．４」から「１１．８」に置換され、そして、節点Ｐ1Ｐ18の離間度が「１１．２」から「１１．８」に置換されている。
【０１３０】
このように動作することによって元地図データから、二分木地図データ作成出力装置２は、被分割ラインを描画するためのラインの名称と、被分割ラインを分割する際の最大の離間度Ｓｍａｘとを備え、被分割ラインを親とすると共に第１及び第２分割ラインを子とし、さらにツリー構造における離間度Ｓを当該離間度Ｓを含めて子孫側の中の最大値で置き換えたツリー構造の二分木地図データを作成し、記憶することができる。
【０１３１】
次に、二分木地図データ作成出力装置２が二分木地図データから間引き度に応じた地図を出力する動作について説明する。
【０１３２】
図１７は、第２の実施形態に係る二分木地図データ作成出力装置における二分木地図データを作成する動作を示すフローチャートである。
【０１３３】
例えば、ユーザが上述の動作によって二分木地図データ作成出力装置２に二分木地図データを作成させること等によって、第２の実施形態に係る二分木地図データが記憶部１４の二分木地図データ記憶部５４に記憶される。そして、記憶部１４の出力地図作成プログラム記憶部５２から第２の実施形態に係る出力地図作成プログラムが呼び出されて実行され、例えば、ユーザが、二分木元地図データから間引き度Ｔに応じた地図を二分木地図データ作成出力装置２に出力させるべく、地図の出力開始コマンドを入力部１２から入力すると、演算処理部１１の出力地図作成処理部４２は、記憶部１４の二分木地図データ記憶部５４に記憶されている二分木地図データに基づいて間引き度Ｔに応じた地図を出力する。
【０１３４】
即ち、図１７において、まず、演算処理部１１の出力地図作成処理部４２は、ユーザに間引き度Ｔの入力を促し、ユーザが入力部１２から間引き度Ｔを入力することによって、間引き度Ｔを受付ける（Ｓ８０）。
【０１３５】
ユーザによって間引き度Ｔが入力されると、出力地図作成処理部４２は、二分木地図データから一のラインのデータを取り出す（Ｓ８１）。例えば、図１５に示す二分木地図データテーブル２０１をラインごとに用意し、一の二分木地図データテーブル２０１を取り出す。
【０１３６】
次に、出力地図作成処理部４２は、この取り出した二分木地図データにおいて、一の被分割ラインのデータを選択し、取り出す（Ｓ８２）。例えば、図１５に示す二分木地図データテーブル２０１において、一のレコードのデータを取り出す。なお、第１の実施形態では、処理Ｓ３１で説明したように、ツリー構造の根のデータを登録するレコード、上述では、管理番号「１」のレコードを常に選択する必要があったが、第２の実施形態では、特に、必ずしも最初に根のデータのレコードを選択する必要はなく、総てのレコードのデータに対して後述の処理を実行すればよい。このため、第１の実施形態よりも二分木地図データの取り扱いが容易である。
【０１３７】
次に、出力地図作成処理部４２は、取り出したレコードのデータにおける親離間度Ｓｐ及び子離間度Ｓｃと間引き度Ｔとの大小関係を比較し、このデータにおける親離間度Ｓｐが間引き度Ｔより大きく、かつ、子離間度Ｓｃが間引き度Ｔ以下であるか否かを判断する（Ｓ８３）。
【０１３８】
ここで、被分割ライン（元のライン及び分割ライン）における親離間度Ｓｐ及び子離間度Ｓｃが第２の実施形態では上述したように子孫側の離間度Ｓが当該被分割ラインの子離間度Ｓｃ以下の値であることから、親離間度Ｓｐが間引き度Ｔ以下か、あるいは、子離間度Ｓｃが間引き度Ｔより大きい場合では、当該被分割ラインは、間引いてよい。つまり、当該被分割ラインは、描画のデータとして採用しなくてもよい。
【０１３９】
従って、処理Ｓ８３における判断の結果、このデータにおける親離間度Ｓｐが間引き度Ｔ以下であるか、あるいは、子離間度Ｓｃが間引き度Ｔより大きい場合（Ｎｏ）には、出力地図作成処理部４２は、処理Ｓ８５を実行し、一方、このデータにおける親離間度Ｓｐが間引き度Ｔより大きく、かつ、子離間度Ｓｃが間引き度Ｔ以下である場合（Ｙｅｓ）には、出力地図作成処理部４２は、当該データの始点及び終点の各座標値を出力部１３に出力してから（Ｓ８４）、処理Ｓ８５を実行する。出力部１３は、始点及び終点を結ぶ線分を描画する。
【０１４０】
そして、出力地図作成処理部４２は、未処理の被分割ラインのデータがあるか否かを判断する。判断の結果、未処理の被分割ラインのデータがある場合（Ｙｅｓ）には、出力地図作成処理部４２は、処理を処理Ｓ８２に戻す。一方、判断の結果、未処理の被分割ラインのデータがない場合（Ｎｏ）には、出力地図作成処理部４２は、上述の処理Ｓ８２乃至処理Ｓ８５の間引き処理が未処理のラインがあるか否かを判断する（Ｓ８６）。
【０１４１】
この処理Ｓ８６における判断の結果、間引き処理が未処理のラインがある場合（Ｙｅｓ）には、出力地図作成処理部４２は、他のラインについて間引き処理を実行すべく、処理を処理Ｓ８１に戻して上述の処理Ｓ８２乃至処理Ｓ８５の間引き処理を続行する。一方、処理Ｓ８６における判断の結果、間引き処理が未処理のラインがない場合（Ｙｅｓ）には、出力地図作成処理部４２は、処理を終了する。
【０１４２】
このように動作することによって二分木地図データ作成出力装置２は、二分木地図データからユーザの間引き度Ｔに応じた地図を出力することができる。そして、二分木地図データ作成出力装置２は、間引き処理を実行する場合、第１の実施形態に係る二分木地図データ作成出力装置１のように、深さ優先探索を行う必要がなく、ラインの各被分割ラインデータに対して描画するか否かを判断するだけでよいので、二分木地図データ作成出力装置２は、ユーザの間引き度Ｔに応じた地図を高速に出力することができる。このため、ユーザは、利用目的に応じて間引いた地図を二分木地図データ作成出力装置２によって容易に、高速に得ることができる。そして、間引き度Ｔと縮尺とを適宜に対応付けることにより、二分木地図データ作成出力装置２は、任意縮尺の地図を容易に、高速に作成することができる。また、間引き度Ｔとサイズとを適宜に対応付けることにより、二分木地図データ作成出力装置２は、任意サイズに応じた地図を容易に、高速に作成することができる。さらに、間引き度Ｔと解像度とを適宜に対応付けることにより、二分木地図データ作成出力装置２は、任意解像度に応じた地図を容易に、高速に作成することができる。
【０１４３】
一具体例として図１５に示す二分木地図データテーブル２０１を用いて１つのラインを出力する場合について説明すると、ユーザによって間引き度Ｔ＝５が入力され、図１７に示す処理Ｓ８２乃至処理Ｓ８５が実行されることにより、Ｐ7Ｐ11、Ｐ11Ｐ16、Ｐ16Ｐ18、Ｐ1Ｐ3及びＰ3Ｐ7が出力部１３に出力され、描画される。
【０１４４】
ここで、上述の第２の実施形態では、処理Ｓ８３で不等式の判断によって、当該被分割ラインのデータを間引くか否かを判断している。一般に、コンピュータは、不等式を満たすか否かの判断よりも、等式を満たすか否かの判断の方が演算処理速度が高速である。そのため、処理Ｓ８３の判断を等式も用いて判断することができるように二分木地図データ作成出力装置２を構成してもよい。
【０１４５】
このような構成の二分木地図データ作成出力装置２の場合では、まず、所定の間隔が空けられて増加していく複数の正の整数（丸め値）を用意し、二分木地図データ記憶部５４に記憶されている二分木地図データの親離間度Ｓｐ及び子離間度Ｓｃの値をこの複数の整数の何れかに切り上げる離間度丸め処理を行う離間度丸め処理部４１６（図１に破線で示す。）を二分木地図データ作成処理部４１にさらに設ける。
【０１４６】
複数の整数は、例えば、５の間隔を空けて増加していく５、１０、１５、２０、・・・のような数値列や１０の間隔を空けて増加していく１０、２０、３０、・・・のような数値列等の任意の数値列でよい。例えば、ここでは、複数の整数として、１０の累乗（べき乗）（指数＝０、１、２、３、・・・）の関係で増加していく整数群、１、１０、１００、１０００、・・・を用意し、二分木地図データの親離間度Ｓｐ及び子離間度Ｓｃの値をこの複数の整数の何れかに切り上げることによって丸め、この丸めた親離間度（丸め親離間度）Ｓｐ’及び子離間度（丸め子離間度）Ｓｃ’を二分木地図データにさらに追加する。例えば、親離間度Ｓｐ及び子離間度Ｓｃが１以下である場合には、１に切り上げ、親離間度Ｓｐ及び子離間度Ｓｃが１より大きく１０以下である場合には、１０に切り上げ、親離間度Ｓｐ及び子離間度Ｓｃが１０より大きく１００以下である場合には、１００に切り上げ、そして、親離間度Ｓｐ及び子離間度Ｓｃが１００より大きく１０００以下である場合には、１０００に切り上げる。そして、図１５に破線で示すように、二分木地図データテーブル２０１に、丸め親離間度Ｓｐ’を登録する丸め親離間度サブフィールド２２８及び丸め子離間度Ｓｃ’を登録する丸め子離間度サブフィールド２２９から成る丸め離間度フィールド２１５をさらに備えさせる。
【０１４７】
そして、上述の処理Ｓ８３に代えて次のように処理を行う。まず、出力地図作成処理部４２は、被分割ラインの丸め親離間度Ｓｐ’及び丸め子離間度Ｓｃ’と入力部１２で入力された間引き度Ｔに基づく丸め間引き度Ｔ’とを用いて所定の規則に応じた等式により始点及び終点の座標値を取得すべき被分割ラインを判別する。
【０１４８】
即ち、丸める所定の規則が切り上げである場合には、出力地図作成処理部４２は、丸め親離間度Ｓｐ’が、入力された間引き度Ｔを切り上げた場合の丸め間引き度Ｔ’より複数の整数の中で一段階下位の丸め値以上の丸め値と等しく、かつ、丸め子離間度Ｓｃ’が、入力された間引き度Ｔを切り上げた場合の丸め間引き度Ｔ’より複数の整数の中で一段階下位の丸め値以下の丸め値と等しいデータを抽出する。例えば、入力された間引き度が「５０」である場合には、これを切り上げた場合の丸め間引き度Ｔ’は、１００となるので、出力地図作成処理部４２は、丸め親離間度Ｓｐ’が１０、１００、１０００、・・・と等しく、かつ、丸め子離間度Ｓｃ’が１０、１と等しいデータを抽出する。
【０１４９】
次に、この抽出したデータのうち、丸め親離間度Ｓｐ’が１００、１０００、・・・と等しく、かつ、丸め子離間度Ｓｃ’が１と等しいデータは、丸める前の親離間度Ｓｐ及び子離間度Ｓｃを用いたとしても、親離間度Ｓｐが間引き度Ｔより大きく、かつ、子離間度Ｓｃが間引き度Ｔ以下である条件を必ず満たすので、出力地図作成処理部４２は、これらデータを出力部１３に出力して描画する。一方、この抽出したデータのうち、丸め親離間度Ｓｐ’が１０に等しいデータ、及び、丸め子離間度Ｓｃ’が１０に等しいデータは、必ずしも、親離間度Ｓｐが間引き度Ｔより大きく、かつ、子離間度Ｓｃが間引き度Ｔ以下である条件を満たすとは限らないので、これら丸め親離間度Ｓｐ’が１０に等しいデータ、及び、丸め子離間度Ｓｃ’が１０と等しいデータに対してのみ、丸める前の元の親離間度Ｓｐ及び子離間度Ｓｃを用いて、親離間度Ｓｐが間引き度Ｔより大きく、かつ、子離間度Ｓｃが間引き度Ｔ以下であるか否かを判断する。そして、出力地図作成処理部４２は、親離間度Ｓｐが間引き度Ｔより大きく、かつ、子離間度Ｓｃが間引き度Ｔ以下であるデータのみを出力部１３に出力して描画する。
【０１５０】
このように構成することにより、不等式によって判断するデータの個数が減るので、より高速に間引き度Ｔに応じた地図を出力することができる。
【０１５１】
なお、上述では、丸める際に切り上げたが切り下げる場合でも同様に等式を用いた処理を行うことができる。
【０１５２】
また、上述の第１及び第２の実施形態に係る二分木地図データ作成出力装置１、２において、ユーザが二分木地図データの総てのデータを用いて地図を作成する場合には、図９や図１７を用いて上述したように、二分木地図データの総てのデータに対して間引き処理を実行して地図を出力すればよいが、ユーザが二分木地図データにデータ化されている地域における一定の地域内の地図を作成する場合等には、出力範囲を決定する必要がある。
【０１５３】
例えば、図９の処理Ｓ３１及び図１７の処理Ｓ８１において、次の出力範囲に応じてラインを選択するライン選択処理を実行する。
【０１５４】
図１８は、出力範囲に応じたライン選択処理を説明するための図である。図１８において、出力範囲は、矩形ＡＢＣＤであり、矩形ＡＢＣＤの各頂点Ａ、Ｂ、Ｃ、Ｄの各座標値Ａ（ＸA、ＹA）、Ｂ（ＸB、ＹB）、Ｃ（ＸC、ＹC）、Ｄ（ＸD、ＹD）が入力部１２から入力されることによって指定される。例えば、マウスを用いて矩形ＡＢＣＤにおける対角関係にある２頂点（例えば、頂点Ａ及び頂点Ｃ）を指定することにより、あるいは、キーボードから直接各頂点のＡ、Ｂ、Ｃ、Ｄの各座標値Ａ（ＸA、ＹA）、Ｂ（ＸB、ＹB）、Ｃ（ＸC、ＹC）、Ｄ（ＸD、ＹD）を入力することによって、二分木地図データ作成出力装置１、２に入力される。
【０１５５】
そして、出力地図作成処理部２２、４２は、図１８のラインＬ11、Ｌ12、Ｌ13のように、ラインの一部又は全部が出力範囲の矩形ＡＢＣＤにかかる場合には、当該ラインを取り出し、図１８のラインＬ21、Ｌ22、Ｌ23、Ｌ24のように、ラインが全く出力範囲の矩形ＡＢＣＤにかからない場合には、当該ラインを取り出さない。
【０１５６】
即ち、図１８のように矩形の各頂点ＡＢＣＤが与えられている場合には、出力地図作成処理部２２、４２は、ラインの根の二分木データにおける始点及び終点のｘ座標ＸRが辺ＡＢの左側にあってＸR＜ＸA（＝ＸB）を満たす場合、及び、根の二分木データにおける始点及び終点のｘ座標ＸRが辺ＣＤの右側にあってＸR＞ＸC（＝ＸD）を満たす場合には、当該ラインを取り出さない。出力地図作成処理部２２、４２は、ラインの根の二分木データにおける始点及び終点のｙ座標ＹRが辺ＤＡの上側にあってＹR＞ＹD（＝ＹA）を満たす場合、及び、根の二分木データにおける始点及び終点のｙ座標ＹRが辺ＢＣの下側にあり、ＹR＜ＹB（＝ＹC）を満たす場合には、当該ラインを取り出さない。そして、出力地図作成処理部２２、４２は、ラインの根の二分木データがこのような各条件を満たさない場合に当該ラインを取り出す。
【０１５７】
このような処理を行うことによって、出力範囲として指定された範囲内のラインの二分木地図データを確実に取り出すことができる。そして、出力範囲として指定された範囲以内で厳密にラインを選択したり、ラインを分断したりする処理を行う必要がないので、簡易にライン選択処理を実行することができる。
【０１５８】
なお、図９の処理Ｓ３１及び図１７の処理Ｓ８１においてこのようなライン選択処理を実行する代わりに、図９の処理Ｓ４１及び図１７の処理Ｓ８４において出力部１３に被分割ラインの始点及び終点の各座標値を出力する際に、このようなライン選択処理を被分割ラインに対して行っても同様に出力範囲として指定された範囲内のラインの二分木地図データを確実に取り出すことができる。
【０１５９】
さらに、このようなライン選択処理においても、等式による判定によって出力範囲を決定するように構成してもよい。図１９は、ラインの始点及び終点の各座標値を丸める座標値丸め処理を説明するための図である。図２０は、丸め座標値を備える二分木地図データを用いた場合のライン選択処理を説明するための図である。
【０１６０】
例えば、図形データに設けられたｘｙ座標系において、一定間隔の格子を備える複数の層を用意し、これら複数の層における格子の間隔を所定の間隔を空けて増加していくように構成する。これら複数の層において、相対的に格子の間隔が小さい方の層を下位層と呼称し、相対的に格子の間隔が大きい方の層を上位層と呼称することとする。そして、ラインが完全に格子によって囲まれた領域である格子領域Ｑ以内に含まれる場合に、当該格子領域Ｑを構成する４つの格子点におけるｘ座標値及びｙ座標値が最も大きい値の格子点（格子の右上の格子点）の座標値に当該ラインの始点及び終点の各座標値を丸める座標値丸め処理を行う座標値丸め処理部４１７（図１に破線で示す。）を二分木地図データ作成処理部２１、４１にさらに設ける。
【０１６１】
各層の格子の間隔は、例えば、５の間隔を空けて増加していく５、１０、１５、２０、・・・のような間隔や１０の間隔を空けて増加していく１０、２０、３０、・・・のような間隔等の任意の間隔でよい。ここでは、例えば、１０の累乗（指数＝０、１、２、３、・・・）の関係で増加していく間隔群１、１０、１００、１０００、・・・を用意し、二分木地図データにおけるラインの始点及び終点の各座標値を丸め、この丸めたラインの始点及び終点の各座標値を二分木地図データにさらに追加する。例えば、図示しないが、二分木地図データテーブル２０１に、丸めた始点及び終点の各座標値（丸め座標値）を登録する丸め座標値フィールドをさらに備えさせる。この丸め座標値フィールドは、図１５に示す始点座標サブフィールド２２２及び終点座標サブフィールド２２３と同様に、ｘ座標サブフィールド及びｙ座標サブフィールドをそれぞれ備えている。
【０１６２】
図１９は、格子間隔１０の層にｘｙ座標値が丸められるラインを例示する図であり、例えば、座標値丸め処理部４１７は、図１９のラインＬ31のように、ラインの全部が完全に格子領域Ｑ21以内に含まれる場合に、当該格子領域Ｑ21を構成する４つの格子点におけるｘ座標値及びｙ座標値が共に最も大きい値の格子点ｑ21（右上の格子点）の座標値（８２０、５４０）に当該ラインの始点及び終点の各座標値を丸める座標値丸め処理を行う。このラインの始点及び終点の各座標値を丸める先の格子点を格子領域Ｑの代表点ｑと呼称することとする。ここで、図１９のラインＬ32のようにラインが格子領域Ｑ11及び格子領域Ｑ12に亘る場合や図１９のラインＬ33のようにラインが格子領域Ｑ22及び格子領域Ｑ12に亘る場合等のように、当該格子間隔１０の層において複数の格子領域Ｑに亘る場合には、より上位層の格子領域Ｑに含まれ、この上位層における格子領域Ｑの代表点ｑに座標値が丸められることになる。例えば、図１９のラインＬ32及びラインＬ33は、格子間隔１００の層における格子領域に完全に含まれることになる。
【０１６３】
なお、図１９において、格子領域Ｑ11は、座標（８１０、５３０）、（８１０、５２０）、（８２０、５２０）、（８２０、５３０）の４点から成る格子によって囲まれた領域であり、格子領域Ｑ12は、座標（８２０、５３０）、（８２０、５２０）、（８３０、５２０）、（８３０、５３０）の４点から成る格子によって囲まれた領域であり、格子領域Ｑ21は、座標（８１０、５４０）、（８１０、５３０）、（８２０、５３０）、（８２０、５４０）の４点から成る格子によって囲まれた領域であり、そして、格子領域Ｑ22は、座標（８２０、５４０）、（８２０、５３０）、（８３０、５３０）、（８３０、５４０）の４点から成る格子によって囲まれた領域である。格子領域Ｑ11の代表点ｑ11は、座標（８２０、５３０）であり、格子領域Ｑ12の代表点ｑ12は、座標（８３０、５３０）であり、格子領域Ｑ21の代表点ｑ21は、座標（８２０、５４０）であり、そして、格子領域Ｑ22の代表点ｑ22は、座標（８３０、５５０）である。
【０１６４】
そして、ライン選択処理を行う場合には、出力地図作成処理部２２、４２は、入力された出力範囲がかかる格子領域Ｑを取り出し、この取り出した格子領域Ｑの代表点ｑにおける座標値と等しい丸められた座標値を持つラインを選択する。
【０１６５】
例えば、図２０に例示するように、出力範囲が矩形ＡＢＣＤである場合には、図２０に網掛で示す格子領域Ｑ21、Ｑ22、Ｑ23、Ｑ24、Ｑ31、Ｑ32、Ｑ33、Ｑ34、Ｑ41、Ｑ42、Ｑ43、Ｑ44に出力範囲がかかり、図２０に●で示すそれらの代表点ｑ21、ｑ22、ｑ23、ｑ24、ｑ31、ｑ32、ｑ33、ｑ34、ｑ41、ｑ42、ｑ43、ｑ44の各座標値ｑ21（８２０、５４０）、ｑ22（８３０、５４０）、ｑ23（８４０、５４０）、ｑ24（８５０、５４０）、ｑ31（８２０、５５０）、ｑ32（８３０、５５０）、ｑ33（８４０、５５０）、ｑ34（８５０、５５０）、ｑ41（８２０、５６０）、ｑ42（８３０、５６０）、ｑ43（８４０、５６０）、ｑ44（８５０、５６０）と等しい丸められた座標値を持つラインを選択する。
【０１６６】
このような処理を行うことによって、出力範囲として指定された範囲内のラインの二分木地図データを等式を用いて確実に取り出すことができるので、より高速に間引き度Ｔに応じた地図を出力することができる。
【０１６７】
なお、上述では、ラインが完全に格子領域Ｑ以内に含まれる場合に、当該格子領域Ｑを構成する４つの格子点におけるｘ座標値及びｙ座標値が共に最も大きい値の格子点（格子の右上の格子点）の座標値に当該ラインの始点及び終点の各座標値を丸めたが、当該格子領域Ｑを構成する４つの格子点のうちの他の格子点における座標値に当該ラインの始点及び終点の各座標値を丸めても、同様に等式を用いた処理を行うことができる。例えば、丸める先の格子点として、ｘ座標値のみが最も大きい値である格子の右下の格子点や、ｙ座標値のみが最も大きい値である格子の左上の格子点や、ｘ座標値及びｙ座標値が共に最も小さい格子の左下の格子点を用いてもよい。
【０１６８】
そして、上述の第１及び第２の実施形態に係る二分木地図データ作成出力装置１、２は、元地図データから二分木地図データを作成すると共に、二分木地図データに基づく間引き度Ｔに応じた地図を作成し出力したが、元地図データから二分木地図データを作成する二分木地図データ作成装置と、二分木地図データに基づく間引き度Ｔに応じた地図を作成し出力する二分木地図データ出力装置とで別体で構成してもよい。このような二分木地図データ作成装置は、機能的に上述の二分木地図データ作成処理部２１、４１を備える演算処理部１１と、入力部１２と、出力部１３と、機能的に二分木地図データ作成プログラム記憶部３１、５１、元地図データ記憶部３３及び二分木地図データ記憶部３４、５４を供える記憶部１４と、バス１５とを備えて構成される。そして、このような二分木地図データ出力装置は、機能的に上述の出力地図作成処理部２２、４２を備える演算処理部１１と、入力部１２と、出力部１３と、機能的に出力地図作成プログラム記憶部３２、５２及び二分木地図データ記憶部３４、５４を供える記憶部１４と、バス１５とを備えて構成される。
【図面の簡単な説明】
【０１６９】
【図１】第１の実施形態に係る二分木地図データ作成出力装置の構成を示すブロック図である。
【図２】第１の実施形態に係る二分木地図データ作成出力装置における二分木地図データを作成する動作を示すフローチャートである。
【図３】ラインを示す図である。
【図４】二分木地図データ作成出力装置における二分木地図データを作成する動作を説明するための図（その１）である。
【図５】二分木地図データ作成出力装置における二分木地図データを作成する動作を説明するための図（その２）である。
【図６】二分木地図データ作成出力装置における二分木地図データを作成する動作を説明するための図（その３）である。
【図７】第１の実施形態に係るテーブルで表現した二分木地図データを示す図である。
【図８】第１の実施形態に係るツリー構造で表現した二分木地図データを示す図である。
【図９】第１の実施形態に係る二分木地図データ作成出力装置における二分木地図データから間引き度に応じた地図を出力する動作を示すフローチャートである。
【図１０】記憶部１４に未処理データとして記憶される分割ラインの様子を示す図である。
【図１１】間引き処理後のラインを示す図である。
【図１２】第２の実施形態に係る二分木地図データ作成出力装置における二分木地図データを作成する動作を示すフローチャートである。
【図１３】第２の実施形態に係る二分木地図データ作成出力装置における離間度の置換処理の動作を示すフローチャートである。
【図１４】第２の実施形態に係るテーブルで表現した二分木地図データ（置換処理前）を示す図である。
【図１５】第２の実施形態に係るテーブルで表現した二分木地図データ（置換処理後）を示す図である。
【図１６】第２の実施形態に係るツリー構造で表現した二分木地図データを示す図である。
【図１７】第２の実施形態に係る二分木地図データ作成出力装置における二分木地図データを作成する動作を示すフローチャートである。
【図１８】出力範囲に応じたライン選択処理を説明するための図である。
【図１９】ラインの始点及び終点の各座標値を丸める座標値丸め処理を説明するための図である。
【図２０】丸め座標値を備える二分木地図データを用いた場合のライン選択処理を説明するための図である。
【符号の説明】
【０１７０】
１、２  二分木地図データ作成出力装置            ２１１  離間度演算部
１１  演算処理部                                ２１２  被分割ライン分割処理部
１２  入力部                                    ２１３  ライン分割処理部
１３  出力部                                    ２１４、４１４  作成処理部
１４  記憶部                                    ４１５  置換処理部
１５  バス                                      ４１６  離間度丸め処理部
１６  外部記憶部                                ４１７  座標値丸め処理部
１７  通信インタフェース部
２１、４１  二分木地図データ作成処理部
２２、４２  出力地図作成処理部
３１、５１  二分木地図データ作成プログラム記憶部
３２、５２  出力地図作成プログラム記憶部
３３  元地図データ記憶部
３４、５４  二分木地図データ記憶部
【図１】
2006195172.tif 000003
【図２】
2006195172.tif 000004
【図３】
2006195172.tif 000005
【図４】
2006195172.tif 000006
【図５】
2006195172.tif 000007
【図６】
2006195172.tif 000008
【図７】
2006195172.tif 000009
【図８】
2006195172.tif 000010
【図９】
2006195172.tif 000011
【図１０】
2006195172.tif 000012
【図１１】
2006195172.tif 000013
【図１２】
2006195172.tif 000014
【図１３】
2006195172.tif 000015
【図１４】
2006195172.tif 000016
【図１５】
2006195172.tif 000017
【図１６】
2006195172.tif 000018
【図１７】
2006195172.tif 000019
【図１８】
2006195172.tif 000020
【図１９】
2006195172.tif 000021
【図２０】
2006195172.tif 000022