我们都知道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. 创建示例表和示例数据
CREATE TABLE edge_table ( id serial,
dir character varying,
source integer,
target integer,
cost double precision, reverse_cost double precision, x1 double precision,
y1 double precision, x2 double precision, y2 double precision, the_geom geometry
);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 2,0, 2,1);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES (-1, 1, 2,1, 3,1);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES (-1, 1, 3,1, 4,1);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 2,1, 2,2);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1,-1, 3,1, 3,2);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 0,2, 1,2);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 1,2, 2,2);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 2,2, 3,2);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 3,2, 4,2);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 2,2, 2,3);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1,-1, 3,2, 3,3);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1,-1, 2,3, 3,3);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1,-1, 3,3, 4,3);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 2,3, 2,4);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 4,2, 4,3);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 4,1, 4,2);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 0.5,3.5, 1.999999999999,3);
INSERT INTO edge_table (cost,reverse_cost,x1,y1,x2,y2) VALUES ( 1, 1, 3.5,2.3, 3.5,4);
这里的(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 http://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));
我们把数据用图形展示出来,图中彩色线段就是最短路线的走向.
