道路網応用のための空間索引木の提案と最短経路探査への応用

概要

論文の詳細を見る
本稿では,道路網をエッジ重み付きグラフととらえ,ネットワークボロノイ図を用いてグラフを分割し,構成した空間索引木とそれを用いた最短経路探査法を提案する.空間索引木の生成にはまず,道路網を表すグラフに対して,ネットワークボロノイ分割を行うことで,全体領域を部分領域に分割する.この分割によって得られた部分領域ごとに,経路探査のための前処理を実行して空間索引を求めておくことによって,経路探査の計算コストを大幅に減らすことができる.各部分領域は,領域内・隣接領域間の最短経路,領域の大きさの指標などの 3 種類の空間索引を持つ.さらに,部分領域をランダムに選択して隣接領域単位で統合することによって,より広い部分領域を得る.この操作を繰り返すことによって領域の包含関係を持ち,平衡木の性質を持つ空間索引木を漸次的に生成する.次に,提案木構造を用いて,領域の統合を用いた再帰的な経路探査アルゴリズムと領域の大きさの指標を用いた経路探査アルゴリズムを与え,その有効性について議論する.提案手法の有効性を確認するため,国土地理院数値地図の道路網データに実際に適用する.まず空間索引木の生成時の評価として,母点の選択確率の木構造への影響,生成時間・サイズなどについて調べる.次に経路探査時の評価として,2つの提案アルゴリズムの定量的な評価を A* 探査アルゴリズムと関連研究の階層型経路ビューモデルと比較しながら行う.提案手法により,ディジタル道路情報を利用して,空間索引木を構成でき,2 点間の経路探査やエッジに沿った距離に基づく範囲問合せなどの時間を圧縮できる.
2009-06-29

道路網応用のための空間索引木の提案と最短経路探査への応用

スポンサーリンク

概要

著者

関連論文

スポンサーリンク