PostgreSQL 路徑規劃插件 pgruoting 介紹

    我們都知道PostgreSQL利用PostGIS插件,善於處理LBS相關的業務.

    PostGIS是對象關係型數據庫係統PostgreSQL的一個擴展，PostGIS提供如下空間信息服務功能:空間對象、空間索引、空間操作函數和空間操作符。同時，PostGIS遵循OpenGIS的規範。

 PostGIS的優勢

一: 支持所有的空間數據類型，這些類型包括:點（POINT）、線（LINESTRING）、多邊形（POLYGON）、多點（MULTIPOINT）、多線（MULTILINESTRING）、多多邊形（MULTIPOLYGON）和集合對象集（GEOMETRYCOLLECTION）等。PostGIS支持所有的對象表達方法，比如WKT和WKB 

二: 支持基於這些數據類型的計算

1 數據存取和構造方法

2 供簡單的空間分析函數

3 提供了一係列的二元謂詞（如Contains、Within、Overlaps和Touches）用於檢測空間對象之間的空間關係，同時返回布爾值來表征對象之間符合這個關係

4 提供了空間操作符（如Union和Difference）用於空間數據操作

本文帶來的PostgreSQL新的插件pgruoting是基於PostGIS的.

pgruoting 提供一套函數,用於滿足用戶在LSB服務中典型的路徑規劃方麵的需求.

RDS PG 12月版本也會支持這個插件.

下麵詳細介紹改插件的典型用法.

A. 該插件依賴PostGIS,創建它需要先創建 pgruoting.

create extension postgis;

create extension pgrouting; 

B. 創建示例表和示例數據

這裏的(x1,y1),(x2,y2)分別對應兩個點,也就是一條線段

我們把連個點連接起來,作為一條線,假想為道路,我們最後得到的最短路徑,就是由連續的線段組成.

UPDATE edge_table SET the_geom = st_makeline(st_point(x1,y1),st_point(x2,y2)),

dir = CASE WHEN (cost>0 and reverse_cost>0) THEN ’B’ -- both ways

WHEN (cost>0 and reverse_cost<0) THEN ’FT’ -- direction of the L 

WHEN (cost<0 and reverse_cost>0) THEN ’TF’ -- reverse direction 

ELSE ’’ END;

使用下列函數,格式化拓撲數據(source和target列),為我們的之後的路徑規劃做鋪墊.

SELECT pgr_createTopology(’edge_table’,0.001); 

執行之後,會產生一個表 edge_table_vertices_pgr.他也在edge_table表的source和target列中表現.他們是一組點的組合.

接下來,我們用pgr_dijkstra函數計算出, edge_table_vertices_pgr中點1 到 11間的最短距離.

改函數的實現核心是Dijkstra 算法，它又叫迪科斯徹算法（Dijkstra），算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離.

Dijkstra 算法可以用來找到兩個城市之間的最短路徑。

實現相關信息請參考

1 https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

2 https://baike.baidu.com/view/1712262.htm?fromtitle=Dijkstra%E7%AE%97%E6%B3%95&fromid=215612&type=syn

我們來計算下1到9間的最短距離

SELECT seq, id1 AS node, id2 AS edge, cost FROM

pgr_dijkstra(' 

SELECT  id AS id,

source::integer, 

target::integer, 

cost::double precision AS cost

FROM edge_table', 

1, 11, false, false);

得到結果

 seq | node | edge | cost 

-----+------+------+------

   0 |    1 |    1 |    1

   1 |    2 |    4 |    1

   2 |    5 |    8 |    1

   3 |    6 |    9 |    1

   4 |   11 |   -1 |    0

(5 rows)

意思是,按照seq的順序,先後經過節點1,2,4,5 最後到達11.

我們把按照順序把1,2,5,6,11 的列the_geom連接起來,也就是是我們最短路徑.

可以參考SQL

create table line(id serial,the_geom geometry);

insert into line (the_geom) select ST_MakeLine(ARRAY (select the_geom

from (SELECT seq, id1 AS node FROM pgr_dijkstra(

'SELECT  id AS id,

 source::integer, 

target::integer, 

cost::double precision AS cost 

FROM edge_table', 1, 11, false, false))path, edge_table_vertices_pgr p

where path.node = p.id order by seq));

我們把數據用圖形展示出來,圖中彩色線段就是最短路線的走向.