- 第8回 PostgreSQLアンカンファレンス＠東京（2016/9/10） - connpass
http://pgunconf.connpass.com/event/37285/ - 第8回 PostgreSQLアンカンファレンス ツイートまとめ - Togetterまとめ
http://togetter.com/li/1023030
■「巡回セールスマン問題」とは何か
「巡回セールスマン問題」というのは、以下のようなものです。
巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。簡単に言うと、「セールスマンが何か所か回る時、回る場所が増えれば増えるほど、可能性のある経路の候補が爆発的に増えていくので、最短経路を導き出すのが困難になる」ということです。回る場所の数「n」に対して、計算量はその階乗「n!」のオーダーとなります。
巡回セールスマン問題 - Wikipedia
そのため、データ量が増えると総当たりで解くことが計算量的に困難になる問題のひとつとして知られています。
■「pgRouting」とは何か
pgRoutingは、PostgreSQLおよびPostGISの拡張で、PostgreSQL/PostGISの地理空間データベースの機能に経路探索（routing）の機能を追加するライブラリです。
- pgRouting Project — Open Source Routing Library
http://pgrouting.org/
- さまざまなクライアント（ライブラリ）を通してデータや属性を加工可能。
- データの変更はすぐに経路探索に反映される。事前の計算などは不要。
- 「コスト」のパラメータは動的にSQLで計算され、テーブルのフィールドやレコードから取得可能。
経路探索のアルゴリズムはいろいろあるようで、コアの機能としては以下のようなアルゴリズムを使うことができます。
- All Pairs Shortest Path, Johnson’s Algorithm
- All Pairs Shortest Path, Floyd-Warshall Algorithm
- Shortest Path A*
- Bi-directional Dijkstra Shortest Path
- Bi-directional A* Shortest Path
- Shortest Path Dijkstra
- Driving Distance
- K-Shortest Path, Multiple Alternative Paths
- K-Dijkstra, One to Many Shortest Path
- Traveling Sales Person
- Turn Restriction Shortest Path (TRSP)
■pgRoutingのpgr_tsp関数
今回使用するpgRoutingの関数はpgr_tspです。
- pgr_tsp - Traveling Sales Person — pgRouting Manual (2.2)
http://docs.pgrouting.org/2.2/en/src/tsp/doc/pgr_tsp.html
- 焼きなまし法 - Wikipedia
https://ja.wikipedia.org/wiki/%E7%84%BC%E3%81%8D%E3%81%AA%E3%81%BE%E3%81%97%E6%B3%95
まず、ユークリッド距離を使う方法ですが、引数にSQL文を渡す必要があり、このSQL文は「id, x, y」というカラムを返却するSQL文である必要があります。
pgr_costResult[] pgr_tsp(sql text, start_id integer); pgr_costResult[] pgr_tsp(sql text, start_id integer, end_id integer);
もう一つの各点間の距離を行列で与える場合には、float型の二次元配列として与えます。
record[] pgr_tsp(matrix float[][], start integer) record[] pgr_tsp(matrix float[][], start integer, end integer)
今回は、前者のユークリッド距離を使うバージョンを使います。
まず、以下のように位置情報をx,yとして持つテーブルを作成しておきます。
pgr=> CREATE TABLE vertex_table ( pgr(> id serial, pgr(> x double precision, pgr(> y double precision pgr(> ); CREATE TABLE pgr=> pgr=> INSERT INTO vertex_table VALUES pgr-> (1,2,0), (2,2,1), (3,3,1), (4,4,1), (5,0,2), (6,1,2), (7,2,2), pgr-> (8,3,2), (9,4,2), (10,2,3), (11,3,3), (12,4,3), (13,2,4); INSERT 0 13 pgr=> SELECT * FROM vertex_table; id | x | y ----+---+--- 1 | 2 | 0 2 | 2 | 1 3 | 3 | 1 4 | 4 | 1 5 | 0 | 2 6 | 1 | 2 7 | 2 | 2 8 | 3 | 2 9 | 4 | 2 10 | 2 | 3 11 | 3 | 3 12 | 4 | 3 13 | 2 | 4 (13 rows) pgr=>
この位置情報のテーブルから「id,x,y」を取得するSQL文を与えて、pgr_tspを実行すると、以下のように最短経路を表示してくれます。
pgr=> SELECT seq, id1, id2, cost FROM pgr_tsp('SELECT id, x, y FROM vertex_table ORDER BY id', 6, 5);
seq | id1 | id2 | cost
-----+-----+-----+------------------
0 | 5 | 6 | 1
1 | 6 | 7 | 1
2 | 7 | 8 | 1.4142135623731
3 | 9 | 10 | 1
4 | 12 | 13 | 1.4142135623731
5 | 10 | 11 | 1
6 | 11 | 12 | 1
7 | 8 | 9 | 1
8 | 3 | 4 | 1
9 | 2 | 3 | 1.4142135623731
10 | 0 | 1 | 1
11 | 1 | 2 | 2.23606797749979
12 | 4 | 5 | 1
(13 rows)
pgr=>
出力で重要なのは「seq、id2、cost」です。seqは経路の順番、id2はノードのid（vertex_tableのidカラム）、costは次のノードに移動するためのコスト（距離）です。
■聖地巡礼の最短経路探索問題
世間では今、映画「君の名は。」が大ヒットしています。（唐突感）
アニメのヒット作には、聖地の存在が欠かせません。そしてそのファンは聖地巡礼をすることになっています（？）。
しかし、聖地といってもたくさんありますし、時間は限られていますので、効率よく回ることが求められてきます。巡るべき聖地が増えれば増えるほど計算量が爆発的に増大し、最短経路を求めることが困難になってきます。多分。
というわけで、「君の名は。」の聖地を巡礼するための最短経路を巡回セールスマン問題としてpgRoutingを使って探索してみます。（手段の目的化）
なお、本エントリはここからが本題です。
■PostGIS/pgRoutingとpykmlのインストール
まず、PostGIS/pgRoutingをインストールします。
PostgreSQLコミュニティのyumレポジトリを使っている場合には以下のコマンドでインストールできます。今回はPostgreSQL 9.5と一緒に使っています。
$ sudo yum install -y postgis2_95 pgrouting_95 (...) $ rpm -qa | grep pgrouting pgrouting_95-2.0.1-1.rhel6.x86_64 $ rpm -qa | grep postgis postgis2_95-2.2.2-1.rhel6.x86_64 $
また、三次元地理空間情報のデータ形式であるKMLファイルを扱うPythonのライブラリpykmlもインストールします。
$ sudo pip install pykml (...) $ pip list | grep pykml pykml (0.1.0) $
インストールが終わったら、今回使うデータベースにPostGISとpgRoutingのEXTENSIONをインストールします。
pgr=# create extension postgis;
CREATE EXTENSION
pgr=# create extension pgrouting;
CREATE EXTENSION
pgr=# \d
List of relations
Schema | Name | Type | Owner
--------+-------------------+-------+----------
public | geography_columns | view | postgres
public | geometry_columns | view | postgres
public | raster_columns | view | postgres
public | raster_overviews | view | postgres
public | spatial_ref_sys | table | postgres
(5 rows)
pgr=#
■データの準備をする
最初、自分で聖地の位置情報のデータを作成しようかとも思っていたのですが、いろいろ探していたらGoogle Mapsに「君の名は。」の聖地マップが公開されていましたので、今回はこれを使います。
- 【君の名は。】聖地巡礼マップ【8/31現在】
https://www.google.com/maps/d/u/0/viewer?mid=1Y_ioR8c1iCSR-t7qTN3Yl1qhAUw&hl=en_US
コピーの方法は、マップの右上にあるプルダウンメニューから「Copy map」を選ぶだけです。
次に、聖地マップのデータをKML形式でエクスポートします。
コピーの時と同じく、プルダウンメニューから「Download KML」を選んで、マップ全体のデータをKMLとしてダウンロードして保存します。
エクスポートしたKMLファイルは以下のようなXMLファイルになっているはずです。
$ head Copy\ of\ 【君の名は。】聖地巡礼マップ【831現在】.kml
<?xml version='1.0' encoding='UTF-8'?>
<kml xmlns='http://www.opengis.net/kml/2.2'>
<Document>
<name>Copy of 【君の名は。】聖地巡礼マップ【8/31現在】</name>
<description><![CDATA[]]></description>
<Folder>
<name>無題のレイヤ</name>
<Placemark>
<name>予告映像カット
</name>
$
次に、KMLファイルの中に含まれている位置情報をPostgreSQLに投入するためのINSERT文に変換します。
今回テーブルは以下の構造にします。
CREATE TABLE seichi ( sid serial primary key, name text not null, descr text, img text, lat float8 not null, lon float8 not null );
sidはシーケンス番号、nameはGoogle Mapsに登録されていた名前、descrは説明文です。imgは位置の画像が設定されたいた場合のURL、lat/lonは緯度経度をfloat8の精度で持ちます。
場所の情報はKMLファイル内の「Placemark」というタグに囲まれていますので、この情報を取得します。
KMLファイルの解析はpykmlモジュールを使って行います。
- Welcome to pyKML — pyKML v0.1.0 documentation
https://pythonhosted.org/pykml/
$ python kml_to_sql.py Copy\ of\ 【君の名は。】聖地巡礼マップ【831現在】.kml > ins.sql
$ head ins.sql
INSERT INTO seichi (name,descr,img,lat,lon) VALUES
('予告映像カット','新宿警察署裏交差点','',139.6944129,35.6925938)
, ('君の名は。第1弾キービジュアル','瀧が立っている横断歩道の背景建物','https://blogger.googleusercontent.com/img/proxy/AVvXsEgLXxyhLQGYjVApXbrHHFw6IQRERj_ElP9jq75ll8YSfZgTToH4FBtM0n5tX5T2hSzDf0E3SZoZAl2mghpnwqvhM-h5XfPChG5Nyj1FrE5G06KFP4ddvnajkQDWHXgRU59VRY8RvW9_rupQI1sR_aylQ8M_w6-TfJMk=',139.723177,35.6607657)
, ('三葉が座っていた総武線ホームのベンチ','','https://blogger.googleusercontent.com/img/proxy/AVvXsEjs-Qf1ula5UcaavKPNgW5l1RrPOblkLW8M_nRWTB2PeNVwCnlApcOEpyeCbWHKU2k3fCFFZGChkPbFPYK152VboPYJRZ478d09RMisUsKnzh7QxyQ7dATT7oGQvuQrS0qqZWHmau5rluf3SaBk6-RaAIwhdPpOBBbp=',139.7020626,35.6840715)
, ('瀧と奥寺先輩がお茶していたスタバ','看板TSUTAYAのTSUの部分にあたるカウンター席','https://blogger.googleusercontent.com/img/proxy/AVvXsEjJovc3KVdT6rnstEyq4eZOWc_r_WCuZNXm57S6nuA24SKQ-C-GZChGQnTsqGUJOj-F-qkYvmcEFEytmTLdLYJ6bEQ_2ErDThFYRZFv_HNZho-BQOhRkzUDUpDjiU-es86G0H86fSYcadNB6ro8q7bZbRF-25PU2vWG=',139.7003701,35.6598526)
, ('君の名は。第1弾キービジュアル','背景の六本木ヒルズ','',139.7293139,35.6603647)
, ('君の名は。第1弾キービジュアル','背景の東京ミッドタウンビル','',139.7312933,35.6662877)
, ('君の名は。第1弾キービジュアル','瀧が立っている横断道','',139.7228122,35.6613584)
, ('道路標識案内板','瀧と奥寺先輩が別れる歩道橋についている道路標識案内板','https://blogger.googleusercontent.com/img/proxy/AVvXsEig76fE_x43p9U6vuYakLKM1xZkH-TgIosQ9dl7hAAb0NxvaCys-MuIIzeby4ElYN0xCMyGSRkKZ8KTDCyaXT3acNn8D5iFdR8FKLecoXTTrepfY86ITUhHA_NFPTa8vtoN2iIAhZ_dpNd-7_FnFhs-4t_yXvqyKTd9=',139.7233808,35.6743456)
, ('歩道橋背景1','瀧と奥寺先輩が別れる歩道橋の背景','https://blogger.googleusercontent.com/img/proxy/AVvXsEg0KNNAo6DX5jUntHLJw-Cen_ySf035voZcrPRCPAQbIldwNNFERUcZ7ixRdaw9PiLcaCY2NP6aoekUvtMCeTqM6M0CEBMKl5fDDdP_NI91NlQgjrEVmGCZWB2mPxiMaZhRvet_vfklN9T6GTXuRP86mg_E26luvq2fyus=',139.7238582,35.6723802)
$
そして、作成したテーブルにINSERT文でデータを流し込みます。
$ psql -f ins.sql pgr INSERT 0 38 $
データができたことを確認したら、準備は完了です。
pgr=> \x Expanded display is on. pgr=> select * from seichi limit 3; -[ RECORD 1 ]----------------------------------------------------------------------------------------------------------------------------------------- sid | 1 name | 予告映像カット descr | 新宿警察署裏交差点 img | lat | 139.6944129 lon | 35.6925938 -[ RECORD 2 ]----------------------------------------------------------------------------------------------------------------------------------------- sid | 2 name | 君の名は。第1弾キービジュアル descr | 瀧が立っている横断歩道の背景建物 img | https://blogger.googleusercontent.com/img/proxy/AVvXsEgLXxyhLQGYjVApXbrHHFw6IQRERj_ElP9jq75ll8YSfZgTToH4FBtM0n5tX5T2hSzDf0E3SZoZAl2mghpnwqvhM-h5XfPChG5Nyj1FrE5G06KFP4ddvnajkQDWHXgRU59VRY8RvW9_rupQI1sR_aylQ8M_w6-TfJMk= lat | 139.723177 lon | 35.6607657 -[ RECORD 3 ]----------------------------------------------------------------------------------------------------------------------------------------- sid | 3 name | 三葉が座っていた総武線ホームのベンチ descr | img | https://blogger.googleusercontent.com/img/proxy/AVvXsEjs-Qf1ula5UcaavKPNgW5l1RrPOblkLW8M_nRWTB2PeNVwCnlApcOEpyeCbWHKU2k3fCFFZGChkPbFPYK152VboPYJRZ478d09RMisUsKnzh7QxyQ7dATT7oGQvuQrS0qqZWHmau5rluf3SaBk6-RaAIwhdPpOBBbp= lat | 139.7020626 lon | 35.6840715 pgr=>
■聖地巡礼の最短経路を求める
それでは、聖地巡礼の最短経路を巡回セールスマン問題として探索してみます。
前述したように、pgr_tsp関数にユークリッド距離を使って計算させます。
pgr_tspに与えるクエリは
SELECT sid id, lat x, lon y FROM seichi ORDER BY sid
となります（エイリアスでカラム名を指定）。
pgr_tsp関数に与える2つ目の引数は、スタートの点のidを示しています。（今回は1番目から出発）
さて、クエリを実行してみましょう。
pgr=> SELECT * FROM pgr_tsp('SELECT sid id, lat x, lon y FROM seichi ORDER BY sid', 1);
seq | id1 | id2 | cost
-----+-----+-----+----------------------
0 | 0 | 1 | 0.00276786017347617
1 | 16 | 17 | 0.00336861318052751
2 | 21 | 22 | 0.00418150821235386
3 | 26 | 27 | 0.00070285384682649
4 | 18 | 19 | 0.00103679575616323
5 | 17 | 18 | 0.000724005262411046
6 | 14 | 15 | 0.00040594088239891
7 | 25 | 26 | 0.00420010183685812
8 | 2 | 3 | 0.00965949435530557
9 | 19 | 20 | 0.00786443285746516
10 | 24 | 25 | 0.00638462619110202
11 | 30 | 31 | 0.000613460422526542
12 | 31 | 32 | 0.0020755731593899
13 | 36 | 37 | 0.00521034970899676
14 | 34 | 35 | 0.00453278438158901
15 | 23 | 24 | 0.00214997988828621
16 | 22 | 23 | 0.00338756302081414
17 | 20 | 21 | 0.00901689128802769
18 | 13 | 14 | 4.29288947063113e-05
19 | 33 | 34 | 0.00758742562995817
20 | 35 | 36 | 0.00655833544277088
21 | 37 | 38 | 0.00662867080567097
22 | 32 | 33 | 0.0076538252201047
23 | 29 | 30 | 0.000494603275347511
24 | 28 | 29 | 0.00116522954392147
25 | 11 | 12 | 0.00340343115400377
26 | 12 | 13 | 0.00387475855377472
27 | 7 | 8 | 0.00202254985600024
28 | 8 | 9 | 0.000924678733398354
29 | 9 | 10 | 0.00108906486492197
30 | 10 | 11 | 0.00636705982066888
31 | 15 | 16 | 0.00573513230013025
32 | 4 | 5 | 0.00657719868789178
33 | 6 | 7 | 0.0222159042861008
34 | 27 | 28 | 0.00284098090455204
35 | 3 | 4 | 0.0228251711761441
36 | 1 | 2 | 0.00981665980311944
37 | 5 | 6 | 0.0453009359877922
(38 rows)
pgr=>
最短経路が出ました。id2カラムの順番に巡礼していけば、最短経路で聖地巡礼ができることになります。
なお、これだけではちょっと分かりづらいので、元の地理のデータをJOINしてnameとdescrを表示してみましょう。（不要なid1とcostカラムも省きます）
pgr=> SELECT
pgr-> t.seq,
pgr-> t.id2,
pgr-> s.name,
pgr-> s.descr
pgr-> FROM
pgr-> pgr_tsp('SELECT sid id, lat x, lon y FROM seichi ORDER BY sid', 1) t
pgr-> LEFT OUTER JOIN seichi s ON t.id2 = s.sid;
seq | id2 | name | descr
-----+-----+--------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------
0 | 1 | 予告映像カット | 新宿警察署裏交差点
1 | 17 | オープニング | ・作中のオープニングの背景・大人になった瀧と三葉がすれ違う歩道橋
2 | 22 | ユニカビジョン |
3 | 27 | 大人になった瀧が走り出てくる改札 | 三葉を探しに飛び出す南口改札
4 | 19 | 瀧の通学路＆大人になった瀧が走っていく場所 | ・はじめて瀧と入れ替わった三葉が学校へ向かう通ったルミネのショップウィンドウ沿い・大人になった瀧が三葉を探しに走っていく
5 | 18 | 作中背景 | 連絡橋からバルト９方面
6 | 15 | 風景カット | サザンテラス口店 スタバの入口階段と手前の花壇
7 | 26 | 大人になった瀧が来ていたスタバ | ここで式の話をしている大人になったテッシーとさやちんが登場
8 | 3 | 三葉が座っていた総武線ホームのベンチ |
9 | 20 | 大人の三葉 | ラスト、 瀧を見つけた大人の三葉が駆け出してくる千駄ヶ谷駅の改札
10 | 25 | 走る三葉 | 大人になった三葉が瀧を見つけに走って通る場所
11 | 31 | 君の名は。 第2弾キービジュアル&作中ラストシーン | 瀧と三葉がすれ違う階段・物語の最後のシーン
12 | 32 | 十字路 | みつはが走ってくるシーン
13 | 37 | 風景カット | 道路標識
14 | 35 | 瀧が息を整える場所 |
15 | 24 | 瀧と奥寺先輩が四ッ谷駅方面を眺める場所 | 就活中の瀧と奥寺先輩
16 | 23 | 瀧（大人）と奥寺先輩が話しながら歩いている道 |
17 | 21 | 瀧と奥寺先輩のデート | 物語終盤、就活中の瀧と奥寺先輩のデートで渡っていた弁慶橋
18 | 14 | 瀧と奥寺先輩の待ち合わせ1 | 四ッ谷駅赤坂方面改札
19 | 34 | 瀧と奥寺先輩の待ち合わせ２ | アトレの方角
20 | 36 | 風景カット | 郵便ポスト
21 | 38 | 風景カット | 四谷三丁目の交差点
22 | 33 | 分かれ道 | 瀧が走っていくシーン
23 | 30 | 太陽の光とドコモタワー |
24 | 29 | 瀧が立っていた歩道橋 | JR総武線信濃町駅前の歩道橋
25 | 12 | 歩道橋背景4 | 瀧と奥寺先輩が別れる歩道橋の下に見切れている道路標識板
26 | 13 | 瀧の通学路 | 瀧と司と真太の下校シーン
27 | 8 | 道路標識案内板 | 瀧と奥寺先輩が別れる歩道橋についている道路標識案内板
28 | 9 | 歩道橋背景1 | 瀧と奥寺先輩が別れる歩道橋の背景
29 | 10 | 歩道橋背景2 | 瀧と奥寺先輩が別れる歩道橋
30 | 11 | 歩道橋背景3 | 瀧と奥寺先輩が別れる歩道橋
31 | 16 | 国立新美術館 |
32 | 5 | 君の名は。第1弾キービジュアル | 背景の六本木ヒルズ
33 | 7 | 君の名は。第1弾キービジュアル | 瀧が立っている横断道
34 | 28 | あおい書店前歩道橋 | 作中、瀧が数回通っていた歩道橋
35 | 4 | 瀧と奥寺先輩がお茶していたスタバ | 看板TSUTAYAのTSUの部分にあたるカウンター席
36 | 2 | 君の名は。第1弾キービジュアル | 瀧が立っている横断歩道の背景建物
37 | 6 | 君の名は。第1弾キービジュアル | 背景の東京ミッドタウンビル
(38 rows)
pgr=>
「新宿警察署裏交差点」を出発点として、聖地巡礼のルートがより具体的に見えてきました。
■求めた最短経路を可視化する
最後に、この巡礼の経路をGoogle Mapsに取り込んで可視化してみます。
経路を可視化するには、2点間に線を引かなければなりません。Google Maps上で線を引かせるには、出発点の緯度経度と、到着点の緯度経度情報が必要です。ウィンドウ関数の匂いがします。
まず、先ほどのクエリを少し修正して、場所の名前ではなく緯度経度を表示させます。
pgr=> SELECT
pgr-> t.seq,
pgr-> t.id2,
pgr-> s.lat,
pgr-> s.lon
pgr-> FROM
pgr-> pgr_tsp('SELECT sid id, lat x, lon y FROM seichi ORDER BY sid', 1) t
pgr-> LEFT OUTER JOIN seichi s ON t.id2 = s.sid;
seq | id2 | lat | lon
-----+-----+-------------+------------
0 | 1 | 139.6944129 | 35.6925938
1 | 17 | 139.6971166 | 35.6931863
2 | 22 | 139.7004586 | 35.6936089
3 | 27 | 139.7002923 | 35.6894307
4 | 19 | 139.7009951 | 35.689422
(...)
33 | 7 | 139.7228122 | 35.6613584
34 | 28 | 139.7010112 | 35.6570849
35 | 4 | 139.7003701 | 35.6598526
36 | 2 | 139.723177 | 35.6607657
37 | 6 | 139.7312933 | 35.6662877
(38 rows)
pgr=>
次に、ウィンドウ関数を使って「前の地点の緯度経度」を表示させます。
pgr=> SELECT
pgr-> t.seq,
pgr-> t.id2,
pgr-> s.lat,
pgr-> s.lon,
pgr-> lag(s.lat) OVER (ORDER BY seq) prev_lat,
pgr-> lag(s.lon) OVER (ORDER BY seq) prev_lon
pgr-> FROM
pgr-> pgr_tsp('SELECT sid id, lat x, lon y FROM seichi ORDER BY sid', 1) t
pgr-> LEFT OUTER JOIN seichi s ON t.id2 = s.sid;
seq | id2 | lat | lon | prev_lat | prev_lon
-----+-----+-------------+------------+-------------+------------
0 | 1 | 139.6944129 | 35.6925938 | |
1 | 17 | 139.6971166 | 35.6931863 | 139.6944129 | 35.6925938
2 | 22 | 139.7004586 | 35.6936089 | 139.6971166 | 35.6931863
3 | 27 | 139.7002923 | 35.6894307 | 139.7004586 | 35.6936089
4 | 19 | 139.7009951 | 35.689422 | 139.7002923 | 35.6894307
(...)
33 | 7 | 139.7228122 | 35.6613584 | 139.7293139 | 35.6603647
34 | 28 | 139.7010112 | 35.6570849 | 139.7228122 | 35.6613584
35 | 4 | 139.7003701 | 35.6598526 | 139.7010112 | 35.6570849
36 | 2 | 139.723177 | 35.6607657 | 139.7003701 | 35.6598526
37 | 6 | 139.7312933 | 35.6662877 | 139.723177 | 35.6607657
(38 rows)
pgr=>
このデータをPythonスクリプトでKMLファイルに変換します。
tsp_to_kml.pyスクリプトでは、psycopg2を使ってPostgreSQLに接続してデータを取り出し、XMLファイルをベタに書き出します。
このスクリプトの出力を保存すると、以下のようなKMLファイルを得られます。
$ python tsp_to_kml.py > route.kml
$ cat route.kml
<?xml version='1.0' encoding='UTF-8'?>
<kml xmlns='http://www.opengis.net/kml/2.2'>
<Document>
<Style id="line-DB4436-5-nodesc">
<LineStyle>
<color>ff0000ff</color>
<width>5</width>
</LineStyle>
</Style>
<name>Copy of 【君の名は。】聖地巡礼マップ【8/31現在】</name>
<description><![CDATA[]]></description>
<Folder>
<name>巡礼最短経路</name>
<Placemark>
<name>Path 1</name>
<styleUrl>#line-DB4436-5-nodesc</styleUrl>
<LineString>
<coordinates>139.6971166,35.6931863,0 139.6944129,35.6925938,0</coordinates>
</LineString>
</Placemark>
<Placemark>
<name>Path 2</name>
<styleUrl>#line-DB4436-5-nodesc</styleUrl>
<LineString>
<coordinates>139.7004586,35.6936089,0 139.6971166,35.6931863,0</coordinates>
</LineString>
</Placemark>
(...)
</Folder>
</Document>
</kml>
$
なお、KMLファイルのFolder要素がGoogle Mapsで言うところのレイヤーに当たります。今回は、巡礼の経路情報はすべて「巡礼最短経路」という一つのレイヤーにまとめてあります。
最後に、作成したroute.kmlというKMLファイルを、Google Mapsにインポートします。
まず、地図に「Add layer」でレイヤーを追加します。
次に、作成した新しいレイヤーに「Import」というメニューがありますので、そこをクリックしてKMLファイルをインポートします。
インポートが無事に完了すれば、レイヤーの名前が「巡礼最短経路」となり、経路が地図上に表示されます。
やったぜ可視化！
- Copy of 【君の名は。】聖地巡礼マップ【8/31現在】
https://drive.google.com/open?id=1-Q4Bmes5ZAkdKofBral_hGEHxu4&usp=sharing
■まとめ
今回は、複数の緯度経度の情報から、それらを結ぶ最短経路を求める演算をpgRoutingを使って実現しました。
また、KMLファイルをエクスポート・インポートすることで、その演算結果をGoogle Mapsのデータを活用して、可視化できることを示しました。
なお、今回は実現できなかったこととして、以下のようなことがあります。
- KMLのエクスポート、インポートをWebAPIでやりたい。（誰か教えてください）
- 地理的な距離ではなく、所用時間などでコスト計算やってみたい。
- 総距離や総時間に制限を設けた上で、「制限時間内にできるだけ多く回る」みたいな探索をしてみたい。
- など。
ぜひ、みなさんも地理情報とPostGISやpgRoutingを使って、何か面白いことにチャレンジしてみていただければと思います。
Enjoy, 聖地巡礼ライフ!!
では、また。
0 件のコメント:
コメントを投稿