• 道路網データの自治体による整備は進められており，オープンに開発者が利用することが可能である．
• 道路網データは，座標の配列として表現されており（KML形式），地図上での表示などの目的では十分であるが，ナビゲーションなどの応用目的として利用したいときには，そのままの形式では不十分である．
• 一方，交差点をノード，交差点を結ぶ道路をエッジとみなす，「道路網グラフデータ」は，ナビゲーションなどアプリケーションで利用するための基本データである．
• 道路網グラフデータは，ナビゲーションサービスを提供するプラットフォーム業者や地図業者は，当然のごとく所有しているが，意外にオープンなデータとして自由に入手できるものは多くない．
• このことは，自由なアプリケーションの発展や，研究者や学生によるグラフアルゴリズムの実験や学習を阻害している．
• そこで，KML形式の道路データから，道路網グラフデータを作成するプログラムを作成し公開する

• 道路網データは，座標の配列となっているが，その座標が交差点となっているとは限らない．
• よって，道路網グラフデータを作成するためには，道路網データから交差点を作成することが必要である．
• 本プログラムでは，交差点は，道路網データから作成される道路の線分2つが交わっている点であるとみなす．
• 出力されるグラフデータには，以下の情報が含まれる
  • ノード：道路網データの座標，交差点
  • エッジ：道路網データでの隣接する座標を結んだエッジ，交差点とそれが隣接するノードとのエッジ

• 交差点の導出は，緯度・経度をx軸・y軸とみなす直交座標系として計算を行っているため，かなり粗い近似値であり，正確には球面座標（楕円体）としての計算が必要である
• 道路の立体交差は考慮されていない，機械的に交点は作成される

• 極めてナイーブに交差点を求めると，道路の数をm，1道路あたりの線分数をnとすると，(mn)^2のオーダーの計算が必要になり，少しデータが増えるとかなりの時間がかかる
• しかし，実際交点が存在する場所は，それほど多くはなく，スパースに分布しているため，平面を長方形のセルに分割し，それぞれに対応する線分を対応づけるシンプルな空間インデックスを作成し，計算量の削減を行った
• 以下の計算例では，新潟市を200x200のセルで分割し計算している（セルに含まれる線分数から判断．セル数の最適値はまだ分析できていない）
• 交点を求める時間：Macbook Air Intel Core i5, メモリ 16GBで測定
  • ナイーブな方法：道路数　100→1分44秒，1500→234分
  • 簡易空間インデックスを使う方法：道路数　18856（新潟市内すべて）→17秒

• 交点以外のノード数： 206622
• 交点のノード数： 184603
• 全ノード数： 391225
• 交点以外のエッジ数： 187766
• 交点を端点に持つエッジ数： 369205
• 全エッジ数： 556971

以下の2つを実行する

python create_intersections.py
python create_graph.py

• 入力データは，inputフォルダに置いてあるが，ファイルcreate_intersections.pyで指定する必要がある
• 出力データは，outputに出力される（ノードとエッジのテキストファイル）

• 新潟市オープンデータより入手した，新潟市内の国道・県道・市道のデータ
  • http://www.city.niigata.lg.jp/shisei/seisaku/it/open-data/opendata-gis/index.html

• create_intersections.py : 交点の計算を行い，交点ファイル（中間生成物）を出力するプログラム（簡易空間インデックスによる方法）
• create_intersections_naive.py : 交点の計算を行い，交点ファイル（中間生成物）を出力するプログラム（素朴に2重ループする方法）
• create_graph.py : 交点ファイルからグラフデータを作成するプログラム
• ./input : 入力となる道路網データ（KML）を置くフォルダ
• ./output : 出力となる道路網グラフデータを置くフォルダ
• ./temp : 中間結果を置くフォルダ
• test_niigata-gis-graph.py: 単体試験に使用
• research_road_file.py: 入力ファイル（KML）の調査に使用