試用 SpatiaLite（三）：尋找路徑
假設我們有這個網絡，數字為成本，箭頭為可往的方向：
為此，我們先創建一個表。name 是路徑的名字，node_from 是此段路徑的起點，node_to 是此段路徑的終點，oneway_from_to 即是能否由起點到終點，oneway_to_from 即是能否由終點到起點，cost 是成本，愈低愈好：
spatialite> CREATE TABLE PathTable( id INTEGER PRIMARY KEY AUTOINCREMENT, name TEXT NOT NULL, node_from TEXT NOT NULL, node_to TEXT NOT NULL, oneway_from_to INTEGER NOT NULL, oneway_to_from INTEGER NOT NULL, cost INTEGER NOT NULL );
由於這是 SpatiaLite 的功能，所以都要有路徑的地理數據，而且它會被用作繪畫最終線段，但在此例子中，我們用了 cost 的行，所以這項地理資料不會列入計算當中。若沒有 cost，線段的長度會用長計算之用：
spatialite> SELECT AddGeometryColumn('PathTable', 'geometry', 4326, 'LINESTRING', 'XY');
按上圖的資料輸入資料庫：
spatialite> INSERT INTO PathTable(name, node_from, node_to, oneway_from_to, oneway_to_from, cost, geometry) VALUES
("AC", "A", "C", 1 , 1 , 5, LineStringFromText("LINESTRING (1 4, 2 5)", 4326)),
("AH", "A", "H", 1 , 0 , 9, LineStringFromText("LINESTRING (1 4, 4 3)", 4326)),
("BE", "B", "E", 1 , 1 , 3, LineStringFromText("LINESTRING (1 2, 2 1)", 4326)),
("CD", "C", "D", 0 , 1 , 5, LineStringFromText("LINESTRING (2 5, 2 3)", 4326)),
("CF", "C", "F", 1 , 1 , 1, LineStringFromText("LINESTRING (2 5, 3 4)", 4326)),
("DE", "D", "E", 1 , 1 , 7, LineStringFromText("LINESTRING (2 3, 2 1)", 4326)),
("DF", "D", "F", 1 , 1 , 3, LineStringFromText("LINESTRING (2 3, 3 4)", 4326)),
("EG", "E", "G", 0 , 1 , 2, LineStringFromText("LINESTRING (2 1, 3 2)", 4326)),
("FG", "F", "G", 1 , 1 , 4, LineStringFromText("LINESTRING (3 4, 3 2)", 4326)),
("FH", "F", "H", 1 , 0 , 2, LineStringFromText("LINESTRING (3 4, 4 3)", 4326)),
("GH", "G", "H", 0 , 1 , 6, LineStringFromText("LINESTRING (3 2, 4 3)", 4326));
之後我們離開 spatialite 工具，利用 spatialite-tools 內的 spatialite_network 工具將資料轉換成網絡。db-path 是 sqlite 檔案路徑，table 是上面資料的表名，output-table 是輸出的表名，其餘的是此工具需要的資料在表內相應的名字：
spatialite_network --db-path database.db --table PathTable --from-column node_from --to-column node_to --geometry-column geometry -c cost --name-column name --oneway-fromto oneway_from_to --oneway-tofrom oneway_to_from --output-table PathTableData
如果成功，應該會見到以下輸出：
SQLite version: 3.7.15.2
SpatiaLite version: 4.0.0
Step I - checking for table and columns existence
spatialite-network
==================================================================
SpatiaLite db: database.db
validating table: PathTable
columns layout
==================================================================
FromNode: node_from
ToNode: node_to
Cost: cost
Name: name
Geometry: geometry
assuming arcs to be BIDIRECTIONAL
OneWay To->From: oneway_to_from
OneWay From->To: oneway_from_to
NETWORK-DATA table creation required: 'PathTableData'
Overwrite not allowed if table already exists
==================================================================
Step II - checking value types consistency
Step III - checking topologic consistency
Step IV - final evaluation
Statistics
==================================================================
# Arcs : 17
# Nodes: 8
Node max incoming arcs: 3
Node max outcoming arcs: 4
# Nodes cardinality=1: 1 [terminal nodes]
# Nodes cardinality=2: 1 [meaningless, pass-through]
==================================================================
OK: network passed validation
you can apply this configuration to build a valid VirtualNetwork
OK: validation passed
OK: NETWORK-DATA table 'PathTableData' successfully created
OK: table 'PathTableData' successfully created
完成後回到 spatialite 工具，輸入以下指令創建 VIRTUAL TABLE，我們之後就利用 PathTableNetwork 來查詢（每次更新資料之後，都要重建此 virtual table）：
spatialite> CREATE VIRTUAL TABLE "PathTableNetwork" USING VirtualNetwork("PathTableData");
之後就可以嘗試查詢，以下結果是 SpatiaLite 計算出成本最低的路徑。NodeFrom 是我們路徑的起點，NodeTo 是終點。Algorithm 是指用上的演算法，第一行 "Dijkstra||A|B|15.0|...|" 的 15.0 是總成本，LINESTRING 是整段線段資料，之後的行數是前進的方法及其成本，此例要由 A 行到 C，再行到 F、G、E，最後到達 B，ArcRowid 是內部的紀錄 id：
spatialite> SELECT Algorithm, ArcRowid, NodeFrom, NodeTo, Cost, AsText(Geometry), Name FROM "PathTableNetwork" WHERE NodeFrom = "A" and NodeTo = "B"; Dijkstra||A|B|15.0|LINESTRING(1 4, 2 5, 3 4, 3 2, 2 1, 1 2)| Dijkstra|12|A|C|5.0||AC Dijkstra|16|C|F|1.0||CF Dijkstra|20|F|G|4.0||FG Dijkstra|19|G|E|2.0||EG Dijkstra|14|E|B|3.0||BE
其他例子：
spatialite> SELECT Algorithm, ArcRowid, NodeFrom, NodeTo, Cost, AsText(Geometry), Name FROM "PathTableNetwork" WHERE NodeFrom = "B" and NodeTo = "A"; Dijkstra||B|A|19.0|LINESTRING(1 2, 2 1, 2 3, 3 4, 2 5, 1 4)| Dijkstra|14|B|E|3.0||BE Dijkstra|17|E|D|7.0||DE Dijkstra|18|D|F|3.0||DF Dijkstra|16|F|C|1.0||CF Dijkstra|12|C|A|5.0||AC spatialite> SELECT Algorithm, ArcRowid, NodeFrom, NodeTo, Cost, AsText(Geometry), Name FROM "PathTableNetwork" WHERE NodeFrom = "A" and NodeTo = "H"; Dijkstra||A|H|8.0|LINESTRING(1 4, 2 5, 3 4, 4 3)| Dijkstra|12|A|C|5.0||AC Dijkstra|16|C|F|1.0||CF Dijkstra|21|F|H|2.0||FH spatialite> SELECT Algorithm, ArcRowid, NodeFrom, NodeTo, Cost, AsText(Geometry), Name FROM "PathTableNetwork" WHERE NodeFrom = "B" and NodeTo = "F"; Dijkstra||B|F|13.0|LINESTRING(1 2, 2 1, 2 3, 3 4)| Dijkstra|14|B|E|3.0||BE Dijkstra|17|E|D|7.0||DE Dijkstra|18|D|F|3.0||DF spatialite> SELECT Algorithm, ArcRowid, NodeFrom, NodeTo, Cost, AsText(Geometry), Name FROM "PathTableNetwork" WHERE NodeFrom = "E" and NodeTo = "G"; Dijkstra||E|G|14.0|LINESTRING(2 1, 2 3, 3 4, 3 2)| Dijkstra|17|E|D|7.0||DE Dijkstra|18|D|F|3.0||DF Dijkstra|20|F|G|4.0||FG spatialite> SELECT Algorithm, ArcRowid, NodeFrom, NodeTo, Cost, AsText(Geometry), Name FROM "PathTableNetwork" WHERE NodeFrom = "G" and NodeTo = "E"; Dijkstra||G|E|2.0|LINESTRING(3 2, 2 1)| Dijkstra|19|G|E|2.0||EG
由於 Dijkstra 演算法是比 A* 慢的，我們可以轉用 A* 來加快查詢：
spatialite> UPDATE "PathTableNetwork" SET Algorithm = 'A*';
查詢，大多數情況都跟 Dijkstra 結果相同：
spatialite> SELECT Algorithm, ArcRowid, NodeFrom, NodeTo, Cost, AsText(Geometry), Name FROM "PathTableNetwork" WHERE NodeFrom = "A" and NodeTo = "B"; A*||A|B|15.0|LINESTRING(1 4, 2 5, 3 4, 3 2, 2 1, 1 2)| A*|12|A|C|5.0||AC A*|16|C|F|1.0||CF A*|20|F|G|4.0||FG A*|19|G|E|2.0||EG A*|14|E|B|3.0||BE
轉回 Dijkstra 演算法：
spatialite> UPDATE "PathTableNetwork" SET Algorithm = 'Dijkstra';
參考資料：
SpatiaLite Tutorial - Fine dining experience: Chez Dijkstra
StackOverflow - How does Dijkstra's Algorithm and A-Star compare?
gis.stackexchange.com - Are there newer routing algorithms (than Dijkstra, A*) in GIS databases?
Wikipedia - Dijkstra's algorithm
Wikipedia - A* search algorithm
Local map rendering and route finding with libchamplain, Spatialite and Open Street Map
內部連結：
【目錄】地理／地理資訊系統／空間資料庫／大地測量內部連結
本文連結